0001: /**
0002: * com.mckoi.util.AbstractBlockIntegerList 20 Sep 2001
0003: *
0004: * Mckoi SQL Database ( http://www.mckoi.com/database )
0005: * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
0006: *
0007: * This program is free software; you can redistribute it and/or
0008: * modify it under the terms of the GNU General Public License
0009: * Version 2 as published by the Free Software Foundation.
0010: *
0011: * This program is distributed in the hope that it will be useful,
0012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0014: * GNU General Public License Version 2 for more details.
0015: *
0016: * You should have received a copy of the GNU General Public License
0017: * Version 2 along with this program; if not, write to the Free Software
0018: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
0019: *
0020: * Change Log:
0021: *
0022: *
0023: */package com.mckoi.util;
0024:
0025: import java.util.ArrayList;
0026:
0027: /**
0028: * An implementation of a list of integer values that are stored across
0029: * an array of blocks. This allows for quicker insertion and deletion of
0030: * integer values, including other memory saving benefits.
0031: * <p>
0032: * The class works as follows;<p>
0033: * <ol>
0034: * <li>The list can contain any number of 'int' values.
0035: * <li>Each value is stored within a block of int's. A block is of finite
0036: * size.
0037: * <li>When a block becomes full, int values are moved around until enough
0038: * space is free. This may be by inserting a new block or by shifting
0039: * information from one block to another.
0040: * <li>When a block becomes empty, it is removed.
0041: * </ol>
0042: * The benefits of this system are that inserts and deletes are fast even
0043: * for very large lists. There are no megabyte sized arraycopys. Also,
0044: * the object could be extended to a version that pages un-used blocks to disk
0045: * thus saving precious system memory.
0046: * <p>
0047: * NOTE: The following methods are <b>NOT</b> optimal:
0048: * get(pos), add(val, pos), remove(pos)
0049: * <p>
0050: * Specifically, they slow as 'pos' nears the end of large lists.
0051: * <p>
0052: * This type of structure is very fast for large sorted lists where values can
0053: * be inserted at any position within the list. Care needs to be taken for
0054: * lists where values are inserted and removed constantly, because
0055: * fragmentation of the list blocks can occur. For example, adding 60,000
0056: * random entries followed by removing 50,000 random entries will result in
0057: * many only partially filled blocks. Since each block takes a constant
0058: * amount of memory, this may not be acceptable.
0059: *
0060: * @author Tobias Downer
0061: */
0062:
0063: public abstract class AbstractBlockIntegerList implements
0064: IntegerListInterface {
0065:
0066: // /**
0067: // * The size of each integer block. (multiply by 4 to get rough size how
0068: // * much each block takes up in memory).
0069: // */
0070: // private static final int BLOCK_SIZE = 512; // (2k memory per block)
0071:
0072: /**
0073: * The list of blocks (objects in this list are of type
0074: * 'IntegerListBlockInterface'.
0075: */
0076: protected ArrayList block_list = new ArrayList(10);
0077:
0078: /**
0079: * The total number of ints in the list.
0080: */
0081: private int count;
0082:
0083: // /**
0084: // * The size of the blocks.
0085: // */
0086: // protected int block_size;
0087:
0088: /**
0089: * If this is set to true, then the list is immutable (we are not permitted
0090: * to insert or remove integers from the list).
0091: */
0092: private boolean immutable;
0093:
0094: /**
0095: * Constructs the list.
0096: */
0097: public AbstractBlockIntegerList() {
0098: immutable = false;
0099: count = 0;
0100: // block_size = BLOCK_SIZE;
0101:
0102: // insertListBlock(0, newListBlock());
0103:
0104: }
0105:
0106: /**
0107: * Constructs the list from the given set of initial blocks.
0108: */
0109: public AbstractBlockIntegerList(IntegerListBlockInterface[] blocks) {
0110: this ();
0111: for (int i = 0; i < blocks.length; ++i) {
0112: block_list.add(blocks[i]);
0113: count += blocks[i].size();
0114: }
0115: }
0116:
0117: /**
0118: * Constructs the list by copying the contents from an IntegerVector.
0119: */
0120: public AbstractBlockIntegerList(IntegerVector ivec) {
0121: this ();
0122:
0123: int sz = ivec.size();
0124: for (int i = 0; i < sz; ++i) {
0125: add(ivec.intAt(i));
0126: }
0127: }
0128:
0129: /**
0130: * Copies the information from the given BlockIntegerList into a new
0131: * object and performs a deep clone of the information in this container.
0132: */
0133: public AbstractBlockIntegerList(IntegerListInterface i_list) {
0134: this ();
0135:
0136: if (i_list instanceof AbstractBlockIntegerList) {
0137: // Optimization for when the input list is a BlockIntegerList
0138: AbstractBlockIntegerList in_list = (AbstractBlockIntegerList) i_list;
0139:
0140: // block_size = in_list.block_size;
0141:
0142: ArrayList in_blocks = in_list.block_list;
0143: int in_blocks_count = in_blocks.size();
0144: // For each block in 'in_list'
0145: for (int i = 0; i < in_blocks_count; ++i) {
0146: // get the block.
0147: IntegerListBlockInterface block = (IntegerListBlockInterface) in_blocks
0148: .get(i);
0149: // Insert a new block in this object.
0150: IntegerListBlockInterface dest_block = insertListBlock(
0151: i, newListBlock());
0152: // Copy the contents of the source block to the new destination block.
0153: block.copyTo(dest_block);
0154: }
0155:
0156: // Set the size of the list
0157: count = i_list.size(); //count;
0158:
0159: } else {
0160: // The case when IntegerListInterface type is not known
0161: IntegerIterator i = i_list.iterator();
0162: while (i.hasNext()) {
0163: add(i.next());
0164: }
0165: }
0166:
0167: // If the given list is immutable then set this list to immutable
0168: if (i_list.isImmutable()) {
0169: setImmutable();
0170: }
0171:
0172: }
0173:
0174: // ---------- Block operations ----------
0175:
0176: /**
0177: * Creates a new ListBlock for the given implementation.
0178: */
0179: protected abstract IntegerListBlockInterface newListBlock();
0180:
0181: /**
0182: * Called when the class decides this ListBlock is no longer needed.
0183: * Provided as an event for derived classes to intercept.
0184: */
0185: protected void deleteListBlock(IntegerListBlockInterface list_block) {
0186: }
0187:
0188: /**
0189: * Copies the data from each block into the given int[] array. The int[]
0190: * array must be big enough to fit all the data in this list.
0191: */
0192: final void copyToArray(int[] array, int offset, int length) {
0193: if (array.length >= length && (offset + length) <= size()) {
0194: for (int i = 0; i < block_list.size(); ++i) {
0195: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0196: .get(i);
0197: offset += block.copyTo(array, offset);
0198: }
0199: return;
0200: }
0201: throw new Error("Size mismatch.");
0202: }
0203:
0204: /**
0205: * Inserts a ListBlock at the given block in the list of ListBlock's.
0206: */
0207: private final IntegerListBlockInterface insertListBlock(int index,
0208: IntegerListBlockInterface list_block) {
0209: block_list.add(index, list_block);
0210:
0211: // Point to next in the list.
0212: if (index + 1 < block_list.size()) {
0213: IntegerListBlockInterface next_b = (IntegerListBlockInterface) block_list
0214: .get(index + 1);
0215: list_block.next = next_b;
0216: next_b.previous = list_block;
0217: } else {
0218: list_block.next = null;
0219: }
0220:
0221: // Point to previous in the list.
0222: if (index > 0) {
0223: IntegerListBlockInterface previous_b = (IntegerListBlockInterface) block_list
0224: .get(index - 1);
0225: list_block.previous = previous_b;
0226: previous_b.next = list_block;
0227: } else {
0228: list_block.previous = null;
0229: }
0230:
0231: return list_block;
0232: }
0233:
0234: /**
0235: * Removes a IntegerListBlockInterface from the given index in the list of
0236: * IntegerListBlockInterface's.
0237: */
0238: private final void removeListBlock(int index) {
0239: // Alter linked list pointers.
0240: IntegerListBlockInterface new_prev = null;
0241: IntegerListBlockInterface new_next = null;
0242: if (index + 1 < block_list.size()) {
0243: new_next = (IntegerListBlockInterface) block_list
0244: .get(index + 1);
0245: }
0246: if (index > 0) {
0247: new_prev = (IntegerListBlockInterface) block_list
0248: .get(index - 1);
0249: }
0250:
0251: if (new_prev != null) {
0252: new_prev.next = new_next;
0253: }
0254: if (new_next != null) {
0255: new_next.previous = new_prev;
0256: }
0257:
0258: IntegerListBlockInterface been_removed = (IntegerListBlockInterface) block_list
0259: .remove(index);
0260: deleteListBlock(been_removed);
0261: }
0262:
0263: /**
0264: * Inserts a value in the given block position in the list.
0265: */
0266: private final void insertIntoBlock(int val, int block_index,
0267: IntegerListBlockInterface block, int position) {
0268: block.insertIntAt(val, position);
0269: ++count;
0270: // Is the block full?
0271: if (block.isFull()) {
0272: // We need to move half of the data out of this block into either the
0273: // next block or create a new block to store it.
0274:
0275: // The size that we going to zap out of this block.
0276: int move_size = (block.size() / 7) - 1;
0277:
0278: // The block to move half the data from this block.
0279: IntegerListBlockInterface move_to;
0280: // Is there a next block?
0281: if (block_index < block_list.size() - 1) {
0282: IntegerListBlockInterface next_b = (IntegerListBlockInterface) block_list
0283: .get(block_index + 1);
0284: // IntegerListBlockInterface next_b = block.next;
0285: // if (next_b != null) {
0286: // Yes, can this block contain half the values from this block?
0287: if (next_b.canContain(move_size)) {
0288: move_to = next_b;
0289: } else {
0290: // Can't contain so insert a new block.
0291: move_to = insertListBlock(block_index + 1,
0292: newListBlock());
0293: }
0294:
0295: } else {
0296: // No next block so create a new block
0297: move_to = insertListBlock(block_index + 1,
0298: newListBlock());
0299: }
0300:
0301: // 'move_to' should be set to the block we are to use to move half the
0302: // data from this block.
0303: block.moveTo(move_to, 0, move_size);
0304:
0305: }
0306: }
0307:
0308: /**
0309: * Removes the value from the given position in the specified block. It
0310: * returns the value that used to be at that position.
0311: */
0312: protected final int removeFromBlock(int block_index,
0313: IntegerListBlockInterface block, int position) {
0314: int old_value = block.removeIntAt(position);
0315: --count;
0316: // If we have emptied out this block, then we should remove it from the
0317: // list.
0318: if (block.isEmpty() && block_list.size() > 1) {
0319: removeListBlock(block_index);
0320: }
0321:
0322: return old_value;
0323: }
0324:
0325: /**
0326: * Uses a binary search algorithm to quickly determine the index of the
0327: * IntegerListBlockInterface within 'block_list' of the block that contains
0328: * the given key value using the IndexComparator as a lookup comparator.
0329: */
0330: private final int findBlockContaining(Object key, IndexComparator c) {
0331: if (count == 0) {
0332: return -1;
0333: }
0334:
0335: int low = 0;
0336: int high = block_list.size() - 1;
0337:
0338: while (low <= high) {
0339: int mid = (low + high) / 2;
0340: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0341: .get(mid);
0342:
0343: // Is what we are searching for lower than the bottom value?
0344: if (c.compare(block.bottomInt(), key) > 0) {
0345: high = mid - 1;
0346: }
0347: // No, then is it greater than the highest value?
0348: else if (c.compare(block.topInt(), key) < 0) {
0349: low = mid + 1;
0350: }
0351: // Must be inside this block then!
0352: else {
0353: return mid;
0354: }
0355: }
0356:
0357: // System.out.println("RETURNING: " + low);
0358:
0359: return -(low + 1); // key not found.
0360: }
0361:
0362: /**
0363: * Uses a binary search algorithm to quickly determine the index of the
0364: * IntegerListBlockInterface within 'block_list' of the block that contains
0365: * the given key value using the IndexComparator as a lookup comparator.
0366: */
0367: private final int findLastBlock(Object key, IndexComparator c) {
0368: if (count == 0) {
0369: return -1;
0370: }
0371:
0372: int low = 0;
0373: int high = block_list.size() - 1;
0374:
0375: while (low <= high) {
0376:
0377: if (high - low <= 2) {
0378: for (int i = high; i >= low; --i) {
0379: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0380: .get(i);
0381: if (c.compare(block.bottomInt(), key) <= 0) {
0382: if (c.compare(block.topInt(), key) >= 0) {
0383: return i;
0384: } else {
0385: return -(i + 1) - 1;
0386: }
0387: }
0388: }
0389: return -(low + 1);
0390: }
0391:
0392: int mid = (low + high) / 2;
0393: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0394: .get(mid);
0395:
0396: // Is what we are searching for lower than the bottom value?
0397: if (c.compare(block.bottomInt(), key) > 0) {
0398: high = mid - 1;
0399: }
0400: // No, then is it greater than the highest value?
0401: else if (c.compare(block.topInt(), key) < 0) {
0402: low = mid + 1;
0403: }
0404: // Equal, so highest must be someplace between mid and high.
0405: else {
0406: low = mid;
0407: if (low == high) {
0408: return low;
0409: }
0410: }
0411: }
0412:
0413: return -(low + 1); // key not found.
0414: }
0415:
0416: /**
0417: * Uses a binary search algorithm to quickly determine the index of the
0418: * IntegerListBlockInterface within 'block_list' of the block that contains
0419: * the given key value using the IndexComparator as a lookup comparator.
0420: */
0421: private final int findFirstBlock(Object key, IndexComparator c) {
0422: if (count == 0) {
0423: return -1;
0424: }
0425:
0426: int low = 0;
0427: int high = block_list.size() - 1;
0428:
0429: while (low <= high) {
0430:
0431: if (high - low <= 2) {
0432: for (int i = low; i <= high; ++i) {
0433: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0434: .get(i);
0435: if (c.compare(block.topInt(), key) >= 0) {
0436: if (c.compare(block.bottomInt(), key) <= 0) {
0437: return i;
0438: } else {
0439: return -(i + 1);
0440: }
0441: }
0442: }
0443: return -(high + 1) - 1;
0444: }
0445:
0446: int mid = (low + high) / 2;
0447: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0448: .get(mid);
0449:
0450: // Is what we are searching for lower than the bottom value?
0451: if (c.compare(block.bottomInt(), key) > 0) {
0452: high = mid - 1;
0453: }
0454: // No, then is it greater than the highest value?
0455: else if (c.compare(block.topInt(), key) < 0) {
0456: low = mid + 1;
0457: }
0458: // Equal, so highest must be someplace between mid and high.
0459: else {
0460: high = mid;
0461: }
0462: }
0463:
0464: return -(low + 1); // key not found.
0465: }
0466:
0467: /**
0468: * Uses a binary search algorithm to quickly determine the index of the
0469: * IntegerListBlockInterface within 'block_list' of the block that contains
0470: * the given value.
0471: */
0472: private final int findFirstBlock(int val) {
0473: if (count == 0) {
0474: return -1;
0475: }
0476:
0477: int low = 0;
0478: int high = block_list.size() - 1;
0479:
0480: while (low <= high) {
0481:
0482: if (high - low <= 2) {
0483: for (int i = low; i <= high; ++i) {
0484: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0485: .get(i);
0486: if (block.topInt() >= val) {
0487: if (block.bottomInt() <= val) {
0488: return i;
0489: } else {
0490: return -(i + 1);
0491: }
0492: }
0493: }
0494: return -(high + 1) - 1;
0495: }
0496:
0497: int mid = (low + high) / 2;
0498: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0499: .get(mid);
0500:
0501: // Is what we are searching for lower than the bottom value?
0502: if (block.bottomInt() > val) {
0503: high = mid - 1;
0504: }
0505: // No, then is it greater than the highest value?
0506: else if (block.topInt() < val) {
0507: low = mid + 1;
0508: }
0509: // Equal, so highest must be someplace between mid and high.
0510: else {
0511: high = mid;
0512: }
0513: }
0514:
0515: return -(low + 1); // key not found.
0516: }
0517:
0518: /**
0519: * Uses a binary search algorithm to quickly determine the index of the
0520: * IntegerListBlockInterface within 'block_list' of the block that contains
0521: * the given value.
0522: */
0523: private final int findLastBlock(int val) {
0524: if (count == 0) {
0525: return -1;
0526: }
0527:
0528: int low = 0;
0529: int high = block_list.size() - 1;
0530:
0531: while (low <= high) {
0532:
0533: if (high - low <= 2) {
0534: for (int i = high; i >= low; --i) {
0535: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0536: .get(i);
0537: if (block.bottomInt() <= val) {
0538: if (block.topInt() >= val) {
0539: return i;
0540: } else {
0541: return -(i + 1) - 1;
0542: }
0543: }
0544: }
0545: return -(low + 1);
0546: }
0547:
0548: int mid = (low + high) / 2;
0549: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0550: .get(mid);
0551:
0552: // Is what we are searching for lower than the bottom value?
0553: if (block.bottomInt() > val) {
0554: high = mid - 1;
0555: }
0556: // No, then is it greater than the highest value?
0557: else if (block.topInt() < val) {
0558: low = mid + 1;
0559: }
0560: // Equal, so highest must be someplace between mid and high.
0561: else {
0562: low = mid;
0563: if (low == high) {
0564: return low;
0565: }
0566: }
0567: }
0568:
0569: return -(low + 1); // key not found.
0570: }
0571:
0572: /**
0573: * Throws an error if the list is immutable. This is called before any
0574: * mutable operations on the list. If the list is mutable and empty then
0575: * an empty block is added to the list.
0576: */
0577: private void checkImmutable() {
0578: if (immutable) {
0579: throw new Error("List is immutable.");
0580: }
0581: // HACK: We have a side effect of checking whether the list is immutable.
0582: // If the block list doesn't contain any entries we add one here. This
0583: // hack reduces the memory requirements.
0584: else if (block_list.size() == 0) {
0585: insertListBlock(0, newListBlock());
0586: }
0587: }
0588:
0589: // ---------- Public methods ----------
0590:
0591: /**
0592: * Sets the list as immutable (we aren't allowed to change the contents).
0593: */
0594: public final void setImmutable() {
0595: immutable = true;
0596: }
0597:
0598: /**
0599: * Returns true if this interface is immutable.
0600: */
0601: public final boolean isImmutable() {
0602: return immutable;
0603: }
0604:
0605: // ---------- Standard get/set/remove operations ----------
0606: // NOTE: Some of these are not optimal.
0607:
0608: /**
0609: * The number of integers that are in the list.
0610: */
0611: public final int size() {
0612: return count;
0613: }
0614:
0615: /**
0616: * Returns the int at the given position in the list. NOTE: This is not
0617: * a very fast routine. Certainly a lot slower than IntegerVector intAt.
0618: */
0619: public final int get(int pos) {
0620: int size = block_list.size();
0621: int start = 0;
0622: for (int i = 0; i < size; ++i) {
0623: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0624: .get(i);
0625: int bsize = block.size();
0626: if (pos >= start && pos < start + bsize) {
0627: return block.intAt(pos - start);
0628: }
0629: start += bsize;
0630: }
0631: throw new Error("'pos' (" + pos + ") out of bounds.");
0632: }
0633:
0634: /**
0635: * Adds an int at the given position in the list.
0636: */
0637: public final void add(int val, int pos) {
0638: checkImmutable();
0639:
0640: int size = block_list.size();
0641: int start = 0;
0642: for (int i = 0; i < size; ++i) {
0643: Object ob = block_list.get(i);
0644: IntegerListBlockInterface block = (IntegerListBlockInterface) ob;
0645: int bsize = block.size();
0646: if (pos >= start && pos <= start + bsize) {
0647: insertIntoBlock(val, i, block, pos - start);
0648: return;
0649: }
0650: start += bsize;
0651: }
0652: throw new Error("'pos' (" + pos + ") out of bounds.");
0653: }
0654:
0655: /**
0656: * Adds an int to the end of the list.
0657: */
0658: public final void add(int val) {
0659: checkImmutable();
0660:
0661: int size = block_list.size();
0662: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0663: .get(size - 1);
0664: insertIntoBlock(val, size - 1, block, block.size());
0665: }
0666:
0667: /**
0668: * Removes an int from the given position in the list. Returns the value
0669: * that used to be at that position.
0670: */
0671: public final int remove(int pos) {
0672: checkImmutable();
0673:
0674: int size = block_list.size();
0675: int start = 0;
0676: for (int i = 0; i < size; ++i) {
0677: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0678: .get(i);
0679: int bsize = block.size();
0680: if (pos >= start && pos <= start + bsize) {
0681: return removeFromBlock(i, block, pos - start);
0682: }
0683: start += bsize;
0684: }
0685: throw new Error("'pos' (" + pos + ") out of bounds.");
0686: }
0687:
0688: // ---------- Fast methods ----------
0689:
0690: /**
0691: * Assuming the list is sorted, this performs a binary search and returns
0692: * true if the value is found, otherwise returns false.
0693: * <p>
0694: * We must supply a 'IndexComparator' for how the list is sorted.
0695: */
0696: public final boolean contains(int val) {
0697: int block_num = findLastBlock(val);
0698:
0699: if (block_num < 0) {
0700: // We didn't find in the list, so return false.
0701: return false;
0702: }
0703:
0704: // We got a block, so find out if it's in the block or not.
0705: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0706: .get(block_num);
0707:
0708: // Find, if not there then return false.
0709: int sr = block.searchLast(val);
0710: return sr >= 0;
0711:
0712: }
0713:
0714: /**
0715: * Inserts plain 'int' values into the list in sorted order.
0716: */
0717: public final void insertSort(int val) {
0718: checkImmutable();
0719:
0720: int block_num = findLastBlock(val);
0721:
0722: if (block_num < 0) {
0723: // Not found a block,
0724: // The block to insert the value,
0725: block_num = (-(block_num + 1)) - 1;
0726: if (block_num < 0) {
0727: block_num = 0;
0728: }
0729: }
0730:
0731: // We got a block, so find out if it's in the block or not.
0732: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0733: .get(block_num);
0734:
0735: // The point to insert in the block,
0736: int i = block.searchLast(val);
0737: if (i < 0) {
0738: i = -(i + 1);
0739: } else {
0740: i = i + 1;
0741: // NOTE: A block can never become totally full so it's always okay to
0742: // skip one ahead.
0743: }
0744:
0745: // Insert value into the block,
0746: insertIntoBlock(val, block_num, block, i);
0747:
0748: }
0749:
0750: /**
0751: * Inserts plain 'int' value into the sorted position in the list only if
0752: * it isn't already in the list. If the value is inserted it returns true,
0753: * otherwise if the value wasn't inserted because it's already in the list,
0754: * it returns false.
0755: */
0756: public final boolean uniqueInsertSort(int val) {
0757: checkImmutable();
0758:
0759: int block_num = findLastBlock(val);
0760:
0761: if (block_num < 0) {
0762: // Not found a block,
0763: // The block to insert the value,
0764: block_num = (-(block_num + 1)) - 1;
0765: if (block_num < 0) {
0766: block_num = 0;
0767: }
0768: }
0769:
0770: // We got a block, so find out if it's in the block or not.
0771: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0772: .get(block_num);
0773:
0774: // The point to insert in the block,
0775: int i = block.searchLast(val);
0776: if (i < 0) {
0777: i = -(i + 1);
0778: } else {
0779: // This means we found the value in the given block, so return false.
0780: return false;
0781: }
0782:
0783: // Insert value into the block,
0784: insertIntoBlock(val, block_num, block, i);
0785:
0786: // Value inserted so return true.
0787: return true;
0788:
0789: }
0790:
0791: /**
0792: * Removes a plain 'int' value from the sorted position in the list only if
0793: * it's already in the list. If the value is removed it returns true,
0794: * otherwise if the value wasn't removed because it couldn't be found in the
0795: * list, it returns false.
0796: */
0797: public final boolean removeSort(int val) {
0798: checkImmutable();
0799:
0800: int block_num = findLastBlock(val);
0801:
0802: if (block_num < 0) {
0803: // Not found a block,
0804: // The block to remove the value,
0805: block_num = (-(block_num + 1)) - 1;
0806: if (block_num < 0) {
0807: block_num = 0;
0808: }
0809: }
0810:
0811: // We got a block, so find out if it's in the block or not.
0812: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0813: .get(block_num);
0814:
0815: // The point to remove the block,
0816: int i = block.searchLast(val);
0817: if (i < 0) {
0818: // This means we can't found the value in the given block, so return
0819: // false.
0820: return false;
0821: }
0822:
0823: // Remove value into the block,
0824: int val_removed = removeFromBlock(block_num, block, i);
0825: if (val != val_removed) {
0826: throw new Error("Incorrect value removed.");
0827: }
0828:
0829: // Value removed so return true.
0830: return true;
0831:
0832: }
0833:
0834: /**
0835: * Assuming the list is sorted, this performs a binary search and returns
0836: * true if the value is found, otherwise returns false.
0837: * <p>
0838: * We must supply a 'IndexComparator' for how the list is sorted.
0839: */
0840: public final boolean contains(Object key, IndexComparator c) {
0841: int block_num = findBlockContaining(key, c);
0842:
0843: if (block_num < 0) {
0844: // We didn't find in the list, so return false.
0845: return false;
0846: }
0847:
0848: // We got a block, so find out if it's in the block or not.
0849: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0850: .get(block_num);
0851:
0852: // Find, if not there then return false.
0853: int sr = block.binarySearch(key, c);
0854: return sr >= 0;
0855:
0856: }
0857:
0858: /**
0859: * Inserts the key/index pair into the list at the correct sorted position
0860: * (determine by the IndexComparator). If the list already contains
0861: * identical key then the value is put on the end of the set. This way,
0862: * the sort is stable (the order of identical elements does not change).
0863: */
0864: public final void insertSort(Object key, int val, IndexComparator c) {
0865: checkImmutable();
0866:
0867: int block_num = findLastBlock(key, c);
0868:
0869: if (block_num < 0) {
0870: // Not found a block,
0871: // The block to insert the value,
0872: block_num = (-(block_num + 1)) - 1;
0873: if (block_num < 0) {
0874: block_num = 0;
0875: }
0876: }
0877:
0878: // We got a block, so find out if it's in the block or not.
0879: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0880: .get(block_num);
0881:
0882: // The point to insert in the block,
0883: int i = block.searchLast(key, c);
0884: if (i < 0) {
0885: i = -(i + 1);
0886: } else {
0887: i = i + 1;
0888: // NOTE: A block can never become totally full so it's always okay to
0889: // skip one ahead.
0890: }
0891:
0892: // Insert value into the block,
0893: insertIntoBlock(val, block_num, block, i);
0894:
0895: }
0896:
0897: /**
0898: * Removes the key/val pair from the list by first searching for it, and then
0899: * removing it from the list.
0900: * <p>
0901: * NOTE: There will be a list scan (bad performance) for the erronious case
0902: * when the key/val pair is not present in the list.
0903: */
0904: public final int removeSort(Object key, int val, IndexComparator c) {
0905: checkImmutable();
0906:
0907: // Find the range of blocks that the value is in.
0908: final int orig_block_num = findFirstBlock(key, c);
0909: int block_num = orig_block_num;
0910: int l_block_num = block_list.size() - 1;
0911: // int l_block_num = findLastBlock(key, c);
0912:
0913: if (block_num < 0) {
0914: // Not found in a block,
0915: throw new Error("Value (" + key
0916: + ") was not found in the list.");
0917: }
0918:
0919: // int i = -1;
0920: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0921: .get(block_num);
0922: // int search_from = block.searchFirst(key, c);
0923: int i = block.iterativeSearch(val);
0924: while (i == -1) {
0925: // If not found, go to next block
0926: ++block_num;
0927: if (block_num > l_block_num) {
0928: throw new Error("Value (" + key
0929: + ") was not found in the list.");
0930: }
0931: block = (IntegerListBlockInterface) block_list
0932: .get(block_num);
0933: // Try and find the value within this block
0934: i = block.iterativeSearch(val);
0935: }
0936:
0937: // int last_block_num = findLastBlock(key, c);
0938: // if (last_block_num > orig_block_num) {
0939: // double percent = (double) (block_num - orig_block_num) /
0940: // (double) (last_block_num - orig_block_num);
0941: // System.out.println("Block range: " + orig_block_num + " to " +
0942: // last_block_num + " p: " + percent);
0943: // }
0944:
0945: // Remove value from the block,
0946: return removeFromBlock(block_num, block, i);
0947:
0948: }
0949:
0950: /**
0951: * Returns the index of the last value in this set that equals the given
0952: * value.
0953: */
0954: public final int searchLast(Object key, IndexComparator c) {
0955: int block_num = findLastBlock(key, c);
0956: int sr;
0957:
0958: if (block_num < 0) {
0959: // Guarenteed not found in any blocks so return start of insert block
0960: block_num = (-(block_num + 1)); // - 1;
0961: sr = -1;
0962: }
0963:
0964: else {
0965: // We got a block, so find out if it's in the block or not.
0966: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0967: .get(block_num);
0968:
0969: // Try and find it in the block,
0970: sr = block.searchLast(key, c);
0971: }
0972:
0973: int offset = 0;
0974: for (int i = 0; i < block_num; ++i) {
0975: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
0976: .get(i);
0977: offset += block.size();
0978: }
0979:
0980: if (sr >= 0) {
0981: return offset + sr;
0982: } else {
0983: return -offset + sr;
0984: }
0985:
0986: }
0987:
0988: /**
0989: * Returns the index of the first value in this set that equals the given
0990: * value.
0991: */
0992: public final int searchFirst(Object key, IndexComparator c) {
0993: int block_num = findFirstBlock(key, c);
0994: int sr;
0995:
0996: if (block_num < 0) {
0997: // Guarenteed not found in any blocks so return start of insert block
0998: block_num = (-(block_num + 1)); // - 1;
0999: // System.out.println("BN (" + key + "): " + block_num);
1000: sr = -1;
1001: }
1002:
1003: else {
1004: // We got a block, so find out if it's in the block or not.
1005: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
1006: .get(block_num);
1007:
1008: // Try and find it in the block,
1009: sr = block.searchFirst(key, c);
1010: }
1011:
1012: int offset = 0;
1013: for (int i = 0; i < block_num; ++i) {
1014: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
1015: .get(i);
1016: offset += block.size();
1017: }
1018:
1019: if (sr >= 0) {
1020: return offset + sr;
1021: } else {
1022: return -offset + sr;
1023: }
1024:
1025: }
1026:
1027: // ---------- Iterator operations ----------
1028:
1029: /**
1030: * Our iterator that walks through the list.
1031: */
1032: private final class BILIterator implements IntegerIterator {
1033:
1034: private int start_offset;
1035: private int end_offset;
1036: private IntegerListBlockInterface current_block;
1037: private int current_block_size;
1038: private int block_index;
1039: private int block_offset;
1040: private int cur_offset;
1041:
1042: public BILIterator(int start_offset, int end_offset) {
1043: this .start_offset = start_offset;
1044: this .end_offset = end_offset;
1045: cur_offset = start_offset - 1;
1046:
1047: if (end_offset >= start_offset) {
1048: // Setup variables to 1 before the start
1049: setupVars(start_offset - 1);
1050: }
1051:
1052: }
1053:
1054: /**
1055: * Sets up the internal variables given an offset.
1056: */
1057: private void setupVars(int pos) {
1058: int size = block_list.size();
1059: int start = 0;
1060: for (block_index = 0; block_index < size; ++block_index) {
1061: IntegerListBlockInterface block = (IntegerListBlockInterface) block_list
1062: .get(block_index);
1063: int bsize = block.size();
1064: if (pos < start + bsize) {
1065: block_offset = pos - start;
1066: if (block_offset < 0) {
1067: block_offset = -1;
1068: }
1069: current_block = block;
1070: current_block_size = bsize;
1071: return;
1072: }
1073: start += bsize;
1074: }
1075: throw new Error("'pos' (" + pos + ") out of bounds.");
1076: }
1077:
1078: // ---------- Implemented from IntegerIterator ----------
1079:
1080: public boolean hasNext() {
1081: return cur_offset < end_offset;
1082: }
1083:
1084: public int next() {
1085: ++block_offset;
1086: ++cur_offset;
1087: if (block_offset >= current_block_size) {
1088: ++block_index;
1089: current_block = (IntegerListBlockInterface) block_list
1090: .get(block_index);
1091: // current_block = current_block.next;
1092: current_block_size = current_block.size();
1093: block_offset = 0;
1094: }
1095: return current_block.intAt(block_offset);
1096: }
1097:
1098: public boolean hasPrevious() {
1099: return cur_offset > start_offset;
1100: }
1101:
1102: private void walkBack() {
1103: --block_offset;
1104: --cur_offset;
1105: if (block_offset < 0) {
1106: if (block_index > 0) {
1107: // if (current_block.previous != null) {
1108: --block_index;
1109: current_block = (IntegerListBlockInterface) block_list
1110: .get(block_index);
1111: // current_block = current_block.previous;
1112: current_block_size = current_block.size();
1113: block_offset = current_block.size() - 1;
1114: }
1115: }
1116: }
1117:
1118: public int previous() {
1119: walkBack();
1120: return current_block.intAt(block_offset);
1121: }
1122:
1123: public void remove() {
1124: checkImmutable();
1125:
1126: // NOT ELEGANT: We check 'block_list' size to determine if the value
1127: // deletion caused blocks to be removed. If it did, we set up the
1128: // internal variables afresh with a call to 'setupVars'.
1129: int orig_block_count = block_list.size();
1130: removeFromBlock(block_index, current_block, block_offset);
1131:
1132: // Did the number of blocks in the list change?
1133: if (orig_block_count == block_list.size()) {
1134: // HACK: Reduce the current cached block size
1135: --current_block_size;
1136: walkBack();
1137: } else {
1138: --cur_offset;
1139: setupVars(cur_offset);
1140: }
1141: --end_offset;
1142: }
1143:
1144: }
1145:
1146: /**
1147: * Returns an IntegerIterator that will walk from the start offset
1148: * (inclusive) to the end offset (inclusive) of this list.
1149: * <p>
1150: * This iterator supports the 'remove' method.
1151: */
1152: public IntegerIterator iterator(int start_offset, int end_offset) {
1153: return new BILIterator(start_offset, end_offset);
1154: }
1155:
1156: /**
1157: * Returns an IntegerIterator that will walk from the start to the end
1158: * this list.
1159: * <p>
1160: * This iterator supports the 'remove' method.
1161: */
1162: public IntegerIterator iterator() {
1163: return iterator(0, size() - 1);
1164: }
1165:
1166: // ---------- Debugging ----------
1167:
1168: public String toString() {
1169: StringBuffer buf = new StringBuffer();
1170: buf.append("Blocks: " + block_list.size() + "\n");
1171: for (int i = 0; i < block_list.size(); ++i) {
1172: buf.append("Block (" + i + "): "
1173: + block_list.get(i).toString() + "\n");
1174: }
1175: return new String(buf);
1176: }
1177:
1178: public void checkSorted(IndexComparator c) {
1179: IntegerIterator iterator = iterator(0, size() - 1);
1180: checkSorted(iterator, c);
1181: }
1182:
1183: public static void checkSorted(IntegerIterator iterator,
1184: IndexComparator c) {
1185: if (iterator.hasNext()) {
1186: int last_index = iterator.next();
1187: while (iterator.hasNext()) {
1188: int cur = iterator.next();
1189: if (c.compare(cur, last_index) < 0) {
1190: throw new Error("List not sorted!");
1191: }
1192: last_index = cur;
1193: }
1194: }
1195: }
1196:
1197: }
|