0001: /*
0002: * $Id: IntBTree.java,v 1.14 2005/12/20 18:32:42 ahimanikya Exp $
0003: * =======================================================================
0004: * Copyright (c) 2002-2005 Axion Development Team. All rights reserved.
0005: *
0006: * Redistribution and use in source and binary forms, with or without
0007: * modification, are permitted provided that the following conditions
0008: * are met:
0009: *
0010: * 1. Redistributions of source code must retain the above
0011: * copyright notice, this list of conditions and the following
0012: * disclaimer.
0013: *
0014: * 2. Redistributions in binary form must reproduce the above copyright
0015: * notice, this list of conditions and the following disclaimer in
0016: * the documentation and/or other materials provided with the
0017: * distribution.
0018: *
0019: * 3. The names "Tigris", "Axion", nor the names of its contributors may
0020: * not be used to endorse or promote products derived from this
0021: * software without specific prior written permission.
0022: *
0023: * 4. Products derived from this software may not be called "Axion", nor
0024: * may "Tigris" or "Axion" appear in their names without specific prior
0025: * written permission.
0026: *
0027: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
0028: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
0029: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
0030: * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
0031: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
0032: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
0033: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
0034: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
0035: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0036: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
0037: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0038: * =======================================================================
0039: */
0040:
0041: package org.axiondb.util;
0042:
0043: import java.io.File;
0044: import java.io.IOException;
0045: import java.io.ObjectInputStream;
0046: import java.io.ObjectOutputStream;
0047: import java.util.ArrayList;
0048: import java.util.List;
0049: import java.util.NoSuchElementException;
0050:
0051: import org.apache.commons.collections.primitives.ArrayIntList;
0052: import org.apache.commons.collections.primitives.IntIterator;
0053: import org.apache.commons.collections.primitives.IntList;
0054: import org.apache.commons.collections.primitives.IntListIterator;
0055: import org.axiondb.io.AxionFileSystem;
0056:
0057: /**
0058: * A B-Tree for integers, based on the implementation described in "Introduction to
0059: * Algorithms" by Cormen, Leiserson and Rivest (CLR).
0060: *
0061: * @version $Revision: 1.14 $ $Date: 2005/12/20 18:32:42 $
0062: * @author Chuck Burdick
0063: * @author Dave Pekarek Krohn
0064: * @author Rodney Waldhoff
0065: * @author Ritesh Adval
0066: * @author Charles Ye
0067: * @author Ahimanikya Satapathy
0068: */
0069: public class IntBTree extends BaseBTree {
0070:
0071: // NB: We are aware that declaring methods as final doesn't improve performance in
0072: // general.The stuff declared final is declared final so that we know it's not
0073: // overriden in any subclass. This makes refactoring easier.
0074:
0075: /**
0076: * Create or load a new root node.
0077: */
0078: public IntBTree(File idxDir, String idxName, int minimizationFactor)
0079: throws IOException, ClassNotFoundException {
0080: super (idxDir, idxName, minimizationFactor);
0081: _keys = new ArrayIntList(getMinimizationFactor());
0082: if ((null != getBTreeMetaData().getDataDirectory() && getBTreeMetaData()
0083: .getCounterFile().exists())) {
0084: setFileId(0);
0085: getBTreeMetaData().loadCounter();
0086: read();
0087: } else {
0088: getBTreeMetaData().assignFileId(this );
0089: }
0090: }
0091:
0092: /**
0093: * Create a new, non-root node.
0094: */
0095: protected IntBTree(BTreeMetaData meta) throws IOException,
0096: ClassNotFoundException {
0097: super (meta);
0098: _keys = new ArrayIntList(getMinimizationFactor());
0099: meta.assignFileId(this );
0100: }
0101:
0102: /**
0103: * Create a non-root node by reading it from disk.
0104: */
0105: protected IntBTree(BTreeMetaData meta, int fileId)
0106: throws IOException, ClassNotFoundException {
0107: super (meta);
0108: _keys = new ArrayIntList(getMinimizationFactor());
0109: setFileId(fileId);
0110: read();
0111: }
0112:
0113: /**
0114: * Clear my keys, values, and file ids. Flags me as dirty.
0115: */
0116: public final void clearData() {
0117: getKeys().clear();
0118: super .clearData();
0119: }
0120:
0121: /**
0122: * Delete an arbitrary instance of the specified key and the specified row
0123: */
0124: public final boolean delete(int key, int rowid) throws IOException,
0125: ClassNotFoundException {
0126: //Comments refer to the cases described in CLR (19.3)
0127: boolean deleted = false;
0128: int size = size();
0129: if (size <= 0) {
0130: return deleted;
0131: }
0132: int i = findNearestKeyBelow(key, rowid);
0133: if (i >= 0
0134: && (isEqual(getKey(i), key) && isNotEqual(getValue(i),
0135: rowid))) {
0136: // Case 0
0137: int pivotLoc = i;
0138: if (!isLeaf()) {
0139: if (pivotLoc > 0
0140: && getChild(pivotLoc - 1).size() >= getMinimizationFactor()) {
0141: // Case 0a, borrow-left
0142: borrowLeft(pivotLoc);
0143: deleteFromChild(pivotLoc, key, rowid);
0144: } else if (pivotLoc + 1 < getChildIds().size()
0145: && getChild(pivotLoc + 1).size() >= getMinimizationFactor()) {
0146: // Case 0a, borrow-right
0147: borrowRight(pivotLoc);
0148: deleteFromChild(pivotLoc, key, rowid);
0149: } else {
0150: // Case 0b : if the key is on the far right,
0151: // then we need to merge the last two nodes
0152: int mergeLoc;
0153: if (pivotLoc < size) {
0154: mergeLoc = pivotLoc;
0155: } else {
0156: mergeLoc = pivotLoc - 1;
0157: }
0158: mergeChildren(mergeLoc, getKey(mergeLoc));
0159: maybeCollapseTree();
0160: delete(key, rowid);
0161: }
0162: }
0163: // else no row found, ignored
0164: } else if ((i < 0 && isNotEqual(getKey(i + 1), key))
0165: || isNotEqual(getKey(i), key)) {
0166: //Case 3
0167: int pivotLoc = i + 1;
0168: if (!isLeaf()
0169: && getChild(pivotLoc).size() < getMinimizationFactor()) {
0170: if (pivotLoc > 0
0171: && getChild(pivotLoc - 1).size() >= getMinimizationFactor()) {
0172: // Case 3a, borrow-left
0173: borrowLeft(pivotLoc);
0174: deleteFromChild(pivotLoc, key, rowid);
0175: } else if (pivotLoc + 1 < getChildIds().size()
0176: && getChild(pivotLoc + 1).size() >= getMinimizationFactor()) {
0177: // Case 3a, borrow-right
0178: borrowRight(pivotLoc);
0179: deleteFromChild(pivotLoc, key, rowid);
0180: } else {
0181: // Case 3b: if the key is on the far right,
0182: // then we need to merge the last two nodes
0183: int mergeLoc;
0184: if (pivotLoc < size) {
0185: mergeLoc = pivotLoc;
0186: } else {
0187: mergeLoc = pivotLoc - 1;
0188: }
0189: mergeChildren(mergeLoc, getKey(mergeLoc));
0190: maybeCollapseTree();
0191: delete(key, rowid);
0192: }
0193: } else {
0194: deleteFromChild(i + 1, key, rowid);
0195: }
0196: } else {
0197: if (isLeaf()) {
0198: // Case 1
0199: removeKeyValuePairAt(i);
0200: deleted = true;
0201: } else {
0202: // Case 2
0203: if (getChild(i).size() >= getMinimizationFactor()) {
0204: // Case 2a, move predecessor up
0205: int[] keyParam = new int[1];
0206: int[] valueParam = new int[1];
0207: getChild(i).getRightMost(keyParam, valueParam);
0208: setKeyValuePairAt(i, keyParam[0], valueParam[0]);
0209: deleteFromChild(i, keyParam[0], valueParam[0]);
0210: } else if (getChild(i + 1).size() >= getMinimizationFactor()) {
0211: // Case 2b, move successor up
0212: int[] keyParam = new int[1];
0213: int[] valueParam = new int[1];
0214: getChild(i + 1).getLeftMost(keyParam, valueParam);
0215: setKeyValuePairAt(i, keyParam[0], valueParam[0]);
0216: deleteFromChild(i + 1, keyParam[0], valueParam[0]);
0217: } else {
0218: //Case 2c, merge nodes
0219: mergeChildren(i, key);
0220:
0221: //Now delete from the newly merged node
0222: deleteFromChild(i, key, rowid);
0223:
0224: maybeCollapseTree();
0225: }
0226: }
0227: }
0228: return deleted;
0229: }
0230:
0231: /**
0232: * Find some occurance of the given key.
0233: */
0234: public final Integer get(int key) throws IOException,
0235: ClassNotFoundException {
0236: Integer result = null;
0237: int i = findNearestKeyAbove(key);
0238: if ((i < size()) && (isEqual(key, getKey(i)))) {
0239: result = new Integer(getValue(i));
0240: } else if (!isLeaf()) {
0241: // recurse to children
0242: result = getChild(i).get(key);
0243: }
0244: return result;
0245: }
0246:
0247: /**
0248: * Obtain an iterator over all values associated with the given key.
0249: */
0250: public final IntListIterator getAll(int key) throws IOException,
0251: ClassNotFoundException {
0252: IntListIteratorChain chain = new IntListIteratorChain();
0253: getAll(key, chain);
0254: return chain;
0255: }
0256:
0257: /**
0258: * Obtain an iterator over all values excluding null key values
0259: */
0260: public final IntListIterator getAllExcludingNull()
0261: throws IOException, ClassNotFoundException {
0262: IntListIteratorChain chain = new IntListIteratorChain();
0263: getAllExcludingNull(chain);
0264: return chain;
0265: }
0266:
0267: /**
0268: * Obtain an iterator over all values greater than or equal to the given key.
0269: */
0270: public final IntListIterator getAllFrom(int key)
0271: throws IOException, ClassNotFoundException {
0272: IntListIteratorChain chain = new IntListIteratorChain();
0273: getAllFrom(key, chain);
0274: return chain;
0275: }
0276:
0277: /**
0278: * Obtain an iterator over all values strictly less than the given key.
0279: */
0280: public final IntListIterator getAllTo(int key) throws IOException,
0281: ClassNotFoundException {
0282: IntListIteratorChain chain = new IntListIteratorChain();
0283: getAllTo(key, chain);
0284: return chain;
0285: }
0286:
0287: public IntListIteratorChain inorderIterator() throws IOException,
0288: ClassNotFoundException {
0289: IntListIteratorChain chain = new IntListIteratorChain();
0290: inorderIterator(chain);
0291: return chain;
0292: }
0293:
0294: /**
0295: * Insert the given key/value pair.
0296: */
0297: public final void insert(int key, int value) throws IOException,
0298: ClassNotFoundException {
0299: // The general strategy here is to:
0300: // (a) find the appropriate node
0301: // (b) if it is not full, simply insert the key/value pair
0302: // (c) else, split the node into two, pulling up the median key to the parent
0303: // Since "pulling up the median key" may require splitting the parent,
0304: // to avoid multiple passes we'll split each full node as we move down the tree.
0305:
0306: if (isFull()) {
0307: // if I'm full,
0308: // create a new node
0309: IntBTree child = allocateNewNode();
0310: // copy all my data to that node
0311: child.addTuples(getKeys(), getValues(), getChildIds());
0312: // clear me
0313: clearData();
0314: // add that new child
0315: addFileId(0, child.getFileId());
0316: // split that child (since it is also full)
0317: subdivideChild(0, child);
0318: }
0319: insertNotfull(key, value);
0320: }
0321:
0322: /**
0323: * Replace any occurance of oldRowId associated with the given key with newRowId. It
0324: * is assumed oldId occurs at most once in the tree.
0325: */
0326: public final void replaceId(int key, int oldRowId, int newRowId)
0327: throws ClassNotFoundException, IOException {
0328: int i = findNearestKeyAbove(key);
0329: boolean valSet = false;
0330: int size = size();
0331: while ((i < size) && isEqual(key, getKey(i))) {
0332: if (!isLeaf()) {
0333: replaceIdInChild(i, key, oldRowId, newRowId);
0334: }
0335: if (getValue(i) == oldRowId) {
0336: setValue(i, newRowId);
0337: valSet = true;
0338: getBTreeMetaData().setDirty(this );
0339: break;
0340: }
0341: i++;
0342: }
0343: if (!valSet && !isLeaf()) {
0344: replaceIdInChild(i, key, oldRowId, newRowId);
0345: }
0346: }
0347:
0348: /**
0349: * Save this tree and all of its children.
0350: *
0351: * @deprecated See {@link #save(File)}
0352: */
0353: public final void save() throws IOException, ClassNotFoundException {
0354: saveCounterIfRoot();
0355: write();
0356: for (int i = 0, I = getChildIds().size(); i < I; i++) {
0357: getChild(i).save();
0358: }
0359: }
0360:
0361: /**
0362: * Returns the number of keys I currently contain. Note that by construction, this
0363: * will be at least {@link #getMinimizationFactor minimizationFactor}-1 and at most
0364: * 2*{@link #getMinimizationFactor minimizationFactor}-1 for all nodes except the
0365: * root (which may have fewer than {@link #getMinimizationFactor minimizationFactor}
0366: * -1 keys).
0367: */
0368: public final int size() {
0369: return getKeys().size();
0370: }
0371:
0372: /**
0373: * Obtain a String representation of this node, suitable for debugging.
0374: */
0375: public final String toString() {
0376: return toString(0);
0377: }
0378:
0379: /**
0380: * @see org.axiondb.util.BaseBTree#reset()
0381: */
0382: public void truncate() {
0383: getKeys().clear();
0384: super .truncate();
0385: }
0386:
0387: public IntListIterator valueIterator() throws IOException {
0388: return new IntIteratorIntListIterator(new BTreeValueIterator(
0389: this ));
0390: }
0391:
0392: public IntListIterator valueIteratorGreaterThan(int fromkey)
0393: throws IOException, ClassNotFoundException {
0394: return valueIteratorGreaterThanOrEqualTo(fromkey + 1);
0395: }
0396:
0397: public IntListIterator valueIteratorGreaterThanOrEqualTo(int fromkey)
0398: throws IOException, ClassNotFoundException {
0399: StateStack stack = new StateStack();
0400: for (IntBTree node = this ; null != node;) {
0401: int i = 0;
0402: for (int size = node.size(); i < size
0403: && fromkey > node.getKey(i);) {
0404: i++;
0405: }
0406: stack.push(node, true, i);
0407: node = node.getChildOrNull(i);
0408: }
0409: return new IntIteratorIntListIterator(new BTreeValueIterator(
0410: stack));
0411: }
0412:
0413: final boolean isValid() throws IOException, ClassNotFoundException {
0414: return isValid(true);
0415: }
0416:
0417: protected final void addKeyValuePair(int key, int value,
0418: boolean setDirty) {
0419: getKeys().add(key);
0420: getValues().add(value);
0421: if (setDirty) {
0422: getBTreeMetaData().setDirty(this );
0423: }
0424: }
0425:
0426: /**
0427: * Create a new node.
0428: */
0429: protected IntBTree createNode(BTreeMetaData meta)
0430: throws IOException, ClassNotFoundException {
0431: return new IntBTree(meta);
0432: }
0433:
0434: /**
0435: * Obtain the key stored at the specified index.
0436: */
0437: protected final int getKey(int index) {
0438: return getKeys().get(index);
0439: }
0440:
0441: /**
0442: * Read the node with the specified fileId from disk.
0443: */
0444: protected IntBTree loadNode(BTreeMetaData meta, int fileId)
0445: throws IOException, ClassNotFoundException {
0446: return new IntBTree(meta, fileId);
0447: }
0448:
0449: /**
0450: * Reads in the node. This doesn't read in the entire subtree, which happens
0451: * incrementally as files are needed.
0452: */
0453: protected void read() throws IOException, ClassNotFoundException {
0454: ObjectInputStream in = null;
0455: AxionFileSystem fs = new AxionFileSystem();
0456: try {
0457: in = fs.openObjectInputSteam(getBTreeMetaData()
0458: .getFileById(getFileId()));
0459: int size = in.readInt();
0460: for (int i = 0; i < size; i++) {
0461: addKeyValuePair(in.readInt(), in.readInt(), false);
0462: }
0463: size = in.readInt();
0464: for (int i = 0; i < size; i++) {
0465: getChildIds().add(in.readInt());
0466: }
0467: } finally {
0468: fs.closeInputStream(in);
0469: }
0470: }
0471:
0472: /**
0473: * Writes the node file out. This is differentiated from save in that it doesn't save
0474: * the entire tree or the counter file.
0475: */
0476: protected void write() throws IOException {
0477: ObjectOutputStream out = null;
0478: AxionFileSystem fs = new AxionFileSystem();
0479: try {
0480: out = fs.createObjectOutputSteam(getBTreeMetaData()
0481: .getFileById(getFileId()));
0482: int size = size();
0483: out.writeInt(size);
0484: for (int i = 0; i < size; i++) {
0485: out.writeInt(getKey(i));
0486: out.writeInt(getValue(i));
0487: }
0488:
0489: size = getChildIds().size();
0490: out.writeInt(size);
0491: for (int i = 0; i < size; i++) {
0492: out.writeInt(getChildIds().get(i));
0493: }
0494: } finally {
0495: fs.closeOutputStream(out);
0496: }
0497: }
0498:
0499: /** Adds the given key/value pair. Assumes I am not full. */
0500: private final void addKeyValuePair(int key, int value) {
0501: addKeyValuePair(key, value, true);
0502: }
0503:
0504: /** Adds the given key/value pair at the given index. Assumes I am not full. */
0505: private final void addKeyValuePair(int index, int key, int value) {
0506: getKeys().add(index, key);
0507: getValues().add(index, value);
0508: getBTreeMetaData().setDirty(this );
0509: }
0510:
0511: /** Adds the given key/value pair. Assumes I am not full. */
0512: private final void addKeyValuePairs(IntList keys, IntList values) {
0513: getKeys().addAll(keys);
0514: getValues().addAll(values);
0515: getBTreeMetaData().setDirty(this );
0516: }
0517:
0518: /** Adds the given key/value/fileId tuples. Assumes I am not full. */
0519: private final void addTuples(IntList keys, IntList values,
0520: IntList fileIds) {
0521: getKeys().addAll(keys);
0522: getValues().addAll(values);
0523: getChildIds().addAll(fileIds);
0524: getBTreeMetaData().setDirty(this );
0525: }
0526:
0527: /**
0528: * Create a new node and flag it as dirty.
0529: */
0530: private final IntBTree allocateNewNode() throws IOException,
0531: ClassNotFoundException {
0532: IntBTree tree = createNode(getBTreeMetaData());
0533: getBTreeMetaData().cacheNode(tree.getFileId(), tree);
0534: getBTreeMetaData().setDirty(tree);
0535: return tree;
0536: }
0537:
0538: private final void borrowLeft(int borrowLoc) throws IOException,
0539: ClassNotFoundException {
0540: IntBTree leftSibling = getChild(borrowLoc - 1);
0541: IntBTree rightSibling = getChild(borrowLoc);
0542:
0543: //Add the upper key to as the first entry of the right sibling
0544: rightSibling.addKeyValuePair(0, getKey(borrowLoc - 1),
0545: getValue(borrowLoc - 1));
0546:
0547: //Make the upper node's key the last key from the left sibling
0548: setKeyValuePairAt(borrowLoc - 1, leftSibling.getKey(leftSibling
0549: .size() - 1), leftSibling.getValue(leftSibling
0550: .getValues().size() - 1));
0551:
0552: //If the siblings aren't leaves, move the last child from the left to be the
0553: // first on the right
0554: if (!leftSibling.isLeaf()) {
0555: rightSibling.addFileId(0, leftSibling.getChild(
0556: leftSibling.getChildIds().size() - 1).getFileId());
0557: }
0558:
0559: //Remove the last entry of the left sibling (now moved to upper node)
0560: leftSibling.removeKeyValuePairAt(leftSibling.size() - 1);
0561: if (!leftSibling.isLeaf()) {
0562: leftSibling.getChildIds().removeElementAt(
0563: leftSibling.getChildIds().size() - 1);
0564: }
0565: }
0566:
0567: private final void borrowRight(int borrowLoc) throws IOException,
0568: ClassNotFoundException {
0569: IntBTree leftSibling = getChild(borrowLoc);
0570: IntBTree rightSibling = getChild(borrowLoc + 1);
0571:
0572: //Add the upper key to as the last entry of the left sibling
0573: leftSibling.addKeyValuePair(getKey(borrowLoc),
0574: getValue(borrowLoc));
0575:
0576: //Make the upper node's key the first key from the right sibling
0577: setKeyValuePairAt(borrowLoc, rightSibling.getKey(0),
0578: rightSibling.getValue(0));
0579:
0580: //If the siblings aren't leaves, move the first child from the right to be the
0581: // last on the left
0582: if (!leftSibling.isLeaf()) {
0583: leftSibling.addFileId(rightSibling.getChild(0).getFileId());
0584: }
0585:
0586: //Remove the first entry of the right sibling (now moved to upper node)
0587: rightSibling.removeKeyValuePairAt(0);
0588: if (!rightSibling.isLeaf()) {
0589: rightSibling.getChildIds().removeElementAt(0);
0590: }
0591: }
0592:
0593: /**
0594: * Compare the given ints via my comparator.
0595: */
0596: private final int compare(int x, int y) {
0597: if (x == NullObject.INSTANCE.intValue()
0598: && y == NullObject.INSTANCE.intValue()) {
0599: return 0;
0600: }
0601: if (x == NullObject.INSTANCE.intValue()
0602: && y != NullObject.INSTANCE.intValue()) {
0603: return -1;
0604: } else if (y == NullObject.INSTANCE.intValue()
0605: && x != NullObject.INSTANCE.intValue()) {
0606: return 1;
0607: }
0608:
0609: return (x > y) ? 1 : ((x < y) ? -1 : 0);
0610: }
0611:
0612: /**
0613: * Delete the given key from the child in the specified position.
0614: */
0615: private final boolean deleteFromChild(int position, int key,
0616: int rowid) throws IOException, ClassNotFoundException {
0617: IntBTree node = getChild(position);
0618: return node.delete(key, rowid);
0619: }
0620:
0621: private final int findNearestKeyAbove(int key) {
0622: int size = size();
0623: int high = size;
0624: int low = 0;
0625: int cur = 0;
0626:
0627: //Short circuit
0628: if (size == 0) {
0629: return 0;
0630: } else if (isLessThan(getKey(size - 1), key)) {
0631: return size;
0632: } else if (isGreaterThanOrEqual(getKey(0), key)) {
0633: return 0;
0634: }
0635:
0636: while (low < high) {
0637: cur = (high + low) / 2;
0638: int comp = compare(key, getKey(cur));
0639: if (high == low) {
0640: cur = low;
0641: break;
0642: } else if (comp == 0) {
0643: //We found it now move to the first
0644: for (; (cur > 0) && (isEqual(key, getKey(cur))); cur--)
0645: ;
0646: break;
0647: } else if (high - low == 1) {
0648: cur = high;
0649: break;
0650: } else if (comp > 0) {
0651: if (low == cur) {
0652: low++;
0653: } else {
0654: low = cur;
0655: }
0656: } else { // comp < 0
0657: high = cur;
0658: }
0659: }
0660:
0661: //Now go to the nearest if there are multiple entries
0662: for (; (cur < size) && isGreaterThan(key, getKey(cur)); cur++) {
0663: }
0664:
0665: return cur;
0666: }
0667:
0668: private final int findNearestKeyBelow(int key) {
0669: int size = size();
0670: int high = size;
0671: int low = 0;
0672: int cur = 0;
0673:
0674: //Short circuit
0675: if (size == 0) {
0676: return -1;
0677: } else if (isLessThanOrEqual(getKey(size - 1), key)) {
0678: return size - 1;
0679: } else if (isGreaterThan(getKey(0), key)) {
0680: return -1;
0681: }
0682:
0683: while (low < high) {
0684: cur = (high + low) / 2;
0685: int comp = compare(key, getKey(cur));
0686: if (0 == comp) {
0687: //We found it now move to the last
0688: for (; (cur < size) && isEqual(key, getKey(cur)); cur++)
0689: ;
0690: break;
0691: } else if (comp > 0) {
0692: if (low == cur) {
0693: low++;
0694: } else {
0695: low = cur;
0696: }
0697: } else { // comp < 0
0698: high = cur;
0699: }
0700: }
0701:
0702: //Now go to the nearest if there are multiple entries
0703: for (; (cur >= 0) && (isLessThan(key, getKey(cur))); cur--)
0704: ;
0705:
0706: return cur;
0707: }
0708:
0709: /**
0710: * Find the index instsance of specified key and the specified row
0711: */
0712: private final int findNearestKeyBelow(int key, int rowid)
0713: throws IOException {
0714: int size = size();
0715: int high = size;
0716: int low = 0;
0717: int cur = 0;
0718:
0719: //Short circuit
0720: if (size == 0) {
0721: return -1;
0722: } else if (isLessThan(getKey(size - 1), key)) {
0723: return size - 1;
0724: } else if (isGreaterThan(getKey(0), key)) {
0725: return -1;
0726: } else if (isEqual(getKey(size - 1), key)) {
0727: // Find a row
0728: cur = findNearestRowBelow(key, rowid, size - 1);
0729: return cur;
0730: }
0731:
0732: while (low < high) {
0733: cur = (high + low) / 2;
0734: int comp = compare(key, getKey(cur));
0735: if (0 == comp) {
0736: // Find a row
0737: cur = findNearestRowBelow(key, rowid, cur);
0738: break;
0739: } else if (comp > 0) {
0740: if (low == cur) {
0741: low++;
0742: } else {
0743: low = cur;
0744: }
0745: } else { // comp < 0
0746: high = cur;
0747: }
0748: }
0749:
0750: //Now go to the nearest if there are multiple entries
0751: for (; (cur >= 0) && (isLessThan(key, getKey(cur))); cur--)
0752: ;
0753:
0754: return cur;
0755: }
0756:
0757: /**
0758: * Find the row instsance of specified key and the specified row and the specified
0759: * index
0760: */
0761: private final int findNearestRowBelow(int key, int rowid, int index)
0762: throws IOException {
0763: int cur = 0;
0764: int start = 0;
0765: int end = 0;
0766: boolean found = false;
0767: int size = size();
0768:
0769: // Find the duplicated keys range
0770: if (index == (size - 1) && index == 0) {
0771: //Case 1
0772: cur = 0;
0773: found = isEqual(rowid, getValue(cur));
0774: if (found) {
0775: cur = 0;
0776: } else if (getChildIds().size() > 0
0777: && isGreaterThan(rowid, getValue(cur))) {
0778: // the root is in the right-sub-tree
0779: cur++;
0780: } else {
0781: // the root is in the left-sub-tree
0782: cur = 0;
0783: }
0784: return cur;
0785: } else if (index == (size - 1)) {
0786: //Case 2
0787: end = index;
0788: cur = index;
0789: // Find the first index which key is specified
0790: for (; (cur >= 0) && isEqual(key, getKey(cur)); cur--) {
0791: if (isEqual(rowid, getValue(cur))) {
0792: found = true;
0793: break;
0794: }
0795: }
0796: start = found ? cur : ++cur;
0797: } else if (index == 0) {
0798: //Case 3
0799: start = index;
0800: cur = 0;
0801: // Find the last index which key is specified
0802: for (; (cur <= size) && isEqual(key, getKey(cur)); cur++) {
0803: if (isEqual(rowid, getValue(cur))) {
0804: found = true;
0805: break;
0806: }
0807: }
0808: end = found ? cur : --cur;
0809: } else {
0810: //Case 4
0811: cur = index;
0812: // Find the first index which key is specified
0813: for (; (cur >= 0) && isEqual(key, getKey(cur)); cur--) {
0814: if (isEqual(rowid, getValue(cur))) {
0815: found = true;
0816: break;
0817: }
0818: }
0819: start = found ? cur : ++cur;
0820: if (!found) {
0821: cur = index;
0822: // Find the last index which key is specified
0823: for (; (cur < size) && isEqual(key, getKey(cur)); cur++) {
0824: if (isEqual(rowid, getValue(cur))) {
0825: found = true;
0826: break;
0827: }
0828: }
0829: end = found ? cur : --cur;
0830: }
0831: }
0832:
0833: if (!found) {
0834: if (isGreaterThan(rowid, getValue(end))) {
0835: //Case 1
0836: // the root is in the right-sub-tree
0837: cur = end;
0838: } else if (isLessThan(rowid, getValue(start))) {
0839: //Case 2
0840: // the root is in the left-sub-tree
0841: cur = start;
0842: } else {
0843: //Case 3
0844: // the root is in the middle-sub-tree
0845: for (int i = start; i < end; i++) {
0846: if (isGreaterThan(rowid, getValue(i))
0847: && isLessThan(rowid, getValue(i + 1))) {
0848: cur = i;
0849: break;
0850: }
0851: }
0852: }
0853: }
0854: return cur;
0855: }
0856:
0857: private final void getAll(int key, IntListIteratorChain chain)
0858: throws IOException, ClassNotFoundException {
0859: int start = findNearestKeyAbove(key);
0860: int size = size();
0861: if (isLeaf()) {
0862: int stop;
0863: for (stop = start; stop < size
0864: && isEqual(key, getKey(stop)); stop++) {
0865: }
0866: chain.addIterator(getValues().subList(start, stop)
0867: .listIterator());
0868: } else {
0869: int i = start;
0870: for (; i < size && isEqual(key, getKey(i)); i++) {
0871: getChild(i).getAll(key, chain);
0872: chain.addIterator(getValue(i));
0873: }
0874: getChild(i).getAll(key, chain);
0875: }
0876: }
0877:
0878: private final void getAllExcludingNull(IntListIteratorChain chain)
0879: throws IOException, ClassNotFoundException {
0880: int start = _keys.lastIndexOf(NullObject.INSTANCE.intValue());
0881:
0882: int size = size();
0883: if (isLeaf() && start != -1 && (start + 1) < size) {
0884: chain.addIterator(getValues().subList(start + 1, size)
0885: .listIterator());
0886: } else {
0887: if (start == -1) {
0888: start = 0;
0889: }
0890: for (int i = start; i < size + 1; i++) {
0891: if (getChildIds().size() > 0) {
0892: getChild(i).getAllExcludingNull(chain);
0893: }
0894: if (i < size) {
0895: chain.addIterator(getValue(i));
0896: } else {
0897: break;
0898: }
0899: }
0900: }
0901: }
0902:
0903: private final void getAllFrom(int key, IntListIteratorChain chain)
0904: throws IOException, ClassNotFoundException {
0905: int start = findNearestKeyAbove(key);
0906: int size = size();
0907: if (isLeaf()) {
0908: chain.addIterator(getValues().subList(start, size)
0909: .listIterator());
0910: } else {
0911: for (int i = start; i < size + 1; i++) {
0912: getChild(i).getAllFrom(key, chain);
0913: if (i < size) {
0914: chain.addIterator(getValue(i));
0915: } else {
0916: break;
0917: }
0918: }
0919: }
0920: }
0921:
0922: private final void getAllTo(int key, IntListIteratorChain chain)
0923: throws IOException, ClassNotFoundException {
0924: int size = size();
0925: if (isLeaf()) {
0926: int endpoint = getKeys().indexOf(key);
0927: if (-1 != endpoint) {
0928: chain.addIterator(getValues().subList(0, endpoint)
0929: .listIterator());
0930: } else {
0931: chain.addIterator(getValues().listIterator());
0932: }
0933: } else {
0934: // else we need to interleave my child nodes as well
0935: for (int i = 0; i < size + 1; i++) {
0936: getChild(i).getAllTo(key, chain);
0937: if (i < size && isGreaterThan(key, getKey(i))) {
0938: chain.addIterator(getValue(i));
0939: } else {
0940: break;
0941: }
0942: }
0943: }
0944: }
0945:
0946: /**
0947: * Return the child node at the given index, or throw an exception if no such row
0948: * exists.
0949: */
0950: private final IntBTree getChild(int index) throws IOException,
0951: ClassNotFoundException {
0952: IntBTree child = getChildOrNull(index);
0953: if (null == child) {
0954: throw new IOException("Node " + getFileId()
0955: + " has no child at index " + index);
0956: }
0957: return child;
0958: }
0959:
0960: /**
0961: * Obtain the node with the specified file id, either from the cache or by loading it
0962: * from disk.
0963: */
0964: private final IntBTree getChildByFileId(int fileid)
0965: throws IOException, ClassNotFoundException {
0966: IntBTree child = (IntBTree) (getBTreeMetaData()
0967: .getCachedNode(fileid));
0968: if (null == child) {
0969: child = loadNode(getBTreeMetaData(), fileid);
0970: getBTreeMetaData().cacheNode(fileid, child);
0971: }
0972: return child;
0973: }
0974:
0975: private final IntBTree getChildOrNull(int index)
0976: throws IOException, ClassNotFoundException {
0977: if (index >= getChildIds().size()) {
0978: return null;
0979: }
0980: return getChildByFileId(getFileIdForIndex(index));
0981: }
0982:
0983: /**
0984: * Obtain a reference to my list of keys.
0985: */
0986: private final IntList getKeys() {
0987: return _keys;
0988: }
0989:
0990: /**
0991: * Finds and deletes the left most value from this subtree. The key and value for the
0992: * node is returned in the parameters. This also does the replacement as it unwraps.
0993: */
0994: private final void getLeftMost(int[] keyParam, int valueParam[])
0995: throws IOException, ClassNotFoundException {
0996: if (isLeaf()) {
0997: keyParam[0] = getKey(0);
0998: valueParam[0] = getValue(0);
0999: } else {
1000: getChild(0).getLeftMost(keyParam, valueParam);
1001: }
1002: }
1003:
1004: /**
1005: * Finds and deletes the right most value from this subtree. The key and value for the
1006: * node is returned in the parameters. This also does the replacement as it unwraps.
1007: */
1008: private final void getRightMost(int[] keyParam, int valueParam[])
1009: throws IOException, ClassNotFoundException {
1010: if (isLeaf()) {
1011: int max = size() - 1;
1012: keyParam[0] = getKey(max);
1013: valueParam[0] = getValue(max);
1014: } else {
1015: int max = getChildIds().size() - 1;
1016: getChild(max).getRightMost(keyParam, valueParam);
1017: }
1018: }
1019:
1020: private final boolean hasChild(int index) throws IOException,
1021: ClassNotFoundException {
1022: return (null != getChildOrNull(index));
1023: }
1024:
1025: private void inorderIterator(IntListIteratorChain chain)
1026: throws IOException, ClassNotFoundException {
1027: int start = 0;
1028: int size = size();
1029: if (isLeaf()) {
1030: int stop = size;
1031: chain.addIterator(getValues().subList(0, stop)
1032: .listIterator());
1033: } else {
1034: int i = start;
1035: for (; i < size; i++) {
1036: getChild(i).inorderIterator(chain);
1037: chain.addIterator(getValue(i));
1038: }
1039: getChild(i).inorderIterator(chain);
1040: }
1041: }
1042:
1043: /** Inserts the given key/value pair into this node, which is known to not be full */
1044: private final void insertNotfull(int key, int value)
1045: throws IOException, ClassNotFoundException {
1046: // find the appropriate slot in me
1047: int i = findNearestKeyBelow(key);
1048: // if I'm a leaf...
1049: if (isLeaf()) {
1050: // ...just insert the key/value pair
1051: addKeyValuePair(i + 1, key, value);
1052: //...and we're done
1053: } else {
1054: // Else if I'm an internal node,
1055: // ...grab the child that should contain the key
1056: i++;
1057: IntBTree child = getChild(i);
1058: // if that child is full, split it
1059: if (child.isFull()) {
1060: // if full, split it
1061: subdivideChild(i, child);
1062: // (move forward one if needed)
1063: if (isGreaterThan(key, getKey(i))) {
1064: i++;
1065: }
1066: }
1067: // then recurse
1068: getChild(i).insertNotfull(key, value);
1069: }
1070: }
1071:
1072: private final boolean isEqual(int x, int y) {
1073: return compare(x, y) == 0;
1074: }
1075:
1076: private final boolean isGreaterThan(int x, int y) {
1077: return compare(x, y) > 0;
1078: }
1079:
1080: private final boolean isGreaterThanOrEqual(int x, int y) {
1081: return compare(x, y) >= 0;
1082: }
1083:
1084: private final boolean isLessThan(int x, int y) {
1085: return compare(x, y) < 0;
1086: }
1087:
1088: private final boolean isLessThanOrEqual(int x, int y) {
1089: return compare(x, y) <= 0;
1090: }
1091:
1092: private final boolean isNotEqual(int x, int y) {
1093: return compare(x, y) != 0;
1094: }
1095:
1096: private final boolean isValid(boolean isRoot) throws IOException,
1097: ClassNotFoundException {
1098: int size = size();
1099: //Check to make sure that the node isn't an empty branch
1100: if (!isLeaf() && (size == 0)) {
1101: return false;
1102: }
1103: //Check to make sure that the node has enough children
1104: if (!isRoot && size < getMinimizationFactor() - 1) {
1105: return false;
1106: }
1107: //Check to make sure that there aren't too many children for the number of
1108: // entries
1109: if (!isLeaf()
1110: && (getChildIds().size() != size + 1 || size != getValues()
1111: .size())) {
1112: return false;
1113: }
1114: //Check all of the children
1115: if (!isLeaf()) {
1116: for (int i = 0, I = getChildIds().size(); i < I; i++) {
1117: if (!getChild(i).isValid(false)) {
1118: return false;
1119: }
1120: }
1121: }
1122: return true;
1123: }
1124:
1125: private final void maybeCollapseTree() throws IOException,
1126: ClassNotFoundException {
1127: if (!isLeaf() && size() <= 0) {
1128: IntBTree nodeToPromote = getChild(0);
1129: setTuples(nodeToPromote.getKeys(), nodeToPromote
1130: .getValues(), nodeToPromote.getChildIds());
1131: }
1132: }
1133:
1134: private final void mergeChildren(int mergeLoc, int key)
1135: throws IOException, ClassNotFoundException {
1136: IntBTree leftChild = getChild(mergeLoc);
1137: IntBTree rightChild = getChild(mergeLoc + 1);
1138:
1139: //Move the key down to the left child
1140: leftChild.addKeyValuePair(key, getValue(mergeLoc));
1141:
1142: //Copy the keys and values from the right to the left
1143: leftChild.addTuples(rightChild.getKeys(), rightChild
1144: .getValues(), rightChild.getChildIds());
1145:
1146: //Now remove the item from the upper node (since it's been put in left child)
1147: removeKeyValuePairAt(mergeLoc);
1148: getChildIds().removeElementAt(mergeLoc + 1);
1149:
1150: rightChild.clearData();
1151: }
1152:
1153: /** Removes the specified given key/value pair. */
1154: private final void removeKeyValuePairAt(int index) {
1155: getKeys().removeElementAt(index);
1156: getValues().removeElementAt(index);
1157: getBTreeMetaData().setDirty(this );
1158: }
1159:
1160: /**
1161: * {@link #replaceId Replace}the specified value within the child in the specified
1162: * position.
1163: */
1164: private final void replaceIdInChild(int position, int key,
1165: int oldRowId, int newRowId) throws IOException,
1166: ClassNotFoundException {
1167: IntBTree node = getChild(position);
1168: node.replaceId(key, oldRowId, newRowId);
1169: }
1170:
1171: /** Sets my key list */
1172: private final void setKeys(IntList keys) {
1173: _keys = keys;
1174: }
1175:
1176: /** Sets the specified given key/value pair. */
1177: private final void setKeyValuePairAt(int index, int key, int value) {
1178: getKeys().set(index, key);
1179: getValues().set(index, value);
1180: getBTreeMetaData().setDirty(this );
1181: }
1182:
1183: /** Sets the given given key/value/file id tuples. */
1184: private final void setTuples(IntList keys, IntList values,
1185: IntList fileIds) {
1186: setKeys(keys);
1187: setValues(values);
1188: if (null != fileIds) {
1189: setChildIds(fileIds);
1190: } else {
1191: getChildIds().clear();
1192: }
1193: getBTreeMetaData().setDirty(this );
1194: }
1195:
1196: /**
1197: * Splits the given node into two nodes. After this method executes, the specified
1198: * child will contain the first {@link #getMinimzationFactor <i>t</i>}keys, and a new
1199: * node (stored at <i>pivot + 1 </i>) will contain the remaining keys. It is assumed
1200: * that child is full (child.size() == getKeyCapacity()) when this method is invoked.
1201: */
1202: private final void subdivideChild(int pivot, IntBTree child)
1203: throws IOException, ClassNotFoundException {
1204: // create the new child node, (a sibling to the specified child)
1205: IntBTree fetus = allocateNewNode();
1206: // insert said child into me (the parent)
1207: addFileId(pivot + 1, fetus.getFileId());
1208:
1209: // copy the tail key/value paris from child to the new node
1210: fetus.addKeyValuePairs(child.getKeys().subList(
1211: getMinimizationFactor(), getKeyCapacity()), child
1212: .getValues().subList(getMinimizationFactor(),
1213: getKeyCapacity()));
1214:
1215: // copy the children of child to the new node, if necessary
1216: int i = 0;
1217: if (!child.isLeaf()) {
1218: IntList sub = child.getChildIds().subList(
1219: getMinimizationFactor(), getKeyCapacity() + 1);
1220: fetus.addFileIds(sub);
1221: // remove the children from child
1222: for (i = getKeyCapacity(); i >= getMinimizationFactor(); i--) {
1223: child.getChildIds().removeElementAt(i);
1224: }
1225: }
1226:
1227: // add the median key (which now splits child from the new node)
1228: // here to the parent
1229: addKeyValuePair(pivot, child
1230: .getKey(getMinimizationFactor() - 1), child
1231: .getValue(getMinimizationFactor() - 1));
1232:
1233: // remove the key/value pairs from child
1234: for (i = (getKeyCapacity() - 1); i > (getMinimizationFactor() - 2); i--) {
1235: child.removeKeyValuePairAt(i);
1236: }
1237: }
1238:
1239: /**
1240: * Print this node, with every line prefixed by 2*space spaces.
1241: */
1242: private final String toString(int space) {
1243: StringBuffer buf = new StringBuffer();
1244: buf.append(space(space));
1245: buf.append(getFileId());
1246: buf.append(": ");
1247: buf.append(getKeys().toString());
1248: buf.append("/");
1249: buf.append(getValues().toString());
1250: buf.append("\n");
1251: if (!isLeaf()) {
1252: for (int i = 0, size = size(); i < size + 1; i++) {
1253: IntBTree child = null;
1254: try {
1255: child = getChild(i);
1256: } catch (Exception e) {
1257: e.printStackTrace();
1258: }
1259: if (null != child) {
1260: buf.append(child.toString(space + 1));
1261: } else {
1262: buf.append(space(space + 1));
1263: buf.append("null");
1264: buf.append("\n");
1265: }
1266: }
1267: }
1268: return buf.toString();
1269: }
1270:
1271: private static class BTreeValueIterator implements IntIterator {
1272:
1273: private StateStack _stack;
1274:
1275: BTreeValueIterator(IntBTree node) throws IOException {
1276: _stack = new StateStack();
1277: _stack.push(node, false, 0);
1278: }
1279:
1280: BTreeValueIterator(StateStack stack) throws IOException {
1281: _stack = stack;
1282: }
1283:
1284: public boolean hasNext() {
1285: while (true) {
1286: if (_stack.isEmpty()) {
1287: return false;
1288: }
1289: State state = _stack.peek();
1290: if ((state.node.isLeaf() || state.visitedChildren)
1291: && state.position >= state.node.size()) {
1292: _stack.pop();
1293: } else {
1294: return true;
1295: }
1296: }
1297: }
1298:
1299: public int next() {
1300: try {
1301: while (true) {
1302: if (_stack.isEmpty()) {
1303: throw new NoSuchElementException();
1304: }
1305: State state = _stack.pop();
1306: if (!state.visitedChildren) {
1307: state.visitedChildren = true;
1308: _stack.push(state);
1309: if (state.node.hasChild(state.position)) {
1310: _stack
1311: .push(state.node
1312: .getChild(state.position),
1313: false, 0);
1314: }
1315: } else if (state.position < state.node.size()) {
1316: int value = state.node.getValue(state.position);
1317: state.position++;
1318: state.visitedChildren = false;
1319: _stack.push(state);
1320: return value;
1321: } else {
1322: // do nothing, I've already popped
1323: }
1324: }
1325: } catch (Exception e) {
1326: throw ExceptionConverter.convertToRuntimeException(e);
1327: }
1328: }
1329:
1330: public void remove() {
1331: throw new UnsupportedOperationException();
1332: }
1333: }
1334:
1335: private static class State {
1336:
1337: IntBTree node;
1338: int position = 0;
1339: boolean visitedChildren = false;
1340:
1341: State(IntBTree n, boolean visited, int pos) {
1342: node = n;
1343: visitedChildren = visited;
1344: position = pos;
1345: }
1346:
1347: public String toString() {
1348: return "<" + node.getFileId() + "," + visitedChildren + ","
1349: + position + ">";
1350: }
1351: }
1352:
1353: private static class StateStack {
1354:
1355: private List _nodes = new ArrayList();
1356:
1357: StateStack() {
1358: }
1359:
1360: public String toString() {
1361: return _nodes.toString();
1362: }
1363:
1364: boolean isEmpty() {
1365: return _nodes.isEmpty();
1366: }
1367:
1368: State peek() {
1369: return (State) _nodes.get(_nodes.size() - 1);
1370: }
1371:
1372: State pop() {
1373: return (State) (_nodes.remove(_nodes.size() - 1));
1374: }
1375:
1376: void push(IntBTree tree, boolean visitedChildren, int position) {
1377: push(new State(tree, visitedChildren, position));
1378: }
1379:
1380: void push(State state) {
1381: _nodes.add(state);
1382: }
1383:
1384: }
1385:
1386: private IntList _keys;
1387:
1388: }
|