1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
-- Copyright 2012 by Till Tantau
--
-- This file may be distributed an/or modified
--
-- 1. under the LaTeX Project Public License and/or
-- 2. under the GNU Public License
--
-- See the file doc/generic/pgf/licenses/LICENSE for more information
-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/lib/LookupTable.lua,v 1.2 2013/04/04 20:43:45 tantau Exp $
---
-- This table provides two utility functions for managing ``lookup
-- tables.'' Such a table is a mixture of an array and a hashtable:
-- It stores (only) tables. Each table is stored once in a normal
-- array position. Additionally, the lookup table is also indexed at
-- the position of the table (used as a key) and this position is set
-- to |true|. This means that you can test whether a table |t| is in the
-- lookup table |l| simply by testing whether |l[t]| is true.
--
local LookupTable = {}
-- Namespace
require("pgf.gd.lib").LookupTable = LookupTable
---
-- Add all elements in the |array| to a lookup table. If an element of
-- the array is already present in the table, it will not be added
-- again.
--
-- This operation takes time $O(|\verb!array!|)$.
--
-- @param l Lookup table
-- @param array An array of to-be-added tables.
function LookupTable.add(l, array)
for i=1,#array do
local t = array[i]
if not l[t] then
l[t] = true
l[#l + 1] = t
end
end
end
---
-- Add one element to a lookup table. If it is already present in the
-- table, it will not be added again.
--
-- This operation takes time $O(1)$.
--
-- @param l Lookup table
-- @param e The to-be-added element.
function LookupTable.addOne(l, e)
if not l[e] then
l[e] = true
l[#l + 1] = e
end
end
---
-- Remove tables from a lookup table.
--
-- Note that this operation is pretty expensive insofar as it will
-- always cost a traversal of the whole lookup table. However, this is
-- also the maximum cost, even when a lot of entries need to be
-- deleted. Thus, it is much better to ``pool'' multiple remove
-- operations in a single one.
--
-- This operation takes time $O(\max\{|\verb!array!|, |\verb!l!|\})$.
--
-- @param l Lookup table
-- @param t An array of to-be-removed tables.
function LookupTable.remove(l, array)
-- Step 1: Mark all to-be-deleted entries
for i=1,#array do
local t = array[i]
if l[t] then
l[t] = false
end
end
-- Step 2: Collect garbage...
local target = 1
for i=1,#l do
local t = l[i]
if l[t] == false then
l[t] = nil
else
l[target] = t
target = target + 1
end
end
for i=#l,target,-1 do
l[i] = nil
end
end
-- Done
return LookupTable
|