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.util.*;
026: import java.io.*;
027: import drjava.smyle.*;
028:
029: public abstract class BTree<A, B> {
030: public interface Node {
031: public boolean isLeaf();
032:
033: public int numChildren();
034:
035: public int numValues();
036:
037: public Node child(int index);
038:
039: public B value(int index);
040:
041: public A key(int index);
042: }
043:
044: public abstract Node root();
045:
046: public abstract void put(A a, B b);
047:
048: public abstract void remove(A a);
049:
050: public abstract B get(A a);
051:
052: public abstract int m();
053:
054: public abstract void clear();
055:
056: public MapIterator<A, B> iterate() {
057: return iterate(false);
058: }
059:
060: class PathEntry {
061: Node node;
062: boolean reverse;
063: int index, highest;
064:
065: PathEntry(Node node, boolean reverse) {
066: this .node = node;
067: this .reverse = reverse;
068: highest = node.isLeaf() ? node.numValues() : node
069: .numChildren();
070: if (reverse)
071: index = highest - 1;
072: }
073:
074: boolean exhausted() {
075: return index < 0 || index >= highest;
076: }
077:
078: int getIndexAndSkip() {
079: int result = index;
080: if (reverse)
081: --index;
082: else
083: ++index;
084: return result;
085: }
086: }
087:
088: public MapIterator<A, B> iterate(final boolean reverse) {
089: class I implements MapIterator<A, B> {
090: Stack<PathEntry> stack = new Stack<PathEntry>();
091: A key;
092:
093: I() {
094: stack.push(new PathEntry(root(), reverse));
095: findNext();
096: }
097:
098: private void checkForComodification() {
099: }
100:
101: public boolean hasNext() {
102: checkForComodification();
103: return !stack.isEmpty();
104: }
105:
106: public B next() {
107: checkForComodification();
108: PathEntry e = stack.peek();
109: int i = e.getIndexAndSkip();
110: B result = e.node.value(i);
111: key = e.node.key(i);
112: findNext();
113: return result;
114: }
115:
116: public void remove() {
117: throw new RuntimeException("TODO");
118: }
119:
120: void findNext() {
121: // Pop completed nodes
122: while (!stack.isEmpty() && stack.peek().exhausted()) {
123: stack.pop();
124: }
125:
126: // Descend to leaf
127: if (!stack.isEmpty()) {
128: while (!stack.peek().node.isLeaf()) {
129: stack.push(new PathEntry(stack.peek().node
130: .child(stack.peek().getIndexAndSkip()),
131: reverse));
132: }
133: }
134: }
135:
136: public A getKey() {
137: return key;
138: }
139: }
140: return new I();
141: }
142:
143: class MinMaxPathEntry extends PathEntry {
144: KeySet<A> set;
145: A min, max;
146:
147: MinMaxPathEntry(Node node, boolean reverse, KeySet<A> set,
148: A min, A max) {
149: super (node, reverse);
150: this .set = set;
151: this .min = min;
152: this .max = max;
153: }
154:
155: MinMaxPathEntry getEntryAndSkip() {
156: int i = getIndexAndSkip();
157: return new MinMaxPathEntry(node.child(i), reverse, set,
158: i == 0 ? min : node.key(i - 1),
159: i == highest - 1 ? max : node.key(i));
160: }
161:
162: boolean interesting() {
163: return set.overlapsWithRange(min, max);
164: }
165: }
166:
167: public MapIterator<A, B> iterate(final A min, final A max,
168: final KeySet<A> set, final boolean reverse) {
169: class I implements MapIterator<A, B> {
170: Stack<MinMaxPathEntry> stack = new Stack<MinMaxPathEntry>();
171: A key;
172:
173: I() {
174: stack.push(new MinMaxPathEntry(root(), reverse, set,
175: min, max));
176: findNext();
177: }
178:
179: private void checkForComodification() {
180: }
181:
182: public boolean hasNext() {
183: checkForComodification();
184: return !stack.isEmpty();
185: }
186:
187: public B next() {
188: checkForComodification();
189: PathEntry e = stack.peek();
190: int i = e.getIndexAndSkip();
191: B result = e.node.value(i);
192: key = e.node.key(i);
193: findNext();
194: return result;
195: }
196:
197: public void remove() {
198: throw new RuntimeException("TODO");
199: }
200:
201: void findNext() {
202: if (stack.isEmpty())
203: return;
204: while (true) {
205: while (!stack.peek().node.isLeaf()
206: || stack.peek().exhausted()) {
207: // Pop completed nodes
208: while (stack.peek().exhausted()) {
209: stack.pop();
210: if (stack.isEmpty())
211: return;
212: }
213:
214: // Descend one step if entry is interesting
215: MinMaxPathEntry entry = stack.peek()
216: .getEntryAndSkip();
217: if (entry.interesting())
218: stack.push(entry);
219: }
220:
221: if (!set.contains(stack.peek().node.key(stack
222: .peek().index)))
223: stack.peek().getIndexAndSkip();
224: else
225: break;
226: }
227: }
228:
229: public A getKey() {
230: return key;
231: }
232: }
233: return new I();
234: }
235: }
|