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
23 import java.util.Comparator;
24
25
26
27
28
29
30
31
32
33
34
35 public class SplayTree<K>
36 {
37 private LinkedBinaryNode<K> header = new LinkedBinaryNode<K>( null );
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
53
54
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
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
105
106
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;
116
117 if ( keyComparator.compare( key, root.key ) != 0 )
118 {
119
120 return;
121 }
122
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
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
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
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
229
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
250
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;
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;
274 l = t;
275 t = t.right;
276 }
277 else
278 {
279 break;
280 }
281 }
282 l.right = t.left;
283 r.left = t.right;
284 t.left = header.right;
285 t.right = header.left;
286 root = t;
287 }
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
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;
320 t.left = y.right;
321 y.right = t;
322 t = y;
323 if ( t.left == null )
324 break;
325 }
326 r.left = t;
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;
337 t.right = y.left;
338 y.left = t;
339 t = y;
340 if ( t.right == null )
341 break;
342 }
343 l.right = t;
344 l = t;
345 t = t.right;
346 }
347 else
348 {
349 break;
350 }
351 }
352 l.right = t.left;
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
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
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 }