1 module TrieTest; 2 3 4 import hunt.collection.ArrayTernaryTrie; 5 import hunt.collection.ArrayTrie; 6 import hunt.collection.ByteBuffer; 7 import hunt.collection.Collection; 8 import hunt.collection.TreeTrie; 9 import hunt.collection.Trie; 10 11 import hunt.collection.BufferUtils; 12 13 import hunt.util.UnitTest; 14 import hunt.Assert; 15 import hunt.text; 16 17 import hunt.logging; 18 import std.conv; 19 20 /** 21 https://www.programcreek.com/java-api-examples/index.php?source_dir=jetty.project-master/jetty-jaspi/src/test/java/org/eclipse/jetty/security/jaspi/JaspiTest.java# 22 */ 23 class TrieTest { 24 Trie!int trie; 25 26 this() { 27 trie= new ArrayTrie!int(128); 28 // trie= new TreeTrie!int(); 29 // trie= new ArrayTernaryTrie!int(128); 30 before(); 31 } 32 33 // this(Trie!int t) 34 // { 35 // trie=t; 36 // } 37 38 void before() 39 { 40 trie.put("hello",1); 41 trie.put("He",2); 42 trie.put("HELL",3); 43 trie.put("wibble",4); 44 trie.put("Wobble",5); 45 trie.put("foo-bar",6); 46 trie.put("foo+bar",7); 47 trie.put("HELL4",8); 48 trie.put("",9); 49 50 // ArrayTernaryTrie!int d = cast(ArrayTernaryTrie!int)trie; 51 // d.dump(); 52 } 53 54 55 void testOverflow() 56 { 57 int i=0; 58 while (true) 59 { 60 if (++i>10000) 61 break; // must not be fixed size 62 if (!trie.put("prefix" ~ i.to!string(), i)) 63 { 64 assert(trie.isFull()); 65 break; 66 } 67 } 68 69 assert(!trie.isFull() || !trie.put("overflow", 0)); 70 } 71 72 void testKeySet() 73 { 74 assert(trie.keySet().contains("hello")); 75 assert(trie.keySet().contains("He")); 76 assert(trie.keySet().contains("HELL")); 77 assert(trie.keySet().contains("wibble")); 78 assert(trie.keySet().contains("Wobble")); 79 assert(trie.keySet().contains("foo-bar")); 80 assert(trie.keySet().contains("foo+bar")); 81 assert(trie.keySet().contains("HELL4")); 82 83 assert(trie.keySet().contains("")); 84 } 85 86 void testGetString() 87 { 88 Assert.assertEquals(1,trie.get("hello")); 89 Assert.assertEquals(2,trie.get("He")); 90 Assert.assertEquals(3,trie.get("HELL")); 91 Assert.assertEquals(4,trie.get("wibble")); 92 Assert.assertEquals(5,trie.get("Wobble")); 93 Assert.assertEquals(6,trie.get("foo-bar")); 94 Assert.assertEquals(7,trie.get("foo+bar")); 95 96 Assert.assertEquals(1,trie.get("Hello")); 97 Assert.assertEquals(2,trie.get("HE")); 98 Assert.assertEquals(3,trie.get("heLL")); 99 Assert.assertEquals(4,trie.get("Wibble")); 100 Assert.assertEquals(5,trie.get("wobble")); 101 Assert.assertEquals(6,trie.get("Foo-bar")); 102 Assert.assertEquals(7,trie.get("FOO+bar")); 103 Assert.assertEquals(8,trie.get("HELL4")); 104 Assert.assertEquals(9,trie.get("")); 105 106 Assert.assertEquals(int.init,trie.get("helloworld")); 107 Assert.assertEquals(int.init,trie.get("Help")); 108 Assert.assertEquals(int.init,trie.get("Blah")); 109 } 110 111 void testGetBuffer() 112 { 113 Assert.assertEquals(1,trie.get(BufferUtils.toBuffer("xhellox"),1,5)); 114 Assert.assertEquals(2,trie.get(BufferUtils.toBuffer("xhellox"),1,2)); 115 Assert.assertEquals(3,trie.get(BufferUtils.toBuffer("xhellox"),1,4)); 116 Assert.assertEquals(4,trie.get(BufferUtils.toBuffer("wibble"),0,6)); 117 Assert.assertEquals(5,trie.get(BufferUtils.toBuffer("xWobble"),1,6)); 118 Assert.assertEquals(6,trie.get(BufferUtils.toBuffer("xfoo-barx"),1,7)); 119 Assert.assertEquals(7,trie.get(BufferUtils.toBuffer("xfoo+barx"),1,7)); 120 121 Assert.assertEquals(1,trie.get(BufferUtils.toBuffer("xhellox"),1,5)); 122 Assert.assertEquals(2,trie.get(BufferUtils.toBuffer("xHELLox"),1,2)); 123 Assert.assertEquals(3,trie.get(BufferUtils.toBuffer("xhellox"),1,4)); 124 Assert.assertEquals(4,trie.get(BufferUtils.toBuffer("Wibble"),0,6)); 125 Assert.assertEquals(5,trie.get(BufferUtils.toBuffer("xwobble"),1,6)); 126 Assert.assertEquals(6,trie.get(BufferUtils.toBuffer("xFOO-barx"),1,7)); 127 Assert.assertEquals(7,trie.get(BufferUtils.toBuffer("xFOO+barx"),1,7)); 128 129 Assert.assertEquals(int.init,trie.get(BufferUtils.toBuffer("xHelloworldx"),1,10)); 130 Assert.assertEquals(int.init,trie.get(BufferUtils.toBuffer("xHelpx"),1,4)); 131 Assert.assertEquals(int.init,trie.get(BufferUtils.toBuffer("xBlahx"),1,4)); 132 } 133 134 void testGetDirectBuffer() 135 { 136 Assert.assertEquals(1,trie.get(BufferUtils.toDirectBuffer("xhellox"),1,5)); 137 Assert.assertEquals(2,trie.get(BufferUtils.toDirectBuffer("xhellox"),1,2)); 138 Assert.assertEquals(3,trie.get(BufferUtils.toDirectBuffer("xhellox"),1,4)); 139 Assert.assertEquals(4,trie.get(BufferUtils.toDirectBuffer("wibble"),0,6)); 140 Assert.assertEquals(5,trie.get(BufferUtils.toDirectBuffer("xWobble"),1,6)); 141 Assert.assertEquals(6,trie.get(BufferUtils.toDirectBuffer("xfoo-barx"),1,7)); 142 Assert.assertEquals(7,trie.get(BufferUtils.toDirectBuffer("xfoo+barx"),1,7)); 143 144 Assert.assertEquals(1,trie.get(BufferUtils.toDirectBuffer("xhellox"),1,5)); 145 Assert.assertEquals(2,trie.get(BufferUtils.toDirectBuffer("xHELLox"),1,2)); 146 Assert.assertEquals(3,trie.get(BufferUtils.toDirectBuffer("xhellox"),1,4)); 147 Assert.assertEquals(4,trie.get(BufferUtils.toDirectBuffer("Wibble"),0,6)); 148 Assert.assertEquals(5,trie.get(BufferUtils.toDirectBuffer("xwobble"),1,6)); 149 Assert.assertEquals(6,trie.get(BufferUtils.toDirectBuffer("xFOO-barx"),1,7)); 150 Assert.assertEquals(7,trie.get(BufferUtils.toDirectBuffer("xFOO+barx"),1,7)); 151 152 Assert.assertEquals(int.init,trie.get(BufferUtils.toDirectBuffer("xHelloworldx"),1,10)); 153 Assert.assertEquals(int.init,trie.get(BufferUtils.toDirectBuffer("xHelpx"),1,4)); 154 Assert.assertEquals(int.init,trie.get(BufferUtils.toDirectBuffer("xBlahx"),1,4)); 155 } 156 157 void testGetBestArray() 158 { 159 Assert.assertEquals(1,trie.getBest(cast(byte[])("xhelloxxxx"),1,8)); 160 Assert.assertEquals(2,trie.getBest(cast(byte[])("xhelxoxxxx"),1,8)); 161 Assert.assertEquals(3,trie.getBest(cast(byte[])("xhellxxxxx"),1,8)); 162 Assert.assertEquals(6,trie.getBest(cast(byte[])("xfoo-barxx"),1,8)); 163 Assert.assertEquals(8,trie.getBest(cast(byte[])("xhell4xxxx"),1,8)); 164 165 Assert.assertEquals(1,trie.getBest(cast(byte[])("xHELLOxxxx"),1,8)); 166 Assert.assertEquals(2,trie.getBest(cast(byte[])("xHELxoxxxx"),1,8)); 167 Assert.assertEquals(3,trie.getBest(cast(byte[])("xHELLxxxxx"),1,8)); 168 Assert.assertEquals(6,trie.getBest(cast(byte[])("xfoo-BARxx"),1,8)); 169 Assert.assertEquals(8,trie.getBest(cast(byte[])("xHELL4xxxx"),1,8)); 170 Assert.assertEquals(9,trie.getBest(cast(byte[])("xZZZZZxxxx"),1,8)); 171 } 172 173 void testGetBestBuffer() 174 { 175 Assert.assertEquals(1,trie.getBest(BufferUtils.toBuffer("xhelloxxxx"),1,8)); 176 Assert.assertEquals(2,trie.getBest(BufferUtils.toBuffer("xhelxoxxxx"),1,8)); 177 Assert.assertEquals(3,trie.getBest(BufferUtils.toBuffer("xhellxxxxx"),1,8)); 178 Assert.assertEquals(6,trie.getBest(BufferUtils.toBuffer("xfoo-barxx"),1,8)); 179 Assert.assertEquals(8,trie.getBest(BufferUtils.toBuffer("xhell4xxxx"),1,8)); 180 181 Assert.assertEquals(1,trie.getBest(BufferUtils.toBuffer("xHELLOxxxx"),1,8)); 182 Assert.assertEquals(2,trie.getBest(BufferUtils.toBuffer("xHELxoxxxx"),1,8)); 183 Assert.assertEquals(3,trie.getBest(BufferUtils.toBuffer("xHELLxxxxx"),1,8)); 184 Assert.assertEquals(6,trie.getBest(BufferUtils.toBuffer("xfoo-BARxx"),1,8)); 185 Assert.assertEquals(8,trie.getBest(BufferUtils.toBuffer("xHELL4xxxx"),1,8)); 186 Assert.assertEquals(9,trie.getBest(BufferUtils.toBuffer("xZZZZZxxxx"),1,8)); 187 188 ByteBuffer buffer = cast(ByteBuffer)BufferUtils.toBuffer("xhelloxxxxxxx").position(2); 189 Assert.assertEquals(1,trie.getBest(buffer,-1,10)); 190 } 191 192 void testGetBestDirectBuffer() 193 { 194 Assert.assertEquals(1,trie.getBest(BufferUtils.toDirectBuffer("xhelloxxxx"),1,8)); 195 Assert.assertEquals(2,trie.getBest(BufferUtils.toDirectBuffer("xhelxoxxxx"),1,8)); 196 Assert.assertEquals(3,trie.getBest(BufferUtils.toDirectBuffer("xhellxxxxx"),1,8)); 197 Assert.assertEquals(6,trie.getBest(BufferUtils.toDirectBuffer("xfoo-barxx"),1,8)); 198 Assert.assertEquals(8,trie.getBest(BufferUtils.toDirectBuffer("xhell4xxxx"),1,8)); 199 200 Assert.assertEquals(1,trie.getBest(BufferUtils.toDirectBuffer("xHELLOxxxx"),1,8)); 201 Assert.assertEquals(2,trie.getBest(BufferUtils.toDirectBuffer("xHELxoxxxx"),1,8)); 202 Assert.assertEquals(3,trie.getBest(BufferUtils.toDirectBuffer("xHELLxxxxx"),1,8)); 203 Assert.assertEquals(6,trie.getBest(BufferUtils.toDirectBuffer("xfoo-BARxx"),1,8)); 204 Assert.assertEquals(8,trie.getBest(BufferUtils.toDirectBuffer("xHELL4xxxx"),1,8)); 205 Assert.assertEquals(9,trie.getBest(BufferUtils.toDirectBuffer("xZZZZZxxxx"),1,8)); 206 207 ByteBuffer buffer = cast(ByteBuffer)BufferUtils.toDirectBuffer("xhelloxxxxxxx").position(2); 208 Assert.assertEquals(1,trie.getBest(buffer,-1,10)); 209 } 210 211 void testFull() 212 { 213 ArrayTrie!int t1 = cast(ArrayTrie!int)trie; 214 ArrayTernaryTrie!int t2 = cast(ArrayTernaryTrie!int)trie; 215 if( t1 is null && t2 is null) return; 216 217 Assert.assertFalse(trie.put("Large: This is a really large key and should blow the maximum size of the array trie as lots of nodes should already be used.",99)); 218 testGetString(); 219 testGetBestArray(); 220 testGetBestBuffer(); 221 } 222 }