KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > daffodilwoods > database > general > OrderedKeyList


1 package com.daffodilwoods.database.general;
2
3 import java.util.*;
4 import com.daffodilwoods.database.resource.*;
5 import com.daffodilwoods.daffodildb.utils.comparator.SuperComparator;
6 public class OrderedKeyList //implements NavigatorS
7
{
8     /**
9      * The Comparator used to maintain order in this TreeMap, or
10      * null if this TreeMap uses its elements natural ordering.
11      *
12      * @serial
13      */

14      private SuperComparator comparator = null;
15
16      private transient Entry root = null;
17
18      private Entry current = null;
19
20      /**
21      * The number of entries in the tree
22      */

23      private transient int size = 0;
24
25      /**
26      * The number of structural modifications to the tree.
27      */

28      private transient int modCount = 0;
29
30      private void incrementSize() throws DException { size++; }
31      private void decrementSize() throws DException { size--; }
32      private static final boolean RED = false;
33      private static final boolean BLACK = true;
34
35      public OrderedKeyList(SuperComparator comparator) {
36       this.comparator = comparator;
37      }
38
39      public int size() throws DException {
40        return size;
41      }
42
43      public boolean containsKey(Object JavaDoc key) throws DException {
44        return getEntry(key) != null;
45      }
46
47      public int getRowCount() throws DException {
48       return size;
49      }
50
51      public boolean containsValue(Object JavaDoc value) throws DException {
52         return (root==null ? false :
53                 (value==null ? valueSearchNull(root)
54                      : valueSearchNonNull(root, value)));
55      }
56
57      private boolean valueSearchNull(Entry n) throws DException {
58         if (n.value == null)
59             return true;
60
61         return (n.left != null && valueSearchNull(n.left)) ||
62                (n.right != null && valueSearchNull(n.right));
63      }
64
65     /* public NavigatorIterator getNavigatorIterator() throws DException {
66          return new NavigatorIterator(new OrderedKeyListIterator());
67      } */

68
69      private boolean valueSearchNonNull(Entry n, Object JavaDoc value) throws DException {
70         if (value.equals(n.value))
71             return true;
72
73         return (n.left != null && valueSearchNonNull(n.left, value)) ||
74                (n.right != null && valueSearchNonNull(n.right, value));
75      }
76
77      public Object JavaDoc getRootKey() throws DException {
78       return root.key;
79      }
80
81      public Entry getKeyEntry() throws DException {
82       return current;
83      }
84 /* public Object getObject(Object key) throws DException {
85        Entry p = getEntry(key);
86        return (p==null ? null : p.value);
87      }
88 */

89      public Object JavaDoc getObject(Object JavaDoc key) throws DException {
90         Entry p = getEntry(key);
91       return p==null ? null : p.value;
92      }
93
94
95      public Object JavaDoc getTopKey() throws DException {
96         Entry p = firstEntry();
97       return p==null ? null : p.key;
98      }
99
100      public Object JavaDoc getPreviousKey(Object JavaDoc key) throws DException {
101       Entry k = getEntry(key);
102       Entry p = predeccesor(k);
103       return p==null ? null : p.key;
104      }
105
106      public Object JavaDoc getNextKey(Object JavaDoc key) throws DException {
107       Entry k = getEntry(key);
108       Entry p = successor(k);
109       return p==null ? null : p.key;
110      }
111
112      public Object JavaDoc getBottomKey() throws DException {
113         Entry p = lastEntry();
114          return p==null ? null : p.key;
115      }
116      public boolean top() throws DException {
117     current = firstEntry();
118       return current != null ; //? false :true
119
}
120
121      private Entry getEntry(Object JavaDoc key) throws DException {
122        Entry p = root;
123        while (p != null) {
124           int cmp = compare(key,p.key);
125           if (cmp == 0)
126               return p;
127           else if (cmp < 0)
128               p = p.left;
129           else
130               p = p.right;
131        }
132        return null;
133      }
134
135    public Object JavaDoc locateNearestRecord(Object JavaDoc value) throws DException {
136        Entry p = root;
137        while (p != null) {
138           int cmp = compare(value,p.key);
139           if (cmp == 0)
140               return p.key;
141           else if (cmp < 0){
142             if(p.left == null)
143                return p.key;
144               p = p.left;
145          }
146           else{
147             if(p.right == null)
148                return p.key;
149               p = p.right;
150          }
151       }
152        return null;
153    }
154
155    public boolean locateKey(Object JavaDoc value) throws DException {
156       return getEntry(value) != null;
157    }
158
159    private Object JavaDoc locateKey1(Object JavaDoc value) throws DException {
160        Entry p = root;
161        while (p != null) {
162           int cmp = compare(value,p.value);
163           if (cmp == 0)
164               return p;
165           else if (cmp < 0)
166               p = p.left;
167           else
168               p = p.right;
169       }
170        return null;
171    }
172
173    public void changeCurrentKey(Object JavaDoc object,Object JavaDoc oldKey) throws DException {
174       Object JavaDoc key = locateKey1(object);
175       if(key == null)
176          return;
177       moveToKey(key);
178    }
179
180      public synchronized void insert(Object JavaDoc key, Object JavaDoc value) throws DException {
181        /*if( value instanceof byte[][] )
182        {
183          Thread.dumpStack();
184          System.exit(0);
185        }*/

186
187        Entry t = root;
188
189        if (t == null) {
190         incrementSize();
191         root = new Entry(key, value, null);
192        current = root;
193         return ;
194        }
195
196        while (true) {
197         int cmp = compare(key, t.key);
198         if (cmp == 0) {
199            t.setValue(value);
200          return;
201         } else if (cmp < 0) {
202            if (t.left != null) {
203               t = t.left;
204            } else {
205             incrementSize();
206             t.left = new Entry(key, value, t);
207             fixAfterInsertion(t.left);
208             return ;
209            }
210         } else { // cmp > 0
211
if (t.right != null) {
212             t = t.right;
213            } else {
214             incrementSize();
215             t.right = new Entry(key, value, t);
216             fixAfterInsertion(t.right);
217             return ;
218            }
219         }
220        }
221      }
222
223      public void remove(Object JavaDoc key) throws DException {
224         try{
225            delete(key);
226         }catch(Exception JavaDoc ex){}
227      }
228
229      public synchronized void delete(Object JavaDoc key) throws DException{
230       if(current == null)
231         throw new DException("DSE986",null);
232       else if( key == null)
233         throw new DException("DSE982",null);
234       Entry p = getEntry(key);
235
236       if(p == null || p.value == null)
237          throw new DException("DSE978",null);
238       if(current == p){
239         if( ! next())// p.right != null
240
if(! previous())
241                 current = null;
242       }
243        deleteEntry(p);
244       p.value = null;
245        return ;
246      }
247
248    /*
249       * moves to element above the current element
250       * Returns true if there is at any data before the current and if
251         yes then set it to the current.
252        Algo :-
253       1. Call the predeccesor and pass the current as the parameter.
254       2. If p is null then return false
255       3. Else, set current to the value returned i.e. previous value and return true
256    */

257    public boolean previous() throws DException {
258       Entry p = predeccesor(current);
259       if(p == null)
260          return false;
261       current = p;
262       return true;
263    }
264
265      public boolean bottom() throws DException {
266       current = lastEntry();
267       return current != null ;
268      }
269
270      public boolean next() throws DException {
271       Entry p = successor(current);
272       if(p != null) {
273          current = p;
274          return true;
275       }
276       else
277          return false;
278      }
279
280    /* Returns true if there the current is at the top.
281       Algo :-
282       1. Checks whether there is any data left of the Current.
283          If there is, then it will always return false
284       2. Else, call the firstEntry() and return true if the
285          value return is the current and not null else false */

286
287    public boolean isTop() throws DException {
288       if( current == null || current.left != null )
289          return false;
290       else {
291          Entry p = firstEntry();
292          return (p != null && current == p);
293       }
294    }
295
296       /* Returns true if there the current is at the bottom.
297       Algo :-
298       1. Checks whether there is any data right of the Current.
299          If there is, then it will always return false
300       2. Else, call the lastEntry() and return true if the
301          value return is the current and not null else false */

302
303    public boolean isBottom() throws DException {
304       if( current == null || current.right != null)
305          return false;
306       else {
307          Entry p = lastEntry();
308          return (p != null && current == p) ;
309       }
310    }
311    /* Returns true if there is any data after the current.
312       1. Checks whether there is any data right of the Current.
313          If there is, then it will always return true
314       2. Else, call the successor() and return true if the
315          value return is not null else false */

316
317    public boolean isNext() throws DException {
318       return current == null ? false :
319             current.right != null ? true :
320                successor(current) != null ;
321    }
322    /* Returns true if there is any data before the current.
323       1. Checks whether there is any data left of the Current.
324          If there is, then it will always return true
325       2. Else, call the predeccessor() and return true if the
326          value return is not null else false */

327    public boolean isPrevious() throws DException {
328       return current == null ? false :
329             current.left != null ? true
330               : predeccesor(current)!= null ;
331    }
332
333    public void moveToKey(Object JavaDoc key) {// throws com.daffodilwoods.database.resource.DException
334
try {
335       if(current == null)
336          throw new DException("DSE562",null);
337       else if(key == null)
338          throw new DException("DSE554",null);
339       Entry p = getEntry(key);
340       current = p == null ? current : p;
341       }
342       catch(Exception JavaDoc e) {
343          e.printStackTrace();
344       }
345    }
346    /* Returns the key for current value*/
347    public Object JavaDoc getKey() throws DException {
348     return current == null ? null : current.key;
349    }
350
351    /**
352     * returns the current value
353    **/

354    public Object JavaDoc getObject() throws DException {
355     return current == null ? null : current.value;
356    }
357
358      protected int compare(Object JavaDoc k1, Object JavaDoc k2) throws DException {
359        return (comparator==null ? ((Comparable JavaDoc)k1).compareTo(k2)
360                  : comparator.compare(k1, k2));
361      }
362
363      private Entry firstEntry() throws DException {
364        Entry p = root;
365        if (p != null)
366         while (p.left != null)
367            p = p.left;
368        return p;
369      }
370
371     /**
372      * Returns the last Entry in the TreeMap (according to the TreeMap's
373      * key-sort function). Returns null if the TreeMap is empty.
374      */

375      private Entry lastEntry() throws DException {
376        Entry p = root;
377        if (p != null)
378         while (p.right != null)
379            p = p.right;
380        return p;
381      }
382
383     /**
384      * Returns the successor of the specified Entry, or null if no such.
385      */

386      private Entry successor(Entry t) throws DException {
387        if (t == null)
388         return null;
389        else if (t.right != null) {
390         Entry p = t.right;
391         while (p.left != null)
392            p = p.left;
393         return p;
394        } else {
395         Entry p = t.parent;
396         Entry ch = t;
397         while (p != null && ch == p.right) {
398            ch = p;
399            p = p.parent;
400         }
401         return p;
402        }
403     }
404
405     /**
406      * Balancing operations.
407      *
408      * Implementations of rebalancings during insertion and deletion are
409      * slightly different than the CLR version. Rather than using dummy
410      * nilnodes, we use a set of accessors that deal properly with null. They
411      * are used to avoid messiness surrounding nullness checks in the main
412      * algorithms.
413      */

414
415     private static boolean colorOf(Entry p) throws DException {
416        return (p == null ? BLACK : p.color);
417     }
418
419     private static Entry parentOf(Entry p) throws DException {
420        return (p == null ? null: p.parent);
421     }
422
423     private static void setColor(Entry p, boolean c) throws DException {
424        if (p != null) p.color = c;
425     }
426
427     private static Entry leftOf(Entry p) throws DException {
428        return (p == null)? null: p.left;
429     }
430
431     private static Entry rightOf(Entry p) throws DException {
432        return (p == null)? null: p.right;
433     }
434
435     /** From CLR **/
436     private void rotateLeft(Entry p) throws DException {
437        Entry r = p.right;
438        p.right = r.left;
439        if (r.left != null)
440           r.left.parent = p;
441        r.parent = p.parent;
442        if (p.parent == null)
443           root = r;
444        else if (p.parent.left == p)
445           p.parent.left = r;
446        else
447           p.parent.right = r;
448        r.left = p;
449        p.parent = r;
450     }
451
452     /** From CLR **/
453     private void rotateRight(Entry p) throws DException {
454        Entry l = p.left;
455        p.left = l.right;
456        if (l.right != null) l.right.parent = p;
457        l.parent = p.parent;
458        if (p.parent == null)
459           root = l;
460        else if (p.parent.right == p)
461           p.parent.right = l;
462     else p.parent.left = l;
463       l.right = p;
464       p.parent = l;
465     }
466
467
468     /** From CLR **/
469     private void fixAfterInsertion(Entry x) throws DException {
470        x.color = RED;
471
472        while (x != null && x != root && x.parent.color == RED) {
473         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
474            Entry y = rightOf(parentOf(parentOf(x)));
475            if (colorOf(y) == RED) {
476             setColor(parentOf(x), BLACK);
477             setColor(y, BLACK);
478             setColor(parentOf(parentOf(x)), RED);
479             x = parentOf(parentOf(x));
480            } else {
481             if (x == rightOf(parentOf(x))) {
482                x = parentOf(x);
483                rotateLeft(x);
484             }
485             setColor(parentOf(x), BLACK);
486             setColor(parentOf(parentOf(x)), RED);
487             if (parentOf(parentOf(x)) != null)
488                rotateRight(parentOf(parentOf(x)));
489            }
490         } else {
491            Entry y = leftOf(parentOf(parentOf(x)));
492            if (colorOf(y) == RED) {
493             setColor(parentOf(x), BLACK);
494             setColor(y, BLACK);
495             setColor(parentOf(parentOf(x)), RED);
496             x = parentOf(parentOf(x));
497            } else {
498             if (x == leftOf(parentOf(x))) {
499                x = parentOf(x);
500                rotateRight(x);
501             }
502             setColor(parentOf(x), BLACK);
503             setColor(parentOf(parentOf(x)), RED);
504             if (parentOf(parentOf(x)) != null)
505                rotateLeft(parentOf(parentOf(x)));
506            }
507         }
508     }
509     root.color = BLACK;
510   }
511
512     /**
513      * Delete node p, and then rebalance the tree.
514      */

