KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > store > access > sort > SortBuffer


1 /*
2
3    Derby - Class org.apache.derby.impl.store.access.sort.SortBuffer
4
5    Licensed to the Apache Software Foundation (ASF) under one or more
6    contributor license agreements. See the NOTICE file distributed with
7    this work for additional information regarding copyright ownership.
8    The ASF licenses this file to you under the Apache License, Version 2.0
9    (the "License"); you may not use this file except in compliance with
10    the License. You may obtain a copy of the License at
11
12       http://www.apache.org/licenses/LICENSE-2.0
13
14    Unless required by applicable law or agreed to in writing, software
15    distributed under the License is distributed on an "AS IS" BASIS,
16    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17    See the License for the specific language governing permissions and
18    limitations under the License.
19
20  */
21
22 package org.apache.derby.impl.store.access.sort;
23
24 import org.apache.derby.iapi.services.sanity.SanityManager;
25 import org.apache.derby.iapi.error.StandardException;
26 import org.apache.derby.iapi.store.access.SortObserver;
27
28 import org.apache.derby.iapi.types.DataValueDescriptor;
29
30 /**
31
32   This class implements an in-memory ordered set
33   based on the balanced binary tree algorithm from
34   Knuth Vol. 3, Sec. 6.2.3, pp. 451-471.
35   Nodes are always maintained in order,
36   so that inserts and deletes can be intermixed.
37   <P>
38   This algorithm will insert/delete N elements
39   in O(N log(N)) time using O(N) space.
40
41 **/
42
43 class SortBuffer
44 {
45     /**
46     Returned from insert when the row was inserted
47     without incident.
48     **/
49     public static final int INSERT_OK = 0;
50
51     /**
52     Returned from insert when the row which was
53     inserted was a duplicate. The set will have
54     aggregated it in.
55     **/
56     public static final int INSERT_DUPLICATE = 1;
57
58     /**
59     Returned from insert when the row was not able to be
60     inserted because the set was full.
61     **/
62     public static final int INSERT_FULL = 2;
63
64     /**
65     The sort this set is associated with.
66     **/
67     private MergeSort sort;
68
69     /**
70     Where to allocate nodes from.
71     **/
72     private NodeAllocator allocator = null;
73
74     /**
75     Special head node for the tree. Head.rightLink is the
76     root of the tree.
77     **/
78     private Node head = null;
79
80     /**
81     The current height of the tree.
82     **/
83     private int height = 0;
84
85     /**
86     Set, as a side effect of deleteLeftMost (only), to the
87     key from the node that was deleted from the tree. This
88     field is only valid after a call to deleteLeftMost.
89     **/
90     private DataValueDescriptor[] deletedKey;
91
92     /**
93     Set, as a side effect of deleteLeftMost and rotateRight,
94     if the subtree they're working on decreased in height.
95     This field is only valid after a call to deleteLeftMost
96     or rotateRight.
97     **/
98     private boolean subtreeShrunk;
99
100     /**
101     Set by the setNextAux() method. This value is stuffed
102     into the aux field of the next node that's allocated.
103     **/
104     private int nextAux;
105
106     /**
107     Read by the getLastAux() method. This value is read out
108     of the last node that was deallocated from the tree.
109     **/
110     private int lastAux;
111
112     /**
113     Arrange that the next node allocated in the tree have
114     it's aux field set to the argument.
115     **/
116     public void setNextAux(int aux)
117     {
118         nextAux = aux;
119     }
120
121     /**
122     Retrieve the aux value from the last node deallocated
123     from the tree.
124     **/
125     public int getLastAux()
126     {
127         return lastAux;
128     }
129
130     /**
131     Construct doesn't do anything, callers must call init
132     and check its return code.
133     **/
134     public SortBuffer(MergeSort sort)
135     {
136         this.sort = sort;
137     }
138
139     /**
140     Initialize. Returns false if the allocator
141     couldn't be initialized.
142     **/
143     public boolean init()
144     {
145         allocator = new NodeAllocator();
146
147         boolean initOK = false;
148
149         if (sort.sortBufferMin > 0)
150             initOK = allocator.init(sort.sortBufferMin, sort.sortBufferMax);
151         else
152             initOK = allocator.init(sort.sortBufferMax);
153
154         if (initOK == false)
155         {
156             allocator = null;
157             return false;
158         }
159         reset();
160         return true;
161     }
162
163     public void reset()
164     {
165         allocator.reset();
166         head = allocator.newNode();
167         height = 0;
168     }
169
170     public void close()
171     {
172         if (allocator != null)
173             allocator.close();
174         allocator = null;
175         height = 0;
176         head = null;
177     }
178
179     /**
180     Grow by a certain percent if we can
181     */
182     public void grow(int percent)
183     {
184         if (percent > 0)
185             allocator.grow(percent);
186     }
187
188
189     /**
190     Return the number of elements this sorter can sort.
191     It's the capacity of the node allocator minus one
192     because the sorter uses one node for the head.
193     **/
194     public int capacity()
195     {
196         if (allocator == null)
197             return 0;
198         return allocator.capacity() - 1;
199     }
200
201     /**
202     Insert a key k into the tree. Returns true if the
203     key was inserted, false if the tree is full. Silently
204     ignores duplicate keys.
205     <P>
206     See Knuth Vol. 3, Sec. 6.2.3, pp. 455-457 for the algorithm.
207     **/
208     public int insert(DataValueDescriptor[] k)
209         throws StandardException
210     {
211         int c;
212         Node p, q, r, s, t;
213
214         if (head.rightLink == null)
215         {
216             if ((sort.sortObserver != null) &&
217                 ((k = sort.sortObserver.insertNonDuplicateKey(k)) == null))
218             {
219                 return INSERT_DUPLICATE;
220             }
221
222             q = allocator.newNode();
223             q.key = k;
224             q.aux = nextAux;
225             head.rightLink = q;
226             height = 1;
227             return INSERT_OK;
228         }
229
230         // [A1. Initialize]
231 t = head;
232         p = s = head.rightLink;
233
234         // Search
235 while (true)
236         {
237             // [A2. Compare]
238 c = sort.compare(k, p.key);
239             if (c == 0)
240             {
241                 // The new key compares equal to the
242 // current node's key.
243
244                 // See if we can use the aggregators
245 // to get rid of the new key.
246 if ((sort.sortObserver != null) &&
247                     ((k = sort.sortObserver.insertDuplicateKey(k, p.key)) == null))
248                 {
249                     return INSERT_DUPLICATE;
250                 }
251
252                 // Keep the duplicate key...
253 // Allocate a new node for the key.
254 q = allocator.newNode();
255                 if (q == null)
256                     return INSERT_FULL;
257                 q.aux = nextAux;
258
259                 // Link the new node onto the current
260 // node's duplicate chain. The assumption
261 // is made that a newly allocated node
262 // has null left and right links.
263 q.key = k;
264                 q.dupChain = p.dupChain;
265                 p.dupChain = q;
266
267                 // From the caller's perspective this was
268 // not a duplicate insertion.
269 return INSERT_OK;
270             }
271
272             if (c < 0)
273             {
274                 // [A3. Move left]
275 q = p.leftLink;
276                 if (q == null)
277                 {
278                     q = allocator.newNode();
279                     if (q == null)
280                         return INSERT_FULL;
281                     q.aux = nextAux;
282                     p.leftLink = q;
283                     break;
284                 }
285             }
286             else // c > 0
287 {
288                 // [A4. Move right]
289 q = p.rightLink;
290                 if (q == null)
291                 {
292                     q = allocator.newNode();
293                     if (q == null)
294                         return INSERT_FULL;
295                     q.aux = nextAux;
296                     p.rightLink = q;
297                     break;
298                 }
299             }
300
301             if (q.balance != 0)
302             {
303                 t = p;
304                 s = q;
305             }
306             p = q;
307         }
308
309         /*
310          * [A5. Insert]
311          * Node has been allocated and placed for k.
312          * Initialize it.
313          */
314
315         if ((sort.sortObserver != null) &&
316             ((k = sort.sortObserver.insertNonDuplicateKey(k)) == null))
317         {
318             return INSERT_DUPLICATE;
319         }
320         q.key = k;
321
322         /*
323          * [A6. Adjust balance factors for nodes between
324          * s and q]
325          */
326
327         c = sort.compare(k, s.key);
328         if (c < 0)
329             r = p = s.leftLink;
330         else
331             r = p = s.rightLink;
332
333         while (p != q)
334         {
335             if (sort.compare(k, p.key) < 0)
336             {
337                 p.balance = -1;
338                 p = p.leftLink;
339             }
340             else // sort.compare(k, p.key) > 0
341 {
342                 p.balance = 1;
343                 p = p.rightLink;
344             }
345         }
346
347         // [A7. Balancing act]
348
349         int a = (c > 0 ? 1 : ((c == 0) ? 0 : -1));
350
351         if (s.balance == 0)
352         {
353             //debug("A7 (i). The tree has gotten higher");
354 s.balance = a;
355             height++;
356             return INSERT_OK;
357         }
358
359         if (s.balance == -a)
360         {
361             //debug("A7 (ii). The tree has gotten more balanced");
362 s.balance = 0;
363             return INSERT_OK;
364         }
365
366         //debug("A7 (iii). The tree has gotten more out of balance");
367
368         // s.balance == a
369 if (r.balance == a)
370         {
371             //debug("A8. Single rotation");
372 p = r;
373             s.setLink(a, r.link(-a));
374             r.setLink(-a, s);
375             s.balance = 0;
376             r.balance = 0;
377         }
378         else // r.balance == -a
379 {
380             //debug("A8. Double rotation");
381 p = r.link(-a);
382             r.setLink(-a, p.link(a));
383             p.setLink(a, r);
384             s.setLink(a, p.link(-a));
385             p.setLink(-a, s);
386
387             if (p.balance == a)
388             {
389                 s.balance = -a;
390                 r.balance = 0;
391             }
392             else if (p.balance == 0)
393             {
394                 s.balance = 0;
395                 r.balance = 0;
396             }
397             else // p.balance == -a
398 {
399                 s.balance = 0;
400                 r.balance = a;
401             }
402
403             p.balance = 0;
404         }
405
406         // [A10. Finishing touch]
407 if (s == t.rightLink)
408             t.rightLink = p;
409         else
410             t.leftLink = p;
411
412         return INSERT_OK;
413     }
414
415     /**
416     Return the lowest key and delete it from
417     the tree, preserving the balance of the tree.
418     **/
419     public DataValueDescriptor[] removeFirst()
420     {
421         if (head.rightLink == null)
422             return null;
423         head.rightLink = deleteLeftmost(head.rightLink);
424         if (this.subtreeShrunk)
425             height--;
426         return this.deletedKey;
427     }
428
429     /**
430     Delete the node with the lowest key from the subtree defined
431     by 'thisNode', maintaining balance in the subtree. Returns
432     the node that should be the new root of the subtree. This
433     method sets this.subtreeShrunk if the subtree of thisNode
434     decreased in height. Saves the key that was in the deleted
435     node in 'deletedKey'.
436     **/
437     private Node deleteLeftmost(Node thisNode)
438     {
439         // If this node has no left child, we've found the
440 // leftmost one, so delete it.
441 if (thisNode.leftLink == null)
442         {
443
444             // See if the current node has duplicates. If so, we'll
445 // just return one of them and not change the tree.
446 if (thisNode.dupChain != null)
447             {
448                 Node dupNode = thisNode.dupChain;
449
450                 //System.out.println("deleteLeftmost(" + thisNode + "): found dup: " + dupNode);
451
452                 // Return the key from the duplicate. Note that even
453 // though the keys compare equal they may not be equal,
454 // depending on how the column ordering was specified.
455 this.deletedKey = dupNode.key;
456                 lastAux = dupNode.aux;
457
458                 // Unlink the dup node and free it.
459 thisNode.dupChain = dupNode.dupChain;
460                 allocator.freeNode(dupNode);
461                 dupNode = null;
462
463                 // Tree is not changing height since we're just removing
464 // a node from the duplicate chain.
465 this.subtreeShrunk = false;
466
467                 // Preserve the current node as the root of this subtree..
468 return thisNode;
469             }
470             else // thisNode.dupChain == null
471 {
472                 //System.out.println("deleteLeftmost(" + thisNode + "): found key");
473
474                 // Key to return is this node's key.
475 this.deletedKey = thisNode.key;
476                 lastAux = thisNode.aux;
477
478                 // We're removing this node, so it's subtree is shrinking
479 // from height 1 to height 0.
480 this.subtreeShrunk = true;
481
482                 // Save this node's right link which might be cleared
483 // out by the allocator.
484 Node newRoot = thisNode.rightLink;
485
486                 // Free the node we're deleting.
487 allocator.freeNode(thisNode);
488
489                 // Rearrange the tree to put this node's right subtree where
490 // this node was.
491 return newRoot;
492             }
493         }
494
495         // Since this wasn't the leftmost node, delete the leftmost
496 // node from this node's left subtree. This operation may
497 // rearrange the subtree, including the possiblility that the
498 // root note changed, so set the root of the left subtree to
499 // what the delete operation wants it to be.
500 thisNode.leftLink = deleteLeftmost(thisNode.leftLink);
501
502         // If the left subtree didn't change size, then this subtree
503 // could not have changed size either.
504 if (this.subtreeShrunk == false)
505             return thisNode;
506
507         // If the delete operation shrunk the subtree, we may have
508 // some rebalancing to do.
509
510         if (thisNode.balance == 1)
511         {
512             // Tree got more unbalanced. Need to do some
513 // kind of rotation to fix it. The rotateRight()
514 // method will set subtreeShrunk appropriately
515 // and return the node that should be the new
516 // root of this subtree.
517 return rotateRight(thisNode);
518         }
519
520         if (thisNode.balance == -1)
521         {
522             // Tree became more balanced
523 thisNode.balance = 0;
524
525             // Since the left subtree was higher, and it
526 // shrunk, then this subtree shrunk, too.
527 this.subtreeShrunk = true;
528         }
529         else // thisNode.balance == 0
530 {
531             // Tree became acceptably unbalanced
532 thisNode.balance = 1;
533
534             // We had a balanced tree, and just the left
535 // subtree shrunk, so this subtree as a whole
536 // has not changed in height.
537 this.subtreeShrunk = false;
538         }
539
540         // We have not rearranged this subtree.
541 return thisNode;
542     }
543
544     /**
545     Perform either a single or double rotation, as appropriate,
546     to get the subtree 'thisNode' back in balance, assuming
547     that the right subtree of 'thisNode' is higher than the
548     left subtree. Returns the node that should be the new
549     root of the subtree.
550     <P>
551     These are the cases depicted in diagrams (1) and (2) of
552     Knuth (p. 454), and the node names reflect these diagrams.
553     However, in deletion, the single rotation may encounter
554     a case where the "beta" and "gamma" subtrees are the same
555     height (b.balance == 0), so the resulting does not always
556     shrink.
557     <P>
558     Note: This code will not do the "mirror image" cases.
559     It only works when the right subtree is the higher one
560     (this is the only case encountered when deleting leftmost
561     nodes from the tree).
562     **/
563     private Node rotateRight(Node thisNode)
564     {
565         Node a = thisNode;
566         Node b = thisNode.rightLink;
567
568         if (b.balance >= 0)
569         {
570             // single rotation
571
572             a.rightLink = b.leftLink;
573             b.leftLink = a;
574
575             if (b.balance == 0)
576             {
577                 a.balance = 1;
578                 b.balance = -1;
579                 this.subtreeShrunk = false;
580             }
581             else // b.balance == 1
582 {
583                 a.balance = 0;
584                 b.balance = 0;
585                 this.subtreeShrunk = true;
586             }
587
588             return b;
589         }
590         else // b.balance == -1
591 {
592             // double rotation
593
594             Node x = b.leftLink;
595
596             a.rightLink = x.leftLink;
597             x.leftLink = a;
598             b.leftLink = x.rightLink;
599             x.rightLink = b;
600
601             if (x.balance == 1)
602             {
603                 a.balance = -1;
604                 b.balance = 0;
605             }
606             else if (x.balance == -1)
607             {
608                 a.balance = 0;
609                 b.balance = 1;
610             }
611             else // x.balance == 0
612 {
613                 a.balance = 0;
614                 b.balance = 0;
615             }
616             x.balance = 0;
617
618             this.subtreeShrunk = true;
619
620             return x;
621         }
622     }
623
624     public void check()
625     {
626         if (SanityManager.DEBUG)
627         {
628             String JavaDoc error = null;
629             if (head.rightLink == null)
630             {
631                 if (height != 0)
632                     error = "empty tree with height " + height;
633             }
634             else
635             {
636                 if (depth(head.rightLink) != height)
637                     error = "tree height " + height + " != depth " + depth(head.rightLink);
638                 else
639                     error = checkNode(head.rightLink);
640             }
641             if (error != null)
642             {
643                 System.out.println("ERROR: " + error);
644                 print();
645                 System.exit(1);
646             }
647         }
648     }
649
650     private String JavaDoc checkNode(Node n)
651     {
652         if (SanityManager.DEBUG)
653         {
654             if (n == null)
655                 return null;
656             int ld = depth(n.leftLink);
657             int rd = depth(n.rightLink);
658             if (n.balance != (rd - ld))
659                 return "node " + n + ": left height " + ld + " right height " + rd;
660             
661             String JavaDoc e;
662             e = checkNode(n.rightLink);
663             if (e == null)
664                 e = checkNode(n.leftLink);
665             return e;
666         }
667         else
668         {
669             return(null);
670         }
671     }
672
673     private int depth(Node n)
674     {
675         int ld = 0;
676         int rd = 0;
677         if (n == null)
678             return 0;
679         if (n.leftLink != null)
680             ld = depth(n.leftLink);
681         if (n.rightLink != null)
682             rd = depth(n.rightLink);
683         if (rd > ld)
684             return rd + 1;
685         else
686             return ld + 1;
687     }
688
689     public void print()
690     {
691         Node root = head.rightLink;
692         System.out.println("tree height: " + height
693             + " root: " + ((root == null) ? -1 : root.id));
694         if (root != null)
695             printRecursive(root, 0);
696     }
697
698     private void printRecursive(Node n, int depth)
699     {
700         if (n.rightLink != null)
701             printRecursive(n.rightLink, depth + 1);
702         for (int i = 0; i < depth; i++)
703             System.out.print(" ");
704         System.out.println(n);
705         if (n.leftLink != null)
706             printRecursive(n.leftLink, depth + 1);
707     }
708
709     private void debug(String JavaDoc s)
710     {
711         if (SanityManager.DEBUG)
712         {
713             System.out.println(" === [" + s + "] ===");
714         }
715     }
716 }
717
Popular Tags