sync with rtgui-0.6

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