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.tests;
024:
025: import java.util.*;
026: import java.io.*;
027: import junit.framework.*;
028: import drjava.smyle.core.*;
029: import drjava.smyle.testtypes.*;
030:
031: public abstract class BTreeTestBase extends TestCase {
032: public BTreeTestBase(String name) {
033: super (name);
034: }
035:
036: BTree<String, String> tree;
037: int m;
038: final int n = 75, smallN = 25;
039: TreeMap<String, String> map;
040: int counter;
041:
042: Comparator<String> comparator = new Comparator<String>() {
043: public int compare(String a, String b) {
044: return Integer.parseInt(a) - Integer.parseInt(b);
045: }
046: };
047:
048: protected abstract BTree<String, String> createTree()
049: throws Exception;
050:
051: protected void additionalChecks() throws Exception {
052: checkGet();
053: checkIterate();
054: }
055:
056: void checkGet() throws Exception {
057: for (int i = 0; i < n; i++) {
058: String key = String.valueOf(i);
059: assertEquals(map.get(key), tree.get(key));
060: }
061: assertNull(tree.get("-10"));
062: }
063:
064: void checkIterate() throws Exception {
065: // test iterate and build temp vector
066:
067: Iterator<String> i1 = map.values().iterator();
068: Iterator<String> i2 = tree.iterate();
069: ArrayList<String> v = new ArrayList<String>();
070: while (i1.hasNext()) {
071: assertTrue(i1.hasNext());
072: String s = i1.next();
073: assertEquals(s, i2.next());
074: v.add(s);
075: }
076: assertTrue(!i2.hasNext());
077:
078: // test iterate(true) using temp vector
079:
080: i2 = tree.iterate(true);
081: for (int i = v.size() - 1; i >= 0; i--) {
082: assertTrue(i2.hasNext());
083: assertEquals(v.get(i), i2.next());
084: }
085: assertTrue(!i2.hasNext());
086: }
087:
088: void checkIterateKeySet(final String s, String value)
089: throws Exception {
090: Iterator<String> i = tree.iterate(null, null,
091: new KeySet<String>() {
092: public boolean contains(String key) {
093: return key.equals(s);
094: }
095:
096: public boolean overlapsWithRange(String min,
097: String max) {
098: //System.out.println("overlapsWithRange "+min+" "+max);
099: return (min == null || comparator.compare(min,
100: s) <= 0)
101: && (max == null || comparator.compare(
102: s, max) < 0);
103: }
104: }, false);
105: assertTrue(i.hasNext());
106: assertEquals(value, i.next());
107: assertTrue(!i.hasNext());
108: }
109:
110: public void setUp() throws Exception {
111: m = 3;
112: tree = createTree();
113: assertEquals(m, tree.m());
114: map = new TreeMap<String, String>(comparator);
115: counter = 0;
116: }
117:
118: public void testEmptyTree() throws Exception {
119: assertTreeContents(map);
120: }
121:
122: void put(String key, String value) throws Exception {
123: tree.put(key, value);
124: map.put(key, value);
125: if ((counter++ & 1) == 0)
126: assertTreeContents(map);
127: }
128:
129: void remove(String key) throws Exception {
130: tree.remove(key);
131: map.remove(key);
132: assertTreeContents(map);
133: }
134:
135: public void testReverseInserts() throws Exception {
136: for (int i = smallN; i > 0; i--)
137: put(String.valueOf(i), "v" + i);
138: additionalChecks();
139: for (int i = smallN; i > 0; i--)
140: remove(String.valueOf(i));
141: }
142:
143: public void testLinearInserts() throws Exception {
144: for (int i = 0; i < smallN; i++)
145: put(String.valueOf(i), "v" + i);
146: additionalChecks();
147: for (int i = 0; i < smallN; i++)
148: remove(String.valueOf(i));
149: }
150:
151: public void testRandomInserts() throws Exception {
152: for (int i = 0; i < 128; i++) {
153: int j = i ^ 0x56;
154: put(String.valueOf(j), "v" + j);
155: }
156: additionalChecks();
157: for (int i = 0; i < 128; i++) {
158: int j = i ^ 0x2d;
159: remove(String.valueOf(j));
160: }
161: }
162:
163: public void testRandomInsertsM4() throws Exception {
164: m = 4;
165: tree = createTree();
166: testRandomInserts();
167: }
168:
169: public void testIterateKeySet() throws Exception {
170: for (int i = 0; i < n; i++)
171: put(String.valueOf(i), "v" + i);
172: checkIterateKeySet("10", "v10");
173: }
174:
175: static <A, B> void printTree(BTree<A, B> tree) throws Exception {
176: StringBuffer buf = new StringBuffer();
177: printSubTree(buf, (BTree.Node) tree.root());
178: System.out.println("Tree: " + buf);
179: }
180:
181: static <A, B> void printSubTree(StringBuffer buf,
182: BTree<A, B>.Node node) throws Exception {
183: buf.append('(');
184: if (node.isLeaf()) {
185: for (int i = 0; i < node.numValues(); i++) {
186: if (i > 0)
187: buf.append(',');
188: buf.append(node.key(i)).append("->").append(
189: node.value(i));
190: }
191: } else {
192: for (int i = 0; i < node.numChildren(); i++) {
193: if (i > 0)
194: buf.append(',').append(node.key(i - 1)).append(',');
195: printSubTree(buf, (BTree.Node) node.child(i));
196: }
197: }
198: buf.append(')');
199: }
200:
201: /** also asserts the tree is balanced */
202: void assertTreeContents(TreeMap<String, String> map)
203: throws Exception {
204: assertTreeContents(tree, map);
205: }
206:
207: public static <A, B> void assertTreeContents(BTree<A, B> tree,
208: TreeMap<A, B> map) throws Exception {
209: try {
210: Iterator<Map.Entry<A, B>> i = map.entrySet().iterator();
211: assertNodeContents(tree, (BTree.Node) tree.root(), i);
212: if (i.hasNext())
213: fail("missing element at end: " + i.next());
214: } catch (AssertionFailedError e) {
215: printTree(tree);
216: throw e;
217: }
218: }
219:
220: static <A,B> void assertNodeContents(BTree<A,B> tree, BTree<A,B>.Node node, Iterator<Map.Entry<A,B>> iterator) throws Exception {
221: int m = tree.m();
222: if (node.isLeaf()) {
223: int n = node.numValues();
224: if (node != tree.root()) {
225: assert("Too few values: "+n+" (m="+m+")", n >= (m+1)/2);
226: }
227: assert("Too many values: "+n+" (m="+m+")", n <= m);
228: for (int i = 0; i < node.numValues(); i++) {
229: if (!iterator.hasNext())
230: fail("Superfluous element: "+node.value(i)+" at "+i);
231: assertEquals(iterator.next().getValue(), node.value(i));
232: }
233: } else {
234: int n = node.numChildren();
235: if (node == tree.root()) {
236: assert("Too few root children: "+n, n >= 2);
237: } else {
238: assert("Too few children: "+n+" (m="+m+")", n >= (m+1)/2);
239: }
240: assert("Too many children: "+n+" (m="+m+")", n <= m);
241: for (int i = 0; i < n; i++)
242: assertNodeContents(tree, node.child(i), iterator);
243: }
244: }
245:
246: public static <A, B> Map<A, B> treeToMap(BTree<A, B> tree) {
247: TreeMap<A, B> map = new TreeMap<A, B>();
248: nodeToMap(tree.root(), map);
249: return map;
250: }
251:
252: public static <A, B> Map<A, B> treeToMap(BTree<A, B> tree,
253: Comparator<A> comparator) {
254: TreeMap<A, B> map = new TreeMap<A, B>(comparator);
255: nodeToMap(tree.root(), map);
256: return map;
257: }
258:
259: static <A, B> void nodeToMap(BTree<A, B>.Node node, Map<A, B> map) {
260: if (node.isLeaf()) {
261: for (int i = 0; i < node.numValues(); i++)
262: map.put(node.key(i), node.value(i));
263: } else {
264: for (int i = 0; i < node.numChildren(); i++)
265: nodeToMap(node.child(i), map);
266: }
267: }
268:
269: public void testReplaceValue() throws Exception {
270: put("1", "1");
271: put("1", "2");
272: }
273:
274: public void testClear() throws Exception {
275: put("1", "5");
276: tree.clear();
277: map.clear();
278: assertTreeContents(map);
279: }
280:
281: public void testDelegationBug() throws Exception {
282: for (int i = 0; i < 4; i++)
283: put(String.valueOf(i), String.valueOf(i));
284: put("2", "3");
285: }
286: }
|