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