diff options
| author | Bernard Xiong <[email protected]> | 2013-02-21 13:11:10 +0800 |
|---|---|---|
| committer | Bernard Xiong <[email protected]> | 2013-02-21 13:11:10 +0800 |
| commit | 385f682d7bfce81ba281faaffb0a250ab94985b8 (patch) | |
| tree | 94fca413db98390d21dc18938067a7a90e470a6f /components/rtgui/utils | |
| parent | c4bd0023f8da136c5788f47f9a0170a77f627be9 (diff) | |
remove RT-Thread GUI from RT-Thread temporary
Diffstat (limited to 'components/rtgui/utils')
41 files changed, 0 insertions, 3062 deletions
diff --git a/components/rtgui/utils/perfect_hash/README b/components/rtgui/utils/perfect_hash/README deleted file mode 100644 index fa798c1d3c..0000000000 --- a/components/rtgui/utils/perfect_hash/README +++ /dev/null @@ -1,49 +0,0 @@ - -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 deleted file mode 100644 index e69de29bb2..0000000000 --- a/components/rtgui/utils/perfect_hash/__init__.py +++ /dev/null diff --git a/components/rtgui/utils/perfect_hash/animals.txt b/components/rtgui/utils/perfect_hash/animals.txt deleted file mode 100644 index ac29563736..0000000000 --- a/components/rtgui/utils/perfect_hash/animals.txt +++ /dev/null @@ -1,7 +0,0 @@ -# '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 deleted file mode 100644 index 6a456a5b97..0000000000 --- a/components/rtgui/utils/perfect_hash/doc/Makefile +++ /dev/null @@ -1,22 +0,0 @@ - - -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 differdeleted file mode 100644 index 08825a1315..0000000000 --- a/components/rtgui/utils/perfect_hash/doc/czech92optimal.pdf +++ /dev/null diff --git a/components/rtgui/utils/perfect_hash/doc/doc.html b/components/rtgui/utils/perfect_hash/doc/doc.html deleted file mode 100644 index 3abb399f32..0000000000 --- a/components/rtgui/utils/perfect_hash/doc/doc.html +++ /dev/null @@ -1,136 +0,0 @@ - - -<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 deleted file mode 100644 index 1bcce9a961..0000000000 --- a/components/rtgui/utils/perfect_hash/doc/doc.in +++ /dev/null @@ -1,130 +0,0 @@ - -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 deleted file mode 100644 index f28dda0ed2..0000000000 --- a/components/rtgui/utils/perfect_hash/doc/doc.txt +++ /dev/null @@ -1,141 +0,0 @@ - -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 deleted file mode 100644 index ef304ed673..0000000000 --- a/components/rtgui/utils/perfect_hash/doc/mktable.py +++ /dev/null @@ -1,22 +0,0 @@ -#!/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 deleted file mode 100644 index b853492659..0000000000 --- a/components/rtgui/utils/perfect_hash/doc/parameters.txt +++ /dev/null @@ -1,11 +0,0 @@ - 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 deleted file mode 100644 index de525f5d5d..0000000000 --- a/components/rtgui/utils/perfect_hash/example-C++/Makefile +++ /dev/null @@ -1,31 +0,0 @@ - -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 deleted file mode 100644 index 9d724a7872..0000000000 --- a/components/rtgui/utils/perfect_hash/example-C++/main.cc +++ /dev/null @@ -1,24 +0,0 @@ - -#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 deleted file mode 100644 index 646c0787be..0000000000 --- a/components/rtgui/utils/perfect_hash/example-C++/mk_header.py +++ /dev/null @@ -1,10 +0,0 @@ -#!/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 deleted file mode 100644 index 964d8bf8a5..0000000000 --- a/components/rtgui/utils/perfect_hash/example-C++/states-code.hh +++ /dev/null @@ -1,19 +0,0 @@ - - -#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 deleted file mode 100644 index ab94be31f6..0000000000 --- a/components/rtgui/utils/perfect_hash/example-C++/states-tmpl.cc +++ /dev/null @@ -1,55 +0,0 @@ - -#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 deleted file mode 100644 index 5538309450..0000000000 --- a/components/rtgui/utils/perfect_hash/example-C++/states.dat +++ /dev/null @@ -1,52 +0,0 @@ -# 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 deleted file mode 100644 index 662ff78442..0000000000 --- a/components/rtgui/utils/perfect_hash/example-PyModule/Makefile +++ /dev/null @@ -1,26 +0,0 @@ - - -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 deleted file mode 100644 index b77e6320b3..0000000000 --- a/components/rtgui/utils/perfect_hash/example-PyModule/stations-tmpl.h +++ /dev/null @@ -1,12 +0,0 @@ - -#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 deleted file mode 100644 index 5358120c34..0000000000 --- a/components/rtgui/utils/perfect_hash/example-PyModule/stations.dat +++ /dev/null @@ -1,500 +0,0 @@ -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 deleted file mode 100644 index bf14e1bbee..0000000000 --- a/components/rtgui/utils/perfect_hash/example-PyModule/stationsmodule.c +++ /dev/null @@ -1,69 +0,0 @@ - -#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 deleted file mode 100644 index 02c06b6926..0000000000 --- a/components/rtgui/utils/perfect_hash/example-PyModule/test.py +++ /dev/null @@ -1,28 +0,0 @@ -#!/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 deleted file mode 100644 index f2927719b4..0000000000 --- a/components/rtgui/utils/perfect_hash/example-Python/Graph.py +++ /dev/null @@ -1,40 +0,0 @@ -#!/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 deleted file mode 100644 index 4f6dd13850..0000000000 --- a/components/rtgui/utils/perfect_hash/example-Python/Makefile +++ /dev/null @@ -1,15 +0,0 @@ - - -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 deleted file mode 100644 index 49131c2b63..0000000000 --- a/components/rtgui/utils/perfect_hash/example-Python/PerfHash.py +++ /dev/null @@ -1,40 +0,0 @@ -#!/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 deleted file mode 100644 index dfe9f92186..0000000000 --- a/components/rtgui/utils/perfect_hash/example-Python/generate_hash.py +++ /dev/null @@ -1,38 +0,0 @@ -#!/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 deleted file mode 100644 index 59b7ef0d67..0000000000 --- a/components/rtgui/utils/perfect_hash/example1-C/Makefile +++ /dev/null @@ -1,31 +0,0 @@ - -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 deleted file mode 100644 index 0d36bcea45..0000000000 --- a/components/rtgui/utils/perfect_hash/example1-C/main.c +++ /dev/null @@ -1,33 +0,0 @@ - -#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 deleted file mode 100644 index 646c0787be..0000000000 --- a/components/rtgui/utils/perfect_hash/example1-C/mk_header.py +++ /dev/null @@ -1,10 +0,0 @@ -#!/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 deleted file mode 100644 index 5717b92d32..0000000000 --- a/components/rtgui/utils/perfect_hash/example1-C/states-code.h +++ /dev/null @@ -1,6 +0,0 @@ - - -/* 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 deleted file mode 100644 index 001ca6e5ce..0000000000 --- a/components/rtgui/utils/perfect_hash/example1-C/states-tmpl.c +++ /dev/null @@ -1,42 +0,0 @@ - -#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 deleted file mode 100644 index 5538309450..0000000000 --- a/components/rtgui/utils/perfect_hash/example1-C/states.dat +++ /dev/null @@ -1,52 +0,0 @@ -# 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 deleted file mode 100644 index 865e8cf7eb..0000000000 --- a/components/rtgui/utils/perfect_hash/example2-C/Makefile +++ /dev/null @@ -1,22 +0,0 @@ - -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 deleted file mode 100644 index 550bdb089d..0000000000 --- a/components/rtgui/utils/perfect_hash/example2-C/keys.tmpl.h +++ /dev/null @@ -1,13 +0,0 @@ - -#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 deleted file mode 100644 index c19db892b8..0000000000 --- a/components/rtgui/utils/perfect_hash/example2-C/main.c +++ /dev/null @@ -1,51 +0,0 @@ - -#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 deleted file mode 100644 index 81f964e9ff..0000000000 --- a/components/rtgui/utils/perfect_hash/example2-C/mk_rnd_keys.py +++ /dev/null @@ -1,17 +0,0 @@ -#!/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 deleted file mode 100644 index dc84f85fdb..0000000000 --- a/components/rtgui/utils/perfect_hash/graph/Makefile +++ /dev/null @@ -1,23 +0,0 @@ - - - -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 deleted file mode 100644 index 86f58cdb38..0000000000 --- a/components/rtgui/utils/perfect_hash/graph/example-pipeline +++ /dev/null @@ -1,4 +0,0 @@ -#!/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 deleted file mode 100644 index 920c70386a..0000000000 --- a/components/rtgui/utils/perfect_hash/graph/py2dot +++ /dev/null @@ -1,216 +0,0 @@ -#!/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 deleted file mode 100644 index e981877634..0000000000 --- a/components/rtgui/utils/perfect_hash/perfect_hash.py +++ /dev/null @@ -1,870 +0,0 @@ -#!/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 deleted file mode 100644 index c7fe1f22e2..0000000000 --- a/components/rtgui/utils/perfect_hash/run +++ /dev/null @@ -1,32 +0,0 @@ -#!/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 diff --git a/components/rtgui/utils/stract_cjk.py b/components/rtgui/utils/stract_cjk.py deleted file mode 100644 index afea09897c..0000000000 --- a/components/rtgui/utils/stract_cjk.py +++ /dev/null @@ -1,163 +0,0 @@ -#encoding: utf-8 -from perfect_hash import perfect_hash - -import re, string, os, random - -cur_dir = os.path.abspath(os.path.dirname(__file__)) - -unicode_chinese_re = u'[\u2E80-\u2EFF\u2F00-\u2FDF\u3000-\u303F\u31C0-\u31EF\u3200-\u32FF\u3300-\u33FF\u3400-\u4DBF\u4DC0-\u4DFF\u4E00-\u9FBF\uF900-\uFAFF\uFE30-\uFE4F\uFF00-\uFFEF]' -match_re = re.compile(unicode_chinese_re) - -def _get_font_lib(f): - reading_data = False - data = [] - for i in f.readlines(): - if i.strip() == 'FONT_BMP_DATA_BEGIN': - reading_data = True - continue - if i.strip() == 'FONT_BMP_DATA_END': - break - if reading_data: - line = [k for k in i.strip().split(',') if k] - data.extend([int(k, 16) for k in line]) - return data - -class font_lib(object): - def __init__(self, f, width, height, encoding): - self.width = width - self.height = height - self._lib = _get_font_lib(f) - # byte per charactor - self._bpc = (width+7)//8*height - self.encoding = encoding - self._finished_push = False - - self.char_dict = {} - - def get_char_data(self, char): - #char_gb = char.encode(self.encoding) - - # copied from font_hz_bmp.c - sec, idx = [ord(i) - 0xA0 for i in char] - #print 'sec %d, idx %d for' % (sec, idx), char - start = (94 * (sec-1) + (idx-1)) * self._bpc - return self._lib[start:start+self._bpc] - - def push_char(self, c): - self.char_dict[c] = self.char_dict.get(c, 0) + 1 - - def push_file(self, f): - try: - for i in f: - t = re.findall(match_re, unicode(i.decode(self.encoding))) - if t: - for c in t: - self.push_char(c.encode(self.encoding)) - except UnicodeDecodeError as e: - try: - print 'error in decoding %s' % f.name - except: - print 'error in decoding string %s' % f - # re-raise the exception and terminate the building process - raise - - def _finish_push(self): - if self._finished_push: - return - - self._char_li = zip(self.char_dict.keys(), self.char_dict.values()) - self._char_li.sort(key=lambda x:x[1], reverse=True) - self._finished_push = True - - #for i in self._char_li: - #print i[0], i[1] - - def get_hash_map(self): - self._finish_push() - li = [] - for i, k in enumerate(self._char_li): - li.append((k[0], i)) - return li - - def get_new_font_lib(self): - self._finish_push() - dat = [] - for c, f in self._char_li: - dat.extend(self.get_char_data(c)) - return dat - - def finish(self): - return self.get_hash_map(), self.get_new_font_lib() - -class mph_options(object): - 'mock object for options' - def __init__(self, verbose=4, delimiter=', ', indent=4, width=80): - self.verbose = verbose - self.delimiter = delimiter - self.indent = indent - self.width = width - -def gen_char_mph(font_lib): - template = open(os.path.join(cur_dir, '..', 'common', 'font_mph-tmpl.c'), 'r').read() - opt = mph_options() - hmap, flib = font_lib.finish() - #print 'compact font lib: %d chars included.' % len(hmap) - #for i in hmap: - #print i[0], repr(i[0]), i[1] - code = perfect_hash.generate_code(hmap, template, perfect_hash.Hash2, opt, - extra_subs={ - 'width':str(font_lib.width), - 'height':str(font_lib.height), - 'font_data':', '.join([hex(i) for i in flib])}) - - return code - -# {name:[file_name, height, width, encoding, instance]} -_font_map = {'hz16':{'fname':'common/hz16font.c', - 'height':16, - 'width':16, - 'encoding':'GB2312', - 'flib':None}, - 'hz12':{'fname':'common/hz12font.c', - 'height':12, - 'width':12, - 'encoding':'GB2312', - 'flib':None} - } - -def get_font_lib(name): - if name not in _font_map.keys(): - return None - - if _font_map[name]['flib'] is None: - _font_map[name]['flib'] = font_lib(open( - os.path.join(cur_dir, '..', _font_map[name]['fname']), 'r'), - _font_map[name]['height'], - _font_map[name]['width'], - _font_map[name]['encoding']) - return _font_map[name]['flib'] - -def gen_cmp_font_file(): - for i in _font_map: - fl = _font_map[i]['flib'] - if fl is not None: - code = gen_char_mph(fl) - with open(os.path.join(cur_dir, '..', 'common', 'font_cmp_%s.c' % i), 'w') as f: - f.write(code) - -if __name__ == '__main__': - import sys - - lib = get_font_lib('hz16') - libn = get_font_lib('hz16') - assert(lib is libn) - - lib.push_file(open(sys.argv[1], 'rb')) - - hmap, flib = lib.finish() - for i in hmap: - print i[0], i[1] - - assert(len(flib) == 32 * len(hmap)) - - print gen_char_mph(lib) |