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.splay;
21
22 import static junit.framework.Assert.assertEquals;
23
24 import java.util.Comparator;
25
26 import org.junit.Before;
27 import org.junit.Test;
28
29
30
31
32
33
34
35 public class SplayTreeTest
36 {
37 SplayTree<Integer> tree;
38
39 @Before
40 public void createTree()
41 {
42 tree = new SplayTree<Integer>( new Comparator<Integer>()
43 {
44
45 public int compare( Integer i1, Integer i2 )
46 {
47 return i1.compareTo( i2 );
48 }
49 });
50 }
51
52 @Test
53 public void testLinkedNodes()
54 {
55 for( int i=0; i< 3; i++)
56 {
57 tree.insert( i );
58 }
59
60 assertEquals( "[0]-->[1]-->[2]-->NULL", getLinkedText());
61
62 tree.remove( 1 );
63 assertEquals( "[0]-->[2]-->NULL", getLinkedText());
64
65 tree.insert( 4 );
66 tree.insert( 3 );
67
68 assertEquals( "[0]-->[2]-->[4]-->[3]-->NULL", getLinkedText());
69
70 tree.remove( 0 );
71 assertEquals( "[2]-->[4]-->[3]-->NULL", getLinkedText());
72
73 tree.remove( 3 );
74 assertEquals( "[2]-->[4]-->NULL", getLinkedText());
75 }
76
77 private String getLinkedText()
78 {
79 LinkedBinaryNode<Integer> first = tree.getFirst();
80 StringBuilder sb = new StringBuilder();
81
82 while( first != null )
83 {
84 sb.append( first )
85 .append( "-->" );
86
87 first = first.next;
88 }
89 sb.append( "NULL" );
90 return sb.toString();
91 }
92 }