IndexNode


1   /*
2    * IndexNode.java
3     *  Copyright (C) <2005>  <Steve Woodcock>
4    *  
5   
6    * Created on 09 May 2003, 15:13
7    */
8   package com.jofti.btree;
9   
10  
11  
12  /**
13   * <p>
14   * The internal nodes in the BTree. These nodes do not contain any data - they are simply pointers to lower level 
15   * index nodes or leaf nodes.</p>
16   * <p>
17   * Each node follows the pattern of an indexnode which is an array of sorted pointers to a lower level index or leaf node. Each entry 
18   * in the array contains the largest value in the subtree under the pointer. The Node itself in its right value contains the largest 
19   * entry in its array.
20   * </p>
21   *
22   * @author  Steve Woodcock (steve@jofti.com)<br>
23   * @version 1.12<br>
24   * 
25   */
26  class IndexNode extends Node {
27      
28      private IndexNodeEntry parentKey = null;
29      
30      protected Object  [] keyList = new Object  [BTree.getMaxNodeSize()+1];
31      
32         
33  
34      private Comparable   rightValue = null;
35      // b+ linked list metaphor to traverse sequentially
36      
37      private NodeLink nextNode = null;
38      
39      private boolean deleted =false;
40      
41      /**
42       * @return  if the node has been deleted.
43       */
44      public boolean isDeleted()
45      {
46          return deleted;
47      }
48      
49      /**
50       * @param deleted Sets the node to deleted if true.
51       */
52      public void setDeleted(boolean deleted)
53      {
54          this.deleted = deleted;
55      }
56      
57      /** Creates a new instance of IndexNode */
58      protected IndexNode() {
59      }
60      
61      
62      
63      /**
64       * Returns the node entry where the entry should be. This is achieved by comparing the right values 
65       * of the node entries in the node.<p>
66       * 
67       * 
68       * @param entry the value to find.
69       * @return The node in this index node that the value should be in (or in a subtreee from that node).
70       */
71      public Node getContainingNode(Comparable   entry) {
72  
73              if (entryNumber ==0)
74              {
75                  return null;
76              }
77              
78              
79              // look through list and see if we have a match
80                  
81              return indexedBinaryRetrieve(keyList,entry);
82  
83          }
84  
85      protected  Node indexedBinaryRetrieve(Object  [] list1, Object   obj)
86      {
87          int i = 0;
88          IndexNodeEntry entry =null;
89          int size =entryNumber;
90          for(int j =  size- 1; i <= j;)
91          {
92              int k = i + j >> 1;
93              entry = (IndexNodeEntry)list1[k];
94              int l = entry.value.compareTo(obj);
95              if(l < 0){
96                  i = k + 1;
97              } else if(l > 0){
98                  j = k - 1;
99              }else{
100                 return entry.getChildNode();
101             }
102         }
103         
104         i= -(i + 1);
105         
106         if (-i == entryNumber){
107                 return entry.getChildNode();
108         }  else{
109             return  ((IndexNodeEntry)list1[-i-1]).getChildNode();
110         }
111         
112     }
113 
114  
115    
116     protected  int indexedBinaryLocate(Object  [] list1, Object   obj)
117     {
118 
119           
120           int low = 0;
121             int high = entryNumber-1;
122             
123             IndexNodeEntry entry =null;
124             while (low <= high) {
125                 int mid = (low + high) >> 1;
126                 
127                 entry = (IndexNodeEntry)list1[mid];
128                 int cmp = entry.compareTo(obj);
129 
130                 if (cmp < 0)
131                 low = mid + 1;
132                 else if (cmp > 0)
133                 high = mid - 1;
134                 else
135                 return mid; // key found
136             }
137             return -(low + 1);  // key not found
138 
139         }
140 
141 
142 
143     
144     /* (non-Javadoc)
145      * @see com.jofti.btree.INode#insertEntry(com.jofti.btree.NodeEntry)
146      */
147     public Object  [] insertEntry(NodeEntry key) {
148         
149         //lets reset the next node if it is deleted
150         resetNextNode();
151         
152         IndexNodeEntry entry = (IndexNodeEntry) key;
153         
154         // if there are no entries then set it in
155         if (entryNumber == 0) {
156             keyList[0]=entry;
157             entry.setContainingNode(this);
158             entryNumber++;
159             rightValue=entry.getValue();
160             return keyList;
161            
162         } else {
163             //loop through entries to find right place
164             // we do not use a binary search here as we want to do different things
165             for (int i=0;i<entryNumber;i++) {
166                 IndexNodeEntry listEntry = (IndexNodeEntry)keyList[i];
167                 // the current node is bigger so insert here
168                 
169                 
170                 // is it bigger than a value in the list
171                 int comparison = listEntry.getValue().compareTo(entry.getValue());
172                 if ( comparison>0) {
173                     
174                     System.arraycopy(keyList, i, keyList, i + 1,
175                             entryNumber - i);
176                     keyList[i] = entry;
177 
178                     entry.setContainingNode(this);
179                     entryNumber++;
180                     return keyList;
181                     // is it equal - which means we will need to rest the conflicting value to make sure
182                     // there is no problem - should be as the result of a split
183                 } else if (comparison ==0 ){
184                     // this is a split node that has a key value that is equal
185                     listEntry.updateValue();
186                     if (i == entryNumber -1){
187                         keyList[entryNumber]=entry;
188                         rightValue=entry.getValue();
189                         
190                     }else{
191                         int inner =i+1;
192                         System.arraycopy(keyList, inner, keyList, inner+1,
193                                 entryNumber - inner);
194                         keyList[inner] = entry;
195                     }
196                      entry.setContainingNode(this);
197                      entryNumber++;
198                      return keyList;
199                 }
200             }
201        
202             keyList[entryNumber]=entry;
203             rightValue=entry.getValue();
204             entry.setContainingNode(this);
205             entryNumber++;
206             return keyList;
207         }
208         
209         
210         
211     }
212     
213     
214     private void resetNextNode(){
215         if (nextNode != null && nextNode.getNode() != null 
216                 && nextNode.getNode().isDeleted())
217         {
218             nextNode = nextNode.getNode().getLinkNode();
219         }
220     }
221     
222     /**
223      * updates the key right value for the node entry passed in.<p> 
224      * 
225      * @param key - the key for the entry to update.<br>
226      * @return - true of the right value for the entire node was updated - false if the node entry was 
227      * not the right most entry.
228      */
229     public boolean updateEntry(NodeEntry key) {
230         
231         resetNextNode();
232         IndexNodeEntry entry = (IndexNodeEntry) key;
233         
234         if (entryNumber == 0) {
235            
236             return false;
237            
238         } else {
239             int length = entryNumber;
240             for (int i=0;i<length;i++) {
241                 IndexNodeEntry listEntry = (IndexNodeEntry)keyList[i];
242                 if (listEntry.getValue().equals(entry.getValue()) ) {
243                     // this is a split node that has a key value that is equal
244                     listEntry.updateValue();
245                     if (i == length -1){
246                         rightValue=listEntry.getValue();
247                     }
248                     return true;
249                 }
250             }
251             return false;
252         }
253         
254         
255         
256     }
257     
258     
259 
260     /**
261      * Sets the keylist for the node entries.<p>
262      * 
263      * @param keys - the new entry list for the node.
264      */
265     public void setKeyList(Object  [] temp){
266         
267 
268 
269         for(int i=0;i<entryNumber;i++){
270                 IndexNodeEntry entry = (IndexNodeEntry) temp[i];
271                 entry.setContainingNode(this);
272                 keyList[i]=entry;
273         }
274 
275     }
276     
277     
278     /* (non-Javadoc)
279      * @see com.jofti.btree.INode#isEmpty()
280      */
281     public boolean isEmpty() {
282         if (entryNumber == 0) {
283             return true;
284         }
285         return false;
286     }
287     
288   
289     
290     /* (non-Javadoc)
291      * @see com.jofti.btree.INode#getRightValue()
292      */
293     public Comparable   getRightValue() {
294          return rightValue;
295     }
296     
297    
298     
299     IndexNodeEntry getParentKey() {
300         return parentKey;
301     }
302     
303     
304     public String   toString() {
305         StringBuffer   buf = new StringBuffer  ();
306         buf.append("  IndexNode{");
307        
308         buf.append(" rightValue:" + getRightValue() +"}");
309         return buf.toString();
310     }
311     
312     public boolean isUnderFull() {
313         if (entryNumber < BTree.getMaxNodeSize() ) {
314             return true;
315         }
316         return false;
317     }
318     
319     /** Setter for property parentNode.
320      * @param parentNode New value of property parentNode.
321      *
322      *
323      */
324     void setParentKey(IndexNodeEntry parentKey) {
325         this.parentKey = parentKey;
326     }
327     
328  
329     
330     /* (non-Javadoc)
331      * @see com.jofti.btree.INode#deleteEntry(com.jofti.btree.NodeEntry)
332      */
333     public boolean deleteEntry(NodeEntry entry) {
334 
335             resetNextNode();
336             
337             int location = indexedBinaryLocate(keyList,entry);
338            
339             if (location >=0) {
340                 // we need to remove the entry
341                 
342                 int numMoved = entryNumber - location - 1;
343                 if (numMoved > 0)
344                     System.arraycopy(keyList, location+1, keyList, location,
345                              numMoved);
346                 keyList[--entryNumber] = null; // Let gc do its work
347                 
348                 
349             
350                 if (entryNumber ==0){
351                     rightValue = BTree.MIN_RIGHT_VALUE;
352                 }else{
353                     ((IndexNodeEntry)keyList[entryNumber-1]).updateValue();
354                     setRightValue(((IndexNodeEntry)keyList[entryNumber-1]).getValue());
355                 }
356                 return true;
357             }
358             return false;
359             
360     }
361     
362     /* (non-Javadoc)
363      * @see com.jofti.btree.INode#splitNode()
364      */
365     public Node splitNode(Object  [] entries)
366     {
367         // first insert the entry
368 
369         Object  [] entriesList = split(entries,entryNumber);
370         
371         
372         
373         Node newNode = NodeFactory.getInstance().createIndexNode();
374 
375         Comparable   currentRight = rightValue;
376 
377         //set up new node
378         EntrySplitWrapper newEntries = ((EntrySplitWrapper)entriesList[1]);
379         
380         newNode.entryNumber = newEntries.size; 
381         newNode.setEntries( (Object  []) newEntries.entries );
382         
383         
384         newNode.setRightValue(currentRight);
385         newNode.setLinkNode(getLinkNode());
386         
387 //          replace values in current node
388         
389         EntrySplitWrapper replacements = (EntrySplitWrapper)entriesList[0];
390         
391         
392         keyList = (Object  [])replacements.entries;
393         entryNumber = replacements.size;
394         setRightValue(((NodeEntry) keyList[entryNumber - 1]).getValue());
395         
396         
397     
398         
399         return newNode;
400 
401     }
402     
403     /* (non-Javadoc)
404      * @see com.jofti.btree.INode#getEntryNumber()
405      */
406     public int getEntryNumber() {
407         return entryNumber;
408     }
409     
410  
411     
412     /* (non-Javadoc)
413      * @see com.jofti.btree.INode#getEntries()
414      */
415     public Object  [] getEntries() {
416         
417         return keyList;
418     }
419     
420 
421 
422     /* (non-Javadoc)
423      * @see com.jofti.btree.Node#setRightValue(java.lang.Comparable)
424      */
425     public void setRightValue(Comparable   value)
426     {
427         this.rightValue = value;
428         
429     }
430 
431     /* (non-Javadoc)
432      * @see com.jofti.btree.Node#split()
433      */
434     
435 
436     /* (non-Javadoc)
437      * @see com.jofti.btree.Node#setEntries(java.util.List)
438      */
439     public void setEntries(Object  [] entries)
440     {
441         setKeyList(entries);
442         
443     }
444 
445     /* (non-Javadoc)
446      * @see com.jofti.btree.Node#getLinkNode()
447      */
448     public NodeLink getLinkNode()
449     {
450         
451         return nextNode;
452     }
453 
454     /* (non-Javadoc)
455      * @see com.jofti.btree.Node#setLinkNode(com.jofti.btree.Node)
456      */
457     public void setLinkNode(NodeLink node)
458     {
459         this.nextNode = node;
460         
461     }
462 
463     /** 
464      * This method checks to see if the value should be contained in the leaf nodes that are 
465      * children of this indexNode (or children of its children). It does not check if the actual 
466      * value is in the sub tree- rather it checks if its values are larger than this value.<p>
467      * 
468      * @param value
469      * 
470      * @return true if the node has a larger value in it - false otherwise.
471      */
472     public boolean contains(Comparable   value)
473     {
474         if (entryNumber ==0 || value ==null)
475         {
476             return false;
477         }
478 
479         if (value instanceof MinComparableValue){
480             return true;
481         }
482          return rightValue.compareTo(value) >=0;
483     }
484     
485    
486 }
487
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags