Java > Open Source Codes > org > apache > poi > util > BinaryTree


1
2 /* ====================================================================
3    Copyright 2002-2004 Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16 ==================================================================== */
17         
18
19 package org.apache.poi.util;
20
21 import java.util.*;
22
23 /**
24  * Red-Black tree-based implementation of Map. This class guarantees
25  * that the map will be in both ascending key order and ascending
26  * value order, sorted according to the natural order for the key's
27  * and value's classes.<p>
28  *
29  * This Map is intended for applications that need to be able to look
30  * up a key-value pairing by either key or value, and need to do so
31  * with equal efficiency.<p>
32  *
33  * While that goal could be accomplished by taking a pair of TreeMaps
34  * and redirecting requests to the appropriate TreeMap (e.g.,
35  * containsKey would be directed to the TreeMap that maps values to
36  * keys, containsValue would be directed to the TreeMap that maps keys
37  * to values), there are problems with that implementation,
38  * particularly when trying to keep the two TreeMaps synchronized with
39  * each other. And if the data contained in the TreeMaps is large, the
40  * cost of redundant storage becomes significant.<p>
41  *
42  * This solution keeps the data properly synchronized and minimizes
43  * the data storage. The red-black algorithm is based on TreeMap's,
44  * but has been modified to simultaneously map a tree node by key and
45  * by value. This doubles the cost of put operations (but so does
46  * using two TreeMaps), and nearly doubles the cost of remove
47  * operations (there is a savings in that the lookup of the node to be
48  * removed only has to be performed once). And since only one node
49  * contains the key and value, storage is significantly less than that
50  * required by two TreeMaps.<p>
51  *
52  * There are some limitations placed on data kept in this Map. The
53  * biggest one is this:<p>
54  *
55  * When performing a put operation, neither the key nor the value may
56  * already exist in the Map. In the java.util Map implementations
57  * (HashMap, TreeMap), you can perform a put with an already mapped
58  * key, and neither cares about duplicate values at all ... but this
59  * implementation's put method with throw an IllegalArgumentException
60  * if either the key or the value is already in the Map.<p>
61  *
62  * Obviously, that same restriction (and consequence of failing to
63  * heed that restriction) applies to the putAll method.<p>
64  *
65  * The Map.Entry instances returned by the appropriate methods will
66  * not allow setValue() and will throw an
67  * UnsupportedOperationException on attempts to call that method.<p>
68  *
69  * New methods are added to take advantage of the fact that values are
70  * kept sorted independently of their keys:<p>
71  *
72  * Object getKeyForValue(Object value) is the opposite of get; it
73  * takes a value and returns its key, if any.<p>
74  *
75  * Object removeValue(Object value) finds and removes the specified
76  * value and returns the now un-used key.<p>
77  *
78  * Set entrySetByValue() returns the Map.Entry's in a Set whose
79  * iterator will iterate over the Map.Entry's in ascending order by
80  * their corresponding values.<p>
81  *
82  * Set keySetByValue() returns the keys in a Set whose iterator will
83  * iterate over the keys in ascending order by their corresponding
84  * values.<p>
85  *
86  * Collection valuesByValue() returns the values in a Collection whose
87  * iterator will iterate over the values in ascending order.<p>
88  *
89  * @author Marc Johnson (mjohnson at apache dot org)
90  */
91 public final class BinaryTree // final for performance
92
93     extends AbstractMap
94 {
95     private Node[] _root = new Node[]
96     {
97         null, null
98     };
99     private int _size = 0;
100     private int _modifications = 0;
101     private Set[] _key_set = new Set[]
102     {
103         null, null
104     };
105     private Set[] _entry_set = new Set[]
106     {
107         null, null
108     };
109     private Collection[] _value_collection = new Collection[]
110     {
111         null, null
112     };
113     private static final int _KEY = 0;
114     private static final int _VALUE = 1;
115     private static final int _INDEX_SUM = _KEY + _VALUE;
116     private static final int _MINIMUM_INDEX = 0;
117     private static final int _INDEX_COUNT = 2;
118     private static final String [] _data_name = new String []
119     {
120         "key", "value"
121     };
122
123     /**
124      * Construct a new BinaryTree
125      */
126
127     public BinaryTree()
128     {
129     }
130
131     /**
132      * Constructs a new BinaryTree from an existing Map, with keys and
133      * values sorted
134      *
135      * @param map the map whose mappings are to be placed in this map.
136      *
137      * @exception ClassCastException if the keys in the map are not
138      * Comparable, or are not mutually
139      * comparable; also if the values in
140      * the map are not Comparable, or
141      * are not mutually Comparable
142      * @exception NullPointerException if any key or value in the map
143      * is null
144      * @exception IllegalArgumentException if there are duplicate keys
145      * or duplicate values in the
146      * map
147      */
148
149     public BinaryTree(final Map map)
150         throws ClassCastException , NullPointerException ,
151                 IllegalArgumentException
152     {
153         putAll(map);
154     }
155
156     /**
157      * Returns the key to which this map maps the specified value.
158      * Returns null if the map contains no mapping for this value.
159      *
160      * @param value value whose associated key is to be returned.
161      *
162      * @return the key to which this map maps the specified value, or
163      * null if the map contains no mapping for this value.
164      *
165      * @exception ClassCastException if the value is of an
166      * inappropriate type for this map.
167      * @exception NullPointerException if the value is null
168      */
169
170     public Object getKeyForValue(final Object value)
171         throws ClassCastException , NullPointerException
172     {
173         return doGet(( Comparable ) value, _VALUE);
174     }
175
176     /**
177      * Removes the mapping for this value from this map if present
178      *
179      * @param value value whose mapping is to be removed from the map.
180      *
181      * @return previous key associated with specified value, or null
182      * if there was no mapping for value.
183      */
184
185     public Object removeValue(final Object value)
186     {
187         return doRemove(( Comparable ) value, _VALUE);
188     }
189
190     /**
191      * Returns a set view of the mappings contained in this map. Each
192      * element in the returned set is a Map.Entry. The set is backed
193      * by the map, so changes to the map are reflected in the set, and
194      * vice-versa. If the map is modified while an iteration over the
195      * set is in progress, the results of the iteration are
196      * undefined. The set supports element removal, which removes the
197      * corresponding mapping from the map, via the Iterator.remove,
198      * Set.remove, removeAll, retainAll and clear operations. It does
199      * not support the add or addAll operations.<p>
200      *
201      * The difference between this method and entrySet is that
202      * entrySet's iterator() method returns an iterator that iterates
203      * over the mappings in ascending order by key. This method's
204      * iterator method iterates over the mappings in ascending order
205      * by value.
206      *
207      * @return a set view of the mappings contained in this map.
208      */
209
210     public Set entrySetByValue()
211     {
212         if (_entry_set[ _VALUE ] == null)
213         {
214             _entry_set[ _VALUE ] = new AbstractSet()
215             {
216                 public Iterator iterator()
217                 {
218                     return new BinaryTreeIterator(_VALUE)
219                     {
220                         protected Object doGetNext()
221                         {
222                             return _last_returned_node;
223                         }
224                     };
225                 }
226
227                 public boolean contains(Object o)
228                 {
229                     if (!(o instanceof Map.Entry))
230                     {
231                         return false;
232                     }
233                     Map.Entry entry = ( Map.Entry ) o;
234                     Object key = entry.getKey();
235                     Node node = lookup(( Comparable ) entry.getValue(),
236                                              _VALUE);
237
238                     return (node != null) && node.getData(_KEY).equals(key);
239                 }
240
241                 public boolean remove(Object o)
242                 {
243                     if (!(o instanceof Map.Entry))
244                     {
245                         return false;
246                     }
247                     Map.Entry entry = ( Map.Entry ) o;
248                     Object key = entry.getKey();
249                     Node node = lookup(( Comparable ) entry.getValue(),
250                                              _VALUE);
251
252                     if ((node != null) && node.getData(_KEY).equals(key))
253                     {
254                         doRedBlackDelete(node);
255                         return true;
256                     }
257                     return false;
258                 }
259
260                 public int size()
261                 {
262                     return BinaryTree.this.size();
263                 }
264
265                 public void clear()
266                 {
267                     BinaryTree.this.clear();
268                 }
269             };
270         }
271         return _entry_set[ _VALUE ];
272     }
273
274     /**
275      * Returns a set view of the keys contained in this map. The set
276      * is backed by the map, so changes to the map are reflected in
277      * the set, and vice-versa. If the map is modified while an
278      * iteration over the set is in progress, the results of the
279      * iteration are undefined. The set supports element removal,
280      * which removes the corresponding mapping from the map, via the
281      * Iterator.remove, Set.remove, removeAll, retainAll, and clear
282      * operations. It does not support the add or addAll
283      * operations.<p>
284      *
285      * The difference between this method and keySet is that keySet's
286      * iterator() method returns an iterator that iterates over the
287      * keys in ascending order by key. This method's iterator method
288      * iterates over the keys in ascending order by value.
289      *
290      * @return a set view of the keys contained in this map.
291      */
292
293     public Set keySetByValue()
294     {
295         if (_key_set[ _VALUE ] == null)
296         {
297             _key_set[ _VALUE ] = new AbstractSet()
298             {
299                 public Iterator iterator()
300                 {
301                     return new BinaryTreeIterator(_VALUE)
302                     {
303                         protected Object doGetNext()
304                         {
305                             return _last_returned_node.getData(_KEY);
306                         }
307                     };
308                 }
309
310                 public int size()
311                 {
312                     return BinaryTree.this.size();
313                 }
314
315                 public boolean contains(Object o)
316                 {
317                     return containsKey(o);
318                 }
319
320                 public boolean remove(Object o)
321                 {
322                     int old_size = _size;
323
324                     BinaryTree.this.remove(o);
325                     return _size != old_size;
326                 }
327
328                 public void clear()
329                 {
330                     BinaryTree.this.clear();
331                 }
332             };
333         }
334         return _key_set[ _VALUE ];
335     }
336
337     /**
338      * Returns a collection view of the values contained in this
339      * map. The collection is backed by the map, so changes to the map
340      * are reflected in the collection, and vice-versa. If the map is
341      * modified while an iteration over the collection is in progress,
342      * the results of the iteration are undefined. The collection
343      * supports element removal, which removes the corresponding
344      * mapping from the map, via the Iterator.remove,
345      * Collection.remove, removeAll, retainAll and clear operations.
346      * It does not support the add or addAll operations.<p>
347      *
348      * The difference between this method and values is that values's
349      * iterator() method returns an iterator that iterates over the
350      * values in ascending order by key. This method's iterator method
351      * iterates over the values in ascending order by key.
352      *
353      * @return a collection view of the values contained in this map.
354      */
355
356     public Collection valuesByValue()
357     {
358         if (_value_collection[ _VALUE ] == null)
359         {
360             _value_collection[ _VALUE ] = new AbstractCollection()
361             {
362                 public Iterator iterator()
363                 {
364                     return new BinaryTreeIterator(_VALUE)
365                     {
366                         protected Object doGetNext()
367                         {
368                             return _last_returned_node.getData(_VALUE);
369                         }
370                     };
371                 }
372
373                 public int size()
374                 {
375                     return BinaryTree.this.size();
376                 }
377
378                 public boolean contains(Object o)
379                 {
380                     return containsValue(o);
381                 }
382
383                 public boolean remove(Object o)
384                 {
385                     int old_size = _size;
386
387                     removeValue(o);
388                     return _size != old_size;
389                 }
390
391                 public boolean removeAll(Collection c)
392                 {
393                     boolean modified = false;
394                     Iterator iter = c.iterator();
395
396                     while (iter.hasNext())
397                     {
398                         if (removeValue(iter.next()) != null)
399                         {
400                             modified = true;
401                         }
402                     }
403                     return modified;
404                 }
405
406                 public void clear()
407                 {
408                     BinaryTree.this.clear();
409                 }
410             };
411         }
412         return _value_collection[ _VALUE ];
413     }
414
415     /**
416      * common remove logic (remove by key or remove by value)
417      *
418      * @param o the key, or value, that we're looking for
419      * @param index _KEY or _VALUE
420      *
421      * @return the key, if remove by value, or the value, if remove by
422      * key. null if the specified key or value could not be
423      * found
424      */
425
426     private Object doRemove(final Comparable o, final int index)
427     {
428         Node node = lookup(o, index);
429         Object rval = null;
430
431         if (node != null)
432         {
433             rval = node.getData(oppositeIndex(index));
434             doRedBlackDelete(node);
435         }
436         return rval;
437     }
438
439     /**
440      * common get logic, used to get by key or get by value
441      *
442      * @param o the key or value that we're looking for
443      * @param index _KEY or _VALUE
444      *
445      * @return the key (if the value was mapped) or the value (if the
446      * key was mapped); null if we couldn't find the specified
447      * object
448      */
449
450     private Object doGet(final Comparable o, final int index)
451     {
452         checkNonNullComparable(o, index);
453         Node node = lookup(o, index);
454
455         return ((node == null) ? null
456                                : node.getData(oppositeIndex(index)));
457     }
458
459     /**
460      * Get the opposite index of the specified index
461      *
462      * @param index _KEY or _VALUE
463      *
464      * @return _VALUE (if _KEY was specified), else _KEY
465      */
466
467     private int oppositeIndex(final int index)
468     {
469
470         // old trick ... to find the opposite of a value, m or n,
471 // subtract the value from the sum of the two possible
472 // values. (m + n) - m = n; (m + n) - n = m
473 return _INDEX_SUM - index;
474     }
475
476     /**
477      * do the actual lookup of a piece of data
478      *
479      * @param data the key or value to be looked up
480      * @param index _KEY or _VALUE
481      *
482      * @return the desired Node, or null if there is no mapping of the
483      * specified data
484      */
485
486     private Node lookup(final Comparable data, final int index)
487     {
488         Node rval = null;
489         Node node = _root[ index ];
490
491         while (node != null)
492         {
493             int cmp = compare(data, node.getData(index));
494
495             if (cmp == 0)
496             {
497                 rval = node;
498                 break;
499             }
500             else
501             {
502                 node = (cmp < 0) ? node.getLeft(index)
503                                  : node.getRight(index);
504             }
505         }
506         return rval;
507     }
508
509     /**
510      * Compare two objects
511      *
512      * @param o1 the first object
513      * @param o2 the second object
514      *
515      * @return negative value if o1 < o2; 0 if o1 == o2; positive
516      * value if o1 > o2
517      */
518
519     private static int compare(final Comparable o1, final Comparable o2)
520     {
521         return (( Comparable ) o1).compareTo(o2);
522     }
523
524     /**
525      * find the least node from a given node. very useful for starting
526      * a sorting iterator ...
527      *
528      * @param node the node from which we will start searching
529      * @param index _KEY or _VALUE
530      *
531      * @return the smallest node, from the specified node, in the
532      * specified mapping
533      */
534
535     private static Node leastNode(final Node node, final int index)
536     {
537         Node rval = node;
538
539         if (rval != null)
540         {
541             while (rval.getLeft(index) != null)
542             {
543                 rval = rval.getLeft(index);
544             }
545         }
546         return rval;
547     }
548
549     /**
550      * get the next larger node from the specified node
551      *
552      * @param node the node to be searched from
553      * @param index _KEY or _VALUE
554      *
555      * @return the specified node
556      */
557
558     private Node nextGreater(final Node node, final int index)
559     {
560         Node rval = null;
561
562         if (node == null)
563         {
564             rval = null;
565         }
566         else if (node.getRight(index) != null)
567         {
568
569             // everything to the node's right is larger. The least of
570 // the right node's descendents is the next larger node
571 rval = leastNode(node.getRight(index), index);
572         }
573         else
574         {
575
576             // traverse up our ancestry until we find an ancestor that
577 // is null or one whose left child is our ancestor. If we
578 // find a null, then this node IS the largest node in the
579 // tree, and there is no greater node. Otherwise, we are
580 // the largest node in the subtree on that ancestor's left
581 // ... and that ancestor is the next greatest node
582 Node parent = node.getParent(index);
583             Node child = node;
584
585             while ((parent != null) && (child == parent.getRight(index)))
586             {
587                 child = parent;
588                 parent = parent.getParent(index);
589             }
590             rval = parent;
591         }
592         return rval;
593     }
594
595     /**
596      * copy the color from one node to another, dealing with the fact
597      * that one or both nodes may, in fact, be null
598      *
599      * @param from the node whose color we're copying; may be null
600      * @param to the node whose color we're changing; may be null
601      * @param index _KEY or _VALUE
602      */
603
604     private static void copyColor(final Node from, final Node to,
605                                   final int index)
606     {
607         if (to != null)
608         {
609             if (from == null)
610             {
611
612                 // by default, make it black
613 to.setBlack(index);
614             }
615             else
616             {
617                 to.copyColor(from, index);
618             }
619         }
620     }
621
622     /**
623      * is the specified node red? if the node does not exist, no, it's
624      * black, thank you
625      *
626      * @param node the node (may be null) in question
627      * @param index _KEY or _VALUE
628      */
629
630     private static boolean isRed(final Node node, final int index)
631     {
632         return ((node == null) ? false
633                                : node.isRed(index));
634     }
635
636     /**
637      * is the specified black red? if the node does not exist, sure,
638      * it's black, thank you
639      *
640      * @param node the node (may be null) in question
641      * @param index _KEY or _VALUE
642      */
643
644     private static boolean isBlack(final Node node, final int index)
645     {
646         return ((node == null) ? true
647                                : node.isBlack(index));
648     }
649
650     /**
651      * force a node (if it exists) red
652      *
653      * @param node the node (may be null) in question
654      * @param index _KEY or _VALUE
655      */
656
657     private static void makeRed(final Node node, final int index)
658     {
659         if (node != null)
660         {
661             node.setRed(index);
662         }
663     }
664
665     /**
666      * force a node (if it exists) black
667      *
668      * @param node the node (may be null) in question
669      * @param index _KEY or _VALUE
670      */
671
672     private static void makeBlack(final Node node, final int index)
673     {
674         if (node != null)
675         {
676             node.setBlack(index);
677         }
678     }
679
680     /**
681      * get a node's grandparent. mind you, the node, its parent, or
682      * its grandparent may not exist. no problem
683      *
684      * @param node the node (may be null) in question
685      * @param index _KEY or _VALUE
686      */
687
688     private static Node getGrandParent(final Node node, final int index)
689     {
690         return getParent(getParent(node, index), index);
691     }
692
693     /**
694      * get a node's parent. mind you, the node, or its parent, may not
695      * exist. no problem
696      *
697      * @param node the node (may be null) in question
698      * @param index _KEY or _VALUE
699      */
700
701     private static Node getParent(final Node node, final int index)
702     {
703         return ((node == null) ? null
704                                : node.getParent(index));
705     }
706
707     /**
708      * get a node's right child. mind you, the node may not exist. no
709      * problem
710      *
711      * @param node the node (may be null) in question
712      * @param index _KEY or _VALUE
713      */
714
715     private static Node getRightChild(final Node node, final int index)
716     {
717         return (node == null) ? null
718                               : node.getRight(index);
719     }
720
721     /**
722      * get a node's left child. mind you, the node may not exist. no
723      * problem
724      *
725      * @param node the node (may be null) in question
726      * @param index _KEY or _VALUE
727      */
728
729     private static Node getLeftChild(final Node node, final int index)
730     {
731         return (node == null) ? null
732                               : node.getLeft(index);
733     }
734
735     /**
736      * is this node its parent's left child? mind you, the node, or
737      * its parent, may not exist. no problem. if the node doesn't
738      * exist ... it's its non-existent parent's left child. If the
739      * node does exist but has no parent ... no, we're not the
740      * non-existent parent's left child. Otherwise (both the specified
741      * node AND its parent exist), check.
742      *
743      * @param node the node (may be null) in question
744      * @param index _KEY or _VALUE
745      */
746
747     private static boolean isLeftChild(final Node node, final int index)
748     {
749         return (node == null) ? true
750                               : ((node.getParent(index) == null) ? false
751                                                                  : (node
752                                                                     == node.getParent(
753                                                                         index).getLeft(
754                                                                         index)));
755     }
756
757     /**
758      * is this node its parent's right child? mind you, the node, or
759      * its parent, may not exist. no problem. if the node doesn't
760      * exist ... it's its non-existent parent's right child. If the
761      * node does exist but has no parent ... no, we're not the
762      * non-existent parent's right child. Otherwise (both the
763      * specified node AND its parent exist), check.
764      *
765      * @param node the node (may be null) in question
766      * @param index _KEY or _VALUE
767      */
768
769     private static boolean isRightChild(final Node node, final int index)
770     {
771         return (node == null) ? true
772                               : ((node.getParent(index) == null) ? false
773                                                                  : (node
774                                                                     == node.getParent(
775                                                                         index).getRight(
776                                                                         index)));
777     }
778
779     /**
780      * do a rotate left. standard fare in the world of balanced trees
781      *
782      * @param node the node to be rotated
783      * @param index _KEY or _VALUE
784      */
785
786     private void rotateLeft(final Node node, final int index)
787     {
788         Node right_child = node.getRight(index);
789
790         node.setRight(right_child.getLeft(index), index);
791         if (right_child.getLeft(index) != null)
792         {
793             right_child.getLeft(index).setParent(node, index);
794         }
795         right_child.setParent(node.getParent(index), index);
796         if (node.getParent(index) == null)
797         {
798
799             // node was the root ... now its right child is the root
800 _root[ index ] = right_child;
801         }
802         else if (node.getParent(index).getLeft(index) == node)
803         {
804             node.getParent(index).setLeft(right_child, index);
805         }
806         else
807         {
808             node.getParent(index).setRight(right_child, index);
809         }
810         right_child.setLeft(node, index);
811         node.setParent(right_child, index);
812     }
813
814     /**
815      * do a rotate right. standard fare in the world of balanced trees
816      *
817      * @param node the node to be rotated
818      * @param index _KEY or _VALUE
819      */
820
821     private void rotateRight(final Node node, final int index)
822     {
823         Node left_child = node.getLeft(index);
824
825         node.setLeft(left_child.getRight(index), index);
826         if (left_child.getRight(index) != null)
827         {
828             left_child.getRight(index).setParent(node, index);
829         }
830         left_child.setParent(node.getParent(index), index);
831         if (node.getParent(index) == null)
832         {
833
834             // node was the root ... now its left child is the root
835 _root[ index ] = left_child;
836         }
837         else if (node.getParent(index).getRight(index) == node)
838         {
839             node.getParent(index).setRight(left_child, index);
840         }
841         else
842         {
843             node.getParent(index).setLeft(left_child, index);
844         }
845         left_child.setRight(node, index);
846         node.setParent(left_child, index);
847     }
848
849     /**
850      * complicated red-black insert stuff. Based on Sun's TreeMap
851      * implementation, though it's barely recognizeable any more
852      *
853      * @param inserted_node the node to be inserted
854      * @param index _KEY or _VALUE
855      */
856
857     private void doRedBlackInsert(final Node inserted_node, final int index)
858     {
859         Node current_node = inserted_node;
860
861         makeRed(current_node, index);
862         while ((current_node != null) && (current_node != _root[ index ])
863                 && (isRed(current_node.getParent(index), index)))
864         {
865             if (isLeftChild(getParent(current_node, index), index))
866             {
867                 Node y = getRightChild(getGrandParent(current_node, index),
868                                        index);
869
870                 if (isRed(y, index))
871                 {
872                     makeBlack(getParent(current_node, index), index);
873                     makeBlack(y, index);
874                     makeRed(getGrandParent(current_node, index), index);
875                     current_node = getGrandParent(current_node, index);
876                 }
877                 else
878                 {
879                     if (isRightChild(current_node, index))
880                     {
881                         current_node = getParent(current_node, index);
882                         rotateLeft(current_node, index);
883                     }
884                     makeBlack(getParent(current_node, index), index);
885                     makeRed(getGrandParent(current_node, index), index);
886                     if (getGrandParent(current_node, index) != null)
887                     {
888                         rotateRight(getGrandParent(current_node, index),
889                                     index);
890                     }
891                 }
892             }
893             else
894             {
895
896                 // just like clause above, except swap left for right
897 Node y = getLeftChild(getGrandParent(current_node, index),
898                                       index);
899
900                 if (isRed(y, index))
901                 {
902                     makeBlack(getParent(current_node, index), index);
903                     makeBlack(y, index);
904                     makeRed(getGrandParent(current_node, index), index);
905                     current_node = getGrandParent(current_node, index);
906                 }
907                 else
908                 {
909                     if (isLeftChild(current_node, index))
910                     {
911                         current_node = getParent(current_node, index);
912                         rotateRight(current_node, index);
913                     }
914                     makeBlack(getParent(current_node, index), index);
915                     makeRed(getGrandParent(current_node, index), index);
916                     if (getGrandParent(current_node, index) != null)
917                     {
918                         rotateLeft(getGrandParent(current_node, index),
919                                    index);
920       &nb