diff options
| author | Grissiom <[email protected]> | 2013-02-01 10:27:10 +0800 |
|---|---|---|
| committer | Grissiom <[email protected]> | 2013-02-01 10:27:10 +0800 |
| commit | f06c70feed0941b5bceedcecf89e9aa22034aca8 (patch) | |
| tree | 89fd3a989b4d88fc72b39eaad6567de3a3d23874 /components/rtgui/utils/perfect_hash | |
| parent | 4f02e67bef7eacee5102d7730356663d9c889e15 (diff) | |
sync with rtgui-0.6
Diffstat (limited to 'components/rtgui/utils/perfect_hash')
40 files changed, 2899 insertions, 0 deletions
diff --git a/components/rtgui/utils/perfect_hash/README b/components/rtgui/utils/perfect_hash/README new file mode 100644 index 0000000000..fa798c1d3c --- /dev/null +++ b/components/rtgui/utils/perfect_hash/README @@ -0,0 +1,49 @@ + +perfect_hash.py + +Ilan Schnell <[email protected]>, 2008 + + +Generate a minimal perfect hash function for the keys in a file, +desired hash values may be specified within this file as well. +A given code template is filled with parameters, such that the +output is code which implements the hash function. +Templates can easily be constructed for any programming language. + +The code is based on an a program A.M. Kuchling wrote: +http://www.amk.ca/python/code/perfect-hash + +The algorithm the program uses is described in the paper +'Optimal algorithms for minimal perfect hashing', +Z. J. Czech, G. Havas and B.S. Majewski. +http://citeseer.ist.psu.edu/122364.html + + +Content: + +perfect_hash.py The actual program, try $ ./perfect_hash.py animals.txt + +doc HTML and plain text documentation + +example1-C An example which shows how to generate a C program + which implements a perfect hash table. + +example2-C Another example in C. + +example-C++ In this C++ example, a class is used to define the + interface to a static lookup table. + +example-PyModule A lookup table in implemented as a C extension module + for Python. + +example-Python Some small Python programs which show how to access + some functions and classes in perfect_hash.py directly, + i.e. using perfect_hash has a Python module, rather + than a standalone program. + +graph A small program `py2dot' which converts the default python + output code from perfect_hash.py into a .dot-file which + can be used by Graphviz (see http://www.graphviz.org/) to + create a picture of the graph. + +run Runs some tests. diff --git a/components/rtgui/utils/perfect_hash/__init__.py b/components/rtgui/utils/perfect_hash/__init__.py new file mode 100644 index 0000000000..e69de29bb2 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/__init__.py diff --git a/components/rtgui/utils/perfect_hash/animals.txt b/components/rtgui/utils/perfect_hash/animals.txt new file mode 100644 index 0000000000..ac29563736 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/animals.txt @@ -0,0 +1,7 @@ +# 'animals.txt' +Elephant +Horse +Camel +Python +Dog +Cat diff --git a/components/rtgui/utils/perfect_hash/doc/Makefile b/components/rtgui/utils/perfect_hash/doc/Makefile new file mode 100644 index 0000000000..6a456a5b97 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/doc/Makefile @@ -0,0 +1,22 @@ + + +all: doc.html doc.txt + + +doc.html: doc.in parameters.txt mktable.py + ./mktable.py >table.html + markdown doc.in | \ + sed -e "s,<h6>table</h6>,m4_include(\`table.html')," | \ + m4 -P >doc.html + rm table.html + + +doc.txt: doc.in parameters.txt + sed <doc.in -e "s,###### table,m4_include(\`parameters.txt')," \ + -e "s,\`\([^\`]*\)\`,'\1',g" | m4 -P >doc.txt + + +clean: + rm doc.html doc.txt + + diff --git a/components/rtgui/utils/perfect_hash/doc/czech92optimal.pdf b/components/rtgui/utils/perfect_hash/doc/czech92optimal.pdf Binary files differnew file mode 100644 index 0000000000..08825a1315 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/doc/czech92optimal.pdf diff --git a/components/rtgui/utils/perfect_hash/doc/doc.html b/components/rtgui/utils/perfect_hash/doc/doc.html new file mode 100644 index 0000000000..3abb399f32 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/doc/doc.html @@ -0,0 +1,136 @@ + + +<h2>Generic Perfect Hash Generator</h2> +<p><em>Ilan Schnell, 2008</em> +</p> +<p>perfect_hash.py provides a perfect hash generator which is not language + specific. That is, the generator can output a perfect hash function for + a given set of keys in any programming language, this is achieved by + filling a given code template. +</p> + +<h3>Acknowledgments:</h3> +<p>This code is derived from A. M. Kuchling's + <a href="http://www.amk.ca/python/code/perfect-hash">Perfect Minimal Hash Generator</a>. +</p> + +<h3>Introduction:</h3> +<p>A perfect hash function of a certain set S of keys is a hash function + which maps all keys in S to different numbers. + That means that for the set S, + the hash function is collision-free, or perfect. + Further, a perfect hash function is called minimal when it maps n keys + to n <em>consecutive</em> integers, usually in the range from 0 to n-1. +</p> +<p>After coming across A. M. Kuchling's Perfect Minimal Hash Generator, + I decided to write a general tool for generating perfect hashes. + It is general in the sense that it can produce perfect hash functions + for almost any programming language. + A given code template is filled with parameters, + such that the output is code which implements the hash function. +</p> +<p>The algorithm the program uses is described in the paper + <a href="http://citeseer.ist.psu.edu/122364.html">"Optimal algorithms for minimal perfect hashing"</a>, + Z. J. Czech, G. Havas and B.S. Majewski. +</p> +<p>I tried to illustrate the algorithm and explain how it works on + <a href="http://ilan.schnell-web.net/prog/perfect-hash/algo.html">this page</a>. +</p> + +<h3>Usage:</h3> +<p>Given a set of keys which are ordinary character string, + the program returns a minimal perfect hash function. + This hash function is returned in the form of Python code by default. + Suppose we have a file with keys: +</p> +<pre><code># 'animals.txt' +Elephant +Horse +Camel +Python +Dog +Cat +</code></pre><p>The exact way this file is parsed can be specified using command line + options, for example it is possible to only read one column from a file + which contains different items in each row. + The program is invoked like this: +</p> +<pre><code># ======================================================================= +# ================= Python code for perfect hash function =============== +# ======================================================================= + +G = [0, 0, 4, 1, 0, 3, 8, 1, 6] + +S1 = [5, 0, 0, 6, 1, 0, 4, 7] +S2 = [7, 3, 6, 7, 8, 5, 7, 6] + +def hash_f(key, T): + return sum(T[i % 8] * ord(c) for i, c in enumerate(str(key))) % 9 + +def perfect_hash(key): + return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % 9 + +# ============================ Sanity check ============================= + +K = ["Elephant", "Horse", "Camel", "Python", "Dog", "Cat"] +H = [0, 1, 2, 3, 4, 5] + +assert len(K) == len(H) == 6 + +for k, h in zip(K, H): + assert perfect_hash(k) == h +</code></pre><p>The way the program works is by filling a code template with the calculated + parameters. The program can take such a template in form of a file and + fill in the calculated parameters, this allows the generation of perfect + hash function in any programming language. The hash function is kept quite + simple and does not require machine or language specific byte level operations + which might be hard to implement in the target language. + The following parameters are available in the template, and will expand to: +</p> +<table> + <tr><th>string</th><th>expands to</th></tr> + <tr><td><code>$NS</code></td><td>the length of S1 and S2</td></tr> + <tr><td><code>$S1</code></td><td>array of integers S1</td></tr> + <tr><td><code>$S2</code></td><td>array of integers S2</td></tr> + <tr><td><code>$NG</code></td><td>length of array G</td></tr> + <tr><td><code>$G</code></td><td>array of integers G</td></tr> + <tr><td><code>$NK</code></td><td>the number of keys, i.e. length of array K and H</td></tr> + <tr><td><code>$K</code></td><td>array with the quoted keys</td></tr> + <tr><td><code>$H</code></td><td>array of integer hash values</td></tr> + <tr><td><code>$$</code></td><td><code>$</code> (a literal dollar sign)</td></tr> +</table> +<p>A literal <code>$</code> is escaped as <code>$$</code>. Since the syntax for arrays is not the + same in all programming languages, some specifics can be adjusted using + command line options. + The section of the built-in template which creates the actual hash function + is: +</p> +<pre><code>G = [$G] + +S1 = [$S1] +S2 = [$S2] + +def hash_f(key, T): + return sum(T[i % $NS] * ord(c) for i, c in enumerate(str(key))) % $NG + +def perfect_hash(key): + return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % $NG +</code></pre><p>Using code templates, makes this program very flexible. The package comes + with several complete examples for C and C++. There are many choices one + faces when implementing a static hash table: do the parameter lists go into + a separate header file, should the API for the table only contain the hash + values, but not the objects being mapped, and so on. + All these various choices are possible because of the template is simply + filled with the parameters, no matter what else is inside the template. +</p> +<p>Another possible use the program is as a python module. The functions and + classes in <code>perfect_hash.py</code> are documented and have clean interfaces. + The folder <code>example-Python</code> has examples which shows how the module + can be used directly in this way. +</p> + +<h3>Requirement:</h3> +<p>Python 2.5 +</p> + + diff --git a/components/rtgui/utils/perfect_hash/doc/doc.in b/components/rtgui/utils/perfect_hash/doc/doc.in new file mode 100644 index 0000000000..1bcce9a961 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/doc/doc.in @@ -0,0 +1,130 @@ + +Generic Perfect Hash Generator +------------------------------ + +*Ilan Schnell, 2008* + +perfect_hash.py provides a perfect hash generator which is not language +specific. That is, the generator can output a perfect hash function for +a given set of keys in any programming language, this is achieved by +filling a given code template. + +### Acknowledgments: + +This code is derived from A. M. Kuchling's +[Perfect Minimal Hash Generator](http://www.amk.ca/python/code/perfect-hash). + +### Introduction: + +A perfect hash function of a certain set S of keys is a hash function +which maps all keys in S to different numbers. +That means that for the set S, +the hash function is collision-free, or perfect. +Further, a perfect hash function is called minimal when it maps n keys +to n *consecutive* integers, usually in the range from 0 to n-1. + +After coming across A. M. Kuchling's Perfect Minimal Hash Generator, +I decided to write a general tool for generating perfect hashes. +It is general in the sense that it can produce perfect hash functions +for almost any programming language. +A given code template is filled with parameters, +such that the output is code which implements the hash function. + +The algorithm the program uses is described in the paper +["Optimal algorithms for minimal perfect hashing"] +(http://citeseer.ist.psu.edu/122364.html), +Z. J. Czech, G. Havas and B.S. Majewski. + +I tried to illustrate the algorithm and explain how it works on +[this page](http://ilan.schnell-web.net/prog/perfect-hash/algo.html). + +### Usage: + +Given a set of keys which are ordinary character string, +the program returns a minimal perfect hash function. +This hash function is returned in the form of Python code by default. +Suppose we have a file with keys: + + # 'animals.txt' + Elephant + Horse + Camel + Python + Dog + Cat + + +The exact way this file is parsed can be specified using command line +options, for example it is possible to only read one column from a file +which contains different items in each row. +The program is invoked like this: + + # ======================================================================= + # ================= Python code for perfect hash function =============== + # ======================================================================= + + G = [0, 0, 4, 1, 0, 3, 8, 1, 6] + + S1 = [5, 0, 0, 6, 1, 0, 4, 7] + S2 = [7, 3, 6, 7, 8, 5, 7, 6] + + def hash_f(key, T): + return sum(T[i % 8] * ord(c) for i, c in enumerate(str(key))) % 9 + + def perfect_hash(key): + return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % 9 + + # ============================ Sanity check ============================= + + K = ["Elephant", "Horse", "Camel", "Python", "Dog", "Cat"] + H = [0, 1, 2, 3, 4, 5] + + assert len(K) == len(H) == 6 + + for k, h in zip(K, H): + assert perfect_hash(k) == h + + +The way the program works is by filling a code template with the calculated +parameters. The program can take such a template in form of a file and +fill in the calculated parameters, this allows the generation of perfect +hash function in any programming language. The hash function is kept quite +simple and does not require machine or language specific byte level operations +which might be hard to implement in the target language. +The following parameters are available in the template, and will expand to: + +###### table + +A literal `$` is escaped as `$$`. Since the syntax for arrays is not the +same in all programming languages, some specifics can be adjusted using +command line options. +The section of the built-in template which creates the actual hash function +is: + + G = [$G] + + S1 = [$S1] + S2 = [$S2] + + def hash_f(key, T): + return sum(T[i % $NS] * ord(c) for i, c in enumerate(str(key))) % $NG + + def perfect_hash(key): + return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % $NG + +Using code templates, makes this program very flexible. The package comes +with several complete examples for C and C++. There are many choices one +faces when implementing a static hash table: do the parameter lists go into +a separate header file, should the API for the table only contain the hash +values, but not the objects being mapped, and so on. +All these various choices are possible because of the template is simply +filled with the parameters, no matter what else is inside the template. + +Another possible use the program is as a python module. The functions and +classes in `perfect_hash.py` are documented and have clean interfaces. +The folder `example-Python` has examples which shows how the module +can be used directly in this way. + +### Requirement: + +Python 2.5 diff --git a/components/rtgui/utils/perfect_hash/doc/doc.txt b/components/rtgui/utils/perfect_hash/doc/doc.txt new file mode 100644 index 0000000000..f28dda0ed2 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/doc/doc.txt @@ -0,0 +1,141 @@ + +Generic Perfect Hash Generator +------------------------------ + +*Ilan Schnell, 2008* + +perfect_hash.py provides a perfect hash generator which is not language +specific. That is, the generator can output a perfect hash function for +a given set of keys in any programming language, this is achieved by +filling a given code template. + +### Acknowledgments: + +This code is derived from A. M. Kuchling's +[Perfect Minimal Hash Generator](http://www.amk.ca/python/code/perfect-hash). + +### Introduction: + +A perfect hash function of a certain set S of keys is a hash function +which maps all keys in S to different numbers. +That means that for the set S, +the hash function is collision-free, or perfect. +Further, a perfect hash function is called minimal when it maps n keys +to n *consecutive* integers, usually in the range from 0 to n-1. + +After coming across A. M. Kuchling's Perfect Minimal Hash Generator, +I decided to write a general tool for generating perfect hashes. +It is general in the sense that it can produce perfect hash functions +for almost any programming language. +A given code template is filled with parameters, +such that the output is code which implements the hash function. + +The algorithm the program uses is described in the paper +["Optimal algorithms for minimal perfect hashing"] +(http://citeseer.ist.psu.edu/122364.html), +Z. J. Czech, G. Havas and B.S. Majewski. + +I tried to illustrate the algorithm and explain how it works on +[this page](http://ilan.schnell-web.net/prog/perfect-hash/algo.html). + +### Usage: + +Given a set of keys which are ordinary character string, +the program returns a minimal perfect hash function. +This hash function is returned in the form of Python code by default. +Suppose we have a file with keys: + + # 'animals.txt' + Elephant + Horse + Camel + Python + Dog + Cat + + +The exact way this file is parsed can be specified using command line +options, for example it is possible to only read one column from a file +which contains different items in each row. +The program is invoked like this: + + # ======================================================================= + # ================= Python code for perfect hash function =============== + # ======================================================================= + + G = [0, 0, 4, 1, 0, 3, 8, 1, 6] + + S1 = [5, 0, 0, 6, 1, 0, 4, 7] + S2 = [7, 3, 6, 7, 8, 5, 7, 6] + + def hash_f(key, T): + return sum(T[i % 8] * ord(c) for i, c in enumerate(str(key))) % 9 + + def perfect_hash(key): + return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % 9 + + # ============================ Sanity check ============================= + + K = ["Elephant", "Horse", "Camel", "Python", "Dog", "Cat"] + H = [0, 1, 2, 3, 4, 5] + + assert len(K) == len(H) == 6 + + for k, h in zip(K, H): + assert perfect_hash(k) == h + + +The way the program works is by filling a code template with the calculated +parameters. The program can take such a template in form of a file and +fill in the calculated parameters, this allows the generation of perfect +hash function in any programming language. The hash function is kept quite +simple and does not require machine or language specific byte level operations +which might be hard to implement in the target language. +The following parameters are available in the template, and will expand to: + + string | expands to + --------+-------------------------------- + $NS | the length of S1 and S2 + $S1 | array of integers S1 + $S2 | array of integers S2 + $NG | length of array G + $G | array of integers G + $NK | the number of keys, i.e. length of array K and H + $K | array with the quoted keys + $H | array of integer hash values + $$ | $ (a literal dollar sign) + + +A literal '$' is escaped as '$$'. Since the syntax for arrays is not the +same in all programming languages, some specifics can be adjusted using +command line options. +The section of the built-in template which creates the actual hash function +is: + + G = [$G] + + S1 = [$S1] + S2 = [$S2] + + def hash_f(key, T): + return sum(T[i % $NS] * ord(c) for i, c in enumerate(str(key))) % $NG + + def perfect_hash(key): + return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % $NG + +Using code templates, makes this program very flexible. The package comes +with several complete examples for C and C++. There are many choices one +faces when implementing a static hash table: do the parameter lists go into +a separate header file, should the API for the table only contain the hash +values, but not the objects being mapped, and so on. +All these various choices are possible because of the template is simply +filled with the parameters, no matter what else is inside the template. + +Another possible use the program is as a python module. The functions and +classes in 'perfect_hash.py' are documented and have clean interfaces. +The folder 'example-Python' has examples which shows how the module +can be used directly in this way. + +### Requirement: + +Python 2.5 diff --git a/components/rtgui/utils/perfect_hash/doc/mktable.py b/components/rtgui/utils/perfect_hash/doc/mktable.py new file mode 100644 index 0000000000..ef304ed673 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/doc/mktable.py @@ -0,0 +1,22 @@ +#!/usr/bin/env python +import re + +def convert(line, head = False): + pat = re.compile(r'([$]\S*)') + line = pat.sub(r'<code>\1</code>', line) + + row = [x.strip() for x in line.split('|')] + fmt = ' <tr><td>%s</td><td>%s</td></tr>' + if head: + fmt = fmt.replace('td', 'th') + print fmt % tuple(row) + + +f = file('parameters.txt') + +print '<table>' +convert(f.readline(), head = True) +f.readline() +for line in f: + convert(line) +print '</table>' diff --git a/components/rtgui/utils/perfect_hash/doc/parameters.txt b/components/rtgui/utils/perfect_hash/doc/parameters.txt new file mode 100644 index 0000000000..b853492659 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/doc/parameters.txt @@ -0,0 +1,11 @@ + string | expands to + --------+-------------------------------- + $NS | the length of S1 and S2 + $S1 | array of integers S1 + $S2 | array of integers S2 + $NG | length of array G + $G | array of integers G + $NK | the number of keys, i.e. length of array K and H + $K | array with the quoted keys + $H | array of integer hash values + $$ | $ (a literal dollar sign) diff --git a/components/rtgui/utils/perfect_hash/example-C++/Makefile b/components/rtgui/utils/perfect_hash/example-C++/Makefile new file mode 100644 index 0000000000..de525f5d5d --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example-C++/Makefile @@ -0,0 +1,31 @@ + +CXX = g++ -Wall + + +lookup: main.o states-code.o + $(CXX) -o $@ $^ + + +main.o: main.cc states-code.hh + $(CXX) -c $< + + +states-code.o: states-code.cc states-code.hh states.dat.h + $(CXX) -c $< + + +states-code.cc: states.dat states-tmpl.cc states-code.hh + ../perfect_hash.py --splitby '|' --keycol 2 states.dat states-tmpl.cc + + +states.dat.h: states.dat + ./mk_header.py >$@ + + +clean: + rm lookup *.o states.dat.h states-code.cc + + +test: + ./lookup 'NY' + ./lookup 'QW' diff --git a/components/rtgui/utils/perfect_hash/example-C++/main.cc b/components/rtgui/utils/perfect_hash/example-C++/main.cc new file mode 100644 index 0000000000..9d724a7872 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example-C++/main.cc @@ -0,0 +1,24 @@ + +#include <iostream> +#include <string> +using namespace std; + +#include "states-code.hh" + + +int main (int argc, char *argv[]) +{ + if (argc != 2) { + printf ("Usage: %s <abbreviation>\n", argv[0]); + return 2; + } + + string abbr = argv[1]; + + State s(abbr); + + cout << "The state of " << s.name () + << " has a population of " << 1e-6 * s.population () << " million.\n"; + + return 0; +} diff --git a/components/rtgui/utils/perfect_hash/example-C++/mk_header.py b/components/rtgui/utils/perfect_hash/example-C++/mk_header.py new file mode 100644 index 0000000000..646c0787be --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example-C++/mk_header.py @@ -0,0 +1,10 @@ +#!/usr/bin/env python + +for line in file('states.dat'): + line = line.strip() + if line.startswith('#'): + continue + + row = tuple(entry.strip() for entry in line.split('|')) + + print ' { "%s", "%s", %s },' % row diff --git a/components/rtgui/utils/perfect_hash/example-C++/states-code.hh b/components/rtgui/utils/perfect_hash/example-C++/states-code.hh new file mode 100644 index 0000000000..964d8bf8a5 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example-C++/states-code.hh @@ -0,0 +1,19 @@ + + +#include <string> +using namespace std; + + +class State +{ +public: + State (const string abbr); + + string name () const { return nam; }; + int population () const { return pop; }; + +private: + string nam; + int pop; +}; + diff --git a/components/rtgui/utils/perfect_hash/example-C++/states-tmpl.cc b/components/rtgui/utils/perfect_hash/example-C++/states-tmpl.cc new file mode 100644 index 0000000000..ab94be31f6 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example-C++/states-tmpl.cc @@ -0,0 +1,55 @@ + +#include <string.h> + +#include <iostream> + +#include "states-code.hh" + +static struct { + char *name; + char *abbr; + int pop; +} states[$NK] = { +#include "states.dat.h" +}; + +static int T1[] = { $S1 }; + +static int T2[] = { $S2 }; + +static int G[] = { $G }; + +static int hash_g (const char *key, const int *T) +{ + int i, sum = 0; + + for (i = 0; key[i] != '\0'; i++) { + sum += T[i] * key[i]; + sum %= $NG; + } + return G[sum]; +} + +static int perfect_hash (const char *key) +{ + if (strlen (key) > $NS) + return 0; + + return (hash_g (key, T1) + hash_g (key, T2)) % $NG; +} + +State::State (const string abbr) +{ + int hash_value = perfect_hash (abbr.c_str ()); + + if (hash_value < $NK && + strcmp(abbr.c_str (), states[hash_value].abbr) == 0) + { + nam = states[hash_value].name; + pop = states[hash_value].pop; + } + else + { + cerr << "'" << abbr << "' is not an abbreviation for a state\n"; + } +} diff --git a/components/rtgui/utils/perfect_hash/example-C++/states.dat b/components/rtgui/utils/perfect_hash/example-C++/states.dat new file mode 100644 index 0000000000..5538309450 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example-C++/states.dat @@ -0,0 +1,52 @@ +# Name | Abr | Population +#--------------+------+--------- +Alabama | AL | 4335400 +Alaska | AK | 611500 +Arizona | AZ | 4664600 +Arkansas | AR | 2531000 +California | CA | 33198100 +Colorado | CO | 3930700 +Connecticut | CT | 3271100 +Delaware | DE | 736900 +Florida | FL | 15012200 +Georgia | GA | 7562200 +Hawaii | HI | 1188400 +Idaho | ID | 1221500 +Illinois | IL | 11981700 +Indiana | IN | 5882500 +Iowa | IA | 2854700 +Kansas | KS | 2603200 +Kentucky | KY | 3921000 +Louisiana | LA | 4361200 +Maine | ME | 1243700 +Maryland | MD | 5122400 +Massachusetts | MA | 6133500 +Michigan | MI | 9825100 +Minnesota | MN | 4704200 +Mississippi | MS | 2739700 +Missouri | MO | 5421400 +Montana | MT | 886400 +Nebraska | NE | 1661400 +Nevada | NV | 1828700 +New Hampshire | NH | 1179100 +New Jersey | NJ | 8078300 +New Mexico | NM | 1738700 +New York | NY | 18197800 +North Carolina | NC | 7483100 +North Dakota | ND | 640000 +Ohio | OH | 11197900 +Oklahoma | OK | 3328100 +Oregon | OR | 3266800 +Pennsylvania | PA | 12044200 +Rhode Island | RI | 987000 +South Carolina | SC | 3781800 +South Dakota | SD | 738500 +Tennessee | TN | 5398200 +Texas | TX | 19274300 +Utah | UT | 2071500 +Vermont | VT | 590400 +Virginia | VA | 6768400 +Washington | WA | 5674900 +West Virginia | WV | 1813200 +Wisconsin | WI | 5224500 +Wyoming | WY | 479500 diff --git a/components/rtgui/utils/perfect_hash/example-PyModule/Makefile b/components/rtgui/utils/perfect_hash/example-PyModule/Makefile new file mode 100644 index 0000000000..662ff78442 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example-PyModule/Makefile @@ -0,0 +1,26 @@ + + +CC = gcc -Wall + + +stations.so: stationsmodule.c stations.dat.h stations-code.h + $(CC) -shared -fPIC -I/usr/local/include/python2.5 \ + -o stations.so stationsmodule.c + + +stations.dat.h: stations.dat + sed <$< >$@ -e 's:\([^,]*\),\([^,]*\): { "\1", "\2" },:' + + +stations-code.h: stations.dat stations-tmpl.h + ../perfect_hash.py --trails 2 $^ + + +clean: + rm stations-code.h stations.dat.h stations.so + + +test: + python -c "import stations; print stations.locator('DL5BAC')" + + diff --git a/components/rtgui/utils/perfect_hash/example-PyModule/stations-tmpl.h b/components/rtgui/utils/perfect_hash/example-PyModule/stations-tmpl.h new file mode 100644 index 0000000000..b77e6320b3 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example-PyModule/stations-tmpl.h @@ -0,0 +1,12 @@ + +#define NK $NK /* number of keys */ +#define NG $NG /* number of vertices */ +#define NS $NS /* elements in T */ + + +int G[] = { $G }; + +int T1[] = { $S1 }; + +int T2[] = { $S2 }; + diff --git a/components/rtgui/utils/perfect_hash/example-PyModule/stations.dat b/components/rtgui/utils/perfect_hash/example-PyModule/stations.dat new file mode 100644 index 0000000000..5358120c34 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example-PyModule/stations.dat @@ -0,0 +1,500 @@ +DL0WM,JO40HM +DM4WDK,JO50OI +M0GHZ,IO81VK +ON2CP,JO21IG +PI4UTR,JO22MC +DO2YMH,JO41AT +ON1GZ,JO20FW +DL5QQ,JO32KB +M0HKB,JO02OB +ON4LBT,JO10WK +SM7VTW,JO65QQ +PA3AYD,JO21UU +DO3LTK,JO43XS +DC0NAC,JO43VI +PD0LQQ,JO20VS +DO1YMJ,JO31WS +DL1EJL,JO31FS +DG3TF,JO53IU +ON1AEN,JO10VW +DL1KDA,JO30FQ +SM7LHI,JO65PO +DG1EIP,JO31JL +PD1AKT,JO22TA +DN1GSK,JO62NL +OQ1AEN,JO10VW +DG9YIH/M,JO31TR +G0UYC,JO02MR +F1PGL,JO20IE +DO1KNB,JO30NQ +DL5NEN,JN59OP +DL1RNO,JO62FK +DO8EF,JO31KK +DL6IY,JN49NI +ON4NOK,JO21LO +DO9MH,JO33QO +PA0PTS,JO23TF +G5LK,IO91SK +DJ6XV,JO31LQ +ON4ARF,JO10MV +PE1OJB,JO22IN +DH1BBO,JO42FS +M1DNJ,JO01GJ +PA0BVD,JO23TF +ON1CJQ,JO10OV +DL2NFX,JN59JU +DL4HG,JO53CM +DG3BEO,JO43JF +OZ4EDR,JO75JF +DD1LT/P,JO44TK +G4OXD,IO91UW +DG1KZF,JO31RN +DO2YPB,JO41JR +DO3JJ,JO31QM +DO5YLM,JO42GA +DL2IAN,JN49BC +PA0ME,JO22OB +DC5PN,JN49HV +PA9JP,JO32MS +PD5RD,JO21IT +PE1PQV,JO32JG +OZ3TT,JO66CB +DO9KS,JO43CE +DJ8MS/P,JO63CT +ON4KBE,JO20BI +PE1JVV,JO21GV +DH0EAQ,JO31IK +DG9RCI,JN59PH +DO6UWE/P,JO31OI +DB7LG,JO44TH +DD5JK,JO31RO +DG6LSW,JO44SP +M1MGD,IO91VC +DL6YAU,JO44PJ +PE1OLM,JO23TF +DG0DRF,JO71JJ +DG3YCB,JO41KV +DF7JS,JO31JM +OZ2NAC,JO55RT +DJ5JD,JO33OO +PA3DHR,JO21DU +PE2JMR,JO33HG +OZ1XAT/A,JO55UL +PA3GKH,JO32HK +G4DCJ,JO02IT +DL4NAC,JN59SV +DF0DS,JO31RM +GW7SMV,IO81LN +DO1AYJ,JO50SU +DL0BAC,JO30BS +DL0JRR,JO31CT +OZ7HAM,JO65CL +DK0ALK,JN38TD +DO6DIB,JO43DA +PA3GTC,JO32LR +DD1LI,JO43WO +DG9ACT/P,JO42QH +PE1PMG,JO31BH +SK7OL,JO66NC +DH0JB,JO31CH +OQ1ARQ,JO10VX +DD7ZT,JO40DH +DL1JJ,JO31IA +DL1EEX,JO31MA +ON4CDF,JO21EE +DL0SE,JO31PG +DO3YY,JO31QM +DK0HC,JO40OQ +DC8BQ,JO31KE +DG1LAR,JO43UP +OZ/DL0IZ/P,JO45GD +DG3TD,JO44GQ +DL6OBH,JO42QI +PA0JCS,JO21DN +DG0OJG,JO50MX +DO1KFB,JO30CS +SM60EW,JO67DA +G4MRS/P,JO01MU +DL5DBM,JO32WO +DK3BM,JO42LH +DD9DV,JO31TO +DO1DQ,JO31TL +OZ5AEK,JO55XO +DG1YAR,JO41CR +OO6LY,JO21LH +DL1PR,JO30JS +DL5ZAB,JO40HC +DO1MGN,JO50DO +SM7UPF,JO65TO +DO1NNN,JO50VF +DK5BD,JO42IX +DL3OCA,JO42VH +HB9MPX,JN47RJ +DG4KAS,JO30DU +DF1UF,JN49HK +DC6GF/P,JN47NX +DG7ES,JN68GI +DF0NF,JO44UH +DG8EKI,JO31MI +OZ9CLN,JO56CE +SK7MW,JO65MJ +DL9ECA,JO31CQ +DF9IC,JN48IW +PD9FJ,JO23KE +DL4LBO,JO43XT +DF0WD,JO42FD +DH4PSG,JO31NN +LA0BY,JO59IX +DJ5FK,JO42SH +DO1ASM,JO50LQ +DL9KCM,JO30IS +DG6MBS,JO41AH +OZ2SYV,JO54RS +DL0HMS,JO42MC +DL2PZ,JN49DW +DG5NEP/P,JO50VF +SM6VKC,JO68CG +DF8AA/P,JO71AA +PA1WM,JO21WW +DO3BTL,JO43HB +PA3GGN,JO21LU +DF1VW,JN39HJ +DJ5KX,JO30PQ +ON1LPA,JO20XO +DJ5QW,JO32SF +G4AJC,IO91VJ +OZ7P,JO45SQ +G4MRS,JO02PB +PD0ZX,JO22QF +DB5BR,JO42FS +DO1JRA,JO42GF +DL1DUF,JO62EJ +DO2NHD,JO40MB +DG6DDE,JO31UM +PA3FBP,JO33GB +DC1GUN,JN68GG +DO2BO,JO33RM +OZ6AQ,JO44UX +OZ1QQ,JO47XG +DG1YBT,JO32QD +DL9YEY,JO41GV +DG1YIV,JO42HF +DB2WD,JN39VV +DF0UKW,JN49HN +OZ1BEF/P,JO46SB +PE1ISU,JO21WD +DO1KOH,JO30HR +DK9SS,JN48OM +PE1OPK,JO23UE +DG3GAQ,JN48GE +DO2FX,JO40LH +SK7BT,JO65MO +OZ1FHU,JO55SR +SK6QW,JO68WR +DL4FBN,JO30WC +DG3FCT,JO41RB +OE2SCM,JN67OV +PA0ZM,JO32GK +DL0MQ,JO41EV +DB3WR,JO31DG +ON2BFV,JO11XA +DJ5DM,JO31FF +G6FPQ,IO91XI +DJ0VZ,JO30GL +OO2WIM,JO20OR +DG7RZ/P,JN59WK +DL5QN,JO42HC +DC9XX,JO43QR +SM7SLU,JO65ML +F1PYW,JN38UP +DG2NJ,JN68OL +DJ5KM,JO42GA +DL3TS,JO30PX +DG4YIE/P,JO41PU +DL0RSH,JO43SV +PE1RYU,JO21GU +DJ3QB,JO32MF +DG4KBY/P,JO42CW +PA3GSX,JO32DM +DG1YRT,JO41KW +DG9BEY,JO42AH +PA3EXO,JO32GW +PE1OPH,JO22XF +DO9FB,JN49BP +F0EUE,JN29VM +G4RRA/P,IO70XR +DL0EDD,JO31IF +SM7MRL,JO66KC +DK5JM,JO43QS +DJ3NU,JO31SL +DH6YMC,JO32MF +DL1DAX,JO31RM +DC4KM,JO30XO +F1TUE,JN38DR +DO4ME,JO43KC +ON7CC,JO10XM +DL1PBC,JO30VJ +DL3IAE,JN49DE +DL1SDN,JN48PP +DL4ANT,JN49LF +DH1NHI,JO50VF +DO1BR,JO42AE +G4ODA,IO92WS +DB2DJ,JO31RM +DL8LAH,JO44QQ +DH9NBB,JN49WS +F1LPV,JO10NP +DL3SF,JO32MF +SM7VXT,JO65NU +DL4LCA/P,JO44XF +DL3FDL,JO40KR +SM7XEN,JO65RL +DL6ABO,JO52GH +EI7IW,IO63SS +DC1QU,JO31TW +DG0OCW,JO50CT +SM7XWM,JO86AJ +ON2MRT,JO20MX +DA0GSN,JO31HB +DL8FBC,JO41UF +F1DBN/P,JO00WT +DJ6CB,JO42JW +DL1SUZ,JO53UN +DJ5NU,JO31QH +DL0SOP,JO54WC +DO1MGN/P,JO50AN +OK1BYR,JN79IP +PD0RAA,JO22WK +DJ9DL,JO31NC +DK5WO,JO30AS +OZ8FYN,JO55EJ +DO1FDR,JO41PD +ON2BIV,JO10RX +ON4AEO,JO10OW +DL4MB,JN49FA +GW4HBZ/P,IO83GC +OZ1BEF,JO46OE +PE0NYJ,JO21VT +DO3LBP,JO43MW +DB3BW,JO42AC +DF6YL,JO31WS +DP0RFU,JO32LS +DF4BV,JO43RH +DJ6GV,JO52HG +DG7KAQ,JO30FS +DH1YPH,JO31VL +SM7JUQ,JO65PO +DG7ACF,JO42UI +DG6NBL,JN59LL +OK1MCS,JN69QR +DL1REM,JO32MF +DN1RDT,JN59WK +OZ3FYN/P,JO55BJ +DB0GSN,JO31JC +DC1GUN/P,JN68GI +DJ1DH/P,JO53BG +DO1RSG/P,JN68KX +PD0FFU,JO20UU +DO8DW,JO31SO +DL8II,JN49GP +PA3DRL,JO21PS +DG8LG,JO44VP +PD0EBF,JO21LQ +OZ9BO,JO46HE +DO3NML,JN59SV +DJ3BP,JO42CX +F6IRS,JN38VN +F5SMZ,JN39EJ +GM1TDU,IO87WE +DL5BAC,JO43LG +DO7OCH,JO51AT +DL1HRY,JO61AD +DK7VA,JO32MK +SM7JPI,JO75DW +DL0GC,JO31CQ +M1IFT,IO93NL +DF5AY,JN49DX +DG1IHH,JN49GJ +DO5BRH,JO43CE +DK6AJ,JO52GH +DL0NF,JN59PL +DG1BHM,JO43PC +DK3RV,JO31DG +DD8EI,JO31NC +PD2PL,JO22HD +DL0GL,JO31LN +DC1PJA,JN49DV +PD2GCM,JO21ET +SI7GM,JO65MO +DG6MOG,JO52XN +OQ4CJU,JO20PS +DG1DPN,JO31RL +DK0BA,JO43NF +DL2HQ,JN48FX +PA4PS,JO33GH +DK0EE,JN58TG +DD9PL,JN49CN +PB0AOK,JO32IH +DC2OOO,JN39NI +DL0NS,JO31IE +ON4BAK,JO31PA +G4DCV,IO91OF +DG4FFF,JO40FA +G3BNE,JO01BJ +DO2GN,JO31PM +DD7PA/P,JN49LM +OZ0A/P,JO55UL +DL8BEV,JO43JH +DJ8UV,JO31OF +PE1PMV,JO32JG +DL8AX,JO31ID +PE1RER,JO22SA +PD0RKC,JO33AD +DC4ASK,JO31MI +DG1YCF,JO42KH +SK7PL,JO76DJ +M1MHZ,IO92WV +DF9PX/P,JO30JF +DG0OZ,JO50LU +DB1BMN/P,JO43HA +DH2UD/P,JO44XS +OZ5AGJ,JO56DF +OZ3AEV,JO55WR +PA1JAN,JO32KV +PE7MO,JO32KR +LA7M,JO48KK +PA1TX,JO32JG +OZ7DAL,JO56IE +PE1PED,JO22QE +DL0WH,JN49HN +DL9KI,JO42GE +M0AIJ,IO92PA +DG0CAL/P,JO31BC +DG1YFF,JO42IG +OZ4DR,JO55WL +G8RWG,JO01BN +OZ3RIN,JO55VK +SM7VXS,JO65UV +DL9EBI,JO31IE +PD5FDV,JO21HV +DL5XB,JO43UL +DJ9IQ,JO30OI +PE1NNX,JO22JN +DB2YC,JO32OF +PA5WT,JO22HG +DO2PK,JO41NW +PE1BVW,JO21DO +DL0TS,JO40FC +DB9KR,JO41DQ +DO1ZB,JO64II +DO4YPM,JO32QI +G0VJG,JO01BL +DD2YCS,JO43FE +DO7MH,JO31MT +G3JHM,IO91LC +DL8FAJ,JO51AD +DG4FR,JO31OJ +ON1DNF,JO20NU +DO4FMK,JO40MF +PI4THT,JO32KF +DK4LI,JO44WQ +DD3FU,JO40IE +DF1LON/P,JO31LH +DL2ARD/P,JO60AR +DH9YBC,JO42HE +G3OHC,IO93KS +DK0HF,JO42IF +DF6QB,JO31WW +DO3HN,JO31LK +M3RCV,JO01AL +DL0SAT,JO41XO +DD7PC,JN49AX +DL2LSM,JO61HH +PA3HHT,JO22QC +PD2OPA,JO21BT +DL0VR,JO31MI +EI3GE,IO63XD +DF9CY,JO54AL +DL1AH,JO42TX +DL1PW,JN49DV +DC9CZ,JO42GA +PA3FJY/P,JO32FI +DG5BGB,JO43HB +ON7LAO,JO20CK +DG0SY,JO54VC +DK5KC,JO30DS +DG6YJ,JO32RB +OO4BAX,JO21IH +DO1LNK,JO53EK +DJ3LE,JO44SK +DO1YCI,JO31NO +DJ8TA,JO41BU +DL8BAV,JO43MF +DO1RSG,JN68ET +DO1PIA,JO31PM +DL1AUW/P,JO51CH +DL0VV,JO64AD +DL3JAN/P,JO60KS +ON50ZTM,JO10UV +PA3GHZ,JO21OI +DL2SDU,JN48XT +DG4YFT,JO31OR +G0UIQ,JO02PW +DF9PX,JN49HU +DG8FAY,JO40GD +DL9LBH,JO30MP +DG5YHK,JO31SR +DC2GY/P,JN48DS +PE1PZS,JO21DV +ON4PS,JO20KQ +PE1PWM,JO22FE +DL2VB/P,JO31KP +DG8BX/P,JO43NA +DK4FG,JO40EM +DO8BAF/P,JN59WK +OK1MSM/P,JN69PR +DC2GY,JN48BQ +DK2LR,JN57KO +DH3UN,JO31TL +DF0SB,JN48GE +ON4CBR,JO10OU +DB3VE,JN39KK +DO2YTM,JO42GA +DJ9CN,JO43DA +M3HKK/P,JO01BB +DK8ZB,JN49KW +DC2AM,JO43WL +DF7KF,JO30GU +DC7KG,JO30LW +SK7CY,JO65RJ +DH6OBN/P,JO42UJ +SK7HR,JO77HM +ON4BAR,JO10MV +DH8OH,JO51AT +DL5OAK,JO52AK +DG1DX,JO31SL +DL0HEU,JN47NX +DL1FX,JN49HS +DN1BE,JO42AH +G4ZTR,JO01KW +DG3YY,JO31QM +DK4WH/P,JN49BH +OK1UEM,JO60TH +PE1LWJ,JO22VJ +OZ0XX,JO54RS +DO1ON,JO51HR +DK0DH,JO31QL +DJ9JY,JO31JM +DG1FDX,JN49LP +DG0CCD,JO52TC +DL5NAV,JO33TF +DL4KCA,JO31JX +DG6NDK,JN59GN +DO9BC,JN48QP +DK1HW,JO42TG +DC4MP,JO31MI +ON4CIN,JO11UB +LA2CFA,JO48JL +DH2SAV,JN48QU +PE1ONM,JO32KR +M5AEH,IO93BS diff --git a/components/rtgui/utils/perfect_hash/example-PyModule/stationsmodule.c b/components/rtgui/utils/perfect_hash/example-PyModule/stationsmodule.c new file mode 100644 index 0000000000..bf14e1bbee --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example-PyModule/stationsmodule.c @@ -0,0 +1,69 @@ + +#include <Python.h> + +#include "stations-code.h" + +static struct { + char *callsign; + char *locator; +} station_list[] = { +#include "stations.dat.h" +}; + +static int hash_f (const char *s, const int *T) +{ + register int i, sum = 0; + + for (i = 0; s[i] != '\0'; i++) { + sum += T[i] * s[i]; + sum %= NG; + } + return sum; +} + +static int perf_hash (const char *k) +{ + if (strlen (k) > NS) + return 0; + + return (G[ hash_f(k, T1) ] + G[ hash_f(k, T2)] ) % NG; +} + +static int getlocator (char *locator, const char *callsign) +{ + int hashval = perf_hash (callsign); + + if (hashval < NK && strcmp(callsign, station_list[hashval].callsign) == 0) { + strcpy (locator, station_list[hashval].locator); + return 1; + } + return 0; +} + +static PyObject * +stations_locator(PyObject *self, PyObject *args) +{ + const char *callsign; + char locator[6]; + + if (!PyArg_ParseTuple(args, "s", &callsign)) + return NULL; + + return Py_BuildValue("s", (getlocator (locator, callsign) == 1) ? + locator : NULL); +} + +static PyMethodDef StationsMethods[] = { + + {"locator", stations_locator, METH_VARARGS, + "Get locator from callsign."}, + + {NULL, NULL, 0, NULL} /* Sentinel */ +}; + + +PyMODINIT_FUNC +initstations(void) +{ + (void) Py_InitModule("stations", StationsMethods); +} diff --git a/components/rtgui/utils/perfect_hash/example-PyModule/test.py b/components/rtgui/utils/perfect_hash/example-PyModule/test.py new file mode 100644 index 0000000000..02c06b6926 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example-PyModule/test.py @@ -0,0 +1,28 @@ +#!/usr/bin/env python +import sys +from timeit import Timer +from stations import locator + +call = sys.argv[1] +print repr(call) +D = {} + +for line in file('stations.dat'): + c, l = [x.strip() for x in line.split(',')] + D[c] = l + +def test1(c): + return D[c] + +print repr(test1(call)) +t = Timer("test1(%r)" % call, "from __main__ import test1") +print t.timeit() + +# ----- + +def test2(c): + return locator(c) + +print repr(test2(call)) +t = Timer("test2(%r)" % call, "from __main__ import test2") +print t.timeit() 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' diff --git a/components/rtgui/utils/perfect_hash/example1-C/Makefile b/components/rtgui/utils/perfect_hash/example1-C/Makefile new file mode 100644 index 0000000000..59b7ef0d67 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example1-C/Makefile @@ -0,0 +1,31 @@ + +CC = gcc -Wall + + +lookup: main.o states-code.o + $(CC) -o $@ $^ + + +main.o: main.c states-code.h states.dat.h + $(CC) -c $< + + +states-code.o: states-code.c states-code.h + $(CC) -c $< + + +states-code.c: states.dat states-tmpl.c + ../perfect_hash.py -vvvv --splitby '|' --keycol 2 $^ + + +states.dat.h: states.dat + ./mk_header.py >$@ + + +clean: + rm lookup *.o states.dat.h states-code.c + + +test: + ./lookup 'NY' + ./lookup 'QW' diff --git a/components/rtgui/utils/perfect_hash/example1-C/main.c b/components/rtgui/utils/perfect_hash/example1-C/main.c new file mode 100644 index 0000000000..0d36bcea45 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example1-C/main.c @@ -0,0 +1,33 @@ + +#include <stdio.h> + +#include "states-code.h" + +struct { + char *name; + char *abbr; + int pop; +} states[] = { +#include "states.dat.h" +}; + + +int main (int argc, char *argv[]) +{ + if (argc != 2) { + printf ("Usage: %s <abbreviation>\n", argv[0]); + return 2; + } + + char *abbr = argv[1]; + int hashval; + + if ((hashval = has_key(abbr)) == -1) + printf ("'%s' is not an abbreviation for a state.\n", abbr); + else + printf ("The state of %s has a population of %g million.\n", + states[hashval].name, + 1e-6 * states[hashval].pop); + + return 0; +} diff --git a/components/rtgui/utils/perfect_hash/example1-C/mk_header.py b/components/rtgui/utils/perfect_hash/example1-C/mk_header.py new file mode 100644 index 0000000000..646c0787be --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example1-C/mk_header.py @@ -0,0 +1,10 @@ +#!/usr/bin/env python + +for line in file('states.dat'): + line = line.strip() + if line.startswith('#'): + continue + + row = tuple(entry.strip() for entry in line.split('|')) + + print ' { "%s", "%s", %s },' % row diff --git a/components/rtgui/utils/perfect_hash/example1-C/states-code.h b/components/rtgui/utils/perfect_hash/example1-C/states-code.h new file mode 100644 index 0000000000..5717b92d32 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example1-C/states-code.h @@ -0,0 +1,6 @@ + + +/* Return hash value of abbreviation 'abbr' if found, -1 otherwise */ +int has_key (const char *abbr); + + diff --git a/components/rtgui/utils/perfect_hash/example1-C/states-tmpl.c b/components/rtgui/utils/perfect_hash/example1-C/states-tmpl.c new file mode 100644 index 0000000000..001ca6e5ce --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example1-C/states-tmpl.c @@ -0,0 +1,42 @@ + +#include <string.h> + +#include "states-code.h" + + +static int T1[] = { $S1 }; + +static int T2[] = { $S2 }; + +static int G[] = { $G }; + +static char *K[] = { $K }; + +static int hash_g (const char *key, const int *T) +{ + int i, sum = 0; + + for (i = 0; key[i] != '\0'; i++) { + sum += T[i] * key[i]; + sum %= $NG; + } + return G[sum]; +} + +static int perfect_hash (const char *key) +{ + if (strlen (key) > $NS) + return 0; + + return (hash_g (key, T1) + hash_g (key, T2)) % $NG; +} + +int has_key (const char *abbr) +{ + int hash_value = perfect_hash (abbr); + + if (hash_value < $NK && strcmp(abbr, K[hash_value]) == 0) + return hash_value; + + return -1; +} diff --git a/components/rtgui/utils/perfect_hash/example1-C/states.dat b/components/rtgui/utils/perfect_hash/example1-C/states.dat new file mode 100644 index 0000000000..5538309450 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example1-C/states.dat @@ -0,0 +1,52 @@ +# Name | Abr | Population +#--------------+------+--------- +Alabama | AL | 4335400 +Alaska | AK | 611500 +Arizona | AZ | 4664600 +Arkansas | AR | 2531000 +California | CA | 33198100 +Colorado | CO | 3930700 +Connecticut | CT | 3271100 +Delaware | DE | 736900 +Florida | FL | 15012200 +Georgia | GA | 7562200 +Hawaii | HI | 1188400 +Idaho | ID | 1221500 +Illinois | IL | 11981700 +Indiana | IN | 5882500 +Iowa | IA | 2854700 +Kansas | KS | 2603200 +Kentucky | KY | 3921000 +Louisiana | LA | 4361200 +Maine | ME | 1243700 +Maryland | MD | 5122400 +Massachusetts | MA | 6133500 +Michigan | MI | 9825100 +Minnesota | MN | 4704200 +Mississippi | MS | 2739700 +Missouri | MO | 5421400 +Montana | MT | 886400 +Nebraska | NE | 1661400 +Nevada | NV | 1828700 +New Hampshire | NH | 1179100 +New Jersey | NJ | 8078300 +New Mexico | NM | 1738700 +New York | NY | 18197800 +North Carolina | NC | 7483100 +North Dakota | ND | 640000 +Ohio | OH | 11197900 +Oklahoma | OK | 3328100 +Oregon | OR | 3266800 +Pennsylvania | PA | 12044200 +Rhode Island | RI | 987000 +South Carolina | SC | 3781800 +South Dakota | SD | 738500 +Tennessee | TN | 5398200 +Texas | TX | 19274300 +Utah | UT | 2071500 +Vermont | VT | 590400 +Virginia | VA | 6768400 +Washington | WA | 5674900 +West Virginia | WV | 1813200 +Wisconsin | WI | 5224500 +Wyoming | WY | 479500 diff --git a/components/rtgui/utils/perfect_hash/example2-C/Makefile b/components/rtgui/utils/perfect_hash/example2-C/Makefile new file mode 100644 index 0000000000..865e8cf7eb --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example2-C/Makefile @@ -0,0 +1,22 @@ + +CC = gcc -Wall + +a.out: main.c keys.code.h + $(CC) $< + + +keys.code.h: keys.dat keys.tmpl.h + ../perfect_hash.py $^ + + +keys.dat: + ./mk_rnd_keys.py 100 >keys.dat + + +clean: + rm keys.dat keys.code.h a.out + + +test: + ./a.out + diff --git a/components/rtgui/utils/perfect_hash/example2-C/keys.tmpl.h b/components/rtgui/utils/perfect_hash/example2-C/keys.tmpl.h new file mode 100644 index 0000000000..550bdb089d --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example2-C/keys.tmpl.h @@ -0,0 +1,13 @@ + +#define NK $NK /* number of keys */ +#define NG $NG /* number of vertices */ +#define NS $NS /* length of array T1 and T2 */ + +int T1[] = { $S1 }; + +int T2[] = { $S2 }; + +int G[] = { $G }; + +char *K[] = { $K }; + diff --git a/components/rtgui/utils/perfect_hash/example2-C/main.c b/components/rtgui/utils/perfect_hash/example2-C/main.c new file mode 100644 index 0000000000..c19db892b8 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example2-C/main.c @@ -0,0 +1,51 @@ + +#include <assert.h> +#include <stdbool.h> +#include <stdio.h> +#include <string.h> + +#include "keys.code.h" + +int hash_g (char *s, int *T) +{ + int i, f = 0; + + for (i = 0; s[i] != '\0'; i++) { + f += T[i] * s[i]; + f %= NG; + } + return G[f]; +} + +int hash (char *k) +{ + if (strlen (k) > NS) + return 0; + + return (hash_g (k, T1) + hash_g (k, T2)) % NG; +} + +bool has_key (char *k) +{ + int h = hash (k); + + return h < NK && strcmp(k, K[h]) == 0; +} + +int main () +{ + int i; + + char *junk = "acnhuvn5yushvghnw7og5siuhgsiuhnglsh45vgghwn"; + + assert (has_key(junk) == 0); + assert (hash(junk) == 0); + + for (i = 0; i < NK; i++) { + assert (has_key(K[i]) == true); + assert (hash(K[i]) == i); + } + puts ("OK"); + + return 0; +} diff --git a/components/rtgui/utils/perfect_hash/example2-C/mk_rnd_keys.py b/components/rtgui/utils/perfect_hash/example2-C/mk_rnd_keys.py new file mode 100644 index 0000000000..81f964e9ff --- /dev/null +++ b/components/rtgui/utils/perfect_hash/example2-C/mk_rnd_keys.py @@ -0,0 +1,17 @@ +#!/usr/bin/env python + +# ./mk_rnd_keys.py 10000 | sort | uniq | shuf >keywords.txt + +import sys +from random import choice, randint +from string import digits, uppercase, lowercase + +def key(): + return ''.join(choice(uppercase + lowercase + digits) + for i in xrange(randint(6, 20))) + +N = int(sys.argv[1]) + + +for n in xrange(N): + print key() diff --git a/components/rtgui/utils/perfect_hash/graph/Makefile b/components/rtgui/utils/perfect_hash/graph/Makefile new file mode 100644 index 0000000000..dc84f85fdb --- /dev/null +++ b/components/rtgui/utils/perfect_hash/graph/Makefile @@ -0,0 +1,23 @@ + + + +animals.ps: animals.dot + neato -Tps $< -Gstart=100 -o $@ + + +animals.dot: animals.py + ./py2dot -l $< -o $@ + + +animals.py: ../animals.txt + ../perfect_hash.py $< >$@ + + +clean: + rm animals.py animals.dot animals.ps + + +test: + true + + diff --git a/components/rtgui/utils/perfect_hash/graph/example-pipeline b/components/rtgui/utils/perfect_hash/graph/example-pipeline new file mode 100644 index 0000000000..86f58cdb38 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/graph/example-pipeline @@ -0,0 +1,4 @@ +#!/bin/bash + +../perfect_hash.py ../animals.txt | ./py2dot | neato -Tps -Gstart=100 -o out.ps + diff --git a/components/rtgui/utils/perfect_hash/graph/py2dot b/components/rtgui/utils/perfect_hash/graph/py2dot new file mode 100644 index 0000000000..920c70386a --- /dev/null +++ b/components/rtgui/utils/perfect_hash/graph/py2dot @@ -0,0 +1,216 @@ +#!/usr/bin/env python + +class Graph: + def __init__(self, N): + self.N = N # number of vertices + + # maps a vertex number to the list of (vertices, edge value) + # to which it is connected by edges. + self.adjacent = [[] for n in xrange(N)] + + def connect(self, vertex1, vertex2, edge_value): + """ + Connect 'vertex1' and 'vertex2' with an edge, with associated + value 'value' + """ + # Add vertices to each other's adjacent list + self.adjacent[vertex1].append( (vertex2, edge_value) ) + self.adjacent[vertex2].append( (vertex1, edge_value) ) + + def check(self): + """ + See if vertex values add up to edge values (mod N). + """ + for vertex in xrange(self.N): + for neighbor, edge_value in self.adjacent[vertex]: + assert (self.vertex_values[vertex] + + self.vertex_values[neighbor]) % self.N == edge_value + + def calc_tree_sizes(self): + """ + After running this method, the attribute size will contain a list, + which maps the vertices to the size of the tree that vertex belongs + to. + """ + visited = self.N * [-1] # -1 unvisited, otherwise the number of tree + treenum = 0 + + # Loop over all vertices, taking unvisited ones as roots. + for root in xrange(self.N): + if visited[root] >= 0: + continue + + # explore tree starting at 'root' + # Stack of vertices to visit, a list of tuples (parent, vertex) + tovisit = [ (None, root) ] + while tovisit: + parent, vertex = tovisit.pop() + visited[vertex] = treenum + + # Loop over adjacent vertices, but skip the vertex we arrived + # here from the first time it is encountered. + skip = True + for neighbor, edge_value in self.adjacent[vertex]: + if skip and neighbor == parent: + skip = False + continue + + if visited[neighbor] >= 0: + # We visited here before, so the graph is cyclic. + exit('Hmm, graph is cyclic.') + + tovisit.append( (vertex, neighbor) ) + + treenum += 1 + + # maps the tree number to number of vertices within that tree + treesizes = treenum * [0] + for tree in visited: + treesizes[tree] += 1 + + self.size = [treesizes[visited[v]] for v in xrange(self.N)] + + if verbose: + freq = (self.N+1) * [0] + for size in treesizes: + freq[size] += 1 + + sys.stderr.write(' Size Trees\n') + for i, f in enumerate(freq): + if f: + sys.stderr.write('%5i %5i\n' % (i, f)) + if i == minsize-1: + sys.stderr.write('--------------\n') + + def write(self, fo, labels = False): + self.calc_tree_sizes() + + fo.write('graph G {\n' + ' size = "8,8";\n' + ' edge [color="#ff0000"]\n') + if labels: + fo.write(' node [color="#a0e0ee", style=filled];\n') + + for vertex, value in enumerate(self.vertex_values): + if self.size[vertex] < minsize: continue + fo.write(' { node [label="%i: %i"] v%i }\n' % ( + vertex, value, vertex)) + else: + fo.write(' node [color="#3377a0", label="",\n' + ' style=filled, shape=circle]\n') + + for vertex in xrange(self.N): # edges + if self.size[vertex] < minsize: continue + for neighbor, edge_value in self.adjacent[vertex]: + if neighbor > vertex: continue + fo.write(' v%i -- v%i%s;\n' % + (vertex, neighbor, + (' [label="%s: %i"]' % (K[edge_value], edge_value)) + if labels else '')) + fo.write('}\n') + fo.close() + + +if __name__ == '__main__': + import sys + from optparse import OptionParser + + usage = "usage: %prog [options] [PYCODE]" + + description = """\ +Given the python code for a perfect hash function which was generated by +perfect_hash.py, e.g. by '$ ../perfect_hash.py animals.txt >animals.py', +this program will create the graph which was used in determining the +perfect hash function. The input python code may also be given to stdin. +The output is saved as in the .dot format which is used by the Graphviz +tools (see http://www.graphviz.org/) to generate a picture of the graph. +""" + + parser = OptionParser(usage = usage, + description = description, + prog = sys.argv[0]) + + parser.add_option("-l", "--labels", + action = "store_true", + help = "Be verbose") + + parser.add_option("-m", "--minsize", + action = "store", + default = 1, + type = "int", + help = "Include only trees in the output which " + "have at least INT vertices. " + "Default is %default, i.e. all trees are " + "included within the output.", + metavar = "INT") + + parser.add_option("-o", "--output", + action = "store", + help = "Specify output FILE explicitly. " + "Default, is stdout. ", + metavar = "FILE") + + parser.add_option("-v", "--verbose", + action = "store_true", + help = "Be verbose") + + options, args = parser.parse_args() + + if options.minsize > 0: + minsize = options.minsize + else: + parser.error("minimal size of trees has to be larger than zero") + + verbose = options.verbose + + if len(args) > 1: + parser.error("incorrect number of arguments") + + # --------------------- end parsing and checking ----------------------- + + if verbose: + sys.stderr.write('minsize (of trees): %i\n' % minsize) + sys.stderr.write('labels (in output): %s\n' % options.labels) + + # ------------ input filehandle + + if len(args)==1: + try: + fi = file(args[0]) + except IOError : + exit("Error: Can't open `%s' for reading." % args[0]) + else: + fi = sys.stdin + + # ------------ read input, i.e. execute code + + exec(fi.read()) + + # ------------ make graph + + g = Graph(len(G)) + g.vertex_values = G + for key, hashval in zip(K, H): + g.connect(hash_f(key, S1), + hash_f(key, S2), + hashval) + g.check() + + # ------------ output filehandle + + if options.output: + try: + fo = file(options.output, 'w') + except IOError : + exit("Error: Can't open `%s' for writing." % options.output) + else: + fo = sys.stdout + + # ------------ write output, i.e. generate .dot output + + g.write(fo, options.labels) + + +# Local Variables: +# mode: python +# End: diff --git a/components/rtgui/utils/perfect_hash/perfect_hash.py b/components/rtgui/utils/perfect_hash/perfect_hash.py new file mode 100644 index 0000000000..e981877634 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/perfect_hash.py @@ -0,0 +1,870 @@ +#!/usr/bin/env python +""" +Generate a minimal perfect hash function for the keys in a file, +desired hash values may be specified within this file as well. +A given code template is filled with parameters, such that the +output is code which implements the hash function. +Templates can easily be constructed for any programming language. + +The code is based on an a program A.M. Kuchling wrote: +http://www.amk.ca/python/code/perfect-hash + +The algorithm the program uses is described in the paper +'Optimal algorithms for minimal perfect hashing', +Z. J. Czech, G. Havas and B.S. Majewski. +http://citeseer.ist.psu.edu/122364.html + +The algorithm works like this: + +1. You have K keys, that you want to perfectly hash against some + desired hash values. + +2. Choose a number N larger than K. This is the number of + vertices in a graph G, and also the size of the resulting table G. + +3. Pick two random hash functions f1, f2, that return values from 0..N-1. + +4. Now, for all keys, you draw an edge between vertices f1(key) and f2(key) + of the graph G, and associate the desired hash value with that edge. + +5. Check if G is acyclic, i.e. has no loops; if no, go back to step 2. + +6. Assign values to each vertex such that, for each edge, you can add + the values for the two vertices and get the desired (hash) value + for that edge. This task is easy, because the graph is acyclic. + This is done by picking a vertex, and assigning it a value of 0. + Then do a depth-first search, assigning values to new vertices so that + they sum up properly. + +7. f1, f2, and vertex values of G now make up a perfect hash function. + + +For simplicity, the implementation of the algorithm combines steps 5 and 6. +That is, we check for loops in G and assign the vertex values in one procedure. +If this procedure succeeds, G is acyclic and the vertex values are assigned. +If the procedure fails, G is cyclic, and we go back to step 2, replacing G +with a new graph, and thereby discarding the vertex values from the failed +attempt. +""" +__author__ = 'Ilan Schnell <[email protected]>, 2008 (and AMK 2000)' +__license__ = 'GNU GPL 2' +__version__ = '0.1' + + +import sys, random, string, cStringIO, StringIO + +verbose = False +trails = 5 + + +class Graph: + """ + 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). + + Example: + >>> G = Graph(3) + >>> 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: + >>> G.assign_vertex_values() + True + >>> 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) + >>> G.assign_vertex_values() + False + """ + def __init__(self, N): + self.N = N # number of vertices + + # maps a vertex number to the list of tuples (vertices, edge value) + # to which it is connected by edges. + self.adjacent = [[] for n in xrange(N)] + + def connect(self, vertex1, vertex2, edge_value): + """ + Connect 'vertex1' and 'vertex2' with an edge, with associated + value 'value' + """ + # Add vertices to each other's adjacent list + self.adjacent[vertex1].append( (vertex2, edge_value) ) + self.adjacent[vertex2].append( (vertex1, edge_value) ) + + def assign_vertex_values(self): + """ + Try to assign the vertex values, such that, for each edge, you can + add the values for the two vertices involved and get the desired + value for that edge, i.e. the desired hash key. + This will fail when the graph is cyclic. + + This is done by a Depth-First Search of the graph. If the search + finds a vertex that was visited before, there's a loop and False is + returned immediately, i.e. the assignment is terminated. + On success (when the graph is acyclic) True is returned. + """ + self.vertex_values = self.N * [-1] # -1 means unassigned + + visited = self.N * [False] + + # Loop over all vertices, taking unvisited ones as roots. + for root in xrange(self.N): + if visited[root]: + continue + + # explore tree starting at 'root' + self.vertex_values[root] = 0 # set arbitrarily to zero + + # Stack of vertices to visit, a list of tuples (parent, vertex) + tovisit = [ (None, root) ] + while tovisit: + parent, vertex = tovisit.pop() + visited[vertex] = True + + # Loop over adjacent vertices, but skip the vertex we arrived + # here from the first time it is encountered. + skip = True + for neighbor, edge_value in self.adjacent[vertex]: + if skip and neighbor == parent: + skip = False + continue + + if visited[neighbor]: + # We visited here before, so the graph is cyclic. + return False + + tovisit.append( (vertex, neighbor) ) + + # Set new vertex's value to the desired edge value, + # minus the value of the vertex we came here from. + self.vertex_values[neighbor] = \ + ( edge_value - self.vertex_values[vertex] ) % self.N + + # check if all vertices have a valid value + for vertex in xrange(self.N): + assert self.vertex_values[vertex] >= 0 + + # We got though, so the graph is acyclic, + # and all values are now assigned. + return True + + +def generate_hash(kdic, Hash): + """ + Return 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. + """ + # N is the number of vertices in the graph G + N = 1 if not kdic else (max(kdic.values()) + 1) + if verbose >= 2: + sys.stderr.write('N = %i\n' % N) + + trail = 0 # Number of trial graphs so far + while True: + if (trail % trails) == 0: # trails failures, increase N slightly + if trail > 0: + N = max(N+1, int(1.05*N)) + if verbose: + sys.stderr.write('\n') + sys.stderr.write('Generating graphs N = %i ' % N) + trail += 1 + + if verbose: + sys.stderr.write('.') + sys.stderr.flush() + + G = Graph(N) # Create graph with N vertices + f1 = Hash(N) # Create 2 random hash functions + f2 = Hash(N) + + # Connect vertices given by the values of the two hash functions + # for each key. Associate the desired hash value with each edge. + for key, hashval in kdic.iteritems(): + G.connect(f1(key), f2(key), hashval) + + # Try to assign the vertex values. This will fail when the graph + # is cyclic. But when the graph is acyclic it will succeed and we + # break out, because we're done. + if G.assign_vertex_values(): + break + + if verbose: + sys.stderr.write('\nAcyclic graph found after %i trails.\n' % trail) + + if verbose >= 2: + sys.stderr.write('N = %i\n' % N) + if verbose: + sys.stderr.write('Checking generated hash function... ') + + # Sanity check the result by actually verifying that all the keys + # hash to the right value. + for key, hashval in kdic.iteritems(): + assert hashval == ( G.vertex_values[f1(key)] + + G.vertex_values[f2(key)] ) % N + + if verbose: + sys.stderr.write('OK\n') + + return f1, f2, G.vertex_values + + +class Hash1: + """ + Random hash function generator. + For simplicity and speed, this doesn't implement any byte-level hashing + scheme. Instead, a random string is generated and prefixing to str(key), + and then Python's hashing function is used. + """ + def __init__(self, N): + self.N = N + self.salt = "".join(random.choice(string.letters + string.digits) + for i in xrange(8)) + + def __call__(self, key): + return hash(self.salt + str(key)) % self.N + + template = """ +def perfect_hash(key): + return (G[ hash('$S1' + str(key)) % $NG ] + + G[ hash('$S2' + str(key)) % $NG ]) % $NG +""" + +class Hash2: + """ + Random hash function generator. + Simple byte level hashing, each byte is multiplied in sequence to a table + containing random numbers modulo N, and then these products are summed up. + The table with random numbers is dynamically expanded whenever + a key longer than the current table size is encountered. + """ + def __init__(self, N): + self.N = N + self.salt = [] + + def __call__(self, key): + skey = key + while len(self.salt) < len(skey): # add more salt if necessary + self.salt.append(random.randint(0, self.N-1)) + + return sum(self.salt[i] * ord(c) + for i, c in enumerate(skey)) % self.N + + template = """ +S1 = [$S1] +S2 = [$S2] + +def hash_f(key, T): + return sum(T[i % $NS] * ord(c) for i, c in enumerate(str(key))) % $NG + +def perfect_hash(key): + return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % $NG +""" + + +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. + + >>> d = PerfHash({'foo':(429, 'bar'), 42:True, False:'baz'}) + >>> d['foo'], d[42], d[False] + ((429, 'bar'), True, 'baz') + >>> d[False] = (1, 2) + >>> d[False] + (1, 2) + >>> d.has_key('foo') + True + >>> d.has_key(True) + False + """ + def __init__(self, dic): + self.klst = [] + self.objs = [] + kdic = {} + for hashval, (key, obj) in enumerate(dic.iteritems()): + self.klst.append(key) + self.objs.append(obj) + kdic[key] = hashval + + self.N = len(dic) + self.f1, self.f2, self.G = generate_hash(kdic, Hash1) + + def __setitem__(self, newkey, newobj): + dic = {} + for key in self.klst: + dic[key] = self[key] + dic[newkey] = newobj + self.__init__(dic) + + def hashval(self, key): + return ( self.G[self.f1(key)] + self.G[self.f2(key)] ) % len(self.G) + + def __getitem__(self, key): + h = self.hashval(key) + if h < self.N and key == self.klst[h]: + return self.objs[h] + else: + raise IndexError + + def has_key(self, key): + h = self.hashval(key) + return h < self.N and key == self.klst[h] + + +class Format: + """ + >>> class o: + ... pass + >>> o.delimiter = ': ' + >>> o.width = 75 + >>> o.indent = 4 + >>> x = Format( o ) + >>> x( range(10) ) + '0: 1: 2: 3: 4: 5: 6: 7: 8: 9' + >>> o.delimiter = '; ' + >>> x = Format( o ) + >>> x( range(5) ) + '0; 1; 2; 3; 4' + >>> o.delimiter = ' ' + >>> x = Format( o ) + >>> x( range(5), quote = True ) + '"0" "1" "2" "3" "4"' + >>> x(42) + '42' + >>> x('Hello') + 'Hello' + """ + def __init__(self, options): + names = ['width', 'indent', 'delimiter'] + + for name in names: + setattr(self, name, getattr(options, name)) + + if verbose >=2: + sys.stderr.write("Format options:\n") + for name in names: + sys.stderr.write(' %s: %r\n' % (name, getattr(self, name))) + + def __call__(self, data, quote = False): + if type(data) != type([]): + return str(data) + + lendel = len(self.delimiter) + aux = StringIO.StringIO() + pos = 20 + for i, elt in enumerate(data): + last = bool(i == len(data)-1) + + s = ('"%s"' if quote else '%s') % elt + + if pos + len(s) + lendel > self.width: + aux.write('\n' + (self.indent * ' ')) + pos = self.indent + + aux.write(s) + pos += len(s) + if not last: + aux.write(self.delimiter) + pos += lendel + + return aux.getvalue() + + +def keyDict(keys_hashes): + """ + Checks a list with (key, hashvalue) tupels and returns dictionary. + + >>> d = keyDict([(1, 2), (3, 4), (5, 6)]) + >>> d[3] + 4 + """ + K = len(keys_hashes) # number of keys + if verbose >= 2: + sys.stderr.write('K = %i\n' % K) + + kdic = dict(keys_hashes) + if len(kdic) < K: + sys.stderr.write('Warning: Input contains duplicate keys\n') + + if len(set(kdic.values())) < K: + sys.stderr.write('Warning: Input contains duplicate hash values\n') + + return kdic + + + +def generate_code(keys_hashes, template, Hash, options, extra_subs): + """ + Takes a list of key value pairs and inserts the generated parameter + lists into the 'template' strinng. 'Hash' is the random hash function + generator, and the optional keywords are formating options. + The return value is the substituted code template. + """ + f1, f2, G = generate_hash(keyDict(keys_hashes), Hash) + + assert f1.N == f2.N == len(G) + assert len(f1.salt) == len(f2.salt) + + fmt = Format(options) + + return string.Template(template).substitute( + NS = len(f1.salt), + S1 = fmt(f1.salt), + S2 = fmt(f2.salt), + NG = len(G), + G = fmt(G), + NK = len(keys_hashes), + K = fmt([key for key, hashval in keys_hashes], quote = True), + H = fmt([hashval for key, hashval in keys_hashes]), + **extra_subs) + + + +def read_table(filename, options): + """ + Reads keys and desired hash value pairs from a file. If no column + for the hash value is specified, a sequence of hash values is generated, + from 0 to N-1, where N is the number of rows found in the file. + """ + if verbose >= 2: + sys.stderr.write("Reading table from file `%s' to extract keys.\n" % + filename) + try: + f = file(filename) + except IOError : + exit("Error: Could not open `%s' for reading." % filename) + + keys_hashes = [] + hashval = -1 + + if verbose >= 2: + sys.stderr.write("Reader options:\n") + for name in ['comment', 'splitby', 'keycol', 'hashcol']: + sys.stderr.write(' %s: %r\n' % + (name, getattr(options, name))) + + for n, line in enumerate(f): + line = line.strip() + if not line or line.startswith(options.comment): + continue + + if line.count(options.comment): # strip content after comment + line = line.split(options.comment)[0].strip() + + row = [col.strip() for col in line.split(options.splitby)] + + try: + key = row[options.keycol-1] + except IndexError : + exit("%s:%i: Error: Cannot read key, not enough columns." % + (filename, n+1)) + + if options.hashcol: + try: + val = row[options.hashcol-1] + except IndexError : + exit("%s:%i: Error: Cannot read hash value, not enough columns." + % (filename, n+1)) + try: + hashval = int(val) + except ValueError : + exit("%s:%i: Error: Cannot convert `%s' to int." % + (filename, n+1, row[options.hashcol-1])) + else: + hashval += 1 + + keys_hashes.append( (key, hashval) ) + + f.close() + + if not keys_hashes: + exit("Error: no keys found in file `%s'." % filename) + + return keys_hashes + + + +def print_keys_hashes(keys_hashes): + fmt = '%-20s %10s' + head = fmt % ('Key', 'Hash value') + sys.stderr.write('\n' + head + '\n') + sys.stderr.write(len(head)*'-' + '\n') + for tup in keys_hashes: + sys.stderr.write(fmt % tup + '\n') + sys.stderr.write('\n') + +def read_template(filename): + if verbose >= 2: + sys.stderr.write("Reading template from file `%s'.\n" % filename) + + try: + f = file(filename) + except IOError : + fatal_error("Error: Could not open `%s' for reading." % filename) + + return f.read() + + +def builtin_template(Hash): + return """\ +# ======================================================================= +# ================= Python code for perfect hash function =============== +# ======================================================================= + +G = [$G] +""" + Hash.template + """ +# ============================ Sanity check ============================= + +K = [$K] +H = [$H] + +assert len(K) == len(H) == $NK + +for k, h in zip(K, H): + assert perfect_hash(k) == h +""" + + +def print_code(code, name, width = 78): + def center(s): + v = (width - len(s))/2 + return '='*v + s + '='*v + sys.stderr.write(center(' BEGIN %s ' % name) + '\n') + sys.stderr.write(code + '\n') + sys.stderr.write(center(' END %s ' % name) + '\n') + + +def self_test(options): + import doctest + global verbose + print 'Starting self tests ...' + + def random_word(): + return ''.join(random.choice(string.letters + string.digits) + for i in xrange(random.randint(1, 20))) + + def flush_dot(): + sys.stdout.write('.') + sys.stdout.flush() + + def run(K, Hash): + flush_dot() + + keys = [chr(65+i) for i in xrange(K)] + hashes = range(K) + + random.shuffle(keys) + random.shuffle(hashes) + + code = generate_code(zip(keys, hashes), + builtin_template(Hash), + Hash, + options) + exec(code) in {} + + verbose = False + for Hash in [Hash1, Hash2]: + for K in xrange(0, 27): + run(K, Hash) + print + + verbose = options.verbose + N = 250 + for Hash in [Hash1, Hash2]: + if verbose: + print 'Generating approximately %i key/hash pairs ...' % N + kh = {} + for i in xrange(N): + kh[random_word()] = i + + if verbose: + print 'Generating code for %i key/hash pairs ...' % len(kh) + code = generate_code(kh.items(), + builtin_template(Hash), + Hash, + options) + if verbose: + print 'Executing code ...' + flush_dot() + exec(code) in {} + + flush_dot() + d = PerfHash(dict([(100-i, i*i) for i in xrange(500)])) + for i in xrange(500): + assert d[100-i] == i*i + flush_dot() + d[None] = True + assert d[None] == True + + if verbose: + print 'Running doctest ...' + + verbose = False + failure_count, test_count = doctest.testmod(report = True, verbose = False) + print + if failure_count: + sys.stderr.write('FAILED\n') + sys.exit(2) + else: + sys.stderr.write('%i tests passed.\n' % test_count) + sys.stderr.write('OK\n') + sys.exit(0) + + +if __name__ == '__main__': + from optparse import OptionParser + + usage = "usage: %prog [options] KEYS_FILE [TMPL_FILE]" + + description = """\ +Generates code for perfect hash functions from +a file with keywords and a code template. +If no template file is provided, a small built-in Python template +is processed and the output code is written to stdout. +""" + + parser = OptionParser(usage = usage, + description = description, + prog = sys.argv[0], + version = "%prog 0.1") + + parser.add_option("--delimiter", + action = "store", + default = ", ", + help = "Delimiter for list items used in output, " + "the default delimiter is '%default'", + metavar = "STR") + + parser.add_option("--indent", + action = "store", + default = 2, + type = "int", + help = "Make INT spaces at the beginning of a " + "new line when generated list is wrapped. " + "Default is %default", + metavar = "INT") + + parser.add_option("--width", + action = "store", + default = 76, + type = "int", + help = "Maximal width of generated list when " + "wrapped. Default width is %default", + metavar = "INT") + + parser.add_option("--comment", + action = "store", + default = "#", + help = "STR is the character, or sequence of " + "characters, which marks the beginning " + "of a comment (which runs till " + "the end of the line), in the input " + "KEYS_FILE. " + "Default is '%default'", + metavar = "STR") + + parser.add_option("--splitby", + action = "store", + default = ",", + help = "STR is the character by which the columns " + "in the input KEYS_FILE are split. " + "Default is '%default'", + metavar = "STR") + + parser.add_option("--keycol", + action = "store", + default = 1, + type = "int", + help = "Specifies the column INT in the input " + "KEYS_FILE which contains the keys. " + "Default is %default, i.e. the first column.", + metavar = "INT") + + parser.add_option("--hashcol", + action = "store", + default = 0, + type = "int", + help = "Specifies the column INT in the input " + "KEYS_FILE which contains the desired " + "hash values. " + "By default the hash values are given by the " + "sequence 0..N-1.", + metavar = "INT") + + parser.add_option("--trails", + action = "store", + default = 5, + type = "int", + help = "Specifies the number of trails before " + "N is increased. A small INT will give " + "compute faster, but the array G will be " + "large. A large INT will take longer to " + "compute but G will be smaller. " + "Default is %default", + metavar = "INT") + + parser.add_option("--hft", + action = "store", + default = 2, + type = "int", + help = "Hash function type INT (see documentation), " + "The default is %default", + metavar = "INT") + + parser.add_option("-e", "--execute", + action = "store_true", + help = "Execute the generated code within " + "the Python interpreter.") + + parser.add_option("-o", "--output", + action = "store", + help = "Specify output FILE explicitly. " + "`-o std' means standard output. " + "`-o no' means no output. " + "By default, the file name is obtained " + "from the name of the template file by " + "substituting `tmpl' to `code'.", + metavar = "FILE") + + parser.add_option("--test", + action = "store_true", + help = "Perform self test") + + parser.add_option("-v", "--verbose", + action = "count", + help = "Be verbose, " + "use -vv to be even more verbose") + + options, args = parser.parse_args() + print type(options), '\n', repr(options) + + if options.trails > 0: + trails = options.trails + else: + parser.error("trails before increasing N has to be larger than zero") + + verbose = options.verbose + + if options.test: + self_test(options) + + if len(args) not in (1, 2): + parser.error("incorrect number of arguments") + + if len(args) == 2 and not args[1].count('tmpl'): + parser.error("template filename does not contain 'tmpl'") + + if options.hft == 1: + Hash = Hash1 + elif options.hft == 2: + Hash = Hash2 + else: + parser.error("Hash function %i not implemented.") + + # --------------------- end parsing and checking -------------- + + # ---------------- keys_file + + keys_file = args[0] + + if verbose: + sys.stderr.write("keys_file = %r\n" % keys_file) + + # ---------------- keys_hashes + + keys_hashes = read_table(keys_file, options) + + if verbose >= 3: + print_keys_hashes(keys_hashes) + + # ---------------- tmpl_file + + if len(args) == 2: + tmpl_file = args[1] + else: + tmpl_file = None + + if verbose: + sys.stderr.write("tmpl_file = %r\n" % tmpl_file) + + # ---------------- template + + if tmpl_file: + template = read_template(tmpl_file) + else: + template = builtin_template(Hash) + + if verbose >= 3: + print_code(template, 'TEMPLATE') + + # ---------------- outname + + if options.output: + outname = options.output + + else: + if tmpl_file: + if tmpl_file.count('tmpl'): + outname = tmpl_file.replace('tmpl', 'code') + else: + exit("Hmm, template filename does not contain 'tmpl'") + else: + outname = 'std' + + if verbose: + sys.stderr.write("outname = %r\n" % outname) + + # ---------------- outstream + + if outname == 'std': + outstream = sys.stdout + + elif outname == 'no': + outstream = None + + else: + try: + outstream = open(outname, 'w') + except IOError : + exit("Error: Could not open `%s' for writing." % outname) + + # ---------------- generated code + + code = generate_code(keys_hashes, template, Hash, options) + if verbose >= 3: + print_code(code, 'GENERATED CODE') + + # ---------------- execute code + + if options.execute or template == builtin_template(Hash): + if verbose: + sys.stderr.write('Executing code...\n') + exec(code) + + # ---------------- write code to output stream + + if outstream: + outstream.write(code) + if not outname == 'std': + outstream.close() diff --git a/components/rtgui/utils/perfect_hash/run b/components/rtgui/utils/perfect_hash/run new file mode 100644 index 0000000000..c7fe1f22e2 --- /dev/null +++ b/components/rtgui/utils/perfect_hash/run @@ -0,0 +1,32 @@ +#!/bin/bash + +function showpwd () +{ + echo '=============' `pwd` +} + +# perform programs self test +showpwd +./perfect_hash.py --test || exit 1 + +# update documentation +for folder in doc +do + cd $folder + showpwd + make + cd .. +done + +# run examples +for folder in example* graph +do + cd $folder + showpwd + make || exit 1 + make test || exit 1 + make clean + cd .. +done + +rm perfect_hash.pyc |