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:
027: public class MemoryBTree<A, B> extends BTree<A, B> {
028: final int m;
029: NodeImpl root = new NodeImpl(true);
030: Comparator<A> comparator;
031:
032: static final boolean debug = false;
033:
034: class SplitResult {
035: A key;
036: NodeImpl newNode;
037:
038: SplitResult(A key, NodeImpl newNode) {
039: this .key = key;
040: this .newNode = newNode;
041: }
042: }
043:
044: public class NodeImpl implements BTree<A, B>.Node {
045: // leafs: n keys, n values
046: // non-leafs: n-1 keys, n children
047: ArrayList<A> keys;
048: ArrayList<NodeImpl> children;
049: ArrayList<B> values;
050:
051: public boolean isLeaf() {
052: return children == null;
053: }
054:
055: public int numChildren() {
056: return children.size();
057: }
058:
059: public int numValues() {
060: return values.size();
061: }
062:
063: public BTree<A, B>.Node child(int index) {
064: return children.get(index);
065: }
066:
067: public B value(int index) {
068: return values.get(index);
069: }
070:
071: public A key(int index) {
072: return keys.get(index);
073: }
074:
075: NodeImpl(boolean leaf) {
076: keys = new ArrayList<A>();
077: if (leaf)
078: values = new ArrayList<B>();
079: else
080: children = new ArrayList<NodeImpl>();
081: }
082:
083: /** returns true if an overflow occurred */
084: boolean add(A key, B value) {
085: if (isLeaf()) {
086: int i = find(key);
087: if (debug)
088: System.out.println("Leaf: inserting " + key
089: + " at " + i + " of " + keys.size());
090: if (i >= 0) {
091: // key exists, replace
092: keys.set(i, key);
093: values.set(i, value);
094: } else {
095: i = ~i;
096: // new key, insert
097: keys.add(i, key);
098: values.add(i, value);
099: }
100:
101: return numValues() > m;
102: } else {
103: int i = find(key);
104: if (i < 0)
105: i = ~i;
106: else
107: ++i;
108: NodeImpl child = children.get(i);
109: if (debug)
110: System.out.println("Delegating " + key
111: + " insertion to child " + i + " of "
112: + children.size());
113: if (child.add(key, value)) {
114: // handle overflow
115: SplitResult sr = child.split();
116: children.add(i + 1, sr.newNode);
117: keys.add(i, sr.key);
118: }
119:
120: return numChildren() > m;
121: }
122: }
123:
124: /** splits the node in half */
125: SplitResult split() {
126: if (isLeaf()) {
127: NodeImpl newNode = new NodeImpl(true);
128: int n = keys.size();
129: int i = n / 2;
130: if (debug)
131: System.out.println("Leaf splitting (m=" + m + ",n="
132: + n + ")");
133: List<A> subKeys = keys.subList(i, n);
134: List<B> subValues = values.subList(i, n);
135: newNode.keys.addAll(subKeys);
136: newNode.values.addAll(subValues);
137: subKeys.clear();
138: subValues.clear();
139: if (debug)
140: System.out.println("L first: " + values.get(0)
141: + ", R first: " + newNode.values.get(0));
142: return new SplitResult(newNode.keys.get(0), newNode);
143: } else {
144: if (debug)
145: System.out.println("Node splitting");
146: NodeImpl newNode = new NodeImpl(false);
147: int n = children.size();
148: int i = n / 2;
149: A splitKey = keys.get(i - 1);
150: List<A> subKeys = keys.subList(i, n - 1);
151: List<NodeImpl> subChildren = children.subList(i, n);
152: newNode.keys.addAll(subKeys);
153: newNode.children.addAll(subChildren);
154: keys.subList(i - 1, n - 1).clear();
155: children.subList(i, n).clear();
156: return new SplitResult(splitKey, newNode);
157: }
158: }
159:
160: /** returns a non-negative index if key was found;
161: returns the one-complement of best-matching index otherwise */
162: int find(A key) {
163: int i = 0, c = -1;
164: while (i < keys.size()
165: && (c = comparator.compare(keys.get(i), key)) < 0)
166: ++i;
167: return c == 0 ? i : ~i;
168: }
169:
170: /** returns true if an underflow occurred
171: (also if node was already underfull on method entrance) */
172: boolean remove(A key) {
173: if (isLeaf()) {
174: int i = find(key);
175: if (i >= 0) {
176: if (debug)
177: System.out.println("Leaf: removing " + key
178: + " at " + i + " of " + keys.size());
179: keys.remove(i);
180: values.remove(i);
181: } else {
182: i = ~i;
183: if (debug)
184: System.out.println("Leaf: " + key
185: + " not found near " + i + " of "
186: + keys.size());
187: }
188:
189: return numValues() < (m + 1) / 2;
190: } else {
191: int i = find(key);
192: if (i >= 0)
193: ++i;
194: else
195: i = ~i;
196: NodeImpl child = children.get(i);
197: if (debug)
198: System.out.println("Delegating " + key
199: + " deletion to child " + i + " of "
200: + children.size());
201: if (child.remove(key)) {
202: // handle underflow
203: if (i != 0)
204: --i;
205: child = children.get(i);
206: child.mergeWith(children.get(i + 1), keys.get(i));
207: children.remove(i + 1);
208: keys.remove(i);
209: if (child.overfull()) {
210: SplitResult sr = child.split();
211: children.add(i + 1, sr.newNode);
212: keys.add(i, sr.key);
213: }
214: }
215:
216: return numChildren() < (m + 1) / 2;
217: }
218: }
219:
220: boolean overfull() {
221: return isLeaf() ? numValues() > m : numChildren() > m;
222: }
223:
224: void mergeWith(NodeImpl node, A middleKey) {
225: if (isLeaf()) {
226: keys.addAll(node.keys);
227: values.addAll(node.values);
228: } else {
229: keys.add(middleKey);
230: keys.addAll(node.keys);
231: children.addAll(node.children);
232: }
233: }
234: }
235:
236: /** @param m maximum number of children per node */
237: public MemoryBTree(int m, Comparator<A> comparator) {
238: this .m = m;
239: this .comparator = comparator;
240: }
241:
242: public BTree<A, B>.Node root() {
243: return root;
244: }
245:
246: public void put(A a, B b) {
247: if (root.add(a, b)) {
248: // handle overflow
249: SplitResult sr = root.split();
250: NodeImpl newRoot = new NodeImpl(false);
251: newRoot.children.add(root);
252: newRoot.children.add(sr.newNode);
253: newRoot.keys.add(sr.key);
254: root = newRoot;
255: }
256: }
257:
258: public void remove(A a) {
259: if (root.remove(a)) {
260: // only handle extreme underflow case: root only contains one child
261: if (!root.isLeaf() && root.numChildren() == 1)
262: root = root.children.get(0);
263: }
264: }
265:
266: public B get(A key) {
267: NodeImpl node = root;
268:
269: while (!node.isLeaf()) {
270: int i = node.find(key);
271: if (i >= 0)
272: ++i;
273: else
274: i = ~i;
275: node = node.children.get(i);
276: }
277:
278: int i = node.find(key);
279: if (i >= 0) {
280: return node.values.get(i);
281: } else {
282: return null;
283: }
284: }
285:
286: public int m() {
287: return m;
288: }
289:
290: public void clear() {
291: root = new NodeImpl(true);
292: }
293: }
|