sync with rtgui-0.6

4 files changed, 133 insertions, 0 deletions

diff --git a/components/rtgui/utils/perfect_hash/example-Python/Graph.py b/components/rtgui/utils/perfect_hash/example-Python/Graph.py
new file mode 100644
index 0000000000..f2927719b4
--- /dev/null
+++ b/components/rtgui/utils/perfect_hash/example-Python/Graph.py
@@ -0,0 +1,40 @@
+#!/usr/bin/env python
+"""
+This example shows how to use the class Graph.
+
+The class implements a graph with 'N' vertices.  First, you connect the
+graph with edges, which have a desired value associated.  Then the vertex
+values are assigned, which will fail if the graph is cyclic.  The vertex
+values are assigned such that the two values corresponding to an edge add
+up to the desired edge value (mod N).
+"""
+import sys
+
+sys.path.append('..')
+from perfect_hash import Graph
+
+G = Graph(3)
+assert G.assign_vertex_values() == True
+    
+# Now we make an edge between vertex 0 and 1 with desired edge value 2:
+G.connect(0, 1, 2)
+
+# Make another edge 1:2 with desired edge value 1:
+G.connect(1, 2, 1)
+    
+# The graph is still acyclic, and assigning values works:
+assert G.assign_vertex_values() == True
+assert G.vertex_values == [0, 2, 2]
+    
+# What do these values mean?
+# When you add the values for edge 0:1 you get 0 + 2 = 2, as desired.
+# For edge 1:2 you add 2 + 2 = 4 = 1 (mod 3), as desired.
+
+# Adding edge 0:2 produces a loop, so the graph is no longer acyclic.
+# Assigning values fails.
+G.connect(0, 2, 0)
+
+assert G.assign_vertex_values() == False
+
+
+print 'OK'
diff --git a/components/rtgui/utils/perfect_hash/example-Python/Makefile b/components/rtgui/utils/perfect_hash/example-Python/Makefile
new file mode 100644
index 0000000000..4f6dd13850
--- /dev/null
+++ b/components/rtgui/utils/perfect_hash/example-Python/Makefile
@@ -0,0 +1,15 @@
+
+
+all:
+	true
+
+
+clean:
+	true
+
+
+test:
+	./generate_hash.py
+	./PerfHash.py
+	./Graph.py
+
diff --git a/components/rtgui/utils/perfect_hash/example-Python/PerfHash.py b/components/rtgui/utils/perfect_hash/example-Python/PerfHash.py
new file mode 100644
index 0000000000..49131c2b63
--- /dev/null
+++ b/components/rtgui/utils/perfect_hash/example-Python/PerfHash.py
@@ -0,0 +1,40 @@
+#!/usr/bin/env python
+"""
+This example shows how to use the class PerfHash.
+
+This class is designed for creating perfect hash tables at run time,
+which should be avoided, in particulat inserting new keys is
+prohibitively expensive since a new perfect hash table needs to be
+constructed.  However, this class can be usefull for testing.
+
+For practical programming purposes in Python the class PerfHash
+should never be used because Python's built-in dictionary is very
+efficient and always faster than PerfHash.
+"""
+
+import sys
+
+sys.path.append('..')
+from perfect_hash import PerfHash
+
+
+month = dict(zip('jan feb mar apr may jun jul aug sep oct mov dec'.split(),
+                 range(1, 13)))
+
+d = PerfHash(month)
+
+
+for m in month:
+    assert month[m] == d[m]
+
+d[True] = False
+
+assert d[True] == False
+
+for i in xrange(10):  # very expensive
+    d[i] = 2*i*i + 3*i -7
+
+assert d[4] == 37
+
+
+print 'OK'
diff --git a/components/rtgui/utils/perfect_hash/example-Python/generate_hash.py b/components/rtgui/utils/perfect_hash/example-Python/generate_hash.py
new file mode 100644
index 0000000000..dfe9f92186
--- /dev/null
+++ b/components/rtgui/utils/perfect_hash/example-Python/generate_hash.py
@@ -0,0 +1,38 @@
+#!/usr/bin/env python
+"""
+This example shows how to use the function generate_hash.
+
+generate_hash(kdic, Hash)
+
+returns hash functions f1 and f2, and G for a perfect minimal hash.
+Input is dictionary 'kdic' with the keys and desired hash values.
+'Hash' is a random hash function generator, that means Hash(N) returns a
+returns a random hash function which returns hash values from 0..N-1.
+"""
+
+import sys
+import random, string
+
+sys.path.append('..')
+from perfect_hash import generate_hash
+
+
+
+month = dict(zip('jan feb mar apr may jun jul aug sep oct mov dec'.split(),
+                 range(1, 13)))
+
+def mkRandHash(N):
+    """
+    Return a random hash function which returns hash values from 0..N-1.
+    """
+    junk = "".join(random.choice(string.letters + string.digits)
+                   for i in xrange(10))
+    return lambda key: hash(junk + str(key)) % N
+
+
+f1, f2, G = generate_hash(month, mkRandHash)
+
+for k, h in month.items():
+    assert h == ( G[f1(k)] + G[f2(k)] ) % len(G)
+
+print 'OK'