0001: // kelondroTree.java
0002: // -----------------------
0003: // part of The Kelondro Database
0004: // (C) by Michael Peter Christen; mc@anomic.de
0005: // first published on http://www.anomic.de
0006: // Frankfurt, Germany, 2004
0007: // last major change: 07.02.2005
0008: //
0009: // This program is free software; you can redistribute it and/or modify
0010: // it under the terms of the GNU General Public License as published by
0011: // the Free Software Foundation; either version 2 of the License, or
0012: // (at your option) any later version.
0013: //
0014: // This program is distributed in the hope that it will be useful,
0015: // but WITHOUT ANY WARRANTY; without even the implied warranty of
0016: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0017: // GNU General Public License for more details.
0018: //
0019: // You should have received a copy of the GNU General Public License
0020: // along with this program; if not, write to the Free Software
0021: // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
0022: //
0023: // Using this software in any meaning (reading, learning, copying, compiling,
0024: // running) means that you agree that the Author(s) is (are) not responsible
0025: // for cost, loss of data or any harm that may be caused directly or indirectly
0026: // by usage of this softare or this documentation. The usage of this software
0027: // is on your own risk. The installation and usage (starting/running) of this
0028: // software may allow other people or application to access your computer and
0029: // any attached devices and is highly dependent on the configuration of the
0030: // software which must be done by the user of the software; the author(s) is
0031: // (are) also not responsible for proper configuration and usage of the
0032: // software, even if provoked by documentation provided together with
0033: // the software.
0034: //
0035: // Any changes to this file according to the GPL as documented in the file
0036: // gpl.txt aside this file in the shipment you received can be done to the
0037: // lines that follows this copyright notice here, but changes must not be
0038: // done inside the copyright notive above. A re-distribution must contain
0039: // the intact and unchanged copyright notice.
0040: // Contributions and changes to the program code must be marked as such.
0041:
0042: /*
0043: This class extends the kelondroRecords and adds a tree structure
0044: */
0045:
0046: package de.anomic.kelondro;
0047:
0048: import java.io.BufferedReader;
0049: import java.io.File;
0050: import java.io.FileReader;
0051: import java.io.IOException;
0052: import java.io.RandomAccessFile;
0053: import java.util.ArrayList;
0054: import java.util.Comparator;
0055: import java.util.Date;
0056: import java.util.HashSet;
0057: import java.util.Iterator;
0058: import java.util.LinkedList;
0059: import java.util.List;
0060: import java.util.Map;
0061: import java.util.StringTokenizer;
0062: import java.util.TreeMap;
0063: import java.util.TreeSet;
0064: import java.util.Vector;
0065: import java.util.logging.Logger;
0066:
0067: import de.anomic.kelondro.kelondroRow.Entry;
0068: import de.anomic.server.logging.serverLog;
0069:
0070: public class kelondroTree extends kelondroCachedRecords implements
0071: kelondroIndex {
0072:
0073: // logging (This probably needs someone to initialize the java.util.logging.* facilities);
0074: public static final Logger log = Logger.getLogger("KELONDRO");
0075:
0076: // define the Over-Head-Array
0077: protected static final short this OHBytes = 2; // our record definition of two bytes
0078: protected static final short this OHHandles = 3; // and three handles overhead
0079: protected static final short this FHandles = 1; // file handles: one for a root pointer
0080:
0081: // define pointers for OH array access
0082: protected static final int magic = 0; // pointer for OHByte-array: marker for Node purpose; defaults to 1
0083: protected static final int balance = 1; // pointer for OHByte-array: balance value of tree node; balanced = 0
0084:
0085: protected static final int parent = 0; // pointer for OHHandle-array: handle()-Value of parent Node
0086: protected static final int leftchild = 1; // pointer for OHHandle-array: handle()-Value of left child Node
0087: protected static final int rightchild = 2; // pointer for OHHandle-array: handle()-Value of right child Node
0088:
0089: protected static final int root = 0; // pointer for FHandles-array: pointer to root node
0090:
0091: // class variables
0092: private final Search writeSearchObj = new Search();
0093: protected Comparator<String> loopDetectionOrder;
0094: protected int readAheadChunkSize = 100;
0095: protected long lastIteratorCount = readAheadChunkSize;
0096:
0097: public kelondroTree(File file, boolean useNodeCache,
0098: long preloadTime, kelondroRow rowdef) throws IOException {
0099: this (file, useNodeCache, preloadTime, rowdef,
0100: rowdef.columns() /* txtProps */, 80 /* txtPropWidth */);
0101: }
0102:
0103: public kelondroTree(File file, boolean useNodeCache,
0104: long preloadTime, kelondroRow rowdef, int txtProps,
0105: int txtPropsWidth) throws IOException {
0106: // opens an existing tree file or creates a new tree file
0107: super (file, useNodeCache, preloadTime, this OHBytes,
0108: this OHHandles, rowdef, this FHandles, txtProps,
0109: txtPropsWidth);
0110: if (!fileExisted) {
0111: // create new file structure
0112: setHandle(root, null); // define the root value
0113: }
0114: super .setLogger(log);
0115: this .loopDetectionOrder = new kelondroByteOrder.StringOrder(
0116: rowdef.objectOrder);
0117: }
0118:
0119: public static final kelondroTree open(File file,
0120: boolean useNodeCache, long preloadTime, kelondroRow rowdef) {
0121: return open(file, useNodeCache, preloadTime, rowdef, rowdef
0122: .columns() /* txtProps */, 80 /* txtPropWidth */);
0123: }
0124:
0125: public static final kelondroTree open(File file,
0126: boolean useNodeCache, long preloadTime, kelondroRow rowdef,
0127: int txtProps, int txtPropsWidth) {
0128: // opens new or existing file; in case that any error occur the file is deleted again and it is tried to create the file again
0129: // if that fails, the method returns null
0130: try {
0131: return new kelondroTree(file, useNodeCache, preloadTime,
0132: rowdef, txtProps, txtPropsWidth);
0133: } catch (IOException e) {
0134: file.delete();
0135: try {
0136: return new kelondroTree(file, useNodeCache,
0137: preloadTime, rowdef, txtProps, txtPropsWidth);
0138: } catch (IOException ee) {
0139: log.severe("cannot open or create file "
0140: + file.toString());
0141: e.printStackTrace();
0142: ee.printStackTrace();
0143: return null;
0144: }
0145: }
0146: }
0147:
0148: public kelondroTree(kelondroRA ra, String filename,
0149: boolean useNodeCache, long preloadTime, kelondroRow rowdef,
0150: boolean exitOnFail) {
0151: // this creates a new tree within a kelondroRA
0152: this (ra, filename, useNodeCache, preloadTime, rowdef,
0153: new kelondroNaturalOrder(true),
0154: rowdef.columns() /* txtProps */,
0155: 80 /* txtPropWidth */, exitOnFail);
0156: }
0157:
0158: public kelondroTree(kelondroRA ra, String filename,
0159: boolean useNodeCache, long preloadTime, kelondroRow rowdef,
0160: kelondroByteOrder objectOrder, int txtProps,
0161: int txtPropsWidth, boolean exitOnFail) {
0162: // this creates a new tree within a kelondroRA
0163: super (ra, filename, useNodeCache, preloadTime, this OHBytes,
0164: this OHHandles, rowdef, this FHandles, txtProps,
0165: txtPropsWidth, exitOnFail);
0166: try {
0167: setHandle(root, null); // define the root value
0168: } catch (IOException e) {
0169: super .logFailure("cannot set root handle / "
0170: + e.getMessage());
0171: if (exitOnFail)
0172: System.exit(-1);
0173: throw new RuntimeException("cannot set root handle / "
0174: + e.getMessage());
0175: }
0176: super .setLogger(log);
0177: this .loopDetectionOrder = new kelondroByteOrder.StringOrder(
0178: rowdef.objectOrder);
0179: }
0180:
0181: public kelondroTree(kelondroRA ra, String filename,
0182: boolean useNodeCache, long preloadTime) throws IOException {
0183: // this opens a file with an existing tree in a kelondroRA
0184: super (ra, filename, useNodeCache, preloadTime);
0185: super .setLogger(log);
0186: }
0187:
0188: public void reset() throws IOException {
0189: super .reset();
0190: setHandle(root, null);
0191: }
0192:
0193: private void commitNode(kelondroNode n) throws IOException {
0194: //kelondroHandle left = n.getOHHandle(leftchild);
0195: //kelondroHandle right = n.getOHHandle(rightchild);
0196: n.commit();
0197: }
0198:
0199: public boolean has(byte[] key) throws IOException {
0200: throw new UnsupportedOperationException(
0201: "has should not be used with kelondroTree.");
0202: }
0203:
0204: // Returns the value to which this map maps the specified key.
0205: public kelondroRow.Entry get(byte[] key) throws IOException {
0206: kelondroRow.Entry result;
0207: synchronized (writeSearchObj) {
0208: writeSearchObj.process(key);
0209: if (writeSearchObj.found()) {
0210: result = row().newEntry(
0211: writeSearchObj.getMatcher().getValueRow());
0212: } else {
0213: result = null;
0214: }
0215: }
0216: return result;
0217: }
0218:
0219: public ArrayList<kelondroRowSet> removeDoubles() {
0220: // this data structure cannot have doubles; return empty array
0221: return new ArrayList<kelondroRowSet>();
0222: }
0223:
0224: public class Search {
0225:
0226: // a search object combines the results of a search in the tree, which are
0227: // - the searched object is found, an index pointing to the node can be returned
0228: // - the object was not found, an index pointing to an appropriate possible parent node
0229: // can be returned, together with the information wether the new key shall
0230: // be left or right child.
0231:
0232: private CacheNode thenode, parentnode;
0233: private boolean found; // property if node was found
0234: private byte child; // -1: left child; 0: root node; 1: right child
0235:
0236: // temporary variables
0237: private kelondroHandle this Handle;
0238: String keybuffer;
0239:
0240: protected Search() {
0241: }
0242:
0243: protected void process(byte[] key) throws IOException {
0244: // searchs the database for the key and stores the result in the thisHandle
0245: // if the key was found, then found=true, thisHandle and leftchild is set;
0246: // else found=false and thisHandle and leftchild is undefined
0247: this Handle = getHandle(root);
0248: parentnode = null;
0249: if (key == null) {
0250: throw new kelondroException(
0251: "startet search process with key == null");
0252: /*
0253: child = 0;
0254: if (thisHandle == null) {
0255: thenode = null;
0256: found = false;
0257: } else {
0258: thenode = getNode(thisHandle, null, 0);
0259: found = true;
0260: }
0261: return;
0262: */
0263: }
0264: thenode = null;
0265: child = 0;
0266: found = false;
0267: int c;
0268:
0269: TreeSet<String> visitedNodeKeys = new TreeSet<String>(
0270: loopDetectionOrder); // to detect loops
0271: // System.out.println("Starting Compare Loop in Database " + filename); // debug
0272: while (this Handle != null) {
0273: try {
0274: parentnode = thenode;
0275: thenode = new CacheNode(this Handle, thenode,
0276: (child == -1) ? leftchild : rightchild,
0277: true);
0278: } catch (IllegalArgumentException e) {
0279: logWarning("kelondroTree.Search.process: fixed a broken handle");
0280: found = false;
0281: return;
0282: }
0283: if (thenode == null)
0284: throw new kelondroException(filename,
0285: "kelondroTree.Search.process: thenode==null");
0286:
0287: keybuffer = new String(thenode.getKey());
0288: if (keybuffer == null) {
0289: // this is an error. distinguish two cases:
0290: // 1. thenode is a leaf node. Then this error can be fixed if we can consider this node as a good node to be replaced with a new value
0291: // 2. thenode is not a leaf node. An exception must be thrown
0292: if ((thenode.getOHHandle(leftchild) == null)
0293: && (thenode.getOHHandle(rightchild) == null)) {
0294: // case 1: recover
0295: deleteNode(this Handle);
0296: thenode = parentnode;
0297: found = false;
0298: return;
0299: } else {
0300: // case 2: fail
0301: throw new kelondroException(
0302: "found key during search process with key == null");
0303: }
0304: }
0305: if (visitedNodeKeys.contains(keybuffer)) {
0306: // we have loops in the database.
0307: // to fix this, all affected nodes must be patched
0308: thenode.setOHByte(magic, (byte) 1);
0309: thenode.setOHByte(balance, (byte) 0);
0310: thenode.setOHHandle(parent, null);
0311: thenode.setOHHandle(leftchild, null);
0312: thenode.setOHHandle(rightchild, null);
0313: thenode.commit();
0314: logWarning("kelondroTree.Search.process: database contains loops; the loop-nodes have been auto-fixed");
0315: found = false;
0316: return;
0317: }
0318: // System.out.println("Comparing key = '" + new String(key) + "' with '" + otherkey + "':"); // debug
0319: c = row().objectOrder
0320: .compare(key, keybuffer.getBytes());
0321: // System.out.println(c); // debug
0322: if (c == 0) {
0323: found = true;
0324: // System.out.println("DEBUG: search for " + new String(key) + " ended with status=" + ((found) ? "found" : "not-found") + ", node=" + ((thenode == null) ? "NULL" : thenode.toString()) + ", parent=" + ((parentnode == null) ? "NULL" : parentnode.toString()));
0325: return;
0326: } else if (c < 0) {
0327: child = -1;
0328: this Handle = thenode.getOHHandle(leftchild);
0329: } else {
0330: child = 1;
0331: this Handle = thenode.getOHHandle(rightchild);
0332: }
0333: visitedNodeKeys.add(keybuffer);
0334: }
0335: // System.out.println("DEBUG: search for " + new String(key) + " ended with status=" + ((found) ? "found" : "not-found") + ", node=" + ((thenode == null) ? "NULL" : thenode.toString()) + ", parent=" + ((parentnode == null) ? "NULL" : parentnode.toString()));
0336: // we reached a node where we must insert the new value
0337: // the parent of this new value can be obtained by getParent()
0338: // all values are set, just return
0339: }
0340:
0341: public boolean found() {
0342: return found;
0343: }
0344:
0345: public CacheNode getMatcher() {
0346: if (found)
0347: return thenode;
0348: throw new IllegalArgumentException(
0349: "wrong access of matcher");
0350: }
0351:
0352: public CacheNode getParent() {
0353: if (found)
0354: return parentnode;
0355: return thenode;
0356: }
0357:
0358: public boolean isRoot() {
0359: if (found)
0360: throw new IllegalArgumentException(
0361: "wrong access of isRoot");
0362: return (child == 0);
0363: }
0364:
0365: public boolean isLeft() {
0366: if (found)
0367: throw new IllegalArgumentException(
0368: "wrong access of leftchild");
0369: return (child == -1);
0370: }
0371:
0372: public boolean isRight() {
0373: if (found)
0374: throw new IllegalArgumentException(
0375: "wrong access of leftchild");
0376: return (child == 1);
0377: }
0378: }
0379:
0380: public synchronized boolean isChild(kelondroNode childn,
0381: kelondroNode parentn, int child) {
0382: if (childn == null)
0383: throw new IllegalArgumentException(
0384: "isLeftChild: Node parameter is NULL");
0385: kelondroHandle lc = parentn.getOHHandle(child);
0386: if (lc == null)
0387: return false;
0388: return (lc.equals(childn.handle()));
0389: }
0390:
0391: public synchronized void putMultiple(List<Entry> rows)
0392: throws IOException {
0393: Iterator<Entry> i = rows.iterator();
0394: while (i.hasNext())
0395: put(i.next());
0396: }
0397:
0398: public kelondroRow.Entry put(kelondroRow.Entry row, Date entryDate)
0399: throws IOException {
0400: return put(row);
0401: }
0402:
0403: public kelondroRow.Entry put(kelondroRow.Entry newrow)
0404: throws IOException {
0405: assert (newrow != null);
0406: assert (newrow.columns() == row().columns());
0407: assert (!(serverLog.allZero(newrow.getPrimaryKeyBytes())));
0408: assert newrow.objectsize() <= super .row().objectsize;
0409: // Associates the specified value with the specified key in this map
0410: kelondroRow.Entry result = null;
0411: //writeLock.stay(2000, 1000);
0412: // first try to find the key element in the database
0413: synchronized (writeSearchObj) {
0414: writeSearchObj.process(newrow.getColBytes(0));
0415: if (writeSearchObj.found()) {
0416: // a node with this key exist. simply overwrite the content and return old content
0417: kelondroNode e = writeSearchObj.getMatcher();
0418: result = row().newEntry(e.getValueRow());
0419: e.setValueRow(newrow.bytes());
0420: commitNode(e);
0421: } else if (writeSearchObj.isRoot()) {
0422: // a node with this key does not exist and there is no node at all
0423: // this therefore creates the root node if an only if there was no root Node yet
0424: if (getHandle(root) != null)
0425: throw new kelondroException(filename,
0426: "tried to create root node twice");
0427: // we dont have any Nodes in the file, so start here to create one
0428: kelondroNode e = new CacheNode(newrow.bytes());
0429: // write the propetries
0430: e.setOHByte(magic, (byte) 1);
0431: e.setOHByte(balance, (byte) 0);
0432: e.setOHHandle(parent, null);
0433: e.setOHHandle(leftchild, null);
0434: e.setOHHandle(rightchild, null);
0435: // do updates
0436: e.commit();
0437: setHandle(root, e.handle());
0438: result = null;
0439: } else {
0440: // a node with this key does not exist
0441: // this creates a new node if there is already at least a root node
0442: // to create the new node, it is necessary to assign it to a parent
0443: // it must also be defined weather this new node is a left child of the
0444: // parent or not. It is checked if the parent node already has a child on
0445: // that side, but not if the assigned position is appropriate.
0446:
0447: // create new node and assign values
0448: CacheNode parentNode = writeSearchObj.getParent();
0449: CacheNode theNode = new CacheNode(newrow.bytes());
0450: theNode.setOHByte(0, (byte) 1); // fresh magic
0451: theNode.setOHByte(1, (byte) 0); // fresh balance
0452: theNode.setOHHandle(parent, parentNode.handle());
0453: theNode.setOHHandle(leftchild, null);
0454: theNode.setOHHandle(rightchild, null);
0455: theNode.commit();
0456:
0457: // check consistency and link new node to parent node
0458: byte parentBalance;
0459: if (writeSearchObj.isLeft()) {
0460: if (parentNode.getOHHandle(leftchild) != null)
0461: throw new kelondroException(
0462: filename,
0463: "tried to create leftchild node twice. parent="
0464: + new String(parentNode
0465: .getKey())
0466: + ", leftchild="
0467: + new String(
0468: new CacheNode(
0469: parentNode
0470: .getOHHandle(leftchild),
0471: (CacheNode) null,
0472: 0, true)
0473: .getKey()));
0474: parentNode.setOHHandle(leftchild, theNode.handle());
0475: } else if (writeSearchObj.isRight()) {
0476: if (parentNode.getOHHandle(rightchild) != null)
0477: throw new kelondroException(
0478: filename,
0479: "tried to create rightchild node twice. parent="
0480: + new String(parentNode
0481: .getKey())
0482: + ", rightchild="
0483: + new String(
0484: new CacheNode(
0485: parentNode
0486: .getOHHandle(rightchild),
0487: (CacheNode) null,
0488: 0, true)
0489: .getKey()));
0490: parentNode
0491: .setOHHandle(rightchild, theNode.handle());
0492: } else {
0493: throw new kelondroException(filename,
0494: "neither left nor right child");
0495: }
0496: commitNode(parentNode);
0497:
0498: // now update recursively the node balance of the parentNode
0499: // what do we have:
0500: // - new Node, called 'theNode'
0501: // - parent Node
0502:
0503: // set balance factor in parent node(s)
0504: boolean increasedHight = true;
0505: String path = "";
0506: byte prevHight;
0507: kelondroHandle parentSideHandle;
0508: while (increasedHight) {
0509:
0510: // update balance
0511: parentBalance = parentNode.getOHByte(balance); // {magic, balance}
0512: prevHight = parentBalance;
0513: parentSideHandle = parentNode
0514: .getOHHandle(leftchild);
0515: if ((parentSideHandle != null)
0516: && (parentSideHandle.equals(theNode
0517: .handle()))) {
0518: // is left child
0519: parentBalance++;
0520: path = "L" + path;
0521: }
0522: parentSideHandle = parentNode
0523: .getOHHandle(rightchild);
0524: if ((parentSideHandle != null)
0525: && (parentSideHandle.equals(theNode
0526: .handle()))) {
0527: // is right child
0528: parentBalance--;
0529: path = "R" + path;
0530: }
0531: increasedHight = ((java.lang.Math
0532: .abs((int) parentBalance) - java.lang.Math
0533: .abs((int) prevHight)) > 0);
0534: parentNode.setOHByte(balance, parentBalance);
0535: commitNode(parentNode);
0536:
0537: // here we either stop because we had no increased hight,
0538: // or we have a balance greater then 1 or less than -1 and we do rotation
0539: // or we crawl up the tree and change the next balance
0540: if (!(increasedHight))
0541: break; // finished
0542:
0543: // check rotation need
0544: if (java.lang.Math.abs((int) parentBalance) > 1) {
0545: // rotate and stop then
0546: //System.out.println("* DB DEBUG: " + path.substring(0,2) + " ROTATION AT NODE " + parentNode.handle().toString() + ": BALANCE=" + parentOHByte[balance]);
0547: if (path.startsWith("LL")) {
0548: LL_RightRotation(parentNode, theNode);
0549: break;
0550: }
0551: if (path.startsWith("RR")) {
0552: RR_LeftRotation(parentNode, theNode);
0553: break;
0554: }
0555: if (path.startsWith("RL")) {
0556: kelondroHandle parentHandle = parentNode
0557: .handle();
0558: LL_RightRotation(theNode, new CacheNode(
0559: theNode.getOHHandle(leftchild),
0560: theNode, leftchild, false));
0561: parentNode = new CacheNode(parentHandle,
0562: null, 0, false); // reload the parent node
0563: RR_LeftRotation(parentNode, new CacheNode(
0564: parentNode.getOHHandle(rightchild),
0565: parentNode, rightchild, false));
0566: break;
0567: }
0568: if (path.startsWith("LR")) {
0569: kelondroHandle parentHandle = parentNode
0570: .handle();
0571: RR_LeftRotation(theNode, new CacheNode(
0572: theNode.getOHHandle(rightchild),
0573: theNode, rightchild, false));
0574: parentNode = new CacheNode(parentHandle,
0575: null, 0, false); // reload the parent node
0576: LL_RightRotation(parentNode, new CacheNode(
0577: parentNode.getOHHandle(leftchild),
0578: parentNode, leftchild, false));
0579: break;
0580: }
0581: break;
0582: }
0583: // crawl up the tree
0584: if (parentNode.getOHHandle(parent) == null)
0585: break; // root reached: stop
0586: theNode = parentNode;
0587: parentNode = new CacheNode(parentNode
0588: .getOHHandle(parent), null, 0, false);
0589: }
0590:
0591: result = null; // that means: no previous stored value present
0592: }
0593: }
0594: //writeLock.release();
0595: return result;
0596: }
0597:
0598: public synchronized void addUnique(kelondroRow.Entry row)
0599: throws IOException {
0600: this .put(row);
0601: }
0602:
0603: public synchronized void addUnique(kelondroRow.Entry row,
0604: Date entryDate) throws IOException {
0605: this .put(row, entryDate);
0606: }
0607:
0608: public synchronized void addUniqueMultiple(
0609: List<kelondroRow.Entry> rows) throws IOException {
0610: Iterator<kelondroRow.Entry> i = rows.iterator();
0611: while (i.hasNext())
0612: addUnique(i.next());
0613: }
0614:
0615: private void assignChild(kelondroNode parentNode,
0616: kelondroNode childNode, int childType) throws IOException {
0617: parentNode.setOHHandle(childType, childNode.handle());
0618: childNode.setOHHandle(parent, parentNode.handle());
0619: commitNode(parentNode);
0620: commitNode(childNode);
0621: }
0622:
0623: private void replace(kelondroNode oldNode,
0624: kelondroNode oldNodeParent, kelondroNode newNode)
0625: throws IOException {
0626: // this routine looks where the oldNode is connected to, and replaces
0627: // the anchor's link to the oldNode by the newNode-link
0628: // the new link gets the anchor as parent link assigned
0629: // the oldNode will not be updated, so this must be done outside this routine
0630: // distinguish case where the oldNode is the root node
0631: if (oldNodeParent == null) {
0632: // this is the root, update root
0633: setHandle(root, newNode.handle());
0634: // update new Node
0635: newNode.setOHHandle(parent, null);
0636: commitNode(newNode);
0637: } else {
0638: // not the root, find parent
0639: // ok, we have the parent, but for updating the child link we must know
0640: // if the oldNode was left or right child
0641: kelondroHandle parentSideHandle = oldNodeParent
0642: .getOHHandle(leftchild);
0643: if ((parentSideHandle != null)
0644: && (parentSideHandle.equals(oldNode.handle()))) {
0645: // update left node from parent
0646: oldNodeParent.setOHHandle(leftchild, newNode.handle());
0647: }
0648: parentSideHandle = oldNodeParent.getOHHandle(rightchild);
0649: if ((parentSideHandle != null)
0650: && (parentSideHandle.equals(oldNode.handle()))) {
0651: // update right node from parent
0652: oldNodeParent.setOHHandle(rightchild, newNode.handle());
0653: }
0654: commitNode(oldNodeParent);
0655: // update new Node
0656: newNode.setOHHandle(parent, oldNodeParent.handle());
0657: commitNode(newNode);
0658: }
0659: // finished. remember that we did not set the links to the oldNode
0660: // we have also not set the children of the newNode.
0661: // this must be done somewhere outside this function.
0662: // if the oldNode is not needed any more, it can be disposed (check childs first).
0663: }
0664:
0665: private static byte max0(byte b) {
0666: if (b > 0)
0667: return b;
0668: return 0;
0669: }
0670:
0671: private static byte min0(byte b) {
0672: if (b < 0)
0673: return b;
0674: return 0;
0675: }
0676:
0677: private void LL_RightRotation(kelondroNode parentNode,
0678: CacheNode childNode) throws IOException {
0679: // replace the parent node; the parent is afterwards unlinked
0680: kelondroHandle p2Handle = parentNode.getOHHandle(parent);
0681: kelondroNode p2Node = (p2Handle == null) ? null
0682: : new CacheNode(p2Handle, null, 0, false);
0683: replace(parentNode, p2Node, childNode);
0684:
0685: // set the left son of the parent to the right son of the childNode
0686: kelondroHandle childOfChild = childNode.getOHHandle(rightchild);
0687: if (childOfChild == null) {
0688: parentNode.setOHHandle(leftchild, null);
0689: } else {
0690: assignChild(parentNode, new CacheNode(childOfChild,
0691: childNode, rightchild, false), leftchild);
0692: }
0693:
0694: // link the old parent node as the right child of childNode
0695: assignChild(childNode, parentNode, rightchild);
0696:
0697: // - newBal(parent) = oldBal(parent) - 1 - max(oldBal(leftChild), 0)
0698: // - newBal(leftChild) = oldBal(leftChild) - 1 + min(newBal(parent), 0)
0699: byte parentBalance = parentNode.getOHByte(balance);
0700: byte childBalance = childNode.getOHByte(balance);
0701: byte oldBalParent = parentBalance;
0702: byte oldBalChild = childBalance;
0703: parentBalance = (byte) (oldBalParent - 1 - max0(oldBalChild));
0704: childBalance = (byte) (oldBalChild - 1 + min0(parentBalance));
0705: parentNode.setOHByte(balance, parentBalance);
0706: childNode.setOHByte(balance, childBalance);
0707: commitNode(parentNode);
0708: commitNode(childNode);
0709: }
0710:
0711: private void RR_LeftRotation(kelondroNode parentNode,
0712: CacheNode childNode) throws IOException {
0713: // replace the parent node; the parent is afterwards unlinked
0714: kelondroHandle p2Handle = parentNode.getOHHandle(parent);
0715: kelondroNode p2Node = (p2Handle == null) ? null
0716: : new CacheNode(p2Handle, null, 0, false);
0717: replace(parentNode, p2Node, childNode);
0718:
0719: // set the left son of the parent to the right son of the childNode
0720: kelondroHandle childOfChild = childNode.getOHHandle(leftchild);
0721: if (childOfChild == null) {
0722: parentNode.setOHHandle(rightchild, null);
0723: } else {
0724: assignChild(parentNode, new CacheNode(childOfChild,
0725: childNode, leftchild, false), rightchild);
0726: }
0727:
0728: // link the old parent node as the left child of childNode
0729: assignChild(childNode, parentNode, leftchild);
0730:
0731: // - newBal(parent) = oldBal(parent) + 1 - min(oldBal(rightChild), 0)
0732: // - newBal(rightChild) = oldBal(rightChild) + 1 + max(newBal(parent), 0)
0733: byte parentBalance = parentNode.getOHByte(balance);
0734: byte childBalance = childNode.getOHByte(balance);
0735: byte oldBalParent = parentBalance;
0736: byte oldBalChild = childBalance;
0737: parentBalance = (byte) (oldBalParent + 1 - min0(oldBalChild));
0738: childBalance = (byte) (oldBalChild + 1 + max0(parentBalance));
0739: parentNode.setOHByte(balance, parentBalance);
0740: childNode.setOHByte(balance, childBalance);
0741: commitNode(parentNode);
0742: commitNode(childNode);
0743: }
0744:
0745: // Associates the specified value with the specified key in this map
0746: public byte[] put(byte[] key, byte[] value) throws IOException {
0747: kelondroRow.Entry row = row().newEntry(
0748: new byte[][] { key, value });
0749: kelondroRow.Entry ret = put(row);
0750: if (ret == null)
0751: return null;
0752: else
0753: return ret.getColBytes(0);
0754: }
0755:
0756: // Removes the mapping for this key from this map if present (optional operation).
0757: public kelondroRow.Entry remove(byte[] key, boolean keepOrder)
0758: throws IOException {
0759: // keepOrder cannot have any effect: the order inside the database file cannot be maintained, but iteration over objects will always maintain the object order
0760: // therefore keepOrder should be true, because the effect is always given, while the data structure does not maintain order
0761: // delete from database
0762: synchronized (writeSearchObj) {
0763: writeSearchObj.process(key);
0764: if (writeSearchObj.found()) {
0765: CacheNode result = writeSearchObj.getMatcher();
0766: kelondroRow.Entry values = row().newEntry(
0767: result.getValueRow());
0768: remove(result, writeSearchObj.getParent());
0769: return values;
0770: } else {
0771: return null;
0772: }
0773: }
0774: }
0775:
0776: public kelondroRow.Entry removeOne() throws IOException {
0777: // removes just any entry and removes that entry
0778: synchronized (writeSearchObj) {
0779: CacheNode theOne = lastNode();
0780: kelondroRow.Entry values = row().newEntry(
0781: theOne.getValueRow());
0782: remove(theOne, null);
0783: return values;
0784: }
0785: }
0786:
0787: public synchronized void removeAll() throws IOException {
0788: while (size() > 0)
0789: remove(lastNode(), null);
0790: }
0791:
0792: private void remove(CacheNode node, kelondroNode parentOfNode)
0793: throws IOException {
0794: // there are three cases when removing a node
0795: // - the node is a leaf - it can be removed easily
0796: // - the node has one child - the child replaces the node
0797: // - the node has two childs - it can be replaced either
0798: // by the greatest node of the left child or the smallest
0799: // node of the right child
0800:
0801: kelondroNode childnode;
0802: if ((node.getOHHandle(leftchild) == null)
0803: && (node.getOHHandle(rightchild) == null)) {
0804: // easy case: the node is a leaf
0805: if (parentOfNode == null) {
0806: // this is the root!
0807: setHandle(root, null);
0808: } else {
0809: kelondroHandle h = parentOfNode.getOHHandle(leftchild);
0810: if ((h != null) && (h.equals(node.handle())))
0811: parentOfNode.setOHHandle(leftchild, null);
0812: h = parentOfNode.getOHHandle(rightchild);
0813: if ((h != null) && (h.equals(node.handle())))
0814: parentOfNode.setOHHandle(rightchild, null);
0815: commitNode(parentOfNode);
0816: }
0817: } else if ((node.getOHHandle(leftchild) != null)
0818: && (node.getOHHandle(rightchild) == null)) {
0819: replace(node, parentOfNode, new CacheNode(node
0820: .getOHHandle(leftchild), node, leftchild, false));
0821: } else if ((node.getOHHandle(leftchild) == null)
0822: && (node.getOHHandle(rightchild) != null)) {
0823: replace(node, parentOfNode, new CacheNode(node
0824: .getOHHandle(rightchild), node, rightchild, false));
0825: } else {
0826: // difficult case: node has two children
0827: CacheNode repl = lastNode(new CacheNode(node
0828: .getOHHandle(leftchild), node, leftchild, false));
0829: //System.out.println("last node is " + repl.toString());
0830: // we remove that replacement node and put it where the node was
0831: // this seems to be recursive, but is not since the replacement
0832: // node cannot have two children (it would not have been the smallest or greatest)
0833: kelondroNode n;
0834: kelondroHandle h;
0835: // remove leaf
0836: if ((repl.getOHHandle(leftchild) == null)
0837: && (repl.getOHHandle(rightchild) == null)) {
0838: // the replacement cannot be the root, so simply remove from parent node
0839: n = new CacheNode(repl.getOHHandle(parent), null, 0,
0840: false); // parent node of replacement node
0841: h = n.getOHHandle(leftchild);
0842: if ((h != null) && (h.equals(repl.handle())))
0843: n.setOHHandle(leftchild, null);
0844: h = n.getOHHandle(rightchild);
0845: if ((h != null) && (h.equals(repl.handle())))
0846: n.setOHHandle(rightchild, null);
0847: commitNode(n);
0848: } else if ((repl.getOHHandle(leftchild) != null)
0849: && (repl.getOHHandle(rightchild) == null)) {
0850: try {
0851: childnode = new CacheNode(repl
0852: .getOHHandle(leftchild), repl, leftchild,
0853: false);
0854: replace(repl, new CacheNode(repl
0855: .getOHHandle(parent), null, 0, false),
0856: childnode);
0857: } catch (IllegalArgumentException e) {
0858: // now treat the situation as if that link had been null before
0859: n = new CacheNode(repl.getOHHandle(parent), null,
0860: 0, false); // parent node of replacement node
0861: h = n.getOHHandle(leftchild);
0862: if ((h != null) && (h.equals(repl.handle())))
0863: n.setOHHandle(leftchild, null);
0864: h = n.getOHHandle(rightchild);
0865: if ((h != null) && (h.equals(repl.handle())))
0866: n.setOHHandle(rightchild, null);
0867: commitNode(n);
0868: }
0869: } else if ((repl.getOHHandle(leftchild) == null)
0870: && (repl.getOHHandle(rightchild) != null)) {
0871: try {
0872: childnode = new CacheNode(repl
0873: .getOHHandle(rightchild), repl, rightchild,
0874: false);
0875: replace(repl, new CacheNode(repl
0876: .getOHHandle(parent), null, 0, false),
0877: childnode);
0878: } catch (IllegalArgumentException e) {
0879: // now treat the situation as if that link had been null before
0880: n = new CacheNode(repl.getOHHandle(parent), null,
0881: 0, false); // parent node of replacement node
0882: h = n.getOHHandle(leftchild);
0883: if ((h != null) && (h.equals(repl.handle())))
0884: n.setOHHandle(leftchild, null);
0885: h = n.getOHHandle(rightchild);
0886: if ((h != null) && (h.equals(repl.handle())))
0887: n.setOHHandle(rightchild, null);
0888: commitNode(n);
0889: }
0890: }
0891: //System.out.println("node before reload is " + node.toString());
0892: node = new CacheNode(node.handle(), null, 0, false); // reload the node, it is possible that it has been changed
0893: //System.out.println("node after reload is " + node.toString());
0894:
0895: // now plant in the replha node
0896: byte b = node.getOHByte(balance); // save balance of disappearing node
0897: kelondroHandle parentHandle = node.getOHHandle(parent);
0898: kelondroHandle leftchildHandle = node
0899: .getOHHandle(leftchild);
0900: kelondroHandle rightchildHandle = node
0901: .getOHHandle(rightchild);
0902: replace(node, parentOfNode, repl);
0903: repl.setOHByte(balance, b); // restore balance
0904: repl.setOHHandle(parent, parentHandle); // restore handles
0905: repl.setOHHandle(leftchild, leftchildHandle);
0906: repl.setOHHandle(rightchild, rightchildHandle);
0907: commitNode(repl);
0908: // last thing to do: change uplinks of children to this new node
0909: if (leftchildHandle != null) {
0910: n = new CacheNode(leftchildHandle, node, leftchild,
0911: false);
0912: n.setOHHandle(parent, repl.handle());
0913: commitNode(n);
0914: }
0915: if (rightchildHandle != null) {
0916: n = new CacheNode(rightchildHandle, node, rightchild,
0917: false);
0918: n.setOHHandle(parent, repl.handle());
0919: commitNode(n);
0920: }
0921: }
0922: // move node to recycling queue
0923: synchronized (this ) {
0924: deleteNode(node.handle());
0925: }
0926: }
0927:
0928: protected CacheNode firstNode() throws IOException {
0929: kelondroHandle h = getHandle(root);
0930: if (h == null)
0931: return null;
0932: return firstNode(new CacheNode(h, null, 0, true));
0933: }
0934:
0935: protected CacheNode firstNode(CacheNode node) throws IOException {
0936: if (node == null)
0937: throw new IllegalArgumentException("firstNode: node=null");
0938: kelondroHandle h = node.getOHHandle(leftchild);
0939: HashSet<String> visitedNodeKeys = new HashSet<String>(); // to detect loops
0940: String nodeKey;
0941: while (h != null) {
0942: try {
0943: node = new CacheNode(h, node, leftchild, true);
0944: nodeKey = new String(node.getKey());
0945: if (visitedNodeKeys.contains(nodeKey))
0946: throw new kelondroException(this .filename,
0947: "firstNode: database contains loops: '"
0948: + nodeKey + "' appears twice.");
0949: visitedNodeKeys.add(nodeKey);
0950: } catch (IllegalArgumentException e) {
0951: // return what we have
0952: return node;
0953: }
0954: h = node.getOHHandle(leftchild);
0955: }
0956: return node;
0957: }
0958:
0959: protected CacheNode lastNode() throws IOException {
0960: kelondroHandle h = getHandle(root);
0961: if (h == null)
0962: return null;
0963: return lastNode(new CacheNode(h, null, 0, true));
0964: }
0965:
0966: protected CacheNode lastNode(CacheNode node) throws IOException {
0967: if (node == null)
0968: throw new IllegalArgumentException("lastNode: node=null");
0969: kelondroHandle h = node.getOHHandle(rightchild);
0970: HashSet<String> visitedNodeKeys = new HashSet<String>(); // to detect loops
0971: String nodeKey;
0972: while (h != null) {
0973: try {
0974: node = new CacheNode(h, node, rightchild, true);
0975: nodeKey = new String(node.getKey());
0976: if (visitedNodeKeys.contains(nodeKey))
0977: throw new kelondroException(this .filename,
0978: "lastNode: database contains loops: '"
0979: + nodeKey + "' appears twice.");
0980: visitedNodeKeys.add(nodeKey);
0981: } catch (IllegalArgumentException e) {
0982: // return what we have
0983: return node;
0984: }
0985: h = node.getOHHandle(rightchild);
0986: }
0987: return node;
0988: }
0989:
0990: private class nodeIterator implements Iterator<CacheNode> {
0991: // we implement an iteration! (not a recursive function as the structure would suggest...)
0992: // the iterator iterates Node objects
0993: CacheNode nextNode = null;
0994: boolean up, rot;
0995: LinkedList<Object[]> nodeStack;
0996: int count;
0997:
0998: public nodeIterator(boolean up, boolean rotating)
0999: throws IOException {
1000: this .count = 0;
1001: this .up = up;
1002: this .rot = rotating;
1003:
1004: // initialize iterator
1005: init((up) ? firstNode() : lastNode());
1006: }
1007:
1008: public nodeIterator(boolean up, boolean rotating,
1009: byte[] firstKey, boolean including) throws IOException {
1010: this .count = 0;
1011: this .up = up;
1012: this .rot = rotating;
1013:
1014: Search search = new Search();
1015: search.process(firstKey);
1016: if (search.found()) {
1017: init(search.getMatcher());
1018: } else {
1019: CacheNode nn = search.getParent();
1020: if (nn == null) {
1021: this .nextNode = null;
1022: } else {
1023: // the node nn may be greater or smaller than the firstKey
1024: // depending on the ordering direction,
1025: // we must find the next smaller or greater node
1026: // this is corrected in the initializer of nodeIterator
1027: init(nn);
1028: }
1029: }
1030:
1031: // correct nextNode upon start
1032: // this happens, if the start node was not proper, or could not be found
1033: while ((nextNode != null) && (nextNode.getKey() != null)) {
1034: int c = row().objectOrder.compare(firstKey, nextNode
1035: .getKey());
1036: if (c == 0) {
1037: if (including) {
1038: break; // correct + finished
1039: } else {
1040: if (hasNext())
1041: next();
1042: else
1043: nextNode = null;
1044: break; // corrected + finished
1045: }
1046: } else if (c < 0) {
1047: if (up) {
1048: break; // correct + finished
1049: } else {
1050: // firstKey < nextNode.getKey(): correct once
1051: if (hasNext())
1052: next();
1053: else
1054: nextNode = null;
1055: }
1056: } else if (c > 0) {
1057: if (up) {
1058: // firstKey > nextNode.getKey(): correct once
1059: if (hasNext())
1060: next();
1061: else
1062: nextNode = null;
1063: } else {
1064: break; // correct + finished
1065: }
1066: }
1067: }
1068: }
1069:
1070: private void init(CacheNode start) throws IOException {
1071: this .nextNode = start;
1072:
1073: // fill node stack for start node
1074: nodeStack = new LinkedList<Object[]>();
1075:
1076: kelondroHandle searchHandle = getHandle(root);
1077: if (searchHandle == null) {
1078: nextNode = null;
1079: return;
1080: }
1081:
1082: CacheNode searchNode = new CacheNode(searchHandle, null, 0,
1083: false);
1084: byte[] startKey = start.getKey();
1085: int c, ct;
1086: while ((c = row().objectOrder.compare(startKey, searchNode
1087: .getKey())) != 0) {
1088: // the current 'thisNode' is not the start node, put it on the stack
1089: ct = (c < 0) ? leftchild : rightchild;
1090: nodeStack.addLast(new Object[] { searchNode,
1091: new Integer(ct) });
1092:
1093: // go to next node
1094: searchHandle = searchNode.getOHHandle(ct);
1095: if (searchHandle == null)
1096: throw new kelondroException(filename,
1097: "nodeIterator.init: start node does not exist (handle null)");
1098: searchNode = new CacheNode(searchHandle, searchNode,
1099: ct, false);
1100: if (searchNode == null)
1101: throw new kelondroException(filename,
1102: "nodeIterator.init: start node does not exist (node null)");
1103: }
1104: // now every parent node to the start node is on the stack
1105: }
1106:
1107: public void finalize() {
1108: nextNode = null;
1109: nodeStack = null;
1110: }
1111:
1112: public boolean hasNext() {
1113: return (rot && (size() > 0)) || (nextNode != null);
1114: }
1115:
1116: public CacheNode next() {
1117: count++;
1118: if ((rot) && (nextNode == null))
1119: try {
1120: init((up) ? firstNode() : lastNode());
1121: } catch (IOException e) {
1122: throw new kelondroException(filename,
1123: "io-error while rot");
1124: }
1125: if (nextNode == null)
1126: throw new kelondroException(filename,
1127: "nodeIterator.next: no more entries available");
1128: if ((count > size()) && (!(rot)))
1129: throw new kelondroException(filename,
1130: "nodeIterator.next: internal loopback; database corrupted");
1131: CacheNode ret = nextNode;
1132:
1133: // middle-case
1134: try {
1135: int childtype = (up) ? rightchild : leftchild;
1136: kelondroHandle childHandle = nextNode
1137: .getOHHandle(childtype);
1138: if (childHandle != null) {
1139: //System.out.println("go to other leg, stack size=" + nodeStack.size());
1140: // we have walked one leg of the tree; now go to the other one: step down to next child
1141: HashSet<kelondroHandle> visitedNodeHandles = new HashSet<kelondroHandle>(); // to detect loops
1142: nodeStack.addLast(new Object[] { nextNode,
1143: new Integer(childtype) });
1144: nextNode = new CacheNode(childHandle, nextNode,
1145: childtype, false);
1146: childtype = (up) ? leftchild : rightchild;
1147: while ((childHandle = nextNode
1148: .getOHHandle(childtype)) != null) {
1149: if (visitedNodeHandles.contains(childHandle)) {
1150: // try to repair the nextNode
1151: nextNode.setOHHandle(childtype, null);
1152: nextNode.commit();
1153: logWarning("nodeIterator.next: internal loopback; fixed loop and try to go on");
1154: break;
1155: }
1156: visitedNodeHandles.add(childHandle);
1157: try {
1158: nodeStack.addLast(new Object[] { nextNode,
1159: new Integer(childtype) });
1160: nextNode = new CacheNode(childHandle,
1161: nextNode, childtype, false);
1162: } catch (IllegalArgumentException e) {
1163: // return what we have
1164: nodeStack.removeLast();
1165: return ret;
1166: }
1167: }
1168: // thats it: we are at a place where we can't go further
1169: // nextNode is correct
1170: } else {
1171: //System.out.println("go up");
1172: // we have walked along both legs of the child-trees.
1173:
1174: // Now step up.
1175: if (nodeStack.size() == 0) {
1176: nextNode = null;
1177: } else {
1178: Object[] stacktop;
1179: CacheNode parentNode = null;
1180: int parentpointer = (up) ? rightchild
1181: : leftchild;
1182: while ((nodeStack.size() != 0)
1183: && (parentpointer == ((up) ? rightchild
1184: : leftchild))) {
1185: //System.out.println("step up");
1186: // go on, walk up further
1187: stacktop = (Object[]) nodeStack
1188: .removeLast(); // top of stack: Node/parentpointer pair
1189: parentNode = (CacheNode) stacktop[0];
1190: parentpointer = ((Integer) stacktop[1])
1191: .intValue();
1192: }
1193: if ((nodeStack.size() == 0)
1194: && (parentpointer == ((up) ? rightchild
1195: : leftchild))) {
1196: nextNode = null;
1197: } else {
1198: nextNode = parentNode;
1199: }
1200: }
1201: }
1202: } catch (IOException e) {
1203: nextNode = null;
1204: }
1205:
1206: return ret;
1207: }
1208:
1209: public void remove() {
1210: throw new java.lang.UnsupportedOperationException(
1211: "kelondroTree: remove in kelondro node iterator not yet supported");
1212: }
1213: }
1214:
1215: public TreeMap<String, kelondroRow.Entry> rowMap(boolean up,
1216: byte[] firstKey, boolean including, int count)
1217: throws IOException {
1218: // returns an ordered map of keys/row relations; key objects are of type String, value objects are of type byte[][]
1219: kelondroByteOrder setOrder = (kelondroByteOrder) row().objectOrder
1220: .clone();
1221: setOrder.direction(up);
1222: setOrder.rotate(firstKey);
1223: TreeMap<String, kelondroRow.Entry> rows = new TreeMap<String, kelondroRow.Entry>(
1224: this .loopDetectionOrder);
1225: CacheNode n;
1226: String key;
1227: synchronized (this ) {
1228: Iterator<CacheNode> i = (firstKey == null) ? new nodeIterator(
1229: up, false)
1230: : new nodeIterator(up, false, firstKey, including);
1231: while ((rows.size() < count) && (i.hasNext())) {
1232: n = i.next();
1233: if (n == null)
1234: return rows;
1235: key = new String(n.getKey());
1236: if (rows.put(key, row().newEntry(n.getValueRow())) != null)
1237: return rows; // protection against loops
1238: }
1239: }
1240: return rows;
1241: }
1242:
1243: public TreeSet<String> keySet(boolean up, boolean rotating,
1244: byte[] firstKey, boolean including, int count)
1245: throws IOException {
1246: // returns an ordered set of keys; objects are of type String
1247: kelondroByteOrder setOrder = (kelondroByteOrder) row().objectOrder
1248: .clone();
1249: setOrder.direction(up);
1250: setOrder.rotate(firstKey);
1251: TreeSet<String> set = new TreeSet<String>(
1252: this .loopDetectionOrder);
1253: kelondroNode n;
1254: synchronized (this ) {
1255: Iterator<CacheNode> i = (firstKey == null) ? new nodeIterator(
1256: up, rotating)
1257: : new nodeIterator(up, rotating, firstKey,
1258: including);
1259: while ((set.size() < count) && (i.hasNext())) {
1260: n = (kelondroNode) i.next();
1261: if ((n != null) && (n.getKey() != null))
1262: set.add(new String(n.getKey()));
1263: }
1264: }
1265: return set;
1266: }
1267:
1268: public kelondroCloneableIterator<kelondroRow.Entry> rows(
1269: boolean up, byte[] firstKey) throws IOException {
1270: // iterates the rows of the Nodes
1271: // enumerated objects are of type byte[][]
1272: // iterates the elements in a sorted way.
1273: // if iteration should start at smallest element, set firstKey to null
1274: return new rowIterator(up, firstKey, this .size());
1275: }
1276:
1277: public class rowIterator implements
1278: kelondroCloneableIterator<kelondroRow.Entry> {
1279:
1280: int chunkSize;
1281: boolean inc;
1282: long count;
1283: byte[] lastKey;
1284: TreeMap<String, kelondroRow.Entry> rowBuffer;
1285: Iterator<Map.Entry<String, kelondroRow.Entry>> bufferIterator;
1286: long guessedCountLimit;
1287:
1288: public rowIterator(boolean up, byte[] firstKey,
1289: long guessedCountLimit) throws IOException {
1290: this .guessedCountLimit = guessedCountLimit;
1291: inc = up;
1292: count = 0;
1293: lastKey = null;
1294: //System.out.println("*** rowIterator: " + filename + ": readAheadChunkSize = " + readAheadChunkSize + ", lastIteratorCount = " + lastIteratorCount);
1295: readAheadChunkSize = Math
1296: .min(
1297: 1000,
1298: 3 + (int) ((3 * readAheadChunkSize + lastIteratorCount) / 4));
1299: chunkSize = (int) Math.min(readAheadChunkSize / 3,
1300: guessedCountLimit);
1301: rowBuffer = rowMap(inc, firstKey, true, chunkSize);
1302: bufferIterator = rowBuffer.entrySet().iterator();
1303: lastIteratorCount = 0;
1304: }
1305:
1306: public rowIterator clone(Object secondStart) {
1307: try {
1308: return new rowIterator(inc, (byte[]) secondStart,
1309: guessedCountLimit);
1310: } catch (IOException e) {
1311: return null;
1312: }
1313: }
1314:
1315: public boolean hasNext() {
1316: return ((bufferIterator != null)
1317: && (bufferIterator.hasNext()) && (count < size()));
1318: }
1319:
1320: public kelondroRow.Entry next() {
1321: if (!(bufferIterator.hasNext()))
1322: return null;
1323: Map.Entry<String, kelondroRow.Entry> entry = bufferIterator
1324: .next();
1325: lastKey = entry.getKey().getBytes();
1326:
1327: // check if this was the last entry in the rowBuffer
1328: if (!(bufferIterator.hasNext())) {
1329: // assign next buffer chunk
1330: try {
1331: lastKey[lastKey.length - 1]++; // ***BUG??? FIXME
1332: rowBuffer = rowMap(inc, lastKey, false, chunkSize);
1333: bufferIterator = rowBuffer.entrySet().iterator();
1334: } catch (IOException e) {
1335: rowBuffer = null;
1336: bufferIterator = null;
1337: }
1338: }
1339:
1340: // return the row
1341: count++;
1342: lastIteratorCount++;
1343: return entry.getValue();
1344: }
1345:
1346: public void remove() {
1347: if (lastKey != null)
1348: try {
1349: kelondroTree.this .remove(lastKey, true);
1350: } catch (IOException e) {
1351: // do nothing
1352: }
1353: }
1354:
1355: }
1356:
1357: public kelondroCloneableIterator<byte[]> keys(boolean up,
1358: byte[] firstKey) throws IOException {
1359: return new keyIterator(up, firstKey, this .size());
1360: }
1361:
1362: public class keyIterator implements
1363: kelondroCloneableIterator<byte[]> {
1364:
1365: int chunkSize;
1366: boolean inc;
1367: long count;
1368: byte[] lastKey;
1369: TreeSet<String> keyBuffer;
1370: Iterator<String> bufferIterator;
1371: long guessedCountLimit;
1372:
1373: public keyIterator(boolean up, byte[] firstKey,
1374: long guessedCountLimit) throws IOException {
1375: this .guessedCountLimit = guessedCountLimit;
1376: inc = up;
1377: count = 0;
1378: lastKey = null;
1379: //System.out.println("*** rowIterator: " + filename + ": readAheadChunkSize = " + readAheadChunkSize + ", lastIteratorCount = " + lastIteratorCount);
1380: readAheadChunkSize = Math
1381: .min(
1382: 1000,
1383: 3 + (int) ((3 * readAheadChunkSize + lastIteratorCount) / 4));
1384: chunkSize = (int) Math.min(readAheadChunkSize / 3,
1385: guessedCountLimit);
1386: keyBuffer = keySet(inc, false, firstKey, true, chunkSize);
1387: bufferIterator = keyBuffer.iterator();
1388: lastIteratorCount = 0;
1389: }
1390:
1391: public keyIterator clone(Object secondStart) {
1392: try {
1393: return new keyIterator(inc, (byte[]) secondStart,
1394: guessedCountLimit);
1395: } catch (IOException e) {
1396: return null;
1397: }
1398: }
1399:
1400: public boolean hasNext() {
1401: return ((bufferIterator != null)
1402: && (bufferIterator.hasNext()) && (count < size()));
1403: }
1404:
1405: public byte[] next() {
1406: if (!(bufferIterator.hasNext()))
1407: return null;
1408: lastKey = bufferIterator.next().getBytes();
1409:
1410: // check if this was the last entry in the rowBuffer
1411: if (!(bufferIterator.hasNext())) {
1412: // assign next buffer chunk
1413: try {
1414: lastKey[lastKey.length - 1]++; // ***BUG??? FIXME
1415: keyBuffer = keySet(inc, false, lastKey, false,
1416: chunkSize);
1417: bufferIterator = keyBuffer.iterator();
1418: } catch (IOException e) {
1419: keyBuffer = null;
1420: bufferIterator = null;
1421: }
1422: }
1423:
1424: // return the row
1425: count++;
1426: lastIteratorCount++;
1427: return lastKey;
1428: }
1429:
1430: public void remove() {
1431: if (lastKey != null)
1432: try {
1433: kelondroTree.this .remove(lastKey, true);
1434: } catch (IOException e) {
1435: // do nothing
1436: }
1437: }
1438:
1439: }
1440:
1441: public int imp(File file, String separator) throws IOException {
1442: // imports a value-separated file, returns number of records that have been read
1443:
1444: RandomAccessFile f = new RandomAccessFile(file, "r");
1445: String s;
1446: StringTokenizer st;
1447: int recs = 0;
1448: kelondroRow.Entry buffer = row().newEntry();
1449: int c;
1450: int line = 0;
1451: while ((s = f.readLine()) != null) {
1452: s = s.trim();
1453: line++;
1454: if ((s.length() > 0) && (!(s.startsWith("#")))) {
1455: st = new StringTokenizer(s, separator);
1456: // buffer the entry
1457: c = 0;
1458: while ((c < row().columns()) && (st.hasMoreTokens())) {
1459: buffer
1460: .setCol(c++, st.nextToken().trim()
1461: .getBytes());
1462: }
1463: if ((st.hasMoreTokens()) || (c != row().columns())) {
1464: System.err
1465: .println("inapropriate number of entries in line "
1466: + line);
1467: } else {
1468: put(buffer);
1469: recs++;
1470: }
1471:
1472: }
1473: }
1474: return recs;
1475: }
1476:
1477: public synchronized int height() {
1478: try {
1479: kelondroHandle h = getHandle(root);
1480: if (h == null)
1481: return 0;
1482: return height(new CacheNode(h, null, 0, false));
1483: } catch (IOException e) {
1484: return 0;
1485: }
1486: }
1487:
1488: private int height(CacheNode node) throws IOException {
1489: if (node == null)
1490: return 0;
1491: kelondroHandle h = node.getOHHandle(leftchild);
1492: int hl = (h == null) ? 0 : height(new CacheNode(h, node,
1493: leftchild, false));
1494: h = node.getOHHandle(rightchild);
1495: int hr = (h == null) ? 0 : height(new CacheNode(h, node,
1496: rightchild, false));
1497: if (hl > hr)
1498: return hl + 1;
1499: return hr + 1;
1500: }
1501:
1502: public void print() throws IOException {
1503: super .print();
1504: int height = height();
1505: System.out.println("HEIGHT = " + height);
1506: Vector<kelondroHandle> this line = new Vector<kelondroHandle>();
1507: this line.add(getHandle(root));
1508: Vector<kelondroHandle> nextline;
1509: kelondroHandle handle;
1510: kelondroNode node;
1511: int linelength, width = (1 << (height - 1))
1512: * (row().width(0) + 1);
1513: String key;
1514: for (int h = 1; h < height; h++) {
1515: linelength = width / (this line.size() * 2);
1516: nextline = new Vector<kelondroHandle>();
1517: for (int i = 0; i < this line.size(); i++) {
1518: handle = (kelondroHandle) this line.elementAt(i);
1519: if (handle == null) {
1520: node = null;
1521: key = "[..]";
1522: } else {
1523: node = new CacheNode(handle, null, 0, false);
1524: if (node == null)
1525: key = "NULL";
1526: else
1527: key = new String(node.getKey());
1528: }
1529: System.out.print(key);
1530: for (int j = 0; j < (linelength - key.length()); j++)
1531: System.out.print("-");
1532: System.out.print("+");
1533: for (int j = 0; j < (linelength - 1); j++)
1534: System.out.print(" ");
1535: if (node == null) {
1536: nextline.add(null);
1537: nextline.add(null);
1538: } else {
1539: nextline.add(node.getOHHandle(leftchild));
1540: nextline.add(node.getOHHandle(rightchild));
1541: }
1542: }
1543: System.out.println();
1544: for (int i = 0; i < this line.size(); i++) {
1545: System.out.print("|");
1546: for (int j = 0; j < (linelength - 1); j++)
1547: System.out.print(" ");
1548: System.out.print("|");
1549: for (int j = 0; j < (linelength - 1); j++)
1550: System.out.print(" ");
1551: }
1552: System.out.println();
1553: this line = nextline;
1554: nextline = null;
1555: }
1556: // now print last line
1557: if ((this line != null) && (width >= 0)) {
1558: linelength = width / this line.size();
1559: for (int i = 0; i < this line.size(); i++) {
1560: handle = (kelondroHandle) this line.elementAt(i);
1561: if (handle == null) {
1562: node = null;
1563: key = "NULL";
1564: } else {
1565: node = new CacheNode(handle, null, 0, false);
1566: if (node == null)
1567: key = "NULL";
1568: else
1569: key = new String(node.getKey());
1570: }
1571: System.out.print(key);
1572: for (int j = 0; j < (linelength - key.length()); j++)
1573: System.out.print(" ");
1574: }
1575: }
1576: System.out.println();
1577: }
1578:
1579: public static void cmd(String[] args) {
1580: System.out.print("kelondroTree ");
1581: for (int i = 0; i < args.length; i++)
1582: System.out.print(args[i] + " ");
1583: System.out.println("");
1584: byte[] ret = null;
1585: try {
1586: if ((args.length > 4) || (args.length < 1)) {
1587: System.err
1588: .println("usage: kelondroTree -c|-u|-v|-g|-d|-i|-s [file]|[key [value]] <db-file>");
1589: System.err
1590: .println("( create, update, view, get, delete, imp, shell)");
1591: System.exit(0);
1592: } else if (args.length == 1) {
1593: if (args[0].equals("-t")) {
1594: // test script
1595: File testFile = new File("test.db");
1596: while (testFile.exists())
1597: testFile.delete();
1598: kelondroTree fm = new kelondroTree(testFile, true,
1599: 10, new kelondroRow(
1600: "byte[] a-4, byte[] b-4",
1601: kelondroNaturalOrder.naturalOrder,
1602: 0));
1603: byte[] dummy = "".getBytes();
1604: fm.put("abc0".getBytes(), dummy);
1605: fm.put("bcd0".getBytes(), dummy);
1606: fm.put("def0".getBytes(), dummy);
1607: fm.put("bab0".getBytes(), dummy);
1608: fm.put("abc1".getBytes(), dummy);
1609: fm.put("bcd1".getBytes(), dummy);
1610: fm.put("def1".getBytes(), dummy);
1611: fm.put("bab1".getBytes(), dummy);
1612: fm.put("abc2".getBytes(), dummy);
1613: fm.put("bcd2".getBytes(), dummy);
1614: fm.put("def2".getBytes(), dummy);
1615: fm.put("bab2".getBytes(), dummy);
1616: fm.put("abc3".getBytes(), dummy);
1617: fm.put("bcd3".getBytes(), dummy);
1618: fm.put("def3".getBytes(), dummy);
1619: fm.put("bab3".getBytes(), dummy);
1620: fm.print();
1621: fm.remove("def1".getBytes(), true);
1622: fm.remove("bab1".getBytes(), true);
1623: fm.remove("abc2".getBytes(), true);
1624: fm.remove("bcd2".getBytes(), true);
1625: fm.remove("def2".getBytes(), true);
1626: fm.remove("bab2".getBytes(), true);
1627: fm.put("def1".getBytes(), dummy);
1628: fm.put("bab1".getBytes(), dummy);
1629: fm.put("abc2".getBytes(), dummy);
1630: fm.put("bcd2".getBytes(), dummy);
1631: fm.put("def2".getBytes(), dummy);
1632: fm.put("bab2".getBytes(), dummy);
1633: fm.print();
1634: fm.close();
1635: ret = null;
1636: }
1637: } else if (args.length == 2) {
1638: kelondroTree fm = new kelondroTree(new File(args[1]),
1639: true, 10, new kelondroRow(
1640: "byte[] a-4, byte[] b-4",
1641: kelondroNaturalOrder.naturalOrder, 0));
1642: if (args[0].equals("-v")) {
1643: fm.print();
1644: ret = null;
1645: }
1646: fm.close();
1647: } else if (args.length == 3) {
1648: if (args[0].equals("-d")) {
1649: kelondroTree fm = new kelondroTree(
1650: new File(args[1]), true, 10,
1651: new kelondroRow("byte[] a-4, byte[] b-4",
1652: kelondroNaturalOrder.naturalOrder,
1653: 0));
1654: fm.remove(args[2].getBytes(), true);
1655: fm.close();
1656: } else if (args[0].equals("-i")) {
1657: kelondroTree fm = new kelondroTree(
1658: new File(args[1]), true, 10,
1659: new kelondroRow("byte[] a-4, byte[] b-4",
1660: kelondroNaturalOrder.naturalOrder,
1661: 0));
1662: int i = fm.imp(new File(args[1]), ";");
1663: fm.close();
1664: ret = (i + " records imported").getBytes();
1665: } else if (args[0].equals("-s")) {
1666: String db = args[2];
1667: BufferedReader f = null;
1668: try {
1669: f = new BufferedReader(new FileReader(args[1]));
1670: String m;
1671: while (true) {
1672: m = f.readLine();
1673: if (m == null)
1674: break;
1675: if ((m.length() > 1)
1676: && (!m.startsWith("#"))) {
1677: m = m + " " + db;
1678: cmd(line2args(m));
1679: }
1680: }
1681: ret = null;
1682: } finally {
1683: if (f != null)
1684: try {
1685: f.close();
1686: } catch (Exception e) {
1687: }
1688: }
1689: } else if (args[0].equals("-g")) {
1690: kelondroTree fm = new kelondroTree(
1691: new File(args[1]), true, 10,
1692: new kelondroRow("byte[] a-4, byte[] b-4",
1693: kelondroNaturalOrder.naturalOrder,
1694: 0));
1695: kelondroRow.Entry ret2 = fm.get(args[2].getBytes());
1696: ret = ((ret2 == null) ? null : ret2.getColBytes(1));
1697: fm.close();
1698: } else if (args[0].equals("-n")) {
1699: kelondroTree fm = new kelondroTree(
1700: new File(args[1]), true, 10,
1701: new kelondroRow("byte[] a-4, byte[] b-4",
1702: kelondroNaturalOrder.naturalOrder,
1703: 0));
1704: //byte[][] keys = fm.getSequentialKeys(args[2].getBytes(), 500, true);
1705: Iterator<kelondroRow.Entry> rowIt = fm.rows(true,
1706: (args[2].length() == 0) ? null : args[2]
1707: .getBytes());
1708: Vector<String> v = new Vector<String>();
1709: while (rowIt.hasNext())
1710: v.add(rowIt.next().getColString(0, null));
1711: ret = v.toString().getBytes();
1712: fm.close();
1713: }
1714: } else if (args.length == 4) {
1715: if (args[0].equals("-c")) {
1716: // create <keylen> <valuelen> <filename>
1717: File f = new File(args[3]);
1718: if (f.exists())
1719: f.delete();
1720: kelondroRow lens = new kelondroRow("byte[] key-"
1721: + Integer.parseInt(args[1])
1722: + ", byte[] value-"
1723: + Integer.parseInt(args[2]),
1724: kelondroNaturalOrder.naturalOrder, 0);
1725: kelondroTree fm = new kelondroTree(f, true, 10,
1726: lens);
1727: fm.close();
1728: } else if (args[0].equals("-u")) {
1729: kelondroTree fm = new kelondroTree(
1730: new File(args[1]), true, 10,
1731: new kelondroRow("byte[] a-4, byte[] b-4",
1732: kelondroNaturalOrder.naturalOrder,
1733: 0));
1734: ret = fm
1735: .put(args[1].getBytes(), args[2].getBytes());
1736: fm.close();
1737: }
1738: }
1739: if (ret == null)
1740: System.out.println("NULL");
1741: else
1742: System.out.println(new String(ret));
1743: } catch (Exception e) {
1744: e.printStackTrace();
1745: }
1746: }
1747:
1748: public static void main(String[] args) {
1749: //cmd(args);
1750: //iterationtest();
1751: //bigtest(Integer.parseInt(args[0]));
1752: randomtest(Integer.parseInt(args[0]));
1753: //smalltest();
1754: }
1755:
1756: public static String[] permutations(int letters) {
1757: String p = "";
1758: for (int i = 0; i < letters; i++)
1759: p = p + ((char) (((int) 'A') + i));
1760: return permutations(p);
1761: }
1762:
1763: public static String[] permutations(String source) {
1764: if (source.length() == 0)
1765: return new String[0];
1766: if (source.length() == 1)
1767: return new String[] { source };
1768: char c = source.charAt(0);
1769: String[] recres = permutations(source.substring(1));
1770: String[] result = new String[source.length() * recres.length];
1771: for (int perm = 0; perm < recres.length; perm++) {
1772: result[perm * source.length()] = c + recres[perm];
1773: for (int pos = 1; pos < source.length() - 1; pos++) {
1774: result[perm * source.length() + pos] = recres[perm]
1775: .substring(0, pos)
1776: + c + recres[perm].substring(pos);
1777: }
1778: result[perm * source.length() + source.length() - 1] = recres[perm]
1779: + c;
1780: }
1781: return result;
1782: }
1783:
1784: public static byte[] testWord(char c) {
1785: return new byte[] { (byte) c, 32, 32, 32 };
1786: }
1787:
1788: public static void randomtest(int elements) {
1789: System.out.println("random " + elements + ":");
1790: String s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".substring(0, elements);
1791: String t, d;
1792: char c;
1793: kelondroTree tt = null;
1794: File testFile = new File("test.db");
1795: byte[] b;
1796: try {
1797: int steps = 0;
1798: while (true) {
1799: if (testFile.exists())
1800: testFile.delete();
1801: tt = new kelondroTree(testFile, true, 10,
1802: new kelondroRow("byte[] a-4, byte[] b-4",
1803: kelondroNaturalOrder.naturalOrder, 0));
1804: steps = 10
1805: + ((int) System.currentTimeMillis() % 7)
1806: * (((int) System.currentTimeMillis() + 17) % 11);
1807: t = s;
1808: d = "";
1809: System.out.println("NEW SESSION");
1810: for (int i = 0; i < steps; i++) {
1811: if ((d.length() < 3)
1812: || ((t.length() > 0) && (((int) System
1813: .currentTimeMillis() % 7) < 2))) {
1814: // add one
1815: c = t
1816: .charAt((int) (System
1817: .currentTimeMillis() % t
1818: .length()));
1819: b = testWord(c);
1820: tt.put(b, b);
1821: d = d + c;
1822: t = t.substring(0, t.indexOf(c))
1823: + t.substring(t.indexOf(c) + 1);
1824: System.out.println("added " + new String(b));
1825: } else {
1826: // delete one
1827: c = d
1828: .charAt((int) (System
1829: .currentTimeMillis() % d
1830: .length()));
1831: b = testWord(c);
1832: tt.remove(b, true);
1833: d = d.substring(0, d.indexOf(c))
1834: + d.substring(d.indexOf(c) + 1);
1835: t = t + c;
1836: System.out.println("removed " + new String(b));
1837: }
1838: //tt.printCache();
1839: //tt.print();
1840:
1841: if (countElements(tt) != tt.size()) {
1842: System.out
1843: .println("wrong size for this table:");
1844: tt.print();
1845: }
1846:
1847: // check all words within
1848: for (int j = 0; j < d.length(); j++) {
1849: if (tt.get(testWord(d.charAt(j))) == null) {
1850: System.out.println("missing entry "
1851: + d.charAt(j) + " in this table:");
1852: tt.print();
1853: }
1854: }
1855: // check all words outside
1856: for (int j = 0; j < t.length(); j++) {
1857: if (tt.get(testWord(t.charAt(j))) != null) {
1858: System.out.println("superfluous entry "
1859: + t.charAt(j) + " in this table:");
1860: tt.print();
1861: }
1862: }
1863: if (tt.get(testWord('z')) != null) {
1864: System.out
1865: .println("superfluous entry z in this table:");
1866: tt.print();
1867: }
1868:
1869: }
1870: //tt.print();
1871: tt.close();
1872: }
1873:
1874: } catch (Exception e) {
1875: e.printStackTrace();
1876: try {
1877: tt.print();
1878: } catch (IOException ee) {
1879: }
1880: System.out.println("TERMINATED");
1881: }
1882: }
1883:
1884: public static void smalltest() {
1885: File f = new File("test.db");
1886: if (f.exists())
1887: f.delete();
1888: try {
1889: kelondroTree tt = new kelondroTree(f, true, 10,
1890: new kelondroRow("byte[] a-4, byte[] b-4",
1891: kelondroNaturalOrder.naturalOrder, 0));
1892: byte[] b;
1893: b = testWord('B');
1894: tt.put(b, b); //tt.print();
1895: b = testWord('C');
1896: tt.put(b, b); //tt.print();
1897: b = testWord('D');
1898: tt.put(b, b); //tt.print();
1899: b = testWord('A');
1900: tt.put(b, b); //tt.print();
1901: b = testWord('D');
1902: tt.remove(b, true); //tt.print();
1903: b = testWord('B');
1904: tt.remove(b, true); //tt.print();
1905: b = testWord('B');
1906: tt.put(b, b); //tt.print();
1907: b = testWord('D');
1908: tt.put(b, b);
1909: b = testWord('E');
1910: tt.put(b, b);
1911: b = testWord('F');
1912: tt.put(b, b);
1913: b = testWord('G');
1914: tt.put(b, b);
1915: b = testWord('H');
1916: tt.put(b, b);
1917: b = testWord('I');
1918: tt.put(b, b);
1919: b = testWord('J');
1920: tt.put(b, b);
1921: b = testWord('K');
1922: tt.put(b, b);
1923: b = testWord('L');
1924: tt.put(b, b);
1925: int c = countElements(tt);
1926: System.out.println("elements: " + c);
1927: Iterator<kelondroRow.Entry> i = tt
1928: .rows(true, testWord('G'));
1929: for (int j = 0; j < c; j++) {
1930: System.out.println("Row "
1931: + j
1932: + ": "
1933: + new String(((kelondroRow.Entry) i.next())
1934: .getColBytes(0)));
1935: }
1936: System.out.println("TERMINATED");
1937: } catch (IOException e) {
1938: e.printStackTrace();
1939: }
1940: }
1941:
1942: /*
1943: public static void iterationtest() {
1944: File f = new File("test.db");
1945: if (f.exists()) f.delete();
1946: try {
1947: kelondroTree tt = new kelondroTree(f, 0, 0, 10, 4, 4, true);
1948: byte[] b;
1949: for (int i = 0; i < 100; i++) {
1950: b = ("T" + i).getBytes(); tt.put(b, b);
1951: }
1952: Iterator i = tt.keys(true, false, null);
1953: while (i.hasNext()) System.out.print((String) i.next() + ", ");
1954: System.out.println();
1955:
1956: i = tt.keys(true, false, "T80".getBytes());
1957: while (i.hasNext()) System.out.print((String) i.next() + ", ");
1958: System.out.println();
1959:
1960: i = tt.keys(true, true, "T80".getBytes());
1961: for (int j = 0; j < 40; j++) System.out.print((String) i.next() + ", ");
1962: System.out.println();
1963:
1964: i = tt.keys(false, true, "T20".getBytes());
1965: for (int j = 0; j < 40; j++) System.out.print((String) i.next() + ", ");
1966: System.out.println();
1967:
1968: tt.close();
1969: } catch (IOException e) {
1970: e.printStackTrace();
1971: }
1972: }
1973: */
1974:
1975: public static kelondroTree testTree(File f, String testentities)
1976: throws IOException {
1977: if (f.exists())
1978: f.delete();
1979: kelondroTree tt = new kelondroTree(f, false, 10,
1980: new kelondroRow("byte[] a-4, byte[] b-4",
1981: kelondroNaturalOrder.naturalOrder, 0));
1982: byte[] b;
1983: for (int i = 0; i < testentities.length(); i++) {
1984: b = testWord(testentities.charAt(i));
1985: tt.put(b, b);
1986: }
1987: return tt;
1988: }
1989:
1990: public static void bigtest(int elements) {
1991: System.out.println("starting big test with " + elements
1992: + " elements:");
1993: long start = System.currentTimeMillis();
1994: String[] s = permutations(elements);
1995: kelondroTree tt;
1996: File testFile = new File("test.db");
1997: try {
1998: for (int i = 0; i < s.length; i++) {
1999: System.out.println("*** probing tree " + i
2000: + " for permutation " + s[i]);
2001: // generate tree and delete elements
2002: tt = testTree(testFile, s[i]);
2003: //tt.print();
2004: if (countElements(tt) != tt.size()) {
2005: System.out.println("wrong size for " + s[i]);
2006: tt.print();
2007: }
2008: tt.close();
2009: for (int j = 0; j < s.length; j++) {
2010: tt = testTree(testFile, s[i]);
2011: //tt.print();
2012: // delete by permutation j
2013: for (int elt = 0; elt < s[j].length(); elt++) {
2014: tt.remove(testWord(s[j].charAt(elt)), true);
2015: //tt.print();
2016: if (countElements(tt) != tt.size()) {
2017: System.out
2018: .println("ERROR! wrong size for probe tree "
2019: + s[i]
2020: + "; probe delete "
2021: + s[j]
2022: + "; position "
2023: + elt);
2024: tt.print();
2025: }
2026: }
2027: // add another one
2028: //tt.print();
2029: /*
2030: b = testWord('0'); tt.put(b, b);
2031: b = testWord('z'); tt.put(b, b);
2032: b = testWord('G'); tt.put(b, b);
2033: b = testWord('t'); tt.put(b, b);
2034: if (countElements(tt) != tt.size()) {
2035: System.out.println("ERROR! wrong size for probe tree " + s[i] + "; probe delete " + s[j] + "; final add");
2036: tt.print();
2037: }
2038: tt.print();
2039: */
2040: // close this
2041: tt.close();
2042: }
2043: }
2044: System.out.println("FINISHED test after "
2045: + ((System.currentTimeMillis() - start) / 1000)
2046: + " seconds.");
2047: } catch (Exception e) {
2048: e.printStackTrace();
2049: System.out.println("TERMINATED");
2050: }
2051: }
2052:
2053: public static int countElements(kelondroIndex t) {
2054: int count = 0;
2055: try {
2056: Iterator<kelondroRow.Entry> iter = t.rows(true, null);
2057: kelondroRow.Entry row;
2058: while (iter.hasNext()) {
2059: count++;
2060: row = iter.next();
2061: if (row == null)
2062: System.out.println("ERROR! null element found");
2063: // else System.out.println("counted element: " + new
2064: // String(n.getKey()));
2065: }
2066: } catch (IOException e) {
2067: }
2068: return count;
2069: }
2070:
2071: }
|