View Javadoc

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  
23  import java.util.Comparator;
24  
25  
26  /**
27   * A generified, top-down, linked, in memory, splay tree implementation. This 
28   * is an adaptation of the <a href="mailto:sleator@cs.cmu.edu">Danny Sleator's
29   * </a> non-linked implementation <b><a href="http://tinyurl.com/2xs3fl">here
30   * </a></b>.
31   *
32   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
33   * @version $Rev: 602753 $
34   */
35  public class SplayTree<K>
36  {
37      private LinkedBinaryNode<K> header = new LinkedBinaryNode<K>( null ); // For splay
38  
39      private LinkedBinaryNode<K> root;
40      private Comparator<K> keyComparator;
41  
42      private LinkedBinaryNode<K> first, last;
43      
44      public SplayTree( Comparator<K> keyComparator )
45      {
46          this.keyComparator = keyComparator;
47          root = null;
48      }
49  
50  
51      /**
52       * Insert into the tree.
53       * @param x the item to insert.
54       * @throws DuplicateItemException if x is already present.
55       */
56      public void insert( K key )
57      {
58          LinkedBinaryNode<K> n;
59          int c;
60          if ( root == null )
61          {
62              root = new LinkedBinaryNode<K>( key );
63              first = root;
64              return;
65          }
66          splay( key );
67          if ( ( c = keyComparator.compare( key, root.key ) ) == 0 )
68          {
69              //      throw new DuplicateItemException( x.toString() );     
70              return;
71          }
72          n = new LinkedBinaryNode<K>( key );
73          
74          if( last == null )
75          {
76            first.next = n;
77  	      n.previous = first;
78          }
79          else
80          {
81          	last.next = n;
82          	n.previous = last;
83          }
84          
85          last = n;
86          
87          if ( c < 0 )
88          {
89              n.left = root.left;
90              n.right = root;
91              root.left = null;
92          }
93          else
94          {
95              n.right = root.right;
96              n.left = root;
97              root.right = null;
98          }
99          root = n;
100     }
101 
102 
103     /**
104      * Remove from the tree.
105      * @param x the item to remove.
106      * @throws ItemNotFoundException if x is not found.
107      */
108     public void remove( K key )
109     {
110         LinkedBinaryNode<K> temp = null;
111         LinkedBinaryNode<K> deleteNode;
112         
113         splay( key );
114 
115         deleteNode = root; // splay makes the node with key 'key' as root 
116 
117         if ( keyComparator.compare( key, root.key ) != 0 )
118         {
119             //            throw new ItemNotFoundException(x.toString());
120             return;
121         }
122         // Now delete the root
123         if ( root.left == null )
124         {
125             root = root.right;
126         }
127         else
128         {
129             temp = root.right;
130             root = root.left;
131             splay( key );
132             root.right = temp;
133         }
134         
135         if( deleteNode == first )
136         {
137         	temp = first.next;
138         	
139         	if( temp != null )
140         	{
141         		first = temp;
142         	}
143         	else
144         	{
145         		first = last = null;
146         	}
147         	
148         }
149         else if( deleteNode == last )
150         {
151         	temp = last.previous;
152        		temp.next = null;
153        		
154         	last = temp;
155         }
156         else
157         {
158             temp = first.next;
159             
160             while( temp != null )
161             {
162                 if( temp == deleteNode )
163                 {
164                   temp.previous.next = temp.next;
165                   temp.next.previous = temp.previous;
166                   temp = null;
167                   break;
168                 }
169                 
170                 temp = temp.next;
171             }
172         }
173     }
174 
175 
176     /**
177      * Find the smallest item in the tree.
178      */
179     public K findMin()
180     {
181         LinkedBinaryNode<K> x = root;
182         if ( root == null )
183             return null;
184         while ( x.left != null )
185             x = x.left;
186         splay( x.key );
187         return x.key;
188     }
189 
190 
191     /**
192      * Find the largest item in the tree.
193      */
194     public K findMax()
195     {
196         LinkedBinaryNode<K> x = root;
197         if ( root == null )
198             return null;
199         while ( x.right != null )
200             x = x.right;
201         splay( x.key );
202         return x.key;
203     }
204 
205 
206     /**
207      * Find an item in the tree.
208      */
209     public K find( K key )
210     {
211         if ( root == null )
212         {
213             return null;
214         }
215         
216         splay( key );
217         
218         if ( keyComparator.compare( root.key, key ) != 0 )
219         {
220             return null;
221         }
222         
223         return root.key;
224     }
225 
226 
227     /**
228      * Test if the tree is logically empty.
229      * @return true if empty, false otherwise.
230      */
231     public boolean isEmpty()
232     {
233         return root == null;
234     }
235 
236 
237     public LinkedBinaryNode<K> getFirst()
238     {
239         return first;
240     }
241 
242 
243     public LinkedBinaryNode<K> getLast()
244     {
245         return last;
246     }
247 
248 
249     /** this method just illustrates the top-down method of
250      * implementing the move-to-root operation 
251      */
252     @SuppressWarnings("unused")
253     private void moveToRoot( K key )
254     {
255         LinkedBinaryNode<K> l, r, t;
256         l = r = header;
257         t = root;
258         header.left = header.right = null;
259         for ( ;; )
260         {
261             if ( keyComparator.compare( key, t.key ) < 0 )
262             {
263                 if ( t.left == null )
264                     break;
265                 r.left = t; /* link right */
266                 r = t;
267                 t = t.left;
268             }
269             else if ( keyComparator.compare( key, t.key ) > 0 )
270             {
271                 if ( t.right == null )
272                     break;
273                 l.right = t; /* link left */
274                 l = t;
275                 t = t.right;
276             }
277             else
278             {
279                 break;
280             }
281         }
282         l.right = t.left; /* assemble */
283         r.left = t.right;
284         t.left = header.right;
285         t.right = header.left;
286         root = t;
287     }
288 
289 
290     /**
291      * Internal method to perform a top-down splay.
292      * 
293      *   splay(key) does the splay operation on the given key.
294      *   If key is in the tree, then the LinkedBinaryNode containing
295      *   that key becomes the root.  If key is not in the tree,
296      *   then after the splay, key.root is either the greatest key
297      *   < key in the tree, or the lest key > key in the tree.
298      *
299      *   This means, among other things, that if you splay with
300      *   a key that's larger than any in the tree, the rightmost
301      *   node of the tree becomes the root.  This property is used
302      *   in the delete() method.
303      */
304 
305     private void splay( K key )
306     {
307         LinkedBinaryNode<K> l, r, t, y;
308         l = r = header;
309         t = root;
310         header.left = header.right = null;
311         for ( ;; )
312         {
313             if ( keyComparator.compare( key, t.key ) < 0 )
314             {
315                 if ( t.left == null )
316                     break;
317                 if ( keyComparator.compare( key, t.left.key ) < 0 )
318                 {
319                     y = t.left; /* rotate right */
320                     t.left = y.right;
321                     y.right = t;
322                     t = y;
323                     if ( t.left == null )
324                         break;
325                 }
326                 r.left = t; /* link right */
327                 r = t;
328                 t = t.left;
329             }
330             else if ( keyComparator.compare( key, t.key ) > 0 )
331             {
332                 if ( t.right == null )
333                     break;
334                 if ( keyComparator.compare( key, t.right.key ) > 0 )
335                 {
336                     y = t.right; /* rotate left */
337                     t.right = y.left;
338                     y.left = t;
339                     t = y;
340                     if ( t.right == null )
341                         break;
342                 }
343                 l.right = t; /* link left */
344                 l = t;
345                 t = t.right;
346             }
347             else
348             {
349                 break;
350             }
351         }
352         l.right = t.left; /* assemble */
353         r.left = t.right;
354         t.left = header.right;
355         t.right = header.left;
356         root = t;
357     }
358 
359 
360     public LinkedBinaryNode<K> getRoot() {
361 		return root;
362 	}
363 
364 
365     /**
366      * Prints the contents of splay tree in pretty format
367      */
368     public void printTree() {
369     	
370     	if( isEmpty() )
371     	{
372     		System.out.println( "Tree is empty" );
373     		return;
374     	}
375     	
376 		getRoot().setDepth( 0 );
377 
378 		System.out.println( getRoot() );
379 		
380 		visit( getRoot().getRight(), getRoot() );
381 		
382 		visit( getRoot().getLeft(), getRoot() );
383 	}
384 	
385 	private void visit( LinkedBinaryNode<K> node, LinkedBinaryNode<K> parentNode ) 
386 	{
387 		if( node == null )
388 		{
389 			return;
390 		}
391 		
392 		if( !node.isLeaf() )
393 		{
394 			node.setDepth( parentNode.getDepth() + 1 );
395 		}
396 		
397 		for( int i=0; i < parentNode.getDepth(); i++ )
398 		{
399 			System.out.print( "|  " );
400 		}
401 
402 		System.out.println( "|--" + node );
403 		
404 		if ( node.getRight() != null )
405 		{
406 			visit( node.getRight(), node );
407 		}
408 		
409 		if( node.getLeft() != null )
410 		{
411 			visit( node.getLeft(), node );
412 		}
413 	}
414 
415 	// test code stolen from Weiss
416     public static void main( String[] args )
417     {
418         SplayTree<Integer> t = new SplayTree<Integer>( new Comparator<Integer>() 
419         {
420             public int compare( Integer i1, Integer i2 )
421             {
422                 return i1.compareTo( i2 );
423             }
424         });
425         final int NUMS = 40000;
426         final int GAP = 307;
427 
428         System.out.println( "Checking... (no bad output means success)" );
429 
430         for ( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
431             t.insert( new Integer( i ) );
432         System.out.println( "Inserts complete" );
433 
434         for ( int i = 1; i < NUMS; i += 2 )
435             t.remove( new Integer( i ) );
436         System.out.println( "Removes complete" );
437 
438         if ( ( ( Integer ) ( t.findMin() ) ).intValue() != 2 || ( ( Integer ) ( t.findMax() ) ).intValue() != NUMS - 2 )
439             System.out.println( "FindMin or FindMax error!" );
440 
441         for ( int i = 2; i < NUMS; i += 2 )
442             if ( ( ( Integer ) t.find( new Integer( i ) ) ).intValue() != i )
443                 System.out.println( "Error: find fails for " + i );
444 
445         for ( int i = 1; i < NUMS; i += 2 )
446             if ( t.find( new Integer( i ) ) != null )
447                 System.out.println( "Error: Found deleted item " + i );
448     }
449 
450 }