1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
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 * Tests the linking of <code>LinkedBinaryNode</code>s present in the splay tree.
31 *
32 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
33 * @version $Rev$, $Date$
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 }