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     */
017    package org.apache.activemq.store.kahadb.disk.index;
018    
019    import java.io.DataInput;
020    import java.io.DataOutput;
021    import java.io.IOException;
022    import java.io.PrintWriter;
023    import java.util.Arrays;
024    import java.util.Iterator;
025    import java.util.Map;
026    import java.util.NoSuchElementException;
027    import java.util.Map.Entry;
028    
029    import org.apache.activemq.store.kahadb.disk.index.BTreeIndex.Prefixer;
030    import org.apache.activemq.store.kahadb.disk.page.Page;
031    import org.apache.activemq.store.kahadb.disk.page.Transaction;
032    import 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     */
039    public 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: Cycle 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                        tx.free(child.getPage());
297                    } else {
298                        
299                        // The child was a leaf. Then we need to actually remove it from this branch node..
300                        // and relink the previous leaf to skip to the next leaf.
301    
302                        BTreeNode<Key, Value> previousLeaf = null;
303                        if( idx > 0 ) {
304                            // easy if we this node hold the previous child.
305                            previousLeaf = getChild(tx, idx-1).getRightLeaf(tx);
306                        } else {
307                            // less easy if we need to go to the parent to find the previous child.
308                            BTreeNode<Key, Value> lp = getLeftPeer(tx, this);
309                            if( lp!=null ) {
310                                previousLeaf = lp.getRightLeaf(tx);
311                            }
312                            // lp will be null if there was no previous child.
313                        }
314    
315                        if( previousLeaf !=null ) {
316                            previousLeaf.next = child.next;
317                            index.storeNode(tx, previousLeaf, true);
318                        }
319    
320                        if( idx < children.length-1 ) {
321                            // Delete it and key to the right.
322                            setBranchData(arrayDelete(keys, idx), arrayDelete(children, idx));
323                        } else {
324                            // It was the last child.. Then delete it and key to the left
325                            setBranchData(arrayDelete(keys, idx-1), arrayDelete(children, idx));
326                        }
327                        
328                        // If we are the root node, and only have 1 child left.  Then 
329                        // make the root be the leaf node.
330                        if( children.length == 1 && parent==null ) {
331                            child = getChild(tx, 0);
332                            keys = child.keys;
333                            children = child.children;
334                            values = child.values;
335                            // free up the page..
336                            tx.free(child.getPage());
337                        }
338                        
339                    }
340                    index.storeNode(tx, this, true);
341                }
342                
343                return rc;
344            } else {
345                int idx = Arrays.binarySearch(keys, key);
346                if (idx < 0) {
347                    return null;
348                } else {
349                    Value oldValue = values[idx];
350                    setLeafData(arrayDelete(keys, idx), arrayDelete(values, idx));
351                    
352                    if( keys.length==0 && parent!=null) {
353                        tx.free(getPage());
354                    } else {
355                        index.storeNode(tx, this, true);
356                    }
357                    
358                    return oldValue;
359                }
360            }
361        }
362    
363        public Value put(Transaction tx, Key key, Value value) throws IOException {
364            if (key == null) {
365                throw new IllegalArgumentException("Key cannot be null");
366            }
367    
368            if( isBranch() ) {
369                return getLeafNode(tx, this, key).put(tx, key, value);
370            } else {
371                int idx = Arrays.binarySearch(keys, key);
372                
373                Value oldValue=null;
374                if (idx >= 0) {
375                    // Key was found... Overwrite
376                    oldValue = values[idx];
377                    values[idx] = value;
378                    setLeafData(keys, values);
379                } else {
380                    // Key was not found, Insert it
381                    idx = -(idx + 1);
382                    setLeafData(arrayInsert(keys, key, idx), arrayInsert(values, value, idx));
383                }
384                
385                try {
386                    index.storeNode(tx, this, allowOverflow());
387                } catch ( Transaction.PageOverflowIOException e ) {
388                    // If we get an overflow 
389                    split(tx);
390                }
391                
392                return oldValue;
393            }
394        }
395    
396        private void promoteValue(Transaction tx, Key key, long nodeId) throws IOException {
397    
398            int idx = Arrays.binarySearch(keys, key);
399            idx = idx < 0 ? -(idx + 1) : idx + 1;
400            setBranchData(arrayInsert(keys, key, idx), arrayInsert(children, nodeId, idx + 1));
401    
402            try {
403                index.storeNode(tx, this, allowOverflow());
404            } catch ( Transaction.PageOverflowIOException e ) {
405                split(tx);
406            }
407    
408        }
409    
410        /**
411         * Internal to the BTreeNode method
412         */
413        private void split(Transaction tx) throws IOException {
414            Key[] leftKeys;
415            Key[] rightKeys;
416            Value[] leftValues=null;
417            Value[] rightValues=null;
418            long[] leftChildren=null;
419            long[] rightChildren=null;
420            Key separator;
421    
422            int vc = keys.length;
423            int pivot = vc / 2;
424    
425            // Split the node into two nodes
426            if( isBranch() ) {
427    
428                leftKeys = createKeyArray(pivot);
429                leftChildren = new long[leftKeys.length + 1];
430                rightKeys = createKeyArray(vc - (pivot + 1));
431                rightChildren = new long[rightKeys.length + 1];
432    
433                System.arraycopy(keys, 0, leftKeys, 0, leftKeys.length);
434                System.arraycopy(children, 0, leftChildren, 0, leftChildren.length);
435                System.arraycopy(keys, leftKeys.length + 1, rightKeys, 0, rightKeys.length);
436                System.arraycopy(children, leftChildren.length, rightChildren, 0, rightChildren.length);
437    
438                // Is it a Simple Prefix BTree??
439                Prefixer<Key> prefixer = index.getPrefixer();
440                if(prefixer!=null) {
441                    separator = prefixer.getSimplePrefix(leftKeys[leftKeys.length - 1], rightKeys[0]);
442                } else {
443                    separator = keys[leftKeys.length];
444                }
445                    
446                
447            } else {
448    
449                leftKeys = createKeyArray(pivot);
450                leftValues = createValueArray(leftKeys.length);
451                rightKeys = createKeyArray(vc - pivot);
452                rightValues = createValueArray(rightKeys.length);
453    
454                System.arraycopy(keys, 0, leftKeys, 0, leftKeys.length);
455                System.arraycopy(values, 0, leftValues, 0, leftValues.length);
456                System.arraycopy(keys, leftKeys.length, rightKeys, 0, rightKeys.length);
457                System.arraycopy(values, leftValues.length, rightValues, 0, rightValues.length);
458    
459                // separator = getSeparator(leftVals[leftVals.length - 1],
460                // rightVals[0]);
461                separator = rightKeys[0];
462    
463            }
464    
465            // Promote the pivot to the parent branch
466            if (parent == null) {
467                
468                // This can only happen if this is the root
469                BTreeNode<Key,Value> rNode = this.index.createNode(tx, this);
470                BTreeNode<Key,Value> lNode = this.index.createNode(tx, this);
471    
472                if( isBranch() ) {
473                    rNode.setBranchData(rightKeys, rightChildren);
474                    lNode.setBranchData(leftKeys, leftChildren);
475                } else {
476                    rNode.setLeafData(rightKeys, rightValues);
477                    lNode.setLeafData(leftKeys, leftValues);
478                    lNode.setNext(rNode.getPageId());
479                }
480    
481                Key[] v = createKeyArray(1);
482                v[0]=separator;
483                setBranchData(v, new long[] { lNode.getPageId(), rNode.getPageId() });
484    
485                index.storeNode(tx, this, true);
486                index.storeNode(tx, rNode, true);
487                index.storeNode(tx, lNode, true);
488                
489            } else {
490                BTreeNode<Key,Value> rNode = this.index.createNode(tx, parent);
491                
492                if( isBranch() ) {
493                    setBranchData(leftKeys, leftChildren);
494                    rNode.setBranchData(rightKeys, rightChildren);
495                } else {
496                    rNode.setNext(next);
497                    next = rNode.getPageId();
498                    setLeafData(leftKeys, leftValues);
499                    rNode.setLeafData(rightKeys, rightValues);
500                }
501    
502                index.storeNode(tx, this, true);
503                index.storeNode(tx, rNode, true);
504                parent.promoteValue(tx, separator, rNode.getPageId());
505            }
506        }
507    
508        public void printStructure(Transaction tx, PrintWriter out, String prefix) throws IOException {
509            if( prefix.length()>0 && parent == null ) {
510                throw new IllegalStateException("Cycle back to root node detected.");
511            }
512            if (parent == null) {
513                prefix += "|";
514                out.println(prefix + getPageId());
515            }
516            if( isBranch() ) {
517                for(int i=0 ; i < children.length; i++) {
518                    BTreeNode<Key, Value> child = getChild(tx, i);
519                    if( i == children.length-1) {
520                        out.println(prefix+"\\- "+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":""));
521                        child.printStructure(tx, out, prefix+"   ");
522                    } else {
523                        out.println(prefix+"|- "+child.getPageId()+(child.isBranch()?" ("+child.children.length+")":"")+" : "+keys[i]);
524                        child.printStructure(tx, out, prefix+"   ");
525                    }
526                }
527            }
528        }
529        
530        
531        public int getMinLeafDepth(Transaction tx, int depth) throws IOException {
532            depth++;
533            if( isBranch() ) {
534                int min = Integer.MAX_VALUE;
535                for(int i=0 ; i < children.length; i++) {
536                    min = Math.min(min, getChild(tx, i).getMinLeafDepth(tx, depth));
537                }
538                return min;
539            } else {
540    //            print(depth*2, "- "+page.getPageId());
541                return depth;
542            }
543        }
544    
545        public int getMaxLeafDepth(Transaction tx, int depth) throws IOException {
546            depth++;
547            if( isBranch() ) {
548                int v = 0;
549                for(int i=0 ; i < children.length; i++) {
550                    v = Math.max(v, getChild(tx, i).getMaxLeafDepth(tx, depth));
551                }
552                depth = v;
553            } 
554            return depth;
555        }
556    
557        public Value get(Transaction tx, Key key) throws IOException {
558            if (key == null) {
559                throw new IllegalArgumentException("Key cannot be null");
560            }
561            if( isBranch() ) {
562                return getLeafNode(tx, this, key).get(tx, key);
563            } else {
564                int idx = Arrays.binarySearch(keys, key);
565                if (idx < 0) {
566                    return null;
567                } else {
568                    return values[idx];
569                }
570            }
571        }
572        
573        public boolean isEmpty(final Transaction tx) throws IOException {
574            return keys.length==0;
575        }
576    
577        public void visit(Transaction tx, BTreeVisitor<Key, Value> visitor) throws IOException {
578            if (visitor == null) {
579                throw new IllegalArgumentException("Visitor cannot be null");
580            }
581            if( isBranch() ) {
582                for(int i=0; i < this.children.length; i++) {
583                    Key key1 = null;
584                    if( i!=0 ) {
585                        key1 = keys[i-1];
586                    }
587                    Key key2 = null;
588                    if( i!=this.children.length-1 ) {
589                        key2 = keys[i];
590                    }
591                    if( visitor.isInterestedInKeysBetween(key1, key2) ) {
592                        BTreeNode<Key, Value> child = getChild(tx, i);
593                        child.visit(tx, visitor);
594                    }
595                }
596            } else {
597                visitor.visit(Arrays.asList(keys), Arrays.asList(values));
598            }
599        }
600        
601        public Map.Entry<Key,Value> getFirst(Transaction tx) throws IOException {
602            BTreeNode<Key, Value> node = this;
603            while( node .isBranch() ) {
604                node = node.getChild(tx, 0);
605            }
606            if( node.values.length>0 ) {
607                return new KeyValueEntry(node.keys[0], node.values[0]);
608            } else {
609                return null;
610            }
611        }
612    
613        public Map.Entry<Key,Value> getLast(Transaction tx) throws IOException {
614            BTreeNode<Key, Value> node = this;
615            while( node.isBranch() ) {
616                node = node.getChild(tx, node.children.length-1);
617            }
618            if( node.values.length>0 ) {
619                int idx = node.values.length-1;
620                return new KeyValueEntry(node.keys[idx], node.values[idx]);
621            } else {
622                return null;
623            }
624        }
625        
626        public BTreeNode<Key,Value> getFirstLeafNode(Transaction tx) throws IOException {
627            BTreeNode<Key, Value> node = this;
628            while( node .isBranch() ) {
629                node = node.getChild(tx, 0);
630            }
631            return node;
632        }
633        
634        public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx, Key startKey) throws IOException {
635            if (startKey == null) {
636                return iterator(tx);
637            }
638            if( isBranch() ) {
639                return getLeafNode(tx, this, startKey).iterator(tx, startKey);
640            } else {
641                int idx = Arrays.binarySearch(keys, startKey);
642                if (idx < 0) {
643                    idx = -(idx + 1);
644                }
645                return new BTreeIterator(tx, this, idx);
646            }
647        }
648    
649        public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx) throws IOException {
650            return new BTreeIterator(tx, getFirstLeafNode(tx), 0);
651        }
652        
653        public void clear(Transaction tx) throws IOException {
654            if( isBranch() ) {
655                for (int i = 0; i < children.length; i++) {
656                    BTreeNode<Key, Value> node = index.loadNode(tx, children[i], this);
657                    node.clear(tx);
658                    tx.free(node.getPage());
659                }
660            }
661            // Reset the root node to be a leaf.
662            if( parent == null ) {
663                setLeafData(createKeyArray(0), createValueArray(0));
664                next=-1;
665                index.storeNode(tx, this, true);
666            }
667        }
668    
669    
670        private static <Key,Value> BTreeNode<Key, Value> getLeafNode(Transaction tx, final BTreeNode<Key, Value> node, Key key) throws IOException {
671            BTreeNode<Key, Value> current = node;
672            while( true ) {
673                if( current.isBranch() ) {
674                    int idx = Arrays.binarySearch(current.keys, key);
675                    idx = idx < 0 ? -(idx + 1) : idx + 1;
676                    BTreeNode<Key, Value> child = current.getChild(tx, idx);        
677    
678                    // A little cycle detection for sanity's sake
679                    if( child == node ) {
680                        throw new IOException("BTree corrupted: Cylce detected.");
681                    }
682                    
683                    current = child;
684                } else {
685                    break;
686                }
687            }
688            return current;
689        }
690    
691        public boolean contains(Transaction tx, Key key) throws IOException {
692            if (key == null) {
693                throw new IllegalArgumentException("Key cannot be null");
694            }
695    
696            if( isBranch() ) {
697                return getLeafNode(tx, this, key).contains(tx, key);
698            } else {
699                int idx = Arrays.binarySearch(keys, key);
700                if (idx < 0) {
701                    return false;
702                } else {
703                    return true;
704                }
705            }
706        }
707    
708        ///////////////////////////////////////////////////////////////////
709        // Implementation methods
710        ///////////////////////////////////////////////////////////////////
711     
712    
713        private boolean allowOverflow() {
714            // Only allow page overflow if there are <= 3 keys in the node.  Otherwise a split will occur on overflow
715            return this.keys.length<=3;
716        }
717    
718    
719        private void setLeafData(Key[] keys, Value[] values) {
720            this.keys = keys;
721            this.values = values;
722            this.children = null;
723        }
724        
725        private void setBranchData(Key[] keys, long[] nodeIds) {
726            this.keys = keys;
727            this.children = nodeIds;
728            this.values = null;
729        }
730    
731        @SuppressWarnings("unchecked")
732        private Key[] createKeyArray(int size) {
733            return (Key[])new Object[size];
734        }
735    
736        @SuppressWarnings("unchecked")
737        private Value[] createValueArray(int size) {
738            return (Value[])new Object[size];
739        }
740        
741        @SuppressWarnings("unchecked")
742        static private <T> T[] arrayDelete(T[] vals, int idx) {
743            T[] newVals = (T[])new Object[vals.length - 1];
744            if (idx > 0) {
745                System.arraycopy(vals, 0, newVals, 0, idx);
746            }
747            if (idx < newVals.length) {
748                System.arraycopy(vals, idx + 1, newVals, idx, newVals.length - idx);
749            }
750            return newVals;
751        }
752        
753        static private long[] arrayDelete(long[] vals, int idx) {
754            long[] newVals = new long[vals.length - 1];
755            if (idx > 0) {
756                System.arraycopy(vals, 0, newVals, 0, idx);
757            }
758            if (idx < newVals.length) {
759                System.arraycopy(vals, idx + 1, newVals, idx, newVals.length - idx);
760            }
761            return newVals;
762        }
763    
764        @SuppressWarnings("unchecked")
765        static private <T> T[] arrayInsert(T[] vals, T val, int idx) {
766            T[] newVals = (T[])new Object[vals.length + 1];
767            if (idx > 0) {
768                System.arraycopy(vals, 0, newVals, 0, idx);
769            }
770            newVals[idx] = val;
771            if (idx < vals.length) {
772                System.arraycopy(vals, idx, newVals, idx + 1, vals.length - idx);
773            }
774            return newVals;
775        }
776    
777    
778        static private long[] arrayInsert(long[] vals, long val, int idx) {
779            
780            long[] newVals = new long[vals.length + 1];
781            if (idx > 0) {
782                System.arraycopy(vals, 0, newVals, 0, idx);
783            }
784            newVals[idx] = val;
785            if (idx < vals.length) {
786                System.arraycopy(vals, idx, newVals, idx + 1, vals.length - idx);
787            }
788            return newVals;
789        }
790    
791        ///////////////////////////////////////////////////////////////////
792        // Property Accessors
793        ///////////////////////////////////////////////////////////////////
794        private boolean isBranch() {
795            return children!=null;
796        }
797    
798        public long getPageId() {
799            return page.getPageId();
800        }
801    
802        public BTreeNode<Key, Value> getParent() {
803            return parent;
804        }
805    
806        public void setParent(BTreeNode<Key, Value> parent) {
807            this.parent = parent;
808        }
809    
810        public Page<BTreeNode<Key, Value>> getPage() {
811            return page;
812        }
813    
814        public void setPage(Page<BTreeNode<Key, Value>> page) {
815            this.page = page;
816        }
817    
818        public long getNext() {
819            return next;
820        }
821    
822        public void setNext(long next) {
823            this.next = next;
824        }
825        
826        @Override
827        public String toString() {
828            return "[BTreeNode "+(isBranch()?"branch":"leaf")+": "+Arrays.asList(keys)+"]";
829        }
830    
831    }
832    
833