diff options
Diffstat (limited to 'components/rtgui/utils/perfect_hash/example-C++')
6 files changed, 191 insertions, 0 deletions
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 |