1   package kiasan.examples.redblacktree;
2   
3   import java.util.NoSuchElementException;
4   
5   import kiasan.examples.common.Range;
6   
7   public class TreeMap<V> {
8     /**
9      * Node in the Tree. Doubles as a means to pass key-value pairs back to user
10     * (see Map.Entry).
11     */
12  
13    static public class Entry<V> {
14      int key;
15  
16      V value;
17  
18      Entry<V> left = null;
19  
20      Entry<V> right = null;
21  
22      Entry<V> parent;
23  
24      boolean color = TreeMap.BLACK;
25  
26      public Entry() {
27        this.parent = null;
28        this.value = null;
29        this.key = -1;
30      }
31  
32      /**
33       * Make a new cell with given key, value, and parent, and with <tt>null</tt>
34       * child links, and BLACK color.
35       */
36      Entry(final int key, final V value, final Entry<V> parent) {
37        this.key = key;
38        this.value = value;
39        this.parent = parent;
40      }
41  
42      /**
43       * Returns true if black properties of tree are correct
44       * 
45       * @post returns true if black properties of tree are correct
46       */
47      protected boolean blackConsistency() {
48  
49        if (this.color != TreeMap.BLACK) // root must be black
50        {
51          return false;
52        }
53        // the number of black nodes on way to any leaf must be same
54        if (!consistentlyBlackHeight(blackHeight())) {
55          return false;
56        }
57        return true;
58      }
59  
60      /**
61       * Returns the black height of this subtree.
62       * 
63       * @pre
64       * @post returns the black height of this subtree
65       */
66      private int blackHeight() {
67        int ret = 0;
68        if (this.color == TreeMap.BLACK) {
69          ret = 1;
70        }
71        if (this.left != null) {
72          ret += this.left.blackHeight();
73        }
74        return ret;
75      }
76  
77      boolean consistency() {
78        return wellConnected(null) && redConsistency() && blackConsistency()
79            && ordered();
80      }
81  
82      /**
83       * Checks to make sure that the black height of tree is height
84       * 
85       * @post checks to make sure that the black height of tree is height
86       */
87      private boolean consistentlyBlackHeight(int height) {
88        boolean ret = true;
89        if (this.color == TreeMap.BLACK) {
90          height--;
91        }
92        if (this.left == null) {
93          ret = ret && (height == 0);
94        } else {
95          ret = ret && (this.left.consistentlyBlackHeight(height));
96        }
97        if (this.right == null) {
98          ret = ret && (height == 0);
99        } else {
100         ret = ret && (this.right.consistentlyBlackHeight(height));
101       }
102 
103       return ret;
104     }
105 
106     @Override
107     public boolean equals(final Object o) {
108       if (!(o instanceof Entry)) {
109         return false;
110       }
111       @SuppressWarnings("unchecked")
112       final Entry e = (Entry) o;
113 
114       return (this.key == e.getKey())
115           && TreeMap.valEquals(this.value, e.getValue());
116     }
117 
118     /**
119      * Returns the key.
120      * 
121      * @return the key.
122      */
123     public int getKey() {
124       return this.key;
125     }
126 
127     /**
128      * Returns the value associated with the key.
129      * 
130      * @return the value associated with the key.
131      */
132     public V getValue() {
133       return this.value;
134     }
135 
136     @Override
137     public int hashCode() {
138       final int keyHash = this.key;
139       final int valueHash = (this.value == null ? 0 : this.value.hashCode());
140       return keyHash ^ valueHash;
141     }
142 
143     private boolean ordered() {
144       return ordered(this, new Range());
145     }
146 
147     private boolean ordered(final Entry<V> t, final Range range) {
148       if (t == null) {
149         return true;
150       }
151       if (!range.inRange(t.key)) {
152         return false;
153       }
154       boolean ret = true;
155       ret = ret && ordered(t.left, range.setUpper(t.key));
156       ret = ret && ordered(t.right, range.setLower(t.key));
157       return ret;
158     }
159 
160     /**
161      * Returns true if no red node in subtree has red children
162      * 
163      * @post returns true if no red node in subtree has red children
164      */
165     private boolean redConsistency() {
166       boolean ret = true;
167       if ((this.color == TreeMap.RED)
168           && (((this.left != null) && (this.left.color == TreeMap.RED)) || ((this.right != null) && (this.right.color == TreeMap.RED)))) {
169         return false;
170       }
171       if (this.left != null) {
172         ret = ret && this.left.redConsistency();
173       }
174       if (this.right != null) {
175         ret = ret && this.right.redConsistency();
176       }
177       return ret;
178     }
179 
180     /**
181      * Replaces the value currently associated with the key with the given
182      * value.
183      * 
184      * @return the value associated with the key before this method was called.
185      */
186     public V setValue(final V value) {
187       final V oldValue = this.value;
188       this.value = value;
189       return oldValue;
190     }
191 
192     int size() {
193       int ls = 0, rs = 0;
194       if (this.left != null) {
195         ls = this.left.size();
196       }
197       if (this.right != null) {
198         rs = this.right.size();
199       }
200       return 1 + ls + rs;
201     }
202 
203     @Override
204     public String toString() {
205       return this.key + "=" + this.value;
206     }
207 
208     /**
209      * Returns true iff this tree is well-connected.
210      */
211 
212     private boolean wellConnected(final Entry<V> expectedParent) {
213       boolean ok = true;
214       if (expectedParent != this.parent) {
215 
216         return false;
217       }
218 
219       if (this.right != null) {
220         // ok && is redundant because ok is assigned true
221         ok = ok && this.right.wellConnected(this);
222       }
223 
224       if (this.left != null) {
225 
226         ok = ok && this.left.wellConnected(this);
227       }
228 
229       if ((this.right == this.left) && (this.right != null)
230           && (this.left != null)) {// left!=null
231         // is
232         // redundant
233         // because
234         // left==right
235         // &&
236         // right!=null
237         return false;
238       }
239 
240       return ok;
241     }
242   }
243 
244   private static final boolean RED = false;
245 
246   private static final boolean BLACK = true;
247 
248   /**
249    * Balancing operations.
250    * 
251    * Implementations of rebalancings during insertion and deletion are slightly
252    * different than the CLR version. Rather than using dummy nilnodes, we use a
253    * set of accessors that deal properly with null. They are used to avoid
254    * messiness surrounding nullness checks in the main algorithms.
255    */
256 
257   private static <V> boolean colorOf(final Entry<V> p) {
259   }
260 
261   /**
262    * Returns the key corresponding to the specified Entry. Throw
263    * NoSuchElementException if the Entry is <tt>null</tt>.
264    */
265   private static int key(final Entry<?> e) {
268     }
270   }
271 
272   // Query Operations
273 
274   private static <V> Entry<V> leftOf(final Entry<V> p) {
276   }
277 
278   private static <V> Entry<V> parentOf(final Entry<V> p) {
280   }
281 
282   private static <V> Entry<V> rightOf(final Entry<V> p) {
284   }
285 
286   private static <V> void setColor(final Entry<V> p, final boolean c) {
289     }
291 
292   /**
293    * Test two values for equality. Differs from o1.equals(o2) only in that it
294    * copes with <tt>null</tt> o1 properly.
295    */
296   private static boolean valEquals(final Object o1, final Object o2) {
297     return (o1 == null ? o2 == null : o1.equals(o2));
298   }
299 
300   /**
301    * The Comparator used to maintain order in this TreeMapGeneric, or null if
302    * this TreeMapGeneric uses its elements natural ordering.
303    * 
304    * @serial
305    */
306 
307   private transient Entry<V> root = null;
308 
309   /**
310    * The number of entries in the tree
311    */
312   private transient int size = 0;
313 
314   /**
315    * The number of structural modifications to the tree.
316    */
317   private transient int modCount = 0;
318 
319   /**
320    * Removes all mappings from this TreeMapGeneric.
321    */
322   public void clear() {
323     this.modCount++;
324     this.size = 0;
325     this.root = null;
326   }
327 
328   /**
329    * Compares two keys using the correct comparison method for this
330    * TreeMapGeneric.
331    */
332   private int compare(final int k1, final int k2) {
335 
338     } else {
340     }
341   }
342 
343   /**
344    * Returns <tt>true</tt> if this map contains a mapping for the specified key.
345    * 
346    * @param key
347    *          key whose presence in this map is to be tested.
348    * 
349    * @return <tt>true</tt> if this map contains a mapping for the specified key.
350    * @throws ClassCastException
351    *           if the key cannot be compared with the keys currently in the map.
352    * @throws NullPointerException
353    *           key is <tt>null</tt> and this map uses natural ordering, or its
354    *           comparator does not tolerate <tt>null</tt> keys.
355    */
356   public boolean containsKey(final int key) {
357     return getEntry(key) != null;
358   }
359 
360   /**
361    * Returns <tt>true</tt> if this map maps one or more keys to the specified
362    * value. More formally, returns <tt>true</tt> if and only if this map
363    * contains at least one mapping to a value <tt>value</tt> such that
364    * <tt>(value==null ? value==null : value.equals(value))</tt>. This operation
365    * will probably require time linear in the Map size for most implementations
366    * of Map.
367    * 
368    * @param value
369    *          value whose presence in this Map is to be tested.
370    * @return <tt>true</tt> if a mapping to <tt>value</tt> exists; <tt>false</tt>
371    *         otherwise.
372    * @since 1.2
373    */
374   public boolean containsValue(final Object value) {
375     return (this.root == null ? false
376         : (value == null ? valueSearchNull(this.root) : valueSearchNonNull(
377             this.root, value)));
378   }
379 
380   private void decrementSize() {
384 
385   /**
386    * Delete node p, and then rebalance the tree.
387    */
388 
389   private void deleteEntry(Entry<V> p) {
391 
392     // If strictly internal, copy successor's element to p and then make p
393     // point to successor.
399     } // p has 2 children
400 
401     // Start fixup at replacement node, if it exists.
403 
405       // Link replacement to parent
409       } else if (p == p.parent.left) {
410         p.parent.left = replacement;
411       } else {
412         p.parent.right = replacement;
413       }
414 
415       // Null out links so they are OK to use by fixAfterDeletion.
417 
418       // Fix replacement
421       }
424     } else { // No children. Use self as phantom replacement and unlink.
427       }
428 
434         }
436       }
437     }
439 
440   /**
441    * Returns the first Entry in the TreeMapGeneric (according to the
442    * TreeMapGeneric's key-sort function). Returns null if the TreeMapGeneric is
443    * empty.
444    */
445   private Entry<V> firstEntry() {
446     Entry<V> p = this.root;
447     if (p != null) {
448       while (p.left != null) {
449         p = p.left;
450       }
451     }
452     return p;
453   }
454 
455   /**
456    * Returns the first (lowest) key currently in this sorted map.
457    * 
458    * @return the first (lowest) key currently in this sorted map.
459    * @throws NoSuchElementException
460    *           Map is empty.
461    */
462   public int firstKey() {
463     return TreeMap.key(firstEntry());
464   }
465 
466   /** From CLR * */
467   private void fixAfterDeletion(Entry<V> x) {
471 
473           TreeMap.setColor(sib, TreeMap.BLACK);
474           TreeMap.setColor(TreeMap.parentOf(x), TreeMap.RED);
475           rotateLeft(TreeMap.parentOf(x));
476           sib = TreeMap.rightOf(TreeMap.parentOf(x));
477         }
478 
483         } else {
484           if (TreeMap.colorOf(TreeMap.rightOf(sib)) == TreeMap.BLACK) {
485             TreeMap.setColor(TreeMap.leftOf(sib), TreeMap.BLACK);
486             TreeMap.setColor(sib, TreeMap.RED);
487             rotateRight(sib);
488             sib = TreeMap.rightOf(TreeMap.parentOf(x));
489           }
490           TreeMap.setColor(sib, TreeMap.colorOf(TreeMap.parentOf(x)));
491           TreeMap.setColor(TreeMap.parentOf(x), TreeMap.BLACK);
492           TreeMap.setColor(TreeMap.rightOf(sib), TreeMap.BLACK);
493           rotateLeft(TreeMap.parentOf(x));
494           x = this.root;
495         }
496       } else { // symmetric
498 
500           TreeMap.setColor(sib, TreeMap.BLACK);
501           TreeMap.setColor(TreeMap.parentOf(x), TreeMap.RED);
502           rotateRight(TreeMap.parentOf(x));
503           sib = TreeMap.leftOf(TreeMap.parentOf(x));
504         }
505 
510         } else {
511           if (TreeMap.colorOf(TreeMap.leftOf(sib)) == TreeMap.BLACK) {
512             TreeMap.setColor(TreeMap.rightOf(sib), TreeMap.BLACK);
513             TreeMap.setColor(sib, TreeMap.RED);
514             rotateLeft(sib);
515             sib = TreeMap.leftOf(TreeMap.parentOf(x));
516           }
517           TreeMap.setColor(sib, TreeMap.colorOf(TreeMap.parentOf(x)));
518           TreeMap.setColor(TreeMap.parentOf(x), TreeMap.BLACK);
519           TreeMap.setColor(TreeMap.leftOf(sib), TreeMap.BLACK);
520           rotateRight(TreeMap.parentOf(x));
521           x = this.root;
522         }
523       }
524     }
525 
528 
529   /** From CLR * */
530   private void fixAfterInsertion(Entry<V> x) {
532 
543         } else {
547           }
549           // seeded
553           }
554         }
555       } else {
563         } else {
567           }
572           }
573         }
574       }
575     }
578 
579   /**
580    * Returns the value to which this map maps the specified key. Returns
581    * <tt>null</tt> if the map contains no mapping for this key. A return value
582    * of <tt>null</tt> does not <i>necessarily</i> indicate that the map contains
583    * no mapping for the key; it's also possible that the map explicitly maps the
584    * key to <tt>null</tt>. The <tt>containsKey</tt> operation may be used to
585    * distinguish these two cases.
586    * 
587    * @param key
588    *          key whose associated value is to be returned.
589    * @return the value to which this map maps the specified key, or
590    *         <tt>null</tt> if the map contains no mapping for the key.
591    * @throws ClassCastException
592    *           key cannot be compared with the keys currently in the map.
593    * @throws NullPointerException
594    *           key is <tt>null</tt> and this map uses natural ordering, or its
595    *           comparator does not tolerate <tt>null</tt> keys.
596    * 
597    * @see #containsKey(Object)
598    */
599   //@ requires ((this.root == null) || this.root.consistency()) && (this.size == this.realSize());
600   //@ ensures true;
601   public V get(final int key) {
604   }
605 
606   /**
607    * Returns this map's entry for the given key, or <tt>null</tt> if the map
608    * does not contain an entry for the key.
609    * 
610    * @return this map's entry for the given key, or <tt>null</tt> if the map
611    *         does not contain an entry for the key.
612    * @throws ClassCastException
613    *           if the key cannot be compared with the keys currently in the map.
614    * @throws NullPointerException
615    *           key is <tt>null</tt> and this map uses natural order, or its
616    *           comparator does not tolerate * <tt>null</tt> keys.
617    */
618   private Entry<V> getEntry(final int key) {
622       // int cmp = compare(k, p.key);
627       } else {
629       }
630     }
632   }
633 
634   private void incrementSize() {
638 
639   /**
640    * Returns the last Entry in the TreeMapGeneric (according to the
641    * TreeMapGeneric's key-sort function). Returns null if the TreeMapGeneric is
642    * empty.
643    */
644   private Entry<V> lastEntry() {
649       }
650     }
652   }
653 
654   /**
655    * Returns the last (highest) key currently in this sorted map.
656    * 
657    * @return the last (highest) key currently in this sorted map.
658    * @throws NoSuchElementException
659    *           Map is empty.
660    */
661   //@ requires ((this.root == null) || this.root.consistency()) && (this.size == this.realSize()); 
662   //@ ensures true;
663   public int lastKey() {
665   }
666 
667   //@ requires ((this.root == null) || this.root.consistency()) && (this.size == this.realSize());
668   //@ ensures ((this.root != null) && this.root.consistency());
669   public V put(final int key, final V value) {
671 
676     }
677 
678     while (true) {
685         } else {
690         }
691       } else { // cmp > 0
694         } else {
699         }
700       }
701     }
702     // return null;
703   }
704 
705   /**
706    * Associates the specified value with the specified key in this map. If the
707    * map previously contained a mapping for this key, the old value is replaced.
708    * 
709    * @param key
710    *          key with which the specified value is to be associated.
711    * @param value
712    *          value to be associated with the specified key.
713    * 
714    * @return previous value associated with specified key, or <tt>null</tt> if
715    *         there was no mapping for key. A <tt>null</tt> return can also
716    *         indicate that the map previously associated <tt>null</tt> with the
717    *         specified key.
718    * @throws ClassCastException
719    *           key cannot be compared with the keys currently in the map.
720    * @throws NullPointerException
721    *           key is <tt>null</tt> and this map uses natural order, or its
722    *           comparator does not tolerate <tt>null</tt> keys.
723    */
724 
725   public int realSize() {
728     }
730   }
731 
732   /**
733    * Removes the mapping for this key from this TreeMapGeneric if present.
734    * 
735    * @param key
736    *          key for which mapping should be removed
737    * @return previous value associated with specified key, or <tt>null</tt> if
738    *         there was no mapping for key. A <tt>null</tt> return can also
739    *         indicate that the map previously associated <tt>null</tt> with the
740    *         specified key.
741    * 
742    * @throws ClassCastException
743    *           key cannot be compared with the keys currently in the map.
744    * @throws NullPointerException
745    *           key is <tt>null</tt> and this map uses natural order, or its
746    *           comparator does not tolerate <tt>null</tt> keys.
747    */
748   //@ requires ((this.root == null) || this.root.consistency()) && (this.size == this.realSize());
749   //@ ensures ((this.root == null) || this.root.consistency()) && (this.size == this.realSize());  
750   public V remove(final int key) {
754     }
755 
759   }
760 
761   /** From CLR * */
762   private void rotateLeft(final Entry<V> p) {
766       r.left.parent = p;
767     }
773     } else {
774       p.parent.right = r;
775     }
779 
780   /** From CLR * */
781   private void rotateRight(final Entry<V> p) {
785       l.right.parent = p;
786     }
792     } else {
793       p.parent.left = l;
794     }
798 
799   /**
800    * Returns the number of key-value mappings in this map.
801    * 
802    * @return the number of key-value mappings in this map.
803    */
804 
805   public int size() {
806     return this.size;
807   }
808 
809   /**
810    * Returns the successor of the specified Entry, or null if no such.
811    */
812   private Entry<V> successor(final Entry<V> t) {
814       return null;
818         p = p.left;
819       }
821     } else {
822       Entry<V> p = t.parent;
823       Entry<V> ch = t;
824       while ((p != null) && (ch == p.right)) {
825         ch = p;
826         p = p.parent;
827       }
828       return p;
829     }
830   }
831 
832   private boolean valueSearchNonNull(final Entry<V> n, final Object value) {
833     // Check this node for the value
834     if (value.equals(n.value)) {
835       return true;
836     }
837 
838     // Check left and right subtrees for value
839     return ((n.left != null) && valueSearchNonNull(n.left, value))
840         || ((n.right != null) && valueSearchNonNull(n.right, value));
841   }
842 
843   private boolean valueSearchNull(final Entry<V> n) {
844     if (n.value == null) {
845       return true;
846     }
847 
848     // Check left and right subtrees for value
849     return ((n.left != null) && valueSearchNull(n.left))
850         || ((n.right != null) && valueSearchNull(n.right));
851   }
852 
853 }