001: /*
002: * $Id: BaseArrayIndex.java,v 1.10 2005/12/20 18:32:30 ahimanikya Exp $
003: * =======================================================================
004: * Copyright (c) 2002-2005 Axion Development Team. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * 1. Redistributions of source code must retain the above
011: * copyright notice, this list of conditions and the following
012: * disclaimer.
013: *
014: * 2. Redistributions in binary form must reproduce the above copyright
015: * notice, this list of conditions and the following disclaimer in
016: * the documentation and/or other materials provided with the
017: * distribution.
018: *
019: * 3. The names "Tigris", "Axion", nor the names of its contributors may
020: * not be used to endorse or promote products derived from this
021: * software without specific prior written permission.
022: *
023: * 4. Products derived from this software may not be called "Axion", nor
024: * may "Tigris" or "Axion" appear in their names without specific prior
025: * written permission.
026: *
027: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
028: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
029: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
030: * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
031: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
032: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
033: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
034: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
035: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
036: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
037: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
038: * =======================================================================
039: */
040:
041: package org.axiondb.engine.indexes;
042:
043: import java.io.File;
044: import java.util.ArrayList;
045: import java.util.List;
046: import java.util.ListIterator;
047:
048: import org.apache.commons.collections.primitives.ArrayIntList;
049: import org.apache.commons.collections.primitives.IntList;
050: import org.apache.commons.collections.primitives.IntListIterator;
051: import org.axiondb.AxionException;
052: import org.axiondb.Column;
053: import org.axiondb.Function;
054: import org.axiondb.Index;
055: import org.axiondb.IndexLoader;
056: import org.axiondb.Row;
057: import org.axiondb.RowIterator;
058: import org.axiondb.RowSource;
059: import org.axiondb.Table;
060: import org.axiondb.engine.rowiterators.EmptyRowIterator;
061: import org.axiondb.engine.rowiterators.LazyRowRowIterator;
062: import org.axiondb.event.RowEvent;
063: import org.axiondb.functions.EqualFunction;
064: import org.axiondb.functions.GreaterThanFunction;
065: import org.axiondb.functions.GreaterThanOrEqualFunction;
066: import org.axiondb.functions.LessThanFunction;
067: import org.axiondb.functions.LessThanOrEqualFunction;
068:
069: /**
070: * Abstract base implemenation for {@link Index indices}that maintain an in-memory,
071: * sorted array of key values (and their associated row identifiers). This type of index
072: * is fast to read, relatively slow to write and somewhat memory expensive when very
073: * large.
074: *
075: * @version $Revision: 1.10 $ $Date: 2005/12/20 18:32:30 $
076: * @author Rodney Waldhoff
077: * @author Chuck Burdick
078: * @author Ritesh Adval
079: */
080: public abstract class BaseArrayIndex extends BaseIndex implements Index {
081:
082: public BaseArrayIndex(String name, Column column, boolean unique) {
083: super (name, column, unique);
084: }
085:
086: public BaseArrayIndex(String name, Column column, boolean unique,
087: IntList values) {
088: super (name, column, unique);
089: _rowIds = values;
090: }
091:
092: public void changeRowId(Table table, Row row, int oldId, int newId)
093: throws AxionException {
094: int colnum = table.getColumnIndex(getIndexedColumn().getName());
095: Object key = row.get(colnum);
096: if (null == key) {
097: // null values aren't indexed
098: } else {
099: int index = find(key, true);
100: for (int i = index, I = _rowIds.size(); i < I; i++) {
101: if (oldId == _rowIds.get(i)) {
102: _rowIds.set(i, newId);
103: break;
104: }
105: }
106: }
107: }
108:
109: public abstract IndexLoader getIndexLoader();
110:
111: public RowIterator getInorderRowIterator(RowSource source)
112: throws AxionException {
113: int minindex = 0;
114: int maxindex = _rowIds.size();
115:
116: return new LazyRowRowIterator(source, _rowIds.subList(minindex,
117: maxindex).listIterator(), source
118: .getColumnIndex(getIndexedColumn().getName()),
119: getKeyList(minindex, maxindex).listIterator(), maxindex);
120: }
121:
122: public abstract List getKeyList();
123:
124: public RowIterator getRowIterator(RowSource source, Function fn,
125: Object value) throws AxionException {
126: Object convertedValue = getIndexedColumn().getDataType()
127: .convert(value);
128:
129: if (null == convertedValue) {
130: // null fails all comparisions I support
131: return EmptyRowIterator.INSTANCE;
132: }
133:
134: int minindex = 0;
135: int maxindex = _rowIds.size();
136:
137: if (fn instanceof EqualFunction) {
138: minindex = find(convertedValue, true);
139: if (minindex >= 0) {
140: if (!isUnique()) {
141: maxindex = find(getIndexedColumn().getDataType()
142: .successor(convertedValue), false);
143: } else {
144: maxindex = minindex + 1;
145: }
146: } else {
147: maxindex = -1;
148: }
149: } else if (fn instanceof GreaterThanFunction) {
150: minindex = find(getIndexedColumn().getDataType().successor(
151: convertedValue), false);
152: } else if (fn instanceof GreaterThanOrEqualFunction) {
153: minindex = find(convertedValue, false);
154: } else if (fn instanceof LessThanFunction) {
155: maxindex = find(convertedValue, false);
156: } else if (fn instanceof LessThanOrEqualFunction) {
157: maxindex = find(getIndexedColumn().getDataType().successor(
158: convertedValue), false);
159: } else {
160: throw new AxionException("Unsupported function" + fn);
161: }
162:
163: if (minindex < 0 || minindex >= _rowIds.size() || maxindex <= 0
164: || minindex == maxindex) {
165: return EmptyRowIterator.INSTANCE;
166: }
167:
168: //FIXME: There should be a better way to fix concurent modification issue
169: IntListIterator resultIds = _rowIds.subList(minindex, maxindex)
170: .listIterator();
171: ArrayIntList ids = new ArrayIntList();
172: while (resultIds.hasNext()) {
173: ids.add(resultIds.next());
174: }
175: ListIterator keyResult = getKeyList(minindex, maxindex)
176: .listIterator();
177: ArrayList keys = new ArrayList();
178: while (keyResult.hasNext()) {
179: keys.add(keyResult.next());
180: }
181:
182: return new LazyRowRowIterator(source, ids.listIterator(),
183: source.getColumnIndex(getIndexedColumn().getName()),
184: keys.listIterator(), ids.size());
185: }
186:
187: public String getType() {
188: return Index.ARRAY;
189: }
190:
191: public void rowDeleted(RowEvent event) throws AxionException {
192: int colnum = event.getTable().getColumnIndex(
193: getIndexedColumn().getName());
194: Object key = event.getOldRow().get(colnum);
195: if (null == key) {
196: // null values aren't indexed
197: } else {
198: if (isUnique()) {
199: // if we're unique, just remove the entry at key
200: int index = removeKey(key);
201: if (-1 != index) {
202: _rowIds.removeElementAt(index);
203: }
204: } else {
205: // if we're not unique, scroll thru to find the right row to remove
206: int index = find(key, true);
207: if (-1 != index) {
208: while (_rowIds.get(index) != event.getOldRow()
209: .getIdentifier()) {
210: index++;
211: }
212: _rowIds.removeElementAt(index);
213: removeKeyAt(index);
214: }
215: }
216: }
217: }
218:
219: public void rowInserted(RowEvent event) throws AxionException {
220: int colnum = event.getTable().getColumnIndex(
221: getIndexedColumn().getName());
222: Object key = event.getNewRow().get(colnum);
223: if (null == key) {
224: // null values aren't indexed
225: } else {
226: int index = insertKey(key);
227: _rowIds.add(index, event.getNewRow().getIdentifier());
228: }
229: }
230:
231: public void rowUpdated(RowEvent event) throws AxionException {
232: int colnum = event.getTable().getColumnIndex(
233: getIndexedColumn().getName());
234: Object newkey = event.getNewRow().get(colnum);
235: Object oldkey = event.getOldRow().get(colnum);
236: if (null == newkey ? null == oldkey : newkey.equals(oldkey)) {
237: return;
238: }
239: rowDeleted(event);
240: rowInserted(event);
241: }
242:
243: public void save(File dataDirectory) throws AxionException {
244: getIndexLoader().saveIndex(this , dataDirectory);
245: }
246:
247: public void saveAfterTruncate(File dataDirectory)
248: throws AxionException {
249: getIndexLoader().saveIndexAfterTruncate(this , dataDirectory);
250: }
251:
252: public boolean supportsFunction(Function fn) {
253: if (fn instanceof EqualFunction) {
254: if (isUnique()) {
255: return true;
256: }
257: return getIndexedColumn().getDataType().supportsSuccessor();
258: } else if (fn instanceof GreaterThanFunction) {
259: return getIndexedColumn().getDataType().supportsSuccessor();
260: } else if (fn instanceof GreaterThanOrEqualFunction) {
261: return true;
262: } else if (fn instanceof LessThanFunction) {
263: return true;
264: } else if (fn instanceof LessThanOrEqualFunction) {
265: return getIndexedColumn().getDataType().supportsSuccessor();
266: } else {
267: return false;
268: }
269: }
270:
271: public void truncate() throws AxionException {
272: if (_rowIds != null) {
273: _rowIds.clear();
274: }
275: }
276:
277: protected abstract int find(Object value, boolean required);
278:
279: protected abstract List getKeyList(int minIndex, int maxIndex);
280:
281: protected IntList getValueList() {
282: return _rowIds;
283: }
284:
285: protected abstract int insertKey(Object value)
286: throws AxionException;
287:
288: protected abstract int removeKey(Object value)
289: throws AxionException;
290:
291: protected abstract void removeKeyAt(int index)
292: throws AxionException;
293:
294: private IntList _rowIds = new ArrayIntList();
295: }
|