summaryrefslogtreecommitdiff
path: root/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/LookupTable.lua
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/LookupTable.lua')
-rw-r--r--graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/LookupTable.lua111
1 files changed, 111 insertions, 0 deletions
diff --git a/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/LookupTable.lua b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/LookupTable.lua
new file mode 100644
index 0000000000..fc2043d523
--- /dev/null
+++ b/graphics/pgf/base/tex/generic/graphdrawing/lua/pgf/gd/lib/LookupTable.lua
@@ -0,0 +1,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 \ No newline at end of file