OrderedKeyList


1   package com.daffodilwoods.daffodildb.server.datasystem.utility;
2   
3   import com.daffodilwoods.daffodildb.server.datasystem.interfaces.*;
4   import java.util.*;
5   import com.daffodilwoods.database.resource.*;
6   import com.daffodilwoods.daffodildb.utils.comparator.SuperComparator;
7   
8   public class OrderedKeyList //implements NavigatorS
9   {
10      /**
11       * The Comparator used to maintain order in this TreeMap, or
12       * null if this TreeMap uses its elements natural ordering.
13       *
14       * @serial
15       */
16       private SuperComparator comparator = null;
17  
18       private transient Entry root = null;
19  
20       private Entry current = null;
21  
22       /**
23       * The number of entries in the tree
24       */
25       private transient int size = 0;
26  
27       /**
28       * The number of structural modifications to the tree.
29       */
30       private transient int modCount = 0;
31  
32       private void incrementSize() throws DException { size++; }
33       private void decrementSize() throws DException { size--; }
34       private static final boolean RED   = false;
35       private static final boolean BLACK = true;
36  
37       public OrderedKeyList(SuperComparator comparator)  {
38        this.comparator = comparator;
39       }
40  
41       public int size() throws DException {
42         return size;
43       }
44  
45       public boolean containsKey(Object   key) throws DException {
46         return getEntry(key) != null;
47       }
48  
49       public int getRowCount() throws DException {
50        return size;
51       }
52  
53       public boolean containsValue(Object   value) throws DException {
54          return (root==null ? false :
55                  (value==null ? valueSearchNull(root)
56                       : valueSearchNonNull(root, value)));
57       }
58  
59       private boolean valueSearchNull(Entry n) throws DException {
60          if (n.value == null)
61              return true;
62  
63          return (n.left  != null && valueSearchNull(n.left)) ||
64                 (n.right != null && valueSearchNull(n.right));
65       }
66  
67      /* public NavigatorIterator getNavigatorIterator() throws DException {
68           return new NavigatorIterator(new OrderedKeyListIterator());
69       } */
70  
71       private boolean valueSearchNonNull(Entry n, Object   value) throws DException {
72          if (value.equals(n.value))
73              return true;
74  
75          return (n.left  != null && valueSearchNonNull(n.left, value)) ||
76                 (n.right != null && valueSearchNonNull(n.right, value));
77       }
78  
79       public Object   getRootKey() throws DException {
80        return root.key;
81       }
82  
83       public Entry getKeyEntry() throws DException {
84        return current;
85       }
86  /*     public Object getObject(Object key) throws DException {
87         Entry p = getEntry(key);
88         return (p==null ? null : p.value);
89       }
90  */
91       public Object   getObject(Object   key) throws DException {
92          Entry p = getEntry(key);
93        return p==null ? null : p.value;
94       }
95  
96  
97       public Object   getTopKey() throws DException {
98          Entry p = firstEntry();
99        return p==null ? null : p.key;
100      }
101 
102      public Object   getPreviousKey(Object   key) throws DException {
103       Entry k = getEntry(key);
104       Entry p = predeccesor(k);
105       return  p==null ? null :  p.key;
106      }
107 
108      public Object   getNextKey(Object   key) throws DException {
109       Entry k = getEntry(key);
110       Entry p = successor(k);
111       return p==null ? null : p.key;
112      }
113 
114      public Object   getBottomKey() throws DException {
115         Entry p = lastEntry();
116          return p==null ? null : p.key;
117      }
118      public boolean top() throws DException {
119     current = firstEntry();
120       return current != null ; //? false :true
121      }
122 
123      private Entry getEntry(Object   key) throws DException {
124        Entry p = root;
125        while (p != null) {
126           int cmp = compare(key,p.key);
127           if (cmp == 0)
128               return p;
129           else if (cmp < 0)
130               p = p.left;
131           else
132               p = p.right;
133        }
134        return null;
135      }
136 
137    public Object   locateNearestRecord(Object   value) throws DException {
138        Entry p = root;
139        while (p != null) {
140           int cmp = compare(value,p.key);
141           if (cmp == 0)
142               return p.key;
143           else if (cmp < 0){
144             if(p.left == null)
145                return p.key;
146               p = p.left;
147          }
148           else{
149             if(p.right == null)
150                return p.key;
151               p = p.right;
152          }
153       }
154        return null;
155    }
156 
157    public boolean locateKey(Object   value) throws DException {
158       return getEntry(value) != null;
159    }
160 
161    private Object   locateKey1(Object   value) throws DException {
162        Entry p = root;
163        while (p != null) {
164           int cmp = compare(value,p.value);
165           if (cmp == 0)
166               return p;
167           else if (cmp < 0)
168               p = p.left;
169           else
170               p = p.right;
171       }
172        return null;
173    }
174 
175    public void changeCurrentKey(Object   object,Object   oldKey) throws DException {
176       Object   key = locateKey1(object);
177       if(key == null)
178          return;
179       moveToKey(key);
180    }
181 
182      public synchronized void insert(Object   key, Object   value) throws DException {
183        /*if( value instanceof byte[][] )
184        {
185          Thread.dumpStack();
186          System.exit(0);
187        }*/
188 
189        Entry t = root;
190 
191        if (t == null) {
192         incrementSize();
193         root = new Entry(key, value, null);
194        current = root;
195         return ;
196        }
197 
198        while (true) {
199         int cmp = compare(key, t.key);
200         if (cmp == 0) {
201            t.setValue(value);
202          return;
203         } else if (cmp < 0) {
204            if (t.left != null) {
205               t = t.left;
206            } else {
207             incrementSize();
208             t.left = new Entry(key, value, t);
209             fixAfterInsertion(t.left);
210             return ;
211            }
212         } else { // cmp > 0
213            if (t.right != null) {
214             t = t.right;
215            } else {
216             incrementSize();
217             t.right = new Entry(key, value, t);
218             fixAfterInsertion(t.right);
219             return ;
220            }
221         }
222        }
223      }
224 
225      public void remove(Object   key) throws DException {
226         try{
227            delete(key);
228         }catch(Exception   ex){}
229      }
230 
231      public synchronized void delete(Object   key) throws DException{
232       if(current == null)
233         throw new DException("DSE986",null);
234       else if( key == null)
235         throw new DException("DSE982",null);
236       Entry p =  getEntry(key);
237 
238       if(p == null || p.value == null)
239          throw new DException("DSE978",null);
240       if(current == p){
241         if( ! next())//   p.right != null
242             if(! previous())
243                 current = null;
244       }
245        deleteEntry(p);
246       p.value = null;
247        return ;
248      }
249 
250    /*
251       * moves to element above the current element
252       * Returns true if there  is at any data before the current and if
253         yes then set it to the current.
254        Algo :-
255       1. Call the predeccesor and pass the current as the parameter.
256       2. If p is null then return false
257       3. Else, set current to the value returned i.e. previous value and return true
258    */
259    public boolean previous() throws DException {
260       Entry p = predeccesor(current);
261       if(p == null)
262          return false;
263       current = p;
264       return true;
265    }
266 
267      public boolean bottom() throws DException {
268       current = lastEntry();
269       return current != null ;
270      }
271 
272      public boolean next() throws DException {
273       Entry p = successor(current);
274       if(p != null) {
275          current = p;
276          return true;
277       }
278       else
279          return false;
280      }
281 
282    /* Returns true if there the current is at the top.
283       Algo :-
284       1. Checks whether there is any data left of the Current.
285          If there is, then it will always return false
286       2. Else, call the firstEntry() and return true if the
287          value return is the current and not null else false   */
288 
289    public boolean isTop() throws DException {
290       if( current == null || current.left != null )
291          return false;
292       else {
293          Entry p = firstEntry();
294          return   (p != null && current == p);
295       }
296    }
297 
298       /* Returns true if there the current is at the bottom.
299       Algo :-
300       1. Checks whether there is any data right of the Current.
301          If there is, then it will always return false
302       2. Else, call the lastEntry() and return true if the
303          value return is the current and not null else false   */
304 
305    public boolean isBottom() throws DException {
306       if( current == null || current.right != null)
307          return false;
308       else {
309          Entry p = lastEntry();
310          return   (p != null && current == p) ;
311       }
312    }
313    /* Returns true if there is any data after the current.
314       1. Checks whether there is any data right of the Current.
315          If there is, then it will always return true
316       2. Else, call the successor() and return true if the
317          value return is not null else false   */
318 
319    public boolean isNext() throws DException {
320       return current == null ? false :
321             current.right != null ? true :
322                successor(current) != null ;
323    }
324    /* Returns true if there is any data before the current.
325       1. Checks whether there is any data left of the Current.
326          If there is, then it will always return true
327       2. Else, call the predeccessor() and return true if the
328          value return is not null else false   */
329    public boolean isPrevious() throws DException {
330       return current == null ? false :
331             current.left != null ? true
332               : predeccesor(current)!= null ;
333    }
334 
335    public void moveToKey(Object   key) {// throws com.daffodilwoods.database.resource.DException
336      try  {
337       if(current == null)
338          throw new DException("DSE562",null);
339       else if(key == null)
340          throw new DException("DSE554",null);
341       Entry p = getEntry(key);
342       current = p == null ? current : p;
343       }
344       catch(Exception   e) {
345          e.printStackTrace();
346       }
347    }
348    /* Returns the key for current value*/
349    public Object   getKey() throws DException {
350     return  current == null ? null : current.key;
351    }
352 
353    /**
354     * returns the current  value
355    **/
356    public Object   getObject() throws DException {
357     return  current == null ? null : current.value;
358    }
359 
360      protected int compare(Object   k1, Object   k2) throws DException {
361        return (comparator==null ? ((Comparable  )k1).compareTo(k2)
362                  : comparator.compare(k1, k2));
363      }
364 
365      private Entry firstEntry() throws DException {
366        Entry p = root;
367        if (p != null)
368         while (p.left != null)
369            p = p.left;
370        return p;
371      }
372 
373     /**
374      * Returns the last Entry in the TreeMap (according to the TreeMap's
375      * key-sort function).  Returns null if the TreeMap is empty.
376      */
377      private Entry lastEntry() throws DException {
378        Entry p = root;
379        if (p != null)
380         while (p.right != null)
381            p = p.right;
382        return p;
383      }
384 
385     /**
386      * Returns the successor of the specified Entry, or null if no such.
387      */
388      private Entry successor(Entry t) throws DException {
389        if (t == null)
390         return null;
391        else if (t.right != null) {
392         Entry p = t.right;
393         while (p.left != null)
394            p = p.left;
395         return p;
396        } else {
397         Entry p = t.parent;
398         Entry ch = t;
399         while (p != null && ch == p.right) {
400            ch = p;
401            p = p.parent;
402         }
403         return p;
404        }
405     }
406 
407     /**
408      * Balancing operations.
409      *
410      * Implementations of rebalancings during insertion and deletion are
411      * slightly different than the CLR version.  Rather than using dummy
412      * nilnodes, we use a set of accessors that deal properly with null.  They
413      * are used to avoid messiness surrounding nullness checks in the main
414      * algorithms.
415      */
416 
417     private static boolean colorOf(Entry p) throws DException {
418        return (p == null ? BLACK : p.color);
419     }
420 
421     private static Entry  parentOf(Entry p) throws DException {
422        return (p == null ? null: p.parent);
423     }
424 
425     private static void setColor(Entry p, boolean c) throws DException {
426        if (p != null)  p.color = c;
427     }
428 
429     private static Entry  leftOf(Entry p) throws DException {
430        return (p == null)? null: p.left;
431     }
432 
433     private static Entry  rightOf(Entry p) throws DException {
434        return (p == null)? null: p.right;
435     }
436 
437     /** From CLR **/
438     private void rotateLeft(Entry p) throws DException {
439        Entry r = p.right;
440        p.right = r.left;
441        if (r.left != null)
442           r.left.parent = p;
443        r.parent = p.parent;
444        if (p.parent == null)
445           root = r;
446        else if (p.parent.left == p)
447           p.parent.left = r;
448        else
449           p.parent.right = r;
450        r.left = p;
451        p.parent = r;
452     }
453 
454     /** From CLR **/
455     private void rotateRight(Entry p) throws DException {
456        Entry l = p.left;
457        p.left = l.right;
458        if (l.right != null) l.right.parent = p;
459        l.parent = p.parent;
460        if (p.parent == null)
461           root = l;
462        else if (p.parent.right == p)
463           p.parent.right = l;
464     else p.parent.left = l;
465       l.right = p;
466       p.parent = l;
467     }
468 
469 
470     /** From CLR **/
471     private void fixAfterInsertion(Entry x) throws DException {
472        x.color = RED;
473 
474        while (x != null && x != root && x.parent.color == RED) {
475         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
476            Entry y = rightOf(parentOf(parentOf(x)));
477            if (colorOf(y) == RED) {
478             setColor(parentOf(x), BLACK);
479             setColor(y, BLACK);
480             setColor(parentOf(parentOf(x)), RED);
481             x = parentOf(parentOf(x));
482            } else {
483             if (x == rightOf(parentOf(x))) {
484                x = parentOf(x);
485                rotateLeft(x);
486             }
487             setColor(parentOf(x), BLACK);
488             setColor(parentOf(parentOf(x)), RED);
489             if (parentOf(parentOf(x)) != null)
490                rotateRight(parentOf(parentOf(x)));
491            }
492         } else {
493            Entry y = leftOf(parentOf(parentOf(x)));
494            if (colorOf(y) == RED) {
495             setColor(parentOf(x), BLACK);
496             setColor(y, BLACK);
497             setColor(parentOf(parentOf(x)), RED);
498             x = parentOf(parentOf(x));
499            } else {
500             if (x == leftOf(parentOf(x))) {
501                x = parentOf(x);
502                rotateRight(x);
503             }
504             setColor(parentOf(x),  BLACK);
505             setColor(parentOf(parentOf(x)), RED);
506             if (parentOf(parentOf(x)) != null)
507                rotateLeft(parentOf(parentOf(x)));
508            }
509         }
510     }
511     root.color = BLACK;
512   }
513 
514     /**
515      * Delete node p, and then rebalance the tree.
516      */
517     private void deleteEntry(Entry p) throws DException {
518         decrementSize();
519 
520     if (p.left != null && p.right != null) {
521         Entry s = successor(p);
522         swapPosition(s, p);
523     }
524 
525     Entry replacement = (p.left != null ? p.left : p.right);
526 
527     if (replacement != null) {
528         replacement.parent = p.parent;
529         if (p.parent == null)
530         root = replacement;
531         else if (p == p.parent.left)
532         p.parent.left  = replacement;
533         else
534         p.parent.right = replacement;
535 
536         p.left = p.right = p.parent = null;
537 
538         if (p.color == BLACK)
539         fixAfterDeletion(replacement);
540     } else if (p.parent == null) { // return if we are the only node.
541         root = null;
542     } else { //  No children. Use self as phantom replacement and unlink.
543         if (p.color == BLACK)
544         fixAfterDeletion(p);
545 
546         if (p.parent != null) {
547         if (p == p.parent.left)
548             p.parent.left = null;
549         else if (p == p.parent.right)
550             p.parent.right = null;
551         p.parent = null;
552         }
553     }
554     }
555 
556 
557      /* Returns the next Data*/
558   private Entry predeccesor(Entry t) throws DException {
559       if (t == null)
560          return null;
561       else if (t.left != null) {
562          Entry p = t.left;
563          while (p.right != null)
564               p = p.right;
565          return p;
566       }
567      else {
568         Entry p = t.parent;
569         Entry ch = t;
570         while (p != null && ch == p.left) {
571            ch = p;
572            p = p.parent;
573         }
574         return p;
575       }
576   }
577 
578   public void show(){
579       try{
580       Object   iter = getTopKey();
581       if(iter != null){
582          do{
583             iter = getNextKey(iter);
584          }while(iter != null);
585       }else
586          ;//// Removed By Program **           System.out.println("No Record In List "+size);
587       }catch(DException E){E.printStackTrace();}
588   }
589 
590   public OrderedKeyListIterator getIterator() throws DException {
591    return new OrderedKeyListIterator();
592   }
593 
594     /** From CLR **/
595     private void fixAfterDeletion(Entry x) throws DException {
596     while (x != root && colorOf(x) == BLACK) {
597         if (x == leftOf(parentOf(x))) {
598         Entry sib = rightOf(parentOf(x));
599 
600         if (colorOf(sib) == RED) {
601             setColor(sib, BLACK);
602             setColor(parentOf(x), RED);
603             rotateLeft(parentOf(x));
604             sib = rightOf(parentOf(x));
605         }
606 
607         if (colorOf(leftOf(sib))  == BLACK &&
608             colorOf(rightOf(sib)) == BLACK) {
609             setColor(sib,  RED);
610             x = parentOf(x);
611         } else {
612             if (colorOf(rightOf(sib)) == BLACK) {
613             setColor(leftOf(sib), BLACK);
614             setColor(sib, RED);
615             rotateRight(sib);
616             sib = rightOf(parentOf(x));
617             }
618             setColor(sib, colorOf(parentOf(x)));
619             setColor(parentOf(x), BLACK);
620             setColor(rightOf(sib), BLACK);
621             rotateLeft(parentOf(x));
622             x = root;
623         }
624         } else { // symmetric
625         Entry sib = leftOf(parentOf(x));
626 
627         if (colorOf(sib) == RED) {
628             setColor(sib, BLACK);
629             setColor(parentOf(x), RED);
630             rotateRight(parentOf(x));
631             sib = leftOf(parentOf(x));
632         }
633 
634         if (colorOf(rightOf(sib)) == BLACK &&
635             colorOf(leftOf(sib)) == BLACK) {
636             setColor(sib,  RED);
637             x = parentOf(x);
638         } else {
639             if (colorOf(leftOf(sib)) == BLACK) {
640             setColor(rightOf(sib), BLACK);
641             setColor(sib, RED);
642             rotateLeft(sib);
643             sib = leftOf(parentOf(x));
644             }
645             setColor(sib, colorOf(parentOf(x)));
646             setColor(parentOf(x), BLACK);
647             setColor(leftOf(sib), BLACK);
648             rotateRight(parentOf(x));
649             x = root;
650         }
651         }
652     }
653 
654     setColor(x, BLACK);
655     }
656 
657     /**
658      * Swap the linkages of two nodes in a tree.
659      */
660     private void swapPosition(Entry x, Entry y) throws DException {
661     Entry px = x.parent, lx = x.left, rx = x.right;
662     Entry py = y.parent, ly = y.left, ry = y.right;
663     boolean xWasLeftChild = px != null && x == px.left;
664     boolean yWasLeftChild = py != null && y == py.left;
665 
666     if (x == py) {  // x was y's parent
667         x.parent = y;
668         if (yWasLeftChild) {
669         y.left = x;
670         y.right = rx;
671         } else {
672         y.right = x;
673         y.left = lx;
674         }
675     } else {
676         x.parent = py;
677         if (py != null) {
678         if (yWasLeftChild)
679             py.left = x;
680         else
681             py.right = x;
682         }
683         y.left = lx;
684         y.right = rx;
685     }
686 
687     if (y == px) { // y was x's parent
688         y.parent = x;
689         if (xWasLeftChild) {
690         x.left = y;
691         x.right = ry;
692         } else {
693         x.right = y;
694         x.left = ly;
695         }
696     } else {
697         y.parent = px;
698         if (px != null) {
699         if (xWasLeftChild)
700             px.left = y;
701         else
702             px.right = y;
703         }
704         x.left = ly;
705         x.right = ry;
706     }
707 
708     if (x.left != null)
709         x.left.parent = x;
710     if (x.right != null)
711         x.right.parent = x;
712     if (y.left != null)
713         y.left.parent = y;
714     if (y.right != null)
715         y.right.parent = y;
716 
717     boolean c = x.color;
718     x.color = y.color;
719     y.color = c;
720 
721     if (root == x)
722         root = y;
723     else if (root == y)
724         root = x;
725     }
726 
727      public class Entry {//implements Map.Entry
728        public Object   key;
729        Object   value;
730        public Entry left = null;
731        public Entry right = null;
732        Entry parent;
733        boolean color = BLACK;
734 
735        /**
736        * Make a new cell with given key, value, and parent, and with <tt>null</tt>
737        * child links, and BLACK color.
738        */
739        Entry(Object   key, Object   value, Entry parent) {
740           this.key = key;
741           this.value = value;
742           this.parent = parent;
743        }
744 
745        /**
746        * Returns the key.
747          *
748        * @return the key.
749        */
750        public Object   getKey() throws DException {
751           return key;
752        }
753 
754        /**
755        * Returns the value associated with the key.
756          *
757        * @return the value associated with the key.
758        */
759        public Object   getValue() throws DException {
760           return value;
761        }
762 
763        /**
764        * Replaces the value currently associated with the key with the given
765        * value.
766          *
767          * @return the value associated with the key before this method was
768          *     called.
769        */
770        public Object   setValue(Object   value) throws DException {
771           Object   oldValue = this.value;
772           this.value = value;
773           return oldValue;
774        }
775 
776      /*  public boolean equals(Object o) throws DException {
777         if (!(o instanceof Map.Entry))
778            return false;
779           Map.Entry e = (Map.Entry)o;
780 
781           return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
782        }*/
783 
784 public int hashCode() {
785           int keyHash = (key==null ? 0 : key.hashCode());
786           int valueHash = (value==null ? 0 : value.hashCode());
787           return keyHash ^ valueHash;
788        }
789 
790 public String   toString() {          return key + "=" + value;
791        }
792   }
793 
794  public class OrderedKeyListIterator {
795     Object   current;
796 
797     public OrderedKeyListIterator() throws DException {
798       current = getTopKey();
799     }
800 
801     public Object   locateNearestRecord(Object   value) throws DException {
802       return OrderedKeyList.this.locateNearestRecord(value);
803     }
804 
805      public int getRowCount() throws DException {
806       return size();
807      }
808 
809     public boolean top() throws DException {
810        current = getTopKey();
811        return current != null;
812     }
813 
814     public boolean bottom() throws DException {
815        current = getBottomKey();
816        return current != null;
817     }
818 
819    public void changeCurrentKey(Object   object,Object   oldKey) throws DException{
820       Entry entry = getEntry(object);
821       if(entry == null)
822          return;
823       moveToKey(entry.key);
824    }
825 
826     public boolean previous() throws DException {
827       Object   p = getPreviousKey(current);
828       if(p == null)
829          return false;
830       current = p;
831       return true;
832     }
833 
834     public boolean next() throws DException {
835       Object   p = getNextKey(current);
836       if(p == null)
837          return false;
838       current = p;
839       return true;
840     }
841 
842     public boolean isTop() throws DException {
843       if( current == null )
844          return false;
845       else {
846          Object   p = getTopKey();
847          return   (p != null && current == p);
848       }
849     }
850 
851     public boolean isBottom() throws DException {
852       if( current == null )
853          return false;
854       else {
855          Object   p = getBottomKey();
856          return   (p != null && current == p) ;
857       }
858     }
859 
860     public boolean isPrevious() throws DException {
861       return current == null ? false :
862                                getPreviousKey(current) != null ;
863     }
864 
865     public boolean isNext() throws DException {
866       return current == null ? false :
867                                getNextKey(current) != null ;
868     }
869 
870     public void moveToKey(Object   key) throws DException
871     {
872       if(key == null)
873          throw new DException("DSE982",null);
874 
875       current = key;
876     }
877 
878     public Object   getKey() throws DException {
879       Entry e = getEntry(current);
880       if(current!=null && e.getValue() == null){
881         Object   nextKey = getNextKey(current);
882         if(nextKey == null ) {
883           Object   previousKey = getPreviousKey(current);
884           if(previousKey == null)
885             return null;
886           else
887             current = previousKey;
888          }
889          else
890             current = nextKey;
891       }
892       return current;
893     }
894 
895     public Object   getObject() throws DException {
896       return OrderedKeyList.this.getObject(current);
897     }
898 
899     public Comparator getComparator() throws DException {
900       return getComparator();
901     }
902  }
903 
904 }
905
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags