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