001: /**
002: * com.mckoi.util.IntegerListBlockInterface 20 Sep 2001
003: *
004: * Mckoi SQL Database ( http://www.mckoi.com/database )
005: * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License
009: * Version 2 as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014: * GNU General Public License Version 2 for more details.
015: *
016: * You should have received a copy of the GNU General Public License
017: * Version 2 along with this program; if not, write to the Free Software
018: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
019: *
020: * Change Log:
021: *
022: *
023: */package com.mckoi.util;
024:
025: /**
026: * A block of an AbstractBlockIntegerList. This exposes the contents of a
027: * block of the list.
028: * <p>
029: * An IntegerListBlockInterface is a single element of a block of integers
030: * that make up some complete list of integers. A block integer list
031: * encapsulates a set of integers making up the block, and a chain to the
032: * next and previous block in the set.
033: *
034: * @author Tobias Downer
035: */
036:
037: public abstract class IntegerListBlockInterface {
038:
039: /**
040: * The next block in the chain.
041: */
042: public IntegerListBlockInterface next;
043:
044: /**
045: * The previous block in the chain.
046: */
047: public IntegerListBlockInterface previous;
048:
049: /**
050: * Set to true whenever the integers of this block are changed via the
051: * mutation methods.
052: */
053: boolean has_changed;
054:
055: /**
056: * Returns true if this store has been modified. The purpose of this
057: * method is to determine if any updates need to be made to any
058: * persistant representation of this store.
059: */
060: public final boolean hasChanged() {
061: return has_changed;
062: }
063:
064: /**
065: * Returns the number of entries in this block.
066: */
067: public abstract int size();
068:
069: /**
070: * Returns true if the block is full.
071: */
072: public abstract boolean isFull();
073:
074: /**
075: * Returns true if the block is empty.
076: */
077: public abstract boolean isEmpty();
078:
079: /**
080: * Returns true if the block has enough room to fill with the given number
081: * of integers.
082: */
083: public abstract boolean canContain(int number);
084:
085: /**
086: * The top int in the list.
087: */
088: public abstract int topInt();
089:
090: /**
091: * The bottom int in the list.
092: */
093: public abstract int bottomInt();
094:
095: /**
096: * Returns the int at the given position in the array.
097: */
098: public abstract int intAt(int pos);
099:
100: /**
101: * Adds an int to the block.
102: */
103: public abstract void addInt(int val);
104:
105: /**
106: * Removes an Int from the specified position in the block.
107: */
108: public abstract int removeIntAt(int pos);
109:
110: /**
111: * Inserts an int at the given position.
112: */
113: public abstract void insertIntAt(int val, int pos);
114:
115: /**
116: * Sets an int at the given position, overwriting anything that was
117: * previously there. It returns the value that was previously at the
118: * element.
119: */
120: public abstract int setIntAt(int val, int pos);
121:
122: /**
123: * Moves a set of values from the end of this block and inserts it into the
124: * given block at the destination index specified. Assumes the
125: * destination block has enough room to store the set. Assumes
126: * 'dest_block' is the same class as this.
127: */
128: public abstract void moveTo(IntegerListBlockInterface dest_block,
129: int dest_index, int length);
130:
131: /**
132: * Copies all the data from this block into the given destination block.
133: * Assumes 'dest_block' is the same class as this.
134: */
135: public abstract void copyTo(IntegerListBlockInterface dest_block);
136:
137: /**
138: * Copies all the data from this block into the given int[] array. Returns
139: * the number of 'int' values copied.
140: */
141: public abstract int copyTo(int[] to, int offset);
142:
143: /**
144: * Clears the object to be re-used.
145: */
146: public abstract void clear();
147:
148: /**
149: * Performs an iterative search through the int values in the list.
150: * If it's found the index of the value is returned, else it returns
151: * -1.
152: */
153: public abstract int iterativeSearch(int val);
154:
155: /**
156: * Performs an iterative search from the given position to the end of
157: * the list in the block.
158: * If it's found the index of the value is returned, else it returns
159: * -1.
160: */
161: public abstract int iterativeSearch(int val, int position);
162:
163: // ---------- Sort algorithms ----------
164:
165: /**
166: * Considers each int a reference to another structure, and the block
167: * sorted by these structures. The method performs a binary search.
168: */
169: public abstract int binarySearch(Object key, IndexComparator c);
170:
171: /**
172: * Considers each int a reference to another structure, and the block
173: * sorted by these structures. Finds the first index in the block that
174: * equals the given key.
175: */
176: public abstract int searchFirst(Object key, IndexComparator c);
177:
178: /**
179: * Considers each int a reference to another structure, and the block
180: * sorted by these structures. Finds the first index in the block that
181: * equals the given key.
182: */
183: public abstract int searchLast(Object key, IndexComparator c);
184:
185: /**
186: * Assuming a sorted block, finds the first index in the block that
187: * equals the given value.
188: */
189: public abstract int searchFirst(int val);
190:
191: /**
192: * Assuming a sorted block, finds the first index in the block that
193: * equals the given value.
194: */
195: public abstract int searchLast(int val);
196:
197: }
|