1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.server.core.avltree;
21
22
23 import static org.junit.Assert.assertEquals;
24 import static org.junit.Assert.assertFalse;
25 import static org.junit.Assert.assertNotNull;
26 import static org.junit.Assert.assertTrue;
27
28 import java.io.File;
29 import java.io.FileInputStream;
30 import java.io.FileNotFoundException;
31 import java.io.FileOutputStream;
32 import java.io.IOException;
33 import java.io.Serializable;
34 import java.util.Comparator;
35
36 import org.junit.AfterClass;
37 import org.junit.Before;
38 import org.junit.Test;
39 import org.slf4j.Logger;
40 import org.slf4j.LoggerFactory;
41
42
43
44
45
46
47
48
49 public class AvlTreeMarshallerTest
50 {
51 private static final long[] AVLTREE_KEYS_PRE_REMOVE =
52 {
53 2, 14, 26, 86, 110, 122, 134, 182
54 };
55
56 private static final long[] AVLTREE_EXPECTED_KEYS_POST_REMOVE =
57 {
58 2, 14, 26, 86, 122, 134, 182
59 };
60
61 private static final byte[] SERIALIZED_AVLTREE_PRE_REMOVE =
62 {
63 0, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0,
64 110, 0, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 8, 0, 0, 0,
65 0, 0, 0, 0, 26, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0,
66 8, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0,
67 0, 0, 0, 0, 4, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0,
68 14, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
69 4, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 86, 0, 0, 0,
70 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0,
71 8, 0, 0, 0, 0, 0, 0, 0, -122, 0, 0, 0, 6, 0, 0, 0,
72 2, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 122, 0, 0, 0,
73 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0,
74 8, 0, 0, 0, 0, 0, 0, 0, -74, 0, 0, 0, 7, 0, 0, 0,
75 0, 0, 0, 0, 0
76 };
77
78
79
80
81
82
83
84
85
86
87
88
89
90 AvlTree<Integer> tree;
91 Comparator<Integer> comparator;
92 AvlTreeMarshaller<Integer> treeMarshaller;
93
94 static AvlTree<Integer> savedTree;
95
96 static File treeFile = new File( System.getProperty( "java.io.tmpdir" ) + File.separator + "avl.tree");
97
98 private static final Logger LOG = LoggerFactory.getLogger( AvlTreeMarshallerTest.class.getSimpleName() );
99
100
101 @Before
102 public void createTree()
103 {
104 comparator = new Comparator<Integer>()
105 {
106 public int compare( Integer i1, Integer i2 )
107 {
108 return i1.compareTo( i2 );
109 }
110 };
111
112
113 tree = new AvlTree<Integer>( comparator );
114 treeMarshaller = new AvlTreeMarshaller<Integer>( comparator, new IntegerKeyMarshaller() );
115 }
116
117
118 @AfterClass
119 public static void deleteFiles()
120 {
121 treeFile.delete();
122 }
123
124
125 @Test
126 public void testRemoveBug() throws IOException
127 {
128 Comparator<Long> comparator = new Comparator<Long>()
129 {
130 public int compare( Long i1, Long i2 )
131 {
132 return i1.compareTo( i2 );
133 }
134 };
135
136
137
138
139
140
141
142 AvlTreeMarshaller<Long> treeMarshaller = new AvlTreeMarshaller<Long>( comparator, new LongMarshaller() );
143 AvlTree<Long> tree = treeMarshaller.deserialize( SERIALIZED_AVLTREE_PRE_REMOVE );
144
145 for ( long key : AVLTREE_KEYS_PRE_REMOVE )
146 {
147 assertNotNull( "Should find " + key, tree.find( key ) );
148 }
149
150
151
152
153
154
155 tree.remove( 110L );
156
157 for ( long key : AVLTREE_EXPECTED_KEYS_POST_REMOVE )
158 {
159 assertNotNull( "Should find " + key, tree.find( key ) );
160 }
161 }
162
163
164 @Test
165 public void testMarshalEmptyTree() throws IOException
166 {
167 byte[] bites = treeMarshaller.serialize( new AvlTree<Integer>( comparator ) );
168 AvlTree<Integer> tree = treeMarshaller.deserialize( bites );
169 assertNotNull( tree );
170 }
171
172
173 @Test
174 public void testRoundTripEmpty() throws IOException
175 {
176 AvlTree<Integer> original = new AvlTree<Integer>( comparator );
177 byte[] bites = treeMarshaller.serialize( original );
178 AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
179 assertTrue( deserialized.isEmpty() );
180 }
181
182
183 @Test
184 public void testRoundTripOneEntry() throws IOException
185 {
186 AvlTree<Integer> original = new AvlTree<Integer>( comparator );
187 original.insert( 0 );
188 byte[] bites = treeMarshaller.serialize( original );
189 AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
190 assertFalse( deserialized.isEmpty() );
191 assertEquals( 1, deserialized.getSize() );
192 assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
193 }
194
195
196 @Test
197 public void testRoundTripOneEntryFirstLast() throws IOException
198 {
199 AvlTree<Integer> original = new AvlTree<Integer>( comparator );
200 original.insert( 0 );
201 byte[] bites = treeMarshaller.serialize( original );
202 AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
203 assertFalse( deserialized.isEmpty() );
204 assertEquals( 1, deserialized.getSize() );
205 assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
206
207 assertNotNull( original.getFirst() );
208 assertEquals( 0, ( int ) original.getFirst().getKey() );
209
210 assertNotNull( deserialized.getFirst() );
211 assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
212
213 assertNotNull( original.getLast() );
214 assertEquals( 0, ( int ) original.getLast().getKey() );
215
216
217 assertNotNull( deserialized.getLast() );
218 assertEquals( 0, ( int ) deserialized.getLast().getKey() );
219 }
220
221
222 @Test
223 public void testRoundTripTwoEntries() throws IOException
224 {
225 AvlTree<Integer> original = new AvlTree<Integer>( comparator );
226 original.insert( 0 );
227 original.insert( 1 );
228 byte[] bites = treeMarshaller.serialize( original );
229 AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
230 assertFalse( deserialized.isEmpty() );
231 assertEquals( 2, deserialized.getSize() );
232 assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
233 assertEquals( 1, ( int ) deserialized.getFirst().next.getKey() );
234 }
235
236
237 @Test
238 public void testRoundTripTwoEntriesFirstLast() throws IOException
239 {
240 AvlTree<Integer> original = new AvlTree<Integer>( comparator );
241 original.insert( 0 );
242 original.insert( 1 );
243 byte[] bites = treeMarshaller.serialize( original );
244 AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
245 assertFalse( deserialized.isEmpty() );
246 assertEquals( 2, deserialized.getSize() );
247 assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
248 assertEquals( 1, ( int ) deserialized.getFirst().next.getKey() );
249
250 assertNotNull( original.getFirst() );
251 assertEquals( 0, ( int ) original.getFirst().getKey() );
252
253 assertNotNull( deserialized.getFirst() );
254 assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
255
256 assertNotNull( original.getLast() );
257 assertEquals( 1, ( int ) original.getLast().getKey() );
258
259
260 assertNotNull( deserialized.getLast() );
261 assertEquals( 1, ( int ) deserialized.getLast().getKey() );
262 }
263
264
265 @Test
266 public void testRoundTripManyEntries() throws Exception
267 {
268 AvlTree<Integer> original = new AvlTree<Integer>( comparator );
269 for ( int ii = 0; ii < 100; ii++ )
270 {
271 original.insert( ii );
272 }
273 byte[] bites = treeMarshaller.serialize( original );
274 AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
275 assertFalse( deserialized.isEmpty() );
276 assertEquals( 100, deserialized.getSize() );
277
278 AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( deserialized );
279 cursor.first();
280 for ( int ii = 0; ii < 100; ii++ )
281 {
282 assertEquals( ii, ( int ) cursor.get() );
283 cursor.next();
284 }
285 }
286
287
288 @Test
289 public void testRoundTripManyEntriesFirstLast() throws Exception
290 {
291 AvlTree<Integer> original = new AvlTree<Integer>( comparator );
292 for ( int ii = 0; ii < 100; ii++ )
293 {
294 original.insert( ii );
295 }
296 byte[] bites = treeMarshaller.serialize( original );
297 AvlTree<Integer> deserialized = treeMarshaller.deserialize( bites );
298 assertFalse( deserialized.isEmpty() );
299 assertEquals( 100, deserialized.getSize() );
300
301 AvlTreeCursor<Integer> cursor = new AvlTreeCursor<Integer>( deserialized );
302 cursor.first();
303 for ( int ii = 0; ii < 100; ii++ )
304 {
305 assertEquals( ii, ( int ) cursor.get() );
306 cursor.next();
307 }
308
309 assertNotNull( original.getFirst() );
310 assertEquals( 0, ( int ) original.getFirst().getKey() );
311
312 assertNotNull( deserialized.getFirst() );
313 assertEquals( 0, ( int ) deserialized.getFirst().getKey() );
314
315 assertNotNull( original.getLast() );
316 assertEquals( 99, ( int ) original.getLast().getKey() );
317
318
319 assertNotNull( deserialized.getLast() );
320 assertEquals( 99, ( int ) deserialized.getLast().getKey() );
321 }
322
323
324 @Test
325 public void testRoundTripManyEntriesDefaultSerialization() throws Exception
326 {
327 Comparator<Bar> barComparator = new Comparator<Bar>() {
328 public int compare( Bar o1, Bar o2 )
329 {
330 return o1.intValue.compareTo( o2.intValue );
331 }
332 };
333
334 AvlTree<Bar> original = new AvlTree<Bar>( barComparator );
335
336 for ( int ii = 0; ii < 100; ii++ )
337 {
338 original.insert( new Bar( ii ) );
339 }
340
341 AvlTreeMarshaller<Bar> marshaller = new AvlTreeMarshaller<Bar>( barComparator );
342 byte[] bites = marshaller.serialize( original );
343 AvlTree<Bar> deserialized = marshaller.deserialize( bites );
344 assertFalse( deserialized.isEmpty() );
345 assertEquals( 100, deserialized.getSize() );
346
347 AvlTreeCursor<Bar> cursor = new AvlTreeCursor<Bar>( deserialized );
348 cursor.first();
349 for ( int ii = 0; ii < 100; ii++ )
350 {
351 assertEquals( ii, ( int ) cursor.get().intValue );
352 cursor.next();
353 }
354 }
355
356
357 static class Bar implements Serializable
358 {
359 Integer intValue = 37;
360 String stringValue = "bar";
361 long longValue = 32L;
362 Foo fooValue = new Foo();
363
364
365 public Bar( int ii )
366 {
367 intValue = ii;
368 }
369 }
370
371
372 static class Foo implements Serializable
373 {
374 float floatValue = 3;
375 String stringValue = "foo";
376 double doubleValue = 1.2;
377 byte byteValue = 3;
378 char charValue = 'a';
379 }
380
381
382 @Test
383 public void testMarshal() throws IOException
384 {
385 tree.insert( 37 );
386 tree.insert( 7 );
387 tree.insert( 25 );
388 tree.insert( 8 );
389 tree.insert( 9 );
390
391 FileOutputStream fout = new FileOutputStream( treeFile );
392 fout.write( treeMarshaller.serialize( tree ) );
393 fout.close();
394
395 savedTree = tree;
396
397 if( LOG.isDebugEnabled() )
398 {
399 LOG.debug("saved tree\n--------");
400 tree.printTree();
401 }
402
403 assertTrue( true );
404 }
405
406
407 @Test
408 public void testUnMarshal() throws FileNotFoundException, IOException
409 {
410 FileInputStream fin = new FileInputStream(treeFile);
411
412 byte[] data = new byte[ ( int )treeFile.length() ];
413 fin.read( data );
414
415 AvlTree<Integer> unmarshalledTree = treeMarshaller.deserialize( data );
416
417 if( LOG.isDebugEnabled() )
418 {
419 LOG.debug("\nunmarshalled tree\n---------------");
420 unmarshalledTree.printTree();
421 }
422
423 assertTrue( savedTree.getRoot().getKey() == unmarshalledTree.getRoot().getKey() );
424
425 unmarshalledTree.insert( 6 );
426
427 assertTrue( savedTree.getRoot().getKey() == unmarshalledTree.getRoot().getKey() );
428 assertTrue( 8 == unmarshalledTree.getRoot().getKey() );
429
430 assertTrue( 37 == unmarshalledTree.getLast().getKey() );
431 unmarshalledTree.insert( 99 );
432 assertTrue( 99 == unmarshalledTree.getLast().getKey() );
433
434 assertTrue( 6 == unmarshalledTree.getFirst().getKey() );
435
436 unmarshalledTree.insert( 0 );
437 assertTrue( 0 == unmarshalledTree.getFirst().getKey() );
438
439 if( LOG.isDebugEnabled() )
440 {
441 LOG.debug("\nmodified tree after unmarshalling\n---------------");
442 unmarshalledTree.printTree();
443 }
444
445 assertNotNull(unmarshalledTree.getFirst());
446 assertNotNull(unmarshalledTree.getLast());
447 }
448
449
450 @Test( expected = IOException.class )
451 public void testDeserializeNullData() throws IOException
452 {
453 treeMarshaller.deserialize( null );
454 }
455
456
457 public class LongMarshaller implements Marshaller<Long>
458 {
459 public byte[] serialize( Long obj ) throws IOException
460 {
461 long id = obj.longValue();
462 byte[] bites = new byte[8];
463
464 bites[0] = ( byte ) ( id >> 56 );
465 bites[1] = ( byte ) ( id >> 48 );
466 bites[2] = ( byte ) ( id >> 40 );
467 bites[3] = ( byte ) ( id >> 32 );
468 bites[4] = ( byte ) ( id >> 24 );
469 bites[5] = ( byte ) ( id >> 16 );
470 bites[6] = ( byte ) ( id >> 8 );
471 bites[7] = ( byte ) id;
472
473 return bites;
474 }
475
476
477 public Long deserialize( byte[] bites ) throws IOException
478 {
479 long id;
480 id = bites[0] + ( ( bites[0] < 0 ) ? 256 : 0 );
481 id <<= 8;
482 id += bites[1] + ( ( bites[1] < 0 ) ? 256 : 0 );
483 id <<= 8;
484 id += bites[2] + ( ( bites[2] < 0 ) ? 256 : 0 );
485 id <<= 8;
486 id += bites[3] + ( ( bites[3] < 0 ) ? 256 : 0 );
487 id <<= 8;
488 id += bites[4] + ( ( bites[4] < 0 ) ? 256 : 0 );
489 id <<= 8;
490 id += bites[5] + ( ( bites[5] < 0 ) ? 256 : 0 );
491 id <<= 8;
492 id += bites[6] + ( ( bites[6] < 0 ) ? 256 : 0 );
493 id <<= 8;
494 id += bites[7] + ( ( bites[7] < 0 ) ? 256 : 0 );
495 return id;
496 }
497 }
498 }