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.avltree;
21  
22  import static junit.framework.Assert.assertEquals;
23  import static org.junit.Assert.assertFalse;
24  import static org.junit.Assert.assertNotNull;
25  import static org.junit.Assert.assertNull;
26  import static org.junit.Assert.assertTrue;
27  
28  import java.util.ArrayList;
29  import java.util.Comparator;
30  import java.util.List;
31  
32  import org.junit.Before;
33  import org.junit.Test;
34  import org.slf4j.Logger;
35  import org.slf4j.LoggerFactory;
36  
37  /**
38   * An AVL tree testcase.
39   *
40   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
41   * @version $Rev$, $Date$
42   */
43  public class AvlTreeTest
44  {
45  
46      AvlTree<Integer> tree;
47  
48      private static final Logger LOG = LoggerFactory.getLogger( AvlTreeTest.class );
49      
50      @Before
51      public void createTree()
52      {
53        tree = new AvlTree<Integer>( new Comparator<Integer>() 
54            {
55  
56              public int compare( Integer i1, Integer i2 )
57              {
58                  return i1.compareTo( i2 );
59              }
60            
61            });  
62      }
63      
64      
65      @Test
66      public void testEmpty()
67      {
68        assertTrue( tree.isEmpty() );
69        assertNull( tree.getFirst() );
70        assertNull( tree.getLast() );
71        
72        tree.remove( 97 ); // remove a non-existing key
73        assertTrue( tree.isEmpty() );
74        
75        if( LOG.isDebugEnabled() ) 
76        {
77            tree.printTree();
78        }
79      }
80      
81      
82      @Test 
83      public void testFirstAndLast()
84      {
85          tree.insert( 7 );
86          assertFalse( tree.isEmpty() );
87          assertNotNull( tree.getFirst() );
88          assertNotNull( tree.getLast() );
89          
90          tree.insert( 10 );
91          assertEquals( 2, tree.getSize() );
92          assertNotNull( tree.getFirst() );
93          assertNotNull( tree.getLast() );
94          assertFalse( tree.getFirst().equals( tree.getLast() ) );
95          assertTrue( tree.getFirst().getKey().equals( 7 ) );
96          assertTrue( tree.getLast().getKey().equals( 10 ) );
97          
98          tree.insert( 3 );
99          assertTrue( tree.getFirst().getKey().equals( 3 ) );
100         assertTrue( tree.getLast().getKey().equals( 10 ) );
101         
102         tree.insert( 11 );
103         assertTrue( tree.getFirst().getKey().equals( 3 ) );
104         assertTrue( tree.getLast().getKey().equals( 11 ) );
105     }
106     
107     
108     @Test
109     public void testInsert()
110     {
111         assertNull( tree.insert( 3 ) );
112         assertFalse( tree.isEmpty() );
113         
114         assertTrue( 3 == tree.insert( 3 ) );// should be ignored
115         assertTrue( 1 == tree.getSize() );
116 
117         assertNotNull( tree.getFirst() );
118         assertNotNull( tree.getLast() );
119         assertTrue( tree.getFirst() == tree.getLast() );
120         
121         tree.remove( 3 );
122         
123         tree.insert( 37 );
124         tree.insert( 70 );
125         tree.insert( 12 );
126         assertTrue( 3 == tree.getSize() );
127         
128         tree.insert( 90 );
129         tree.insert( 25 );
130         tree.insert( 99 );
131         tree.insert( 91 );
132         tree.insert( 24 );
133         tree.insert( 28 );
134         tree.insert( 26 );
135         
136         if( LOG.isDebugEnabled() ) 
137         {
138             tree.printTree();
139         }
140         
141         tree.remove( 24 ); // this causes a single left rotation on node with key 12
142         if( LOG.isDebugEnabled() ) 
143         { 
144             tree.printTree();
145         }
146         assertTrue( tree.getRoot().getLeft().key == 26 );
147     }
148     
149     
150     @Test
151     public void testSingleRightRotation()
152     {
153      // right rotation
154       tree.insert( 3 );
155       tree.insert( 2 );
156       tree.insert( 1 );
157       
158       assertEquals("1,2,3", getInorderForm());
159     }
160 
161     @Test
162     public void testSingleLeftRotation()
163     {
164      // left rotation
165       tree.insert( 1 );
166       tree.insert( 2 );
167       tree.insert( 3 );
168       
169       assertEquals("1,2,3", getInorderForm());
170     }
171 
172     
173     @Test
174     public void testDoubleLeftRotation() // left-right totation
175     {
176      // double left rotation
177       tree.insert( 1 );
178       tree.insert( 3 );
179       tree.insert( 2 );
180       
181       assertEquals("1,2,3", getInorderForm());
182     }
183     
184     @Test
185     public void testDoubleRightRotation() // right-left totation
186     {
187      // double left rotation
188       tree.insert( 3 );
189       tree.insert( 1 );
190       tree.insert( 2 );
191       assertEquals("1,2,3", getInorderForm());
192     }
193     
194     @Test
195     public void testLinks()
196     {
197         tree.insert( 37 );
198         tree.insert( 1 );
199         tree.insert( 2 );
200         tree.insert( 10 );
201         tree.insert( 11 );
202         tree.insert( 25 );
203         tree.insert( 5 );
204         
205         assertTrue( 1 == tree.getFirst().key );
206         assertTrue( 37 == tree.getLast().key );
207     }
208     
209     @Test
210     public void testRemove()
211     {
212         tree.insert( 3 );
213         tree.insert( 2 );
214         tree.insert( 1 );
215         
216         LOG.debug(getLinkedText());
217         tree.remove( 2 );
218         LOG.debug(getLinkedText());
219         assertEquals("1,3", getInorderForm());
220         
221         tree.remove( 1 );
222         assertEquals("3", getInorderForm());
223         assertTrue( 3 == tree.getRoot().key );
224         
225         assertNull( tree.remove( 777 ) );// key not present
226         assertTrue( 3 == tree.remove( 3 ) );
227         assertTrue(tree.isEmpty());
228         
229         tree.insert( 37 );
230         tree.insert( 39 );
231         tree.insert( 27 );
232         tree.insert( 38 );
233         tree.insert( 21 );
234         tree.insert( 26 );
235         tree.insert( 43 );
236         assertEquals( "21,26,27,37,38,39,43", getInorderForm() );
237 
238         tree.remove( 26 ); // remove a non-root non-leaf node in the left sub tree of root
239         assertEquals( "21,27,37,38,39,43", getInorderForm() );
240 
241         tree.remove( 43 );
242         assertEquals( "21,27,37,38,39", getInorderForm() );
243 
244         tree.remove( 39 );
245         assertEquals( "21,27,37,38", getInorderForm() );
246         
247         assertTrue( 37 == tree.getRoot().key ); // check the root value
248         
249         tree.remove( 38 ); // a double right rotation has to happen after this
250         assertTrue( 27 == tree.getRoot().key ); // check the root value after double right rotation
251         assertEquals( "21,27,37", getInorderForm() );
252         
253         if( LOG.isDebugEnabled() ) 
254         {
255             tree.printTree();
256         }
257     }
258 
259     @Test
260     public void testLinkedNodes()
261     {
262         for( int i=0; i< 3; i++)
263         {
264            tree.insert( i ); 
265         }
266         
267         assertEquals( "[0]-->[1]-->[2]-->NULL", getLinkedText());
268         
269         tree.remove( 1 );
270         assertEquals( "[0]-->[2]-->NULL", getLinkedText());
271         
272         tree.insert( 4 );
273         tree.insert( 3 );
274         
275         assertEquals( "[0]-->[2]-->[3]-->[4]-->NULL", getLinkedText());
276         
277         tree.remove( 0 );
278         assertEquals( "[2]-->[3]-->[4]-->NULL", getLinkedText());
279         
280         tree.remove( 3 );
281         assertEquals( "[2]-->[4]-->NULL", getLinkedText());
282     }
283     
284     @Test
285     public void testFind()
286     {
287         tree.insert( 1 );
288         tree.insert( 70 );
289         tree.insert( 21 );
290         tree.insert( 12 );
291         tree.insert( 27 );
292         tree.insert( 11 );
293         
294         assertNotNull( tree.find( 11 ) );
295         assertNull( tree.find( 0 ));
296         
297         tree.setRoot( null );
298         assertNull( tree.find( 3 ));
299     }
300     
301     @Test
302     public void testFindGreater()
303     {
304         assertNull( tree.findGreater( 1 ) );
305         
306         tree.insert( 1 );
307         assertNull( tree.findGreater( 1 ) );
308         
309         tree.insert( 0 );
310         tree.insert( 3 );
311         tree.insert( 7 );
312         tree.insert( 6 );
313         tree.insert( 2 );
314         tree.insert( 8 );
315         
316         assertFalse( 1 == tree.findGreater( 1 ).key );
317         assertTrue( 2 == tree.findGreater( 1 ).key );
318         assertTrue( 6 == tree.findGreater( 4 ).key );
319         assertNull( tree.findGreater( 8 ) );
320     }
321     
322     @Test
323     public void testFindLess()
324     {
325         assertNull( tree.findLess( 1 ) );
326         
327         tree.insert( 1 );
328         assertNull( tree.findLess( 1 ) );
329 
330         tree.insert( 2 );
331         tree.insert( 7 );
332         tree.insert( 3 );
333         tree.insert( 6 );
334         tree.insert( 0 );
335         tree.insert( 37 );
336         
337         assertFalse( 0 == tree.findLess( 5 ).key );
338         assertTrue( 3 == tree.findLess( 5 ).key );
339         assertTrue( 7 == tree.findLess( 8 ).key );
340         assertNull( tree.findLess( 0 ) );
341     }
342     
343     @Test
344     public void testFindMaxMin()
345     {
346         tree.insert( 72 );
347         tree.insert( 79 );
348         
349         tree.remove( 72 );// should call findMax internally
350         assertTrue( 79 == tree.getRoot().key );
351         
352         tree.insert( 11 );
353         tree.remove( 79 ); // should call findMin internally
354         assertTrue( 11 == tree.getRoot().key );
355     }
356     
357     @Test
358     public void testGetKeys()
359     {
360         tree.insert( 72 );
361         tree.insert( 79 );
362         tree.insert( 1 );
363         tree.insert( 2 );
364         tree.insert( 3 );
365         tree.insert( 7 );
366         tree.insert( 34 );
367         
368         assertTrue( 7 == tree.getKeys().size() );
369     }
370     
371     @Test
372     public void testTreeRoationAtLeftChildAfterDeletingRoot()
373     {
374         int[] keys = { 86, 110, 122, 2, 134, 26, 14, 182 }; // order is important to produce the expected tree
375         int[] expectedKeys = { 2, 14, 26, 86, 122, 134, 182 };
376         
377         for( int key:keys )
378         {
379             tree.insert( key );
380         }
381         
382         tree.remove( 110 );
383 
384         for ( int key : expectedKeys )
385         {
386             assertNotNull( "Should find " + key, tree.find( key ) );
387         }
388     }
389     
390 
391     @Test
392     public void testDetachNodesAtLeftChildAfterDeletingRoot()
393     {
394         int[] keys = { 110, 122, 2, 134, 86, 14, 26, 182 }; // order is important to produce the expected tree
395         
396         for( int key:keys )
397         {
398             tree.insert( key );
399         }
400 
401         tree.remove( 110 );
402         
403         assertEquals( 26, ( int ) tree.find( 14 ).right.key );
404     }
405 
406 
407     @Test
408     public void testRemoveInRightSubtree()
409     {
410         int[] keys = { 8, 4, 13, 6, 15, 7, 10, 5, 14, 2, 11, 3, 9, 1 }; // order is important to produce the expected tree
411         
412         for( int key:keys )
413         {
414             tree.insert( key );
415         }
416 
417         tree.remove( 13 );
418         
419         assertEquals( 11, ( int ) tree.find( 8 ).right.key );
420     }
421 
422    
423     @Test
424     public void testRemoveInLeftSubtree()
425     {
426         int[] keys = { 8, 4, 12, 6, 7, 16, 10, 5, 11, 9, 17, 5, 14, 2, 13, 1, 3 }; // order is important to produce the expected tree
427         
428         for( int key:keys )
429         {
430             tree.insert( key );
431         }
432 
433         tree.remove( 16 );
434 
435         assertEquals( 8, ( int ) tree.getRoot().key );
436         assertEquals( 12, ( int ) tree.getRoot().right.key );
437         assertEquals( 14, ( int ) tree.getRoot().right.right.key );
438         assertEquals( 13, ( int ) tree.find( 14 ).left.key );
439     }
440     
441     
442     private String getLinkedText() 
443     {
444         LinkedAvlNode<Integer> first = tree.getFirst();
445         StringBuilder sb = new StringBuilder();
446         
447         while( first != null )
448         {
449             sb.append( first )
450               .append( "-->" );
451             
452             first = first.next;
453         }
454         sb.append( "NULL" );
455         return sb.toString();
456     }
457     
458     private String getInorderForm()
459     {
460       StringBuilder sb = new StringBuilder();
461       List<LinkedAvlNode<Integer>> path = new ArrayList<LinkedAvlNode<Integer>>();
462       
463       traverse( tree.getRoot(), path );
464       int i;
465       for( i=0; i < path.size() -1; i++ )
466       {
467           sb.append( path.get( i ).key )
468             .append( ',' );
469       }
470       
471       sb.append( path.get( i ).key );
472       
473       return sb.toString();
474     }
475     
476     private void traverse( LinkedAvlNode<Integer> startNode, List<LinkedAvlNode<Integer>> path )
477     {
478       //1. pre-order
479         
480       if( startNode.left != null )
481       {
482           traverse( startNode.left, path );
483       }
484       
485       path.add( startNode ); //2. in-order NOTE: change this line's position to change the type of traversal
486 
487       if( startNode.right != null )
488       {
489          traverse( startNode.right, path ); 
490       }
491       //3. post-order
492     }
493 }