added exams and timings for exhashmap<>
authorChristian Bauer <Christian.Bauer@uni-mainz.de>
Wed, 20 Aug 2003 22:01:35 +0000 (22:01 +0000)
committerChristian Bauer <Christian.Bauer@uni-mainz.de>
Wed, 20 Aug 2003 22:01:35 +0000 (22:01 +0000)
check/Makefile.am
check/exam_hashmap.cpp [new file with mode: 0644]
check/exams.cpp
check/exams.h
check/exams.ref
check/time_hashmap.cpp [new file with mode: 0644]
check/times.cpp
check/times.h
check/times.ref

index 5e3d2d5..48e7a99 100644 (file)
@@ -9,19 +9,19 @@ checks_LDADD = ../ginac/libginac.la
 
 exams_SOURCES = exam_paranoia.cpp exam_numeric.cpp exam_powerlaws.cpp \
   exam_inifcns.cpp exam_inifcns_nstdsums.cpp exam_inifcns_nstdsums.h \
-  exam_differentiation.cpp \
-  exam_polygcd.cpp exam_normalization.cpp exam_pseries.cpp exam_matrices.cpp \
-  exam_lsolve.cpp exam_indexed.cpp exam_color.cpp exam_clifford.cpp \
-  exam_archive.cpp exam_structure.cpp exam_misc.cpp exams.cpp exams.h
+  exam_differentiation.cpp exam_polygcd.cpp exam_normalization.cpp \
+  exam_pseries.cpp exam_matrices.cpp exam_lsolve.cpp exam_indexed.cpp \
+  exam_color.cpp exam_clifford.cpp exam_archive.cpp exam_structure.cpp \
+  exam_hashmap.cpp exam_misc.cpp exams.cpp exams.h
 exams_LDADD = ../ginac/libginac.la
 
 times_SOURCES = time_dennyfliegner.cpp time_gammaseries.cpp \
-  time_vandermonde.cpp time_toeplitz.cpp time_lw_A.cpp time_lw_B.cpp \
-  time_lw_C.cpp time_lw_D.cpp time_lw_E.cpp time_lw_F.cpp time_lw_G.cpp \
-  time_lw_H.cpp time_lw_IJKL.cpp time_lw_M1.cpp time_lw_M2.cpp time_lw_N.cpp \
-  time_lw_O.cpp time_lw_P.cpp time_lw_Pprime.cpp time_lw_Q.cpp \
-  time_lw_Qprime.cpp time_antipode.cpp time_fateman_expand.cpp \
-  timer.cpp timer.h times.cpp times.h
+  time_vandermonde.cpp time_toeplitz.cpp time_hashmap.cpp time_lw_A.cpp \
+  time_lw_B.cpp time_lw_C.cpp time_lw_D.cpp time_lw_E.cpp time_lw_F.cpp \
+  time_lw_G.cpp time_lw_H.cpp time_lw_IJKL.cpp time_lw_M1.cpp time_lw_M2.cpp \
+  time_lw_N.cpp time_lw_O.cpp time_lw_P.cpp time_lw_Pprime.cpp time_lw_Q.cpp \
+  time_lw_Qprime.cpp time_antipode.cpp time_fateman_expand.cpp timer.cpp \
+  timer.h times.cpp times.h
 times_LDADD = ../ginac/libginac.la
 
 INCLUDES = -I$(srcdir)/../ginac -I../ginac