515     private void deleteEntry(Entry p) throws DException {
516         decrementSize();
517
518     if (p.left != null && p.right != null) {
519         Entry s = successor(p);
520         swapPosition(s, p);
521     }
522
523     Entry replacement = (p.left != null ? p.left : p.right);
524
525     if (replacement != null) {
526         replacement.parent = p.parent;
527         if (p.parent == null)
528         root = replacement;
529         else if (p == p.parent.left)
530         p.parent.left = replacement;
531         else
532         p.parent.right = replacement;
533
534         p.left = p.right = p.parent = null;
535
536         if (p.color == BLACK)
537         fixAfterDeletion(replacement);
538     } else if (p.parent == null) { // return if we are the only node.
539
root = null;
540     } else { // No children. Use self as phantom replacement and unlink.
541
if (p.color == BLACK)
542         fixAfterDeletion(p);
543
544         if (p.parent != null) {
545         if (p == p.parent.left)
546             p.parent.left = null;
547         else if (p == p.parent.right)
548             p.parent.right = null;
549         p.parent = null;
550         }
551     }
552     }
553
554
555      /* Returns the next Data*/
556   private Entry predeccesor(Entry t) throws DException {
557       if (t == null)
558          return null;
559       else if (t.left != null) {
560          Entry p = t.left;
561          while (p.right != null)
562               p = p.right;
563          return p;
564       }
565      else {
566         Entry p = t.parent;
567         Entry ch = t;
568         while (p != null && ch == p.left) {
569            ch = p;
570            p = p.parent;
571         }
572         return p;
573       }
574   }
575
576   public void show(){
577       try{
578       Object JavaDoc iter = getTopKey();
579       if(iter != null){
580          do{
581             iter = getNextKey(iter);
582          }while(iter != null);
583       }else
584          ;//// Removed By Program ** System.out.println("No Record In List "+size);
585
}catch(DException E){E.printStackTrace();}
586   }
587
588   public OrderedKeyListIterator getIterator() throws DException {
589    return new OrderedKeyListIterator();
590   }
591
592     /** From CLR **/
593     private void fixAfterDeletion(Entry x) throws DException {
594     while (x != root && colorOf(x) == BLACK) {
595         if (x == leftOf(parentOf(x))) {
596         Entry sib = rightOf(parentOf(x));
597
598         if (colorOf(sib) == RED) {
599             setColor(sib, BLACK);
600             setColor(parentOf(x), RED);
601             rotateLeft(parentOf(x));
602             sib = rightOf(parentOf(x));
603         }
604
605         if (colorOf(leftOf(sib)) == BLACK &&
606             colorOf(rightOf(sib)) == BLACK) {
607             setColor(sib, RED);
608             x = parentOf(x);
609         } else {
610             if (colorOf(rightOf(sib)) == BLACK) {
611             setColor(leftOf(sib), BLACK);
612             setColor(sib, RED);
613             rotateRight(sib);
614             sib = rightOf(parentOf(x));
615             }
616             setColor(sib, colorOf(parentOf(x)));
617             setColor(parentOf(x), BLACK);
618             setColor(rightOf(sib), BLACK);
619             rotateLeft(parentOf(x));
620             x = root;
621         }
622         } else { // symmetric
623
Entry sib = leftOf(parentOf(x));
624
625         if (colorOf(sib) == RED) {
626             setColor(sib, BLACK);
627             setColor(parentOf(x), RED);
628             rotateRight(parentOf(x));
629             sib = leftOf(parentOf(x));
630         }
631
632         if (colorOf(rightOf(sib)) == BLACK &&
633             colorOf(leftOf(sib)) == BLACK) {
634             setColor(sib, RED);
635             x = parentOf(x);
636         } else {
637             if (colorOf(leftOf(sib)) == BLACK) {
638             setColor(rightOf(sib), BLACK);
639             setColor(sib, RED);
640             rotateLeft(sib);
641             sib = leftOf(parentOf(x));
642             }
643             setColor(sib, colorOf(parentOf(x)));
644             setColor(parentOf(x), BLACK);
645             setColor(leftOf(sib), BLACK);
646             rotateRight(parentOf(x));
647             x = root;
648         }
649         }
650     }
651
652     setColor(x, BLACK);
653     }
654
655     /**
656      * Swap the linkages of two nodes in a tree.
657      */

