summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/LookupTable.lua
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2014-02-27 00:01:50 +0000
committerKarl Berry <karl@freefriends.org>2014-02-27 00:01:50 +0000
commit90ae413a94da014dbf7a6a8ab584f7c668483a5a (patch)
tree4e0528a2b2fb2004988e7fc804ea2f1354f1f5d5 /Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/LookupTable.lua
parent800cc56380d1edfe567a6a66bef13e8950eb2b0c (diff)
pgf 3.0.0
git-svn-id: svn://tug.org/texlive/trunk@33057 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/LookupTable.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/LookupTable.lua111
1 files changed, 111 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/LookupTable.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/lib/LookupTable.lua
new file mode 100644
index 00000000000..a3c04ca54df
--- /dev/null
+++ b/Master/texmf-dist/tex/generic/pgf/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: /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 \ No newline at end of file