001/**
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.activemq.store.kahadb.disk.index;
018
019import java.io.DataInput;
020import java.io.DataOutput;
021import java.io.IOException;
022import java.io.PrintWriter;
023import java.util.Arrays;
024import java.util.Iterator;
025import java.util.Map;
026import java.util.NoSuchElementException;
027import java.util.Map.Entry;
028
029import org.apache.activemq.store.kahadb.disk.index.BTreeIndex.Prefixer;
030import org.apache.activemq.store.kahadb.disk.page.Page;
031import org.apache.activemq.store.kahadb.disk.page.Transaction;
032import org.apache.activemq.store.kahadb.disk.util.VariableMarshaller;
033
034
035/**
036 * The BTreeNode class represents a node in the BTree object graph.  It is stored in 
037 * one Page of a PageFile.
038 */
039public final class BTreeNode<Key,Value> {
040
041    // The index that this node is part of.
042    private final BTreeIndex<Key,Value> index;
043    // The parent node or null if this is the root node of the BTree
044    private BTreeNode<Key,Value> parent;
045    // The page associated with this node
046    private Page<BTreeNode<Key,Value>> page;
047    
048    // Order list of keys in the node
049    private Key[] keys;
050    // Values associated with the Keys. Null if this is a branch node.
051    private Value[] values;
052    // nodeId pointers to children BTreeNodes. Null if this is a leaf node.
053    private long[] children;
054    // The next leaf node after this one.  Used for fast iteration of the entries.
055    private long next = -1;
056    
057    private final class KeyValueEntry implements Map.Entry<Key, Value> {
058        private final Key key;
059        private final Value value;
060
061        public KeyValueEntry(Key key, Value value) {
062            this.key = key;
063            this.value = value;
064        }
065
066        public Key getKey() {
067            return key;
068        }
069
070        public Value getValue() {
071            return value;
072        }
073
074        public Value setValue(Value value) {
075            throw new UnsupportedOperationException();
076        }
077
078    }
079
080    private final class BTreeIterator implements Iterator<Map.Entry<Key, Value>> {
081        
082        private final Transaction tx;
083        private final Key endKey;
084        BTreeNode<Key,Value> current;
085        int nextIndex;
086        Map.Entry<Key,Value> nextEntry;
087
088        private BTreeIterator(Transaction tx, BTreeNode<Key, Value> current, int nextIndex, Key endKey) {
089            this.tx = tx;
090            this.current = current;
091            this.nextIndex=nextIndex;
092            this.endKey = endKey;
093            if (endKey != null && endKey.equals(0l)) {
094                Thread.dumpStack();
095            }
096        }
097
098        synchronized private void findNextPage() {
099            if( nextEntry!=null ) {
100                return;
101            }
102            
103            try {
104                while( current!=null ) {
105                    if( nextIndex >= current.keys.length ) {
106                        // we need to roll to the next leaf..
107                        if( current.next >= 0 ) {
108                            current = index.loadNode(tx, current.next, null);
109                            assert !current.isBranch() : "Should have linked to the next leaf node.";
110                            nextIndex=0;
111                        } else {
112                            break;
113                        }
114                    }  else {
115                        if (endKey != null && current.keys[nextIndex].equals(endKey)) {
116                            break;
117                        }
118                        nextEntry = new KeyValueEntry(current.keys[nextIndex], current.values[nextIndex]);
119                        nextIndex++;
120                        break;
121                    }
122                    
123                }
124            } catch (IOException e) {
125            }
126        }
127
128        public boolean hasNext() {
129            findNextPage();
130            return nextEntry !=null;
131        }
132
133        public Entry<Key, Value> next() {
134            findNextPage(); 
135            if( nextEntry !=null ) {
136                Entry<Key, Value> lastEntry = nextEntry;
137                nextEntry=null;
138                return lastEntry;
139            } else {
140                throw new NoSuchElementException();
141            }
142        }
143
144        public void remove() {
145            throw new UnsupportedOperationException();
146        }
147    }
148
149    /**
150     * The Marshaller is used to store and load the data in the BTreeNode into a Page.
151     *  
152     * @param <Key>
153     * @param <Value>
154     */
155    static public class Marshaller<Key,Value> extends VariableMarshaller<BTreeNode<Key,Value>> {
156        private final BTreeIndex<Key,Value> index;
157        
158        public Marshaller(BTreeIndex<Key,Value> index) {
159            this.index = index;
160        }
161
162        public void writePayload(BTreeNode<Key,Value> node, DataOutput os) throws IOException {
163            // Write the keys
164            short count = (short)node.keys.length; // cast may truncate value...
165            if( count != node.keys.length ) {
166                throw new IOException("Too many keys");
167            }
168            
169            os.writeShort(count);
170            for (int i = 0; i < node.keys.length; i++) {
171                index.getKeyMarshaller().writePayload(node.keys[i], os);
172            }
173            
174            if( node.isBranch() ) {
175                // If this is a branch...
176                os.writeBoolean(true);
177                for (int i = 0; i < count+1; i++) {
178                    os.writeLong(node.children[i]);
179                }
180                
181            } else {
182                // If this is a leaf
183                os.writeBoolean(false);
184                for (int i = 0; i < count; i++) {
185                    index.getValueMarshaller().writePayload(node.values[i], os);
186                }
187                os.writeLong(node.next);
188            }
189        }
190
191        @SuppressWarnings("unchecked")
192        public BTreeNode<Key,Value> readPayload(DataInput is) throws IOException {
193            BTreeNode<Key,Value>  node = new BTreeNode<Key,Value>(index);
194            int count = is.readShort();
195            
196            node.keys = (Key[])new Object[count];
197            for (int i = 0; i < count; i++) {
198                node.keys[i] = index.getKeyMarshaller().readPayload(is);
199            }
200            
201            if( is.readBoolean() ) {
202                node.children = new long[count+1];
203                for (int i = 0; i < count+1; i++) {
204                    node.children[i] = is.readLong();
205                }
206            } else {
207                node.values = (Value[])new Object[count];
208                for (int i = 0; i < count; i++) {
209                    node.values[i] = index.getValueMarshaller().readPayload(is);
210                }
211                node.next = is.readLong();
212            }
213            return node;
214        }
215    }
216
217    public BTreeNode(BTreeIndex<Key,Value> index) {
218        this.index = index;
219    }
220    
221    public void setEmpty() {
222        setLeafData(createKeyArray(0), createValueArray(0));
223    }
224    
225
226    /**
227     * Internal (to the BTreeNode) method. Because this method is called only by
228     * BTreeNode itself, no synchronization done inside of this method.
229     * @throws IOException 
230     */
231    private BTreeNode<Key,Value> getChild(Transaction tx, int idx) throws IOException {
232        if (isBranch() && idx >= 0 && idx < children.length) {
233            BTreeNode<Key, Value> result = this.index.loadNode(tx, children[idx], this);
234            return result;
235        } else {
236            return null;
237        }
238    }
239
240
241    /**
242     * Returns the right most leaf from the current btree graph.
243     * @throws IOException
244     */
245    private BTreeNode<Key,Value> getRightLeaf(Transaction tx) throws IOException {
246        BTreeNode<Key,Value> cur = this;
247        while(cur.isBranch()) {
248            cur = cur.getChild(tx, cur.keys.length);
249        }
250        return cur;
251    }
252
253    /**
254     * Returns the left most leaf from the current btree graph.
255     * @throws IOException
256     */
257    private BTreeNode<Key,Value> getLeftLeaf(Transaction tx) throws IOException {
258        BTreeNode<Key,Value> cur = this;
259        while(cur.isBranch()) {
260            cur = cur.getChild(tx, 0);
261        }
262        return cur;
263    }
264
265    /**
266     * Returns the left most leaf from the current btree graph.
267     * @throws IOException
268     */
269    private BTreeNode<Key,Value> getLeftPeer(Transaction tx, BTreeNode<Key,Value> x) throws IOException {
270        BTreeNode<Key,Value> cur = x;
271        while( cur.parent !=null ) {
272            if( cur.parent.children[0] == cur.getPageId() ) {
273                cur = cur.parent;
274            } else {
275                for( int i=0; i < cur.parent.children.length; i ++) {
276                    if( cur.parent.children[i]==cur.getPageId() ) {
277                        return  cur.parent.getChild(tx, i-1);
278                    }
279                }
280                throw new AssertionError("page "+x+" was decendent of "+cur.getPageId());
281            }
282        }
283        return null;
284    }
285
286    public Value remove(Transaction tx, Key key) throws IOException {
287
288        if(isBranch()) {
289            int idx = Arrays.binarySearch(keys, key);
290            idx = idx < 0 ? -(idx + 1) : idx + 1;
291            BTreeNode<Key, Value> child = getChild(tx, idx);
292            if( child.getPageId() == index.getPageId() ) {
293                throw new IOException("BTree corrupted: Cycle detected.");
294            }
295            Value rc = child.remove(tx, key);
296            
297            // child node is now empty.. remove it from the branch node.
298            if( child.keys.length == 0 ) {
299                
300                // If the child node is a branch, promote
301                if( child.isBranch() ) {
302                    // This is cause branches are never really empty.. they just go down to 1 child..
303                    children[idx] = child.children[0];
304                    tx.free(child.getPage());
305                } else {
306                    
307                    // The child was a leaf. Then we need to actually remove it from this branch node..
308                    // and relink the previous leaf to skip to the next leaf.
309
310                    BTreeNode<Key, Value> previousLeaf = null;
311                    if( idx > 0 ) {
312                        // easy if we this node hold the previous child.
313                        previousLeaf = getChild(tx, idx-1).getRightLeaf(tx);
314                    } else {
315                        // less easy if we need to go to the parent to find the previous child.
316                        BTreeNode<Key, Value> lp = getLeftPeer(tx, this);
317                        if( lp!=null ) {
318                            previousLeaf = lp.getRightLeaf(tx);
319                        }
320                        // lp will be null if there was no previous child.
321                    }
322
323                    if( previousLeaf !=null ) {
324                        previousLeaf.next = child.next;
325                        index.storeNode(tx, previousLeaf, true);
326                    }
327
328                    if( idx < children.length-1 ) {
329                        // Delete it and key to the right.
330                        setBranchData(arrayDelete(keys, idx), arrayDelete(children, idx));
331                    } else {
332                        // It was the last child.. Then delete it and key to the left
333                        setBranchData(arrayDelete(keys, idx-1), arrayDelete(children, idx));
334                    }
335                    
336                    // If we are the root node, and only have 1 child left.  Then 
337                    // make the root be the leaf node.
338                    if( children.length == 1 && parent==null ) {
339                        child = getChild(tx, 0);
340                        keys = child.keys;
341                        children = child.children;
342                        values = child.values;
343                        // free up the page..
344                        tx.free(child.getPage());
345                    }
346                    
347                }
348                index.storeNode(tx, this, true);
349            }
350            
351            return rc;
352        } else {
353            int idx = Arrays.binarySearch(keys, key);
354            if (idx < 0) {
355                return null;
356            } else {
357                Value oldValue = values[idx];
358                setLeafData(arrayDelete(keys, idx), arrayDelete(values, idx));
359                
360                if( keys.length==0 && parent!=null) {
361                    tx.free(getPage());
362                } else {
363                    index.storeNode(tx, this, true);
364                }
365                
366                return oldValue;
367            }
368        }
369    }
370
371    public Value put(Transaction tx, Key key, Value value) throws IOException {
372        if (key == null) {
373            throw new IllegalArgumentException("Key cannot be null");
374        }
375
376        if( isBranch() ) {
377            return getLeafNode(tx, this, key).put(tx, key, value);
378        } else {
379            int idx = Arrays.binarySearch(keys, key);
380            
381            Value oldValue=null;
382            if (idx >= 0) {
383                // Key was found... Overwrite
384                oldValue = values[idx];
385                values[idx] = value;
386                setLeafData(keys, values);
387            } else {
388                // Key was not found, Insert it
389                idx = -(idx + 1);
390                setLeafData(arrayInsert(keys, key, idx), arrayInsert(values, value, idx));
391            }
392            
393            try {
394                index.storeNode(tx, this, allowOverflow());
395            } catch ( Transaction.PageOverflowIOException e ) {
396                // If we get an overflow 
397                split(tx);
398            }
399            
400            return oldValue;
401        }
402    }
403
404    private void promoteValue(Transaction tx, Key key, long nodeId) throws IOException {
405
406        int idx = Arrays.binarySearch(keys, key);
407        idx = idx < 0 ? -(idx + 1) : idx + 1;
408        setBranchData(arrayInsert(keys, key, idx), arrayInsert(children, nodeId, idx + 1));
409
410        try {
411            index.storeNode(tx, this, allowOverflow());
412        } catch ( Transaction.PageOverflowIOException e ) {
413            split(tx);
414        }
415
416    }
417
418    /**
419     * Internal to the BTreeNode method
420     */
421    private void split(Transaction tx) throws IOException {
422        Key[] leftKeys;
423        Key[] rightKeys;
424        Value[] leftValues=null;
425        Value[] rightValues=null;
426        long[] leftChildren=null;
427        long[] rightChildren=null;
428        Key separator;
429
430        int vc = keys.length;
431        int pivot = vc / 2;
432
433        // Split the node into two nodes
434        if( isBranch() ) {
435
436            leftKeys = createKeyArray(pivot);
437            leftChildren = new long[leftKeys.length + 1];
438            rightKeys = createKeyArray(vc - (pivot + 1));
439            rightChildren = new long[rightKeys.length + 1];
440
441            System.arraycopy(keys, 0, leftKeys, 0, leftKeys.length);
442            System.arraycopy(children, 0, leftChildren, 0, leftChildren.length);
443            System.arraycopy(keys, leftKeys.length + 1, rightKeys, 0, rightKeys.length);
444            System.arraycopy(children, leftChildren.length, rightChildren, 0, rightChildren.length);
445
446            // Is it a Simple Prefix BTree??
447            Prefixer<Key> prefixer = index.getPrefixer();
448            if(prefixer!=null) {
449                separator = prefixer.getSimplePrefix(leftKeys[leftKeys.length - 1], rightKeys[0]);
450            } else {
451                separator = keys[leftKeys.length];
452            }
453                
454            
455        } else {
456
457            leftKeys = createKeyArray(pivot);
458            leftValues = createValueArray(leftKeys.length);
459            rightKeys = createKeyArray(vc - pivot);
460            rightValues = createValueArray(rightKeys.length);
461
462            System.arraycopy(keys, 0, leftKeys, 0, leftKeys.length);
463            System.arraycopy(values, 0, leftValues, 0, leftValues.length);
464            System.arraycopy(keys, leftKeys.length, rightKeys, 0, rightKeys.length);
465            System.arraycopy(values, leftValues.length, rightValues, 0, rightValues.length);
466
467            // separator = getSeparator(leftVals[leftVals.length - 1],
468            // rightVals[0]);
469            separator = rightKeys[0];
470
471        }
472
473        // Promote the pivot to the parent branch
474        if (parent == null) {
475            
476            // This can only happen if this is the root
477            BTreeNode<Key,Value> rNode = this.index.createNode(tx, this);
478            BTreeNode<Key,Value> lNode = this.index.createNode(tx, this);
479
480            if( isBranch() ) {
481                rNode.setBranchData(rightKeys, rightChildren);
482                lNode.setBranchData(leftKeys, leftChildren);
483            } else {
484                rNode.setLeafData(rightKeys, rightValues);
485                lNode.setLeafData(leftKeys, leftValues);
486                lNode.setNext(rNode.getPageId());
487            }
488
489            Key[] v = createKeyArray(1);
490            v[0]=separator;
491            setBranchData(v, new long[] { lNode.getPageId(), rNode.getPageId() });
492
493            index.storeNode(tx, this, true);
494            index.storeNode(tx, rNode, true);
495            index.storeNode(tx, lNode, true);
496            
497        } else {
498            BTreeNode<Key,Value> rNode = this.index.createNode(tx, parent);
499            
500            if( isBranch() ) {
501                setBranchData(leftKeys, leftChildren);
502                rNode.setBranchData(rightKeys, rightChildren);
503            } else {
504                rNode.setNext(next);
505                next = rNode.getPageId();
506                setLeafData(leftKeys, leftValues);
507                rNode.setLeafData(rightKeys, rightValues);
508            }
509
510            index.storeNode(tx, this, true);
511            index.storeNode(tx, rNode, true);
512            parent.promoteValue(tx, separator, rNode.getPageId());
513        }
514    }
515
516    public void printStructure(Transaction tx, PrintWriter out, String prefix) throws IOException {
517        if( prefix.length()>0 && parent == null ) {
518            throw new IllegalStateException("Cycle back to root node detected.");
519        }
520        if (parent == null) {
521            prefix += "|";
522            out.println(prefix + getPageId());
523        }
524        if( isBranch() ) {
525            for(int i=0 ; i < children.length; i++) {
526                BTreeNode<Key, Value> child = getChild(tx, i);
527                if( i == children.length-1) {
528                    out.println(prefix+"\\- "+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":""));
529                    child.printStructure(tx, out, prefix+"   ");
530                } else {
531                    out.println(prefix+"|- "+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":"")+" : "+keys[i]);
532                    child.printStructure(tx, out, prefix+"   ");
533                }
534            }
535        }
536    }
537    
538    
539    public int getMinLeafDepth(Transaction tx, int depth) throws IOException {
540        depth++;
541        if( isBranch() ) {
542            int min = Integer.MAX_VALUE;
543            for(int i=0 ; i < children.length; i++) {
544                min = Math.min(min, getChild(tx, i).getMinLeafDepth(tx, depth));
545            }
546            return min;
547        } else {
548//            print(depth*2, "- "+page.getPageId());
549            return depth;
550        }
551    }
552
553    public int getMaxLeafDepth(Transaction tx, int depth) throws IOException {
554        depth++;
555        if( isBranch() ) {
556            int v = 0;
557            for(int i=0 ; i < children.length; i++) {
558                v = Math.max(v, getChild(tx, i).getMaxLeafDepth(tx, depth));
559            }
560            depth = v;
561        } 
562        return depth;
563    }
564
565    public Value get(Transaction tx, Key key) throws IOException {
566        if (key == null) {
567            throw new IllegalArgumentException("Key cannot be null");
568        }
569        if( isBranch() ) {
570            return getLeafNode(tx, this, key).get(tx, key);
571        } else {
572            int idx = Arrays.binarySearch(keys, key);
573            if (idx < 0) {
574                return null;
575            } else {
576                return values[idx];
577            }
578        }
579    }
580    
581    public boolean isEmpty(final Transaction tx) throws IOException {
582        return keys.length==0;
583    }
584
585    public void visit(Transaction tx, BTreeVisitor<Key, Value> visitor) throws IOException {
586        if (visitor == null) {
587            throw new IllegalArgumentException("Visitor cannot be null");
588        }
589        if( isBranch() ) {
590            for(int i=0; i < this.children.length; i++) {
591                Key key1 = null;
592                if( i!=0 ) {
593                    key1 = keys[i-1];
594                }
595                Key key2 = null;
596                if( i!=this.children.length-1 ) {
597                    key2 = keys[i];
598                }
599                if( visitor.isInterestedInKeysBetween(key1, key2) ) {
600                    BTreeNode<Key, Value> child = getChild(tx, i);
601                    child.visit(tx, visitor);
602                }
603            }
604        } else {
605            visitor.visit(Arrays.asList(keys), Arrays.asList(values));
606        }
607    }
608    
609    public Map.Entry<Key,Value> getFirst(Transaction tx) throws IOException {
610        BTreeNode<Key, Value> node = this;
611        while( node .isBranch() ) {
612            node = node.getChild(tx, 0);
613        }
614        if( node.values.length>0 ) {
615            return new KeyValueEntry(node.keys[0], node.values[0]);
616        } else {
617            return null;
618        }
619    }
620
621    public Map.Entry<Key,Value> getLast(Transaction tx) throws IOException {
622        BTreeNode<Key, Value> node = this;
623        while( node.isBranch() ) {
624            node = node.getChild(tx, node.children.length-1);
625        }
626        if( node.values.length>0 ) {
627            int idx = node.values.length-1;
628            return new KeyValueEntry(node.keys[idx], node.values[idx]);
629        } else {
630            return null;
631        }
632    }
633    
634    public BTreeNode<Key,Value> getFirstLeafNode(Transaction tx) throws IOException {
635        BTreeNode<Key, Value> node = this;
636        while( node .isBranch() ) {
637            node = node.getChild(tx, 0);
638        }
639        return node;
640    }
641    
642    public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx, Key startKey, Key endKey) throws IOException {
643        if (startKey == null) {
644            return iterator(tx);
645        }
646        if( isBranch() ) {
647            return getLeafNode(tx, this, startKey).iterator(tx, startKey, endKey);
648        } else {
649            int idx = Arrays.binarySearch(keys, startKey);
650            if (idx < 0) {
651                idx = -(idx + 1);
652            }
653            return new BTreeIterator(tx, this, idx, endKey);
654        }
655    }
656
657    public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx) throws IOException {
658        return new BTreeIterator(tx, getFirstLeafNode(tx), 0, null);
659    }
660    
661    public void clear(Transaction tx) throws IOException {
662        if( isBranch() ) {
663            for (int i = 0; i < children.length; i++) {
664                BTreeNode<Key, Value> node = index.loadNode(tx, children[i], this);
665                node.clear(tx);
666                tx.free(node.getPage());
667            }
668        }
669        // Reset the root node to be a leaf.
670        if( parent == null ) {
671            setLeafData(createKeyArray(0), createValueArray(0));
672            next=-1;
673            index.storeNode(tx, this, true);
674        }
675    }
676
677
678    private static <Key,Value> BTreeNode<Key, Value> getLeafNode(Transaction tx, final BTreeNode<Key, Value> node, Key key) throws IOException {
679        BTreeNode<Key, Value> current = node;
680        while( true ) {
681            if( current.isBranch() ) {
682                int idx = Arrays.binarySearch(current.keys, key);
683                idx = idx < 0 ? -(idx + 1) : idx + 1;
684                BTreeNode<Key, Value> child = current.getChild(tx, idx);        
685
686                // A little cycle detection for sanity's sake
687                if( child == node ) {
688                    throw new IOException("BTree corrupted: Cylce detected.");
689                }
690                
691                current = child;
692            } else {
693                break;
694            }
695        }
696        return current;
697    }
698
699    public boolean contains(Transaction tx, Key key) throws IOException {
700        if (key == null) {
701            throw new IllegalArgumentException("Key cannot be null");
702        }
703
704        if( isBranch() ) {
705            return getLeafNode(tx, this, key).contains(tx, key);
706        } else {
707            int idx = Arrays.binarySearch(keys, key);
708            if (idx < 0) {
709                return false;
710            } else {
711                return true;
712            }
713        }
714    }
715
716    ///////////////////////////////////////////////////////////////////
717    // Implementation methods
718    ///////////////////////////////////////////////////////////////////
719 
720
721    private boolean allowOverflow() {
722        // Only allow page overflow if there are <= 3 keys in the node.  Otherwise a split will occur on overflow
723        return this.keys.length<=3;
724    }
725
726
727    private void setLeafData(Key[] keys, Value[] values) {
728        this.keys = keys;
729        this.values = values;
730        this.children = null;
731    }
732    
733    private void setBranchData(Key[] keys, long[] nodeIds) {
734        this.keys = keys;
735        this.children = nodeIds;
736        this.values = null;
737    }
738
739    @SuppressWarnings("unchecked")
740    private Key[] createKeyArray(int size) {
741        return (Key[])new Object[size];
742    }
743
744    @SuppressWarnings("unchecked")
745    private Value[] createValueArray(int size) {
746        return (Value[])new Object[size];
747    }
748    
749    @SuppressWarnings("unchecked")
750    static private <T> T[] arrayDelete(T[] vals, int idx) {
751        T[] newVals = (T[])new Object[vals.length - 1];
752        if (idx > 0) {
753            System.arraycopy(vals, 0, newVals, 0, idx);
754        }
755        if (idx < newVals.length) {
756            System.arraycopy(vals, idx + 1, newVals, idx, newVals.length - idx);
757        }
758        return newVals;
759    }
760    
761    static private long[] arrayDelete(long[] vals, int idx) {
762        long[] newVals = new long[vals.length - 1];
763        if (idx > 0) {
764            System.arraycopy(vals, 0, newVals, 0, idx);
765        }
766        if (idx < newVals.length) {
767            System.arraycopy(vals, idx + 1, newVals, idx, newVals.length - idx);
768        }
769        return newVals;
770    }
771
772    @SuppressWarnings("unchecked")
773    static private <T> T[] arrayInsert(T[] vals, T val, int idx) {
774        T[] newVals = (T[])new Object[vals.length + 1];
775        if (idx > 0) {
776            System.arraycopy(vals, 0, newVals, 0, idx);
777        }
778        newVals[idx] = val;
779        if (idx < vals.length) {
780            System.arraycopy(vals, idx, newVals, idx + 1, vals.length - idx);
781        }
782        return newVals;
783    }
784
785
786    static private long[] arrayInsert(long[] vals, long val, int idx) {
787        
788        long[] newVals = new long[vals.length + 1];
789        if (idx > 0) {
790            System.arraycopy(vals, 0, newVals, 0, idx);
791        }
792        newVals[idx] = val;
793        if (idx < vals.length) {
794            System.arraycopy(vals, idx, newVals, idx + 1, vals.length - idx);
795        }
796        return newVals;
797    }
798
799    ///////////////////////////////////////////////////////////////////
800    // Property Accessors
801    ///////////////////////////////////////////////////////////////////
802    private boolean isBranch() {
803        return children!=null;
804    }
805
806    public long getPageId() {
807        return page.getPageId();
808    }
809
810    public BTreeNode<Key, Value> getParent() {
811        return parent;
812    }
813
814    public void setParent(BTreeNode<Key, Value> parent) {
815        this.parent = parent;
816    }
817
818    public Page<BTreeNode<Key, Value>> getPage() {
819        return page;
820    }
821
822    public void setPage(Page<BTreeNode<Key, Value>> page) {
823        this.page = page;
824    }
825
826    public long getNext() {
827        return next;
828    }
829
830    public void setNext(long next) {
831        this.next = next;
832    }
833    
834    @Override
835    public String toString() {
836        return "[BTreeNode "+(isBranch()?"branch":"leaf")+": "+Arrays.asList(keys)+"]";
837    }
838
839}
840
841