658     private void swapPosition(Entry x, Entry y) throws DException {
659     Entry px = x.parent, lx = x.left, rx = x.right;
660     Entry py = y.parent, ly = y.left, ry = y.right;
661     boolean xWasLeftChild = px != null && x == px.left;
662     boolean yWasLeftChild = py != null && y == py.left;
663
664     if (x == py) { // x was y's parent
665
x.parent = y;
666         if (yWasLeftChild) {
667         y.left = x;
668         y.right = rx;
669         } else {
670         y.right = x;
671         y.left = lx;
672         }
673     } else {
674         x.parent = py;
675         if (py != null) {
676         if (yWasLeftChild)
677             py.left = x;
678         else
679             py.right = x;
680         }
681         y.left = lx;
682         y.right = rx;
683     }
684
685     if (y == px) { // y was x's parent
686
y.parent = x;
687         if (xWasLeftChild) {
688         x.left = y;
689         x.right = ry;
690         } else {
691         x.right = y;
692         x.left = ly;
693         }
694     } else {
695         y.parent = px;
696         if (px != null) {
697         if (xWasLeftChild)
698             px.left = y;
699         else
700             px.right = y;
701         }
702         x.left = ly;
703         x.right = ry;
704     }
705
706     if (x.left != null)
707         x.left.parent = x;
708     if (x.right != null)
709         x.right.parent = x;
710     if (y.left != null)
711         y.left.parent = y;
712     if (y.right != null)
713         y.right.parent = y;
714
715     boolean c = x.color;
716     x.color = y.color;
717     y.color = c;
718
719     if (root == x)
720         root = y;
721     else if (root == y)
722         root = x;
723     }
724
725      public class Entry {//implements Map.Entry
726
public Object JavaDoc key;
727        Object JavaDoc value;
728        public Entry left = null;
729        public Entry right = null;
730        Entry parent;
731        boolean color = BLACK;
732
733        /**
734        * Make a new cell with given key, value, and parent, and with <tt>null</tt>
735        * child links, and BLACK color.
736        */

737        Entry(Object JavaDoc key, Object JavaDoc value, Entry parent) {
738           this.key = key;
739           this.value = value;
740           this.parent = parent;
741        }
742
743        /**
744        * Returns the key.
745          *
746        * @return the key.
747        */

748        public Object JavaDoc getKey() throws DException {
749           return key;
750        }
751
752        /**
753        * Returns the value associated with the key.
754          *
755        * @return the value associated with the key.
756        */

757        public Object JavaDoc getValue() throws DException {
758           return value;
759        }
760
761        /**
762        * Replaces the value currently associated with the key with the given
763        * value.
764          *
765          * @return the value associated with the key before this method was
766          * called.
767        */

768        public Object JavaDoc setValue(Object JavaDoc value) throws DException {
769           Object JavaDoc oldValue = this.value;
770           this.value = value;
771           return oldValue;
772        }
773
774      /* public boolean equals(Object o) throws DException {
775         if (!(o instanceof Map.Entry))
776            return false;
777           Map.Entry e = (Map.Entry)o;
778
779           return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
780        }*/

781
782 public int hashCode() {
783           int keyHash = (key==null ? 0 : key.hashCode());
784           int valueHash = (value==null ? 0 : value.hashCode());
785           return keyHash ^ valueHash;
786        }
787
788 public String JavaDoc toString() { return key + "=" + value;
789        }
790   }
791
792  public class OrderedKeyListIterator {
793     Object JavaDoc current;
794
795     public OrderedKeyListIterator() throws DException {
796       current = getTopKey();
797     }
798
799     public Object JavaDoc locateNearestRecord(Object JavaDoc value) throws DException {
800       return OrderedKeyList.this.locateNearestRecord(value);
801     }
802
803      public int getRowCount() throws DException {
804       return size();
805      }
806
807     public boolean top() throws DException {
808        current = getTopKey();
809        return current != null;
810     }
811
812     public boolean bottom() throws DException {
813        current = getBottomKey();
814        return current != null;
815     }
816
817    public void changeCurrentKey(Object JavaDoc object,Object JavaDoc oldKey) throws DException{
818       Entry entry = getEntry(object);
819       if(entry == null)
820          return;
821       moveToKey(entry.key);
822    }
823
824     public boolean previous() throws DException {
825       Object JavaDoc p = getPreviousKey(current);
826       if(p == null)
827          return false;
828       current = p;
829       return true;
830     }
831
832     public boolean next() throws DException {
833       Object JavaDoc p = getNextKey(current);
834       if(p == null)
835          return false;
836       current = p;
837       return true;
838     }
839
840     public boolean isTop() throws DException {
841       if( current == null )
842          return false;
843       else {
844          Object JavaDoc p = getTopKey();
845          return (p != null && current == p);
846       }
847     }
848
849     public boolean isBottom() throws DException {
850       if( current == null )
851          return false;
852       else {
853          Object JavaDoc p = getBottomKey();
854          return (p != null && current == p) ;
855       }
856     }
857
858     public boolean isPrevious() throws DException {
859       return current == null ? false :
860                                getPreviousKey(current) != null ;
861     }
862
863     public boolean isNext() throws DException {
864       return current == null ? false :
865                                getNextKey(current) != null ;
866     }
867
868     public void moveToKey(Object JavaDoc key) throws DException
869     {
870       if(key == null)
871          throw new DException("DSE982",null);
872
873       current = key;
874     }
875
876     public Object JavaDoc getKey() throws DException {
877       Entry e = getEntry(current);
878       if(current!=null && e.getValue() == null){
879         Object JavaDoc nextKey = getNextKey(current);
880         if(nextKey == null ) {
881           Object JavaDoc previousKey = getPreviousKey(current);
882           if(previousKey == null)
883             return null;
884           else
885             current = previousKey;
886          }
887          else
888             current = nextKey;
889       }
890       return current;
891     }
892
893     public Object JavaDoc getObject() throws DException {
894       return OrderedKeyList.this.getObject(current);
895     }
896
897     public Comparator getComparator() throws DException {
898       return getComparator();
899     }
900  }
901
902 }
903
Popular Tags