diff --git a/check/exam_hashmap.cpp b/check/exam_hashmap.cpp
new file mode 100644 (file)
index 0000000..b360476
--- /dev/null
@@ -0,0 +1,293 @@
+/** @file exam_hashmap.cpp
+ *
+ *  Regression tests for the exhashmap<> container. */
+
+/*
+ *  GiNaC Copyright (C) 1999-2003 Johannes Gutenberg University Mainz, Germany
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include "exams.h"
+
+unsigned exam_hashmap()
+{
+       unsigned result = 0;
+       unsigned N = 100;
+
+       cout << "examining hash maps" << flush;
+       clog << "----------hash maps:" << endl;
+
+       // Create empty container
+       exhashmap<unsigned> M1;
+       if (M1.size() != 0) {
+               clog << "Newly constructed container has size() != 0" << endl;
+               ++result;
+       }
+       if (!M1.empty()) {
+               clog << "Newly constructed container is not empty" << endl;
+               ++result;
+       }
+
+       cout << '.' << flush;
+
+       // Insert elements
+       for (unsigned i = 0; i < N; ++i)
+               M1.insert(make_pair(i, i));
+
+       if (M1.size() != N) {
+               clog << "After " << N << " insertions, size() returns " << M1.size() << " instead of " << N << endl;
+               ++result;
+       }
+
+       for (unsigned i = 0; i < N; ++i) {
+               if (M1[i] != i) {
+                       clog << "Lookup of key " << i << " in M1 didn't return correct value" << endl;
+                       ++result;
+                       break;
+               }
+       }
+
+       if (M1.size() != N) {
+               clog << "After " << N << " lookups, size() returns " << M1.size() << " instead of " << N << endl;
+               ++result;
+       }
+
+       cout << '.' << flush;
+
+       // Test constructor from two iterators and operator==
+       exhashmap<unsigned> M2(M1.begin(), M1.end());
+       if (M2.size() != M1.size()) {
+               clog << "Constructor from two iterators: size of destination container (" << M2.size() << ") not equal to size of source (" << M1.size() << ")" << endl;
+               ++result;
+       }
+
+       for (unsigned i = 0; i < N; ++i) {
+               if (M2[i] != i) {
+                       clog << "Lookup of key " << i << " in M2 didn't return correct value" << endl;
+                       ++result;
+                       break;
+               }
+       }
+
+       if (M2 != M1) {
+               clog << "Copied container not equal to source" << endl;
+               ++result;
+       }
+
+       cout << '.' << flush;
+
+       // Test assignment operator
+       exhashmap<unsigned> M3;
+       M3 = M1;
+       if (M3.size() != N) {
+               clog << "Assignment operator: size of assigned container not equal to size of original" << endl;
+               ++result;
+       }
+
+       for (unsigned i = 0; i < N; ++i) {
+               if (M3[i] != i) {
+                       clog << "Lookup of key " << i << " in M3 didn't return correct value" << endl;
+                       ++result;
+                       break;
+               }
+       }
+
+       cout << '.' << flush;
+
+       // Test insert(it, it)
+       exhashmap<unsigned> M4;
+       M4.insert(M1.begin(), M1.end());
+
+       if (M4.size() != M1.size()) {
+               clog << "insert(it, it): size of destination container not equal to size of source" << endl;
+               ++result;
+       }
+
+       for (unsigned i = 0; i < N; ++i) {
+               if (M4[i] != i) {
+                       clog << "Lookup of key " << i << " in M4 didn't return correct value" << endl;
+                       ++result;
+                       break;
+               }
+       }
+
+       cout << '.' << flush;
+
+       // Test insert()/find()
+       symbol x("x"), y("y");
+       exhashmap<unsigned> M5;
+       M5.insert(make_pair(x-2, 1));
+       M5.insert(make_pair(sin(x+y), 2));
+       M5.insert(make_pair(Pi, 3));
+       M5.insert(make_pair(0, 4));
+       M5.insert(make_pair(4*pow(x, y), 5));
+       if (M5.size() != 5) {
+               clog << "After 5 insertions, size() returns " << M5.size() << " instead of 5" << endl;
+               ++result;
+       }
+
+       exhashmap<unsigned>::const_iterator cit = M5.find(sin(x+y));
+       if (cit == M5.end()) {
+               clog << "Lookup of sin(x+y) didn't find anything" << endl;
+               ++result;
+       }
+       if (!cit->first.is_equal(sin(x+y))) {
+               clog << "Lookup of sin(x+y) returned an incorrect iterator" << endl;
+               ++result;
+       }
+       if (cit->second != 2) {
+               clog << "Lookup of sin(x+y) returned wrong value" << endl;
+               ++result;
+       }
+
+       cout << '.' << flush;
+
+       // Test re-inserting insert()
+       pair<exhashmap<unsigned>::iterator, bool> pit = M5.insert(make_pair(sin(x+y), 42));
+       if (pit.second) {
+               clog << "Reinsertion of sin(x+y) inserted a new value" << endl;
+               ++result;
+       }
+       if (!pit.first->first.is_equal(sin(x+y))) {
+               clog << "Reinsertion of sin(x+y) returned an incorrect iterator" << endl;
+               ++result;
+       }
+       if (pit.first->second != 2) {
+               clog << "Reinsertion of sin(x+y) changed the value" << endl;
+               ++result;
+       }
+
+       cout << '.' << flush;
+
+       // Test operator[]
+       unsigned v = M5[sin(x+y)];
+       if (M5.size() != 5) {
+               clog << "operator[] with an existing key changed the container size" << endl;
+               ++result;
+       }
+       if (v != 2) {
+               clog << "operator[] with an existing key returned the wrong value" << endl;
+               ++result;
+       }
+
+       v = M5[y+1];
+       if (M5.size() != 6) {
+               clog << "operator[] with a new key didn't insert a new value" << endl;
+               ++result;
+       }
+       if (v != 0) {
+               clog << "operator[] with a new key returned the wrong value" << endl;
+               ++result;
+       }
+
+       cout << '.' << flush;
+
+       // Test erase()
+       exhashmap<unsigned>::iterator it = M5.find(y+1);
+       if (it == M5.end()) {
+               clog << "Key y+1 wasn't found" << endl;
+               ++result;
+       }
+       if (!it->first.is_equal(y+1)) {
+               clog << "find() returned an incorrect iterator" << endl;
+               ++result;
+       }
+       if (it->second != 0) {
+               clog << "find() returned an incorrect value" << endl;
+               +result;
+       }
+
+       M5.erase(it);
+       if (M5.size() != 5) {
+               clog << "erase(it) didn't reduce the size of the container" << endl;
+               ++result;
+       }
+
+       it = M5.find(y+1);
+       if (it != M5.end()) {
+               clog << "Key was still found after erase()" << endl;
+               ++result;
+       }
+
+       exhashmap<unsigned>::size_type n = M5.erase(Pi);
+       if (n != 1) {
+               clog << "erase(Pi) returned " << n << " instead of 1" << endl;
+               ++result;
+       }
+       if (M5.size() != 4) {
+               clog << "erase(Pi) didn't reduce the size of the container" << endl;
+               ++result;
+       }
+
+       n = M5.erase(42);
+       if (n != 0) {
+               clog << "erase(42) returned " << n << " instead of 0" << endl;
+               ++result;
+       }
+       if (M5.size() != 4) {
+               clog << "erase(42) reduced the size of the container" << endl;
+               ++result;
+       }
+
+       cout << '.' << flush;
+
+       // Test swap()
+       exhashmap<unsigned> M6;
+       M6.swap(M1);
+       if (M6.size() != N) {
+               clog << "After swap, size() returns " << M6.size() << " instead of " << N << endl;
+               ++result;
+       }
+       if (M1.size() != 0) {
+               clog << "After swap with empty container, size() returns " << M1.size() << " instead of 0" << endl;
+               ++result;
+       }
+
+       cout << '.' << flush;
+
+       // Test clear()
+       M2.clear();
+       if (M2.size() != 0) {
+               clog << "Size of cleared container is " << M5.size() << " instead of 0" << endl;
+               ++result;
+       }
+
+       cout << '.' << flush;
+
+       // Test count()
+       n = M5.count(Pi);
+       if (n != 0) {
+               clog << "count(Pi) returns " << n << " instead of 0" << endl;
+               ++result;
+       }
+
+       n = M5.count(4*pow(x, y));
+       if (n != 1) {
+               clog << "count(4*x^y) returns " << n << " instead of 1" << endl;
+               ++result;
+       }
+
+       cout << '.' << flush;
+
+       if (!result) {
+               cout << " passed " << endl;
+               clog << "(no output)" << endl;
+       } else {
+               cout << " failed " << endl;
+       }
+
+       return result;
+}
index ed8f814..11c7320 100644 (file)
@@ -52,6 +52,7 @@ try { \
        EXAM(clifford)
        EXAM(archive)
        EXAM(structure)
+       EXAM(hashmap)
        EXAM(misc)
        
        if (result) {
index 635ff0d..9de1238 100644 (file)
@@ -45,6 +45,7 @@ unsigned exam_color();
 unsigned exam_clifford();
 unsigned exam_archive();
 unsigned exam_structure();
+unsigned exam_hashmap();
 unsigned exam_misc();
 
 #endif // ndef EXAMS_H
index e83d409..016a9c2 100644 (file)
@@ -30,5 +30,7 @@
 (no output)
 ----------structure template:
 (no output)
+----------hash maps:
+(no output)
 ----------miscellaneous other things:
 (no output)
diff --git a/check/time_hashmap.cpp b/check/time_hashmap.cpp
new file mode 100644 (file)
index 0000000..a72e468
--- /dev/null
@@ -0,0 +1,110 @@
+/** @file time_hashmap.cpp
+ *
+ *  Timings for exhashmap<> operations. */
+
+/*
+ *  GiNaC Copyright (C) 1999-2003 Johannes Gutenberg University Mainz, Germany
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include "times.h"
+
+template <class T>
+static void run_timing(unsigned size, double &time_insert, double &time_find, double &time_erase)
+{
+       vector<symbol> S;
+       T M;
+       timer t;
+
+       S.reserve(size);
+       for (unsigned i=0; i<size; ++i)
+               S.push_back(symbol());
+
+       t.start();
+       for (unsigned i=0; i<size; ++i)
+               M[S[i]] = S[(i+1)%size];
+       time_insert = t.read();
+
+       t.start();
+       for (unsigned i=0; i<size; ++i) {
+               if (!M[S[i]].is_equal(S[(i+1)%size])) {
+                       clog << "map lookup failed" << endl;
+                       return;
+               }
+       }
+       time_find = t.read();
+
+       t.start();
+       for (unsigned i=0; i<size; ++i) {
+               if (M.erase(S[i]) != 1) {
+                       clog << "erasing element " << S[i] << " failed" << endl;
+                       return;
+               }
+       }
+       if (!M.empty()) {
+               clog << "map not empty (size = " << M.size() << ") after erasing all elements" << endl;
+               return;
+       }
+       time_erase = t.read();
+}
+
+
+unsigned time_hashmap()
+{
+       unsigned result = 0;
+
+       cout << "timing hash map operations" << flush;
+       clog << "-------hash map operations:" << endl;
+
+       unsigned s[] = {10000, 50000, 100000, 500000};
+       vector<unsigned> sizes(s, s+sizeof(s)/sizeof(*s));
+
+       vector<double> times_insert, times_find, times_erase;
+
+       for (vector<unsigned>::const_iterator i = sizes.begin(); i != sizes.end(); ++i) {
+               double time_insert, time_find, time_erase;
+
+               run_timing< exhashmap<ex> >(*i, time_insert, time_find, time_erase);
+
+// If you like, you can compare it with this:
+//             run_timing< std::map<ex, ex, ex_is_less> >(*i, time_insert, time_find, time_erase);
+
+               times_insert.push_back(time_insert);
+               times_find.push_back(time_find);
+               times_erase.push_back(time_erase);
+               cout << '.' << flush;
+       }
+
+       if (!result) {
+               cout << " passed ";
+               clog << "(no output)" << endl;
+       } else {
+               cout << " failed ";
+       }
+
+       // print the report:
+       cout << endl << "          size:\t";
+       copy(sizes.begin(), sizes.end(), ostream_iterator<unsigned>(cout, "\t"));
+       cout << endl << "      insert/s:\t";
+       copy(times_insert.begin(), times_insert.end(), ostream_iterator<double>(cout, "\t"));
+       cout << endl << "        find/s:\t";
+       copy(times_find.begin(), times_find.end(), ostream_iterator<double>(cout, "\t"));
+       cout << endl << "       erase/s:\t";
+       copy(times_erase.begin(), times_erase.end(), ostream_iterator<double>(cout, "\t"));
+       cout << endl;
+
+       return result;
+}
index e405403..9ada2bf 100644 (file)
@@ -39,6 +39,7 @@ try { \
        TIME(gammaseries)
        TIME(vandermonde)
        TIME(toeplitz)
+       TIME(hashmap)
        TIME(lw_A)
        TIME(lw_B)
        TIME(lw_C)
index 85052de..cd0645b 100644 (file)
@@ -39,6 +39,7 @@ unsigned time_dennyfliegner();
 unsigned time_gammaseries();
 unsigned time_vandermonde();
 unsigned time_toeplitz();
+unsigned time_hashmap();
 unsigned time_lw_A();
 unsigned time_lw_B();
 unsigned time_lw_C();
index d34c8fd..e053079 100644 (file)
@@ -6,6 +6,8 @@
 (no output)
 -------determinant of polyvariate symbolic Toeplitz matrices:
 (no output)
+-------hash map operations:
+(no output)
 -------Lewis-Wester test A (divide factorials):
 (no output)
 -------Lewis-Wester test B (sum of rational numbers):