TrieTest source code

1 module TrieTest;
2 
3 
4 import hunt.collection.ArrayTernaryTrie;
5 import hunt.collection.ArrayTrie;
6 import hunt.io.ByteBuffer;
7 import hunt.collection.Collection;
8 import hunt.collection.TreeTrie;
9 import hunt.collection.Trie;
10 
11 import hunt.io.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 }