001: /*
002: This source file is part of Smyle, a database library.
003: For up-to-date information, see http://www.drjava.de/smyle
004: Copyright (C) 2001 Stefan Reich (doc@drjava.de)
005:
006: This library is free software; you can redistribute it and/or
007: modify it under the terms of the GNU Lesser General Public
008: License as published by the Free Software Foundation; either
009: version 2.1 of the License, or (at your option) any later version.
010:
011: This library 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 GNU
014: Lesser General Public License for more details.
015:
016: You should have received a copy of the GNU Lesser General Public
017: License along with this library; if not, write to the Free Software
018: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019:
020: For full license text, see doc/license/lgpl.txt in this distribution
021: */
022:
023: package drjava.smyle.core;
024:
025: import java.io.*;
026: import java.util.*;
027: import java.lang.Object;
028: import java.lang.ref.*;
029: import org.artsProject.mcop.*;
030: import org.artsProject.mcop.core.*;
031: import org.artsProject.util.*;
032: import drjava.smyle.*;
033: import drjava.smyle.meta.*;
034:
035: /** a TableIterator (enhanced iterator) that scans through an index.
036: performs filtering and local sorting (within an index leaf) */
037: class IndexScan<T extends Struct<T>> implements TableIterator<T> {
038: TableImpl<T> table;
039: Filter<T> filter;
040: Index<T> index;
041: boolean reversed;
042: KeySet<UniversalKey> keySet;
043: MapIterator<UniversalKey, ChunkRefs> it;
044: TableIterator<T> it2;
045: int expectedModCount, elementsReturned;
046: T t;
047: ChunkRef prevChunk, chunk;
048: UniversalKey currentKey;
049:
050: // for debugging
051: int itCount, it2Count;
052:
053: IndexScan(TableImpl<T> table, Filter<T> filter, Index<T> index) {
054: init(table, filter, index, null);
055: }
056:
057: IndexScan(TableImpl<T> table, Filter<T> filter, Index<T> index,
058: KeySet<UniversalKey> keySet) {
059: init(table, filter, index, keySet);
060: }
061:
062: private void init(TableImpl<T> table, Filter<T> filter,
063: Index<T> index, KeySet<UniversalKey> keySet) {
064: this .table = table;
065: this .filter = filter;
066: this .index = index;
067: this .keySet = keySet;
068: this .reversed = filter.isReversed();
069:
070: init();
071: }
072:
073: private void init() {
074: expectedModCount = table.modCount;
075:
076: if (keySet != null)
077: it = index.tree.iterate(null, null, keySet, reversed);
078: else
079: it = index.tree.iterate(reversed);
080: if (TableImpl.debug)
081: itCount = 0;
082:
083: findNext();
084: }
085:
086: private void checkForComodification() {
087: if (table.modCount != expectedModCount)
088: throw new ConcurrentModificationException();
089: }
090:
091: public boolean hasNext() {
092: checkForComodification();
093: return chunk != null;
094: }
095:
096: public T next() {
097: checkForComodification();
098: T result = t != null ? t : table.loadElement(chunk);
099: findNext();
100: return result;
101: }
102:
103: public ChunkRef nextChunk() {
104: checkForComodification();
105: findNext();
106: return prevChunk;
107: }
108:
109: public void remove() {
110: checkForComodification();
111: table.removeChunk(prevChunk.index);
112: int n = elementsReturned;
113: if (TableImpl.debug)
114: System.out.println("IndexScan.remove(), n=" + n);
115: restart();
116: while (--n > 1)
117: findNext();
118: }
119:
120: private void restart() {
121: elementsReturned = 0;
122: chunk = null;
123: it2 = null;
124: init();
125: }
126:
127: void findNext() {
128: ++elementsReturned;
129: if (TableImpl.debug && elementsReturned > 200000)
130: throw new InternalSmyleError(
131: "IndexScan.findNext: Too many elements!");
132:
133: prevChunk = chunk;
134: while (true) {
135: if (it2 == null) {
136: if (it == null || !it.hasNext()) {
137: chunk = null;
138: t = null;
139: return;
140: }
141:
142: if (TableImpl.debug && ++itCount > 20000)
143: throw new InternalSmyleError(
144: "IndexScan.findNext: Too many tree leafs");
145: ArrayList<ChunkRef> v = it.next().list;
146: currentKey = it.getKey();
147: if (reversed) {
148: v = new ArrayList<ChunkRef>(v);
149: Collections.reverse(v);
150: }
151:
152: final Iterator<ChunkRef> i = v.iterator();
153: it2 = new ChunklistScan<T>(table, i);
154: it2Count = 0;
155:
156: if (v.size() > 1 && !filter._getOrder().isEmpty())
157: it2 = new SortedIterator<T>(table, it2, filter);
158: }
159:
160: while (it2.hasNext()) {
161: if (TableImpl.debug && ++it2Count > 5000)
162: throw new InternalSmyleError(
163: "IndexScan.findNext: Too many elements returned by "
164: + it2);
165: chunk = it2.nextChunk();
166: if (filter != null) {
167: t = table.loadElement(chunk);
168: if (table.matches(filter, t))
169: return;
170: } else {
171: t = null;
172: return;
173: }
174: }
175:
176: it2 = null;
177: }
178: }
179:
180: /*static volatile int globalId;
181: TableIterator<T> sortByIndexField(int idx) {
182: int id = globalId++;
183: System.out.println("sortByIndexField "+id+": starting");
184: ArrayList<ChunkRef> l = new ArrayList<ChunkRef>();
185: final HashMap<ChunkRef,UniversalKey> keys = new HashMap<ChunkRef,UniversalKey>();
186: int dims = table.indexedFields.size();
187:
188: while (chunk != null) {
189: l.add(chunk);
190: if ((l.size() & 1023) == 1)
191: System.out.println("sortByIndexField "+id+": "+l.size()+" elements found, last is: "
192: +table.loadElementChunk(chunk.index));
193: keys.put(chunk, currentKey.extractDimension(idx, dims));
194: findNext();
195: }
196:
197: System.out.println("sortByIndexField "+id+": sorting "+l.size()+" elements");
198: Collections.sort(l, new Comparator<ChunkRef>() {
199: public int compare(ChunkRef a, ChunkRef b) {
200: //System.out.println(table.loadElement(a)+" <-> "+table.loadElement(b));
201: //System.out.println(keys.get(a)+" <-> "+keys.get(b));
202: return reversed
203: ? keys.get(b).compareTo(keys.get(a))
204: : keys.get(a).compareTo(keys.get(b));
205: }
206: });
207:
208: System.out.println("sortByIndexField "+id+": returning");
209: Iterator<ChunkRef> i = l.iterator();
210: ChunklistScan result = new ChunklistScan(table, l.iterator());
211: return result;
212: }*/
213: }
|