summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/LookupTable.lua
blob: fc2043d523720d296311259e682d421dab4cadaf (plain)
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$



---
-- 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