test/src/TestRadixTree.cpp

   1 /* Copyright_License {
   2
   3   XCSoar Glide Computer - http://www.xcsoar.org/
   4   Copyright (C) 2000-2013 The XCSoar Project
   5   A detailed list of copyright holders can be found in the file "AUTHORS".
   6
   7   This program is free software; you can redistribute it and/or
   8   modify it under the terms of the GNU General Public License
   9   as published by the Free Software Foundation; either version 2
  10   of the License, or (at your option) any later version.
  11
  12   This program is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15   GNU General Public License for more details.
  16
  17   You should have received a copy of the GNU General Public License
  18   along with this program; if not, write to the Free Software
  19   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  20 }
  21 */
  22
  23 #define PRINT_RADIX_TREE
  24
  25 #include <iostream>
  26
  27 #include "Util/RadixTree.hpp"
  28 #include "TestUtil.hpp"
  29
  30 struct Sum {
  31   int value;
  32
  33   Sum():value(0) {}
  34
  35   void operator()(int x) {
  36     value += x;
  37   }
  38 };
  39
  40 static int
  41 all_sum(const RadixTree<int> &rt)
  42 {
  43   Sum sum;
  44   rt.VisitAll(sum);
  45   return sum.value;
  46 }
  47
  48 static int
  49 prefix_sum(const RadixTree<int> &rt, const TCHAR *prefix)
  50 {
  51   Sum sum;
  52   rt.VisitPrefix(prefix, sum);
  53   return sum.value;
  54 }
  55
  56 template<typename T>
  57 struct AscendingKeyVisitor
  58   : public std::binary_function<const TCHAR *, T, void> {
  59   tstring last;
  60
  61   void operator()(const TCHAR *key, const T &value) {
  62     ok1(last.compare(key) <= 0);
  63     last = key;
  64   }
  65 };
  66
  67 template<typename T>
  68 static void
  69 check_ascending_keys(const RadixTree<T> &tree)
  70 {
  71   AscendingKeyVisitor<T> visitor;
  72   tree.VisitAllPairs(visitor);
  73 }
  74
  75 int main(int argc, char **argv)
  76 {
  77   plan_tests(86);
  78
  79   TCHAR buffer[64], *suggest;
  80
  81   RadixTree<int> irt;
  82   irt.Add(_T("foo"), 42);
  83   ok1(all_sum(irt) == 42);
  84   ok1(prefix_sum(irt, _T("")) == 42);
  85   ok1(prefix_sum(irt, _T("f")) == 42);
  86   ok1(prefix_sum(irt, _T("fo")) == 42);
  87   ok1(prefix_sum(irt, _T("foo")) == 42);
  88   ok1(prefix_sum(irt, _T("foobar")) == 0);
  89
  90   irt.Add(_T("foa"), 0);
  91   ok1(all_sum(irt) == 42);
  92   check_ascending_keys(irt);
  93
  94   suggest = irt.Suggest(_T("xyz"), buffer, 64);
  95   ok1(suggest == NULL);
  96
  97   suggest = irt.Suggest(_T(""), buffer, 64);
  98   ok1(suggest != NULL);
  99   ok1(_tcscmp(suggest, _T("f")) == 0);
 100
 101   suggest = irt.Suggest(_T("f"), buffer, 64);
 102   ok1(suggest != NULL);
 103   ok1(_tcscmp(suggest, _T("o")) == 0);
 104
 105   suggest = irt.Suggest(_T("foo"), buffer, 64);
 106   ok1(suggest != NULL);
 107   ok1(_tcscmp(suggest, _T("")) == 0);
 108
 109   irt.Add(_T("bar"), 1);
 110   ok1(all_sum(irt) == 43);
 111   ok1(prefix_sum(irt, _T("")) == 43);
 112   ok1(prefix_sum(irt, _T("f")) == 42);
 113
 114   suggest = irt.Suggest(_T(""), buffer, 64);
 115   ok1(suggest != NULL);
 116   ok1(_tcscmp(suggest, _T("bf")) == 0);
 117
 118   suggest = irt.Suggest(_T("ba"), buffer, 64);
 119   ok1(suggest != NULL);
 120   ok1(_tcscmp(suggest, _T("r")) == 0);
 121
 122   irt.Add(_T("foo"), 2);
 123   ok1(all_sum(irt) == 45);
 124   ok1(prefix_sum(irt, _T("")) == 45);
 125   ok1(prefix_sum(irt, _T("f")) == 44);
 126   ok1(prefix_sum(irt, _T("fo")) == 44);
 127   ok1(prefix_sum(irt, _T("foo")) == 44);
 128   ok1(prefix_sum(irt, _T("foobar")) == 0);
 129
 130   ok1(irt.Get(_T("foo"), 0) == 42 || irt.Get(_T("foo"), 0) == 2);
 131   ok1(irt.GetIf(_T("foo"), 0, std::bind1st(std::equal_to<int>(), 42)) == 42);
 132   ok1(irt.GetIf(_T("foo"), 0, std::bind1st(std::equal_to<int>(), 2)) == 2);
 133   ok1(irt.GetIf(_T("foo"), 0, std::bind1st(std::equal_to<int>(), 22)) == 0);
 134
 135   suggest = irt.Suggest(_T("foo"), buffer, 64);
 136   ok1(suggest != NULL);
 137   ok1(_tcscmp(suggest, _T("")) == 0);
 138
 139   irt.Add(_T("baz"), 3);
 140   ok1(all_sum(irt) == 48);
 141   ok1(prefix_sum(irt, _T("b")) == 4);
 142   ok1(prefix_sum(irt, _T("ba")) == 4);
 143   ok1(prefix_sum(irt, _T("bar")) == 1);
 144   ok1(prefix_sum(irt, _T("baz")) == 3);
 145
 146   suggest = irt.Suggest(_T(""), buffer, 64);
 147   ok1(suggest != NULL);
 148   ok1(_tcscmp(suggest, _T("bf")) == 0);
 149
 150   suggest = irt.Suggest(_T("ba"), buffer, 64);
 151   ok1(suggest != NULL);
 152   ok1(_tcscmp(suggest, _T("rz")) == 0);
 153
 154   irt.Add(_T("foobar"), 4);
 155   ok1(all_sum(irt) == 52);
 156   ok1(prefix_sum(irt, _T("f")) == 48);
 157   ok1(prefix_sum(irt, _T("fo")) == 48);
 158   ok1(prefix_sum(irt, _T("foo")) == 48);
 159   ok1(prefix_sum(irt, _T("foobar")) == 4);
 160
 161   suggest = irt.Suggest(_T("foo"), buffer, 64);
 162   ok1(suggest != NULL);
 163   ok1(_tcscmp(suggest, _T("b")) == 0);
 164
 165   irt.Add(_T("fo"), 5);
 166   ok1(all_sum(irt) == 57);
 167   ok1(prefix_sum(irt, _T("f")) == 53);
 168   ok1(prefix_sum(irt, _T("fo")) == 53);
 169   ok1(prefix_sum(irt, _T("foo")) == 48);
 170   ok1(prefix_sum(irt, _T("foobar")) == 4);
 171
 172   irt.Add(_T("fooz"), 6);
 173   ok1(all_sum(irt) == 63);
 174   ok1(prefix_sum(irt, _T("f")) == 59);
 175   ok1(prefix_sum(irt, _T("fo")) == 59);
 176   ok1(prefix_sum(irt, _T("foo")) == 54);
 177
 178   suggest = irt.Suggest(_T("foo"), buffer, 64);
 179   ok1(suggest != NULL);
 180   ok1(_tcscmp(suggest, _T("bz")) == 0);
 181
 182   irt.Add(_T("fooy"), 7);
 183   ok1(all_sum(irt) == 70);
 184   ok1(prefix_sum(irt, _T("f")) == 66);
 185   ok1(prefix_sum(irt, _T("fo")) == 66);
 186   ok1(prefix_sum(irt, _T("foo")) == 61);
 187
 188   suggest = irt.Suggest(_T("foo"), buffer, 64);
 189   ok1(suggest != NULL);
 190   ok1(_tcscmp(suggest, _T("byz")) == 0);
 191
 192   irt.Add(_T("foo"), 8);
 193   ok1(all_sum(irt) == 78);
 194   ok1(prefix_sum(irt, _T("foo")) == 69);
 195
 196   irt.Remove(_T("foo"), 42);
 197   ok1(all_sum(irt) == 36);
 198   ok1(prefix_sum(irt, _T("foo")) == 27);
 199
 200   irt.Remove(_T("foo"));
 201   ok1(all_sum(irt) == 26);
 202   ok1(prefix_sum(irt, _T("")) == 26);
 203   ok1(prefix_sum(irt, _T("foo")) == 17);
 204
 205   irt.Add(_T(""), 9);
 206   ok1(all_sum(irt) == 35);
 207   ok1(prefix_sum(irt, _T("")) == 35);
 208   ok1(prefix_sum(irt, _T("foo")) == 17);
 209
 210   check_ascending_keys(irt);
 211
 212   return exit_status();
 213 }