001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package com.db4o.db4ounit.common.btree;
022:
023: import com.db4o.internal.btree.*;
024:
025: import db4ounit.*;
026:
027: public class SearcherLowestHighestTestCase implements TestCase,
028: TestLifeCycle {
029:
030: private Searcher _searcher;
031:
032: private static final int SEARCH_FOR = 9;
033:
034: private static final int[] EVEN_EVEN_VALUES = new int[] { 4, 9, 9,
035: 9, 9, 11, 13, 17 };
036:
037: private static final int[] EVEN_ODD_VALUES = new int[] { 4, 5, 9,
038: 9, 9, 11, 13, 17 };
039:
040: private static final int[] ODD_EVEN_VALUES = new int[] { 4, 9, 9,
041: 9, 9, 11, 13 };
042:
043: private static final int[] ODD_ODD_VALUES = new int[] { 4, 5, 9, 9,
044: 9, 11, 13 };
045:
046: private static final int[] NO_MATCH_EVEN = new int[] { 4, 5, 10,
047: 10, 10, 11 };
048:
049: private static final int[] NO_MATCH_ODD = new int[] { 4, 5, 10, 10,
050: 10, 11, 13 };
051:
052: private static final int[][] MATCH_VALUES = new int[][] {
053: EVEN_EVEN_VALUES, EVEN_ODD_VALUES, ODD_EVEN_VALUES,
054: ODD_ODD_VALUES };
055:
056: private static final int[][] NO_MATCH_VALUES = new int[][] {
057: NO_MATCH_EVEN, NO_MATCH_ODD };
058:
059: private static final SearchTarget[] ALL_TARGETS = new SearchTarget[] {
060: SearchTarget.LOWEST, SearchTarget.ANY, SearchTarget.HIGHEST };
061:
062: public void testMatch() {
063: for (int i = 0; i < MATCH_VALUES.length; i++) {
064: int[] values = MATCH_VALUES[i];
065:
066: int lo = lowMatch(values);
067: search(values, SearchTarget.LOWEST);
068: Assert.areEqual(lo, _searcher.cursor());
069: Assert.isTrue(_searcher.foundMatch());
070:
071: int hi = highMatch(values);
072: search(values, SearchTarget.HIGHEST);
073: Assert.areEqual(hi, _searcher.cursor());
074: Assert.isTrue(_searcher.foundMatch());
075: }
076: }
077:
078: public void testNoMatch() {
079: for (int i = 0; i < NO_MATCH_VALUES.length; i++) {
080: int[] values = NO_MATCH_VALUES[i];
081:
082: int lo = lowMatch(values);
083: search(values, SearchTarget.LOWEST);
084: Assert.areEqual(lo, _searcher.cursor());
085: Assert.isFalse(_searcher.foundMatch());
086:
087: int hi = highMatch(values);
088: search(values, SearchTarget.HIGHEST);
089: Assert.areEqual(hi, _searcher.cursor());
090: Assert.isFalse(_searcher.foundMatch());
091: }
092: }
093:
094: public void testEmpty() {
095: int[] values = new int[] {};
096: for (int i = 0; i < ALL_TARGETS.length; i++) {
097: search(values, ALL_TARGETS[i]);
098: Assert.areEqual(0, _searcher.cursor());
099: Assert.isFalse(_searcher.foundMatch());
100: Assert.isFalse(_searcher.beforeFirst());
101: Assert.isFalse(_searcher.afterLast());
102: }
103: }
104:
105: public void testOneValueMatch() {
106: int[] values = new int[] { 9 };
107: for (int i = 0; i < ALL_TARGETS.length; i++) {
108: search(values, ALL_TARGETS[i]);
109: Assert.areEqual(0, _searcher.cursor());
110: Assert.isTrue(_searcher.foundMatch());
111: Assert.isFalse(_searcher.beforeFirst());
112: Assert.isFalse(_searcher.afterLast());
113: }
114: }
115:
116: public void testOneValueLower() {
117: int[] values = new int[] { 8 };
118: for (int i = 0; i < ALL_TARGETS.length; i++) {
119: search(values, ALL_TARGETS[i]);
120: Assert.areEqual(0, _searcher.cursor());
121: Assert.isFalse(_searcher.foundMatch());
122: Assert.isFalse(_searcher.beforeFirst());
123: Assert.isTrue(_searcher.afterLast());
124: }
125: }
126:
127: public void testOneValueHigher() {
128: int[] values = new int[] { 8 };
129: for (int i = 0; i < ALL_TARGETS.length; i++) {
130: search(values, ALL_TARGETS[i]);
131: Assert.areEqual(0, _searcher.cursor());
132: Assert.isFalse(_searcher.foundMatch());
133: Assert.isFalse(_searcher.beforeFirst());
134: Assert.isTrue(_searcher.afterLast());
135: }
136: }
137:
138: public void testTwoValuesMatch() {
139: int[] values = new int[] { 9, 9 };
140: search(values, SearchTarget.LOWEST);
141: Assert.areEqual(0, _searcher.cursor());
142: Assert.isTrue(_searcher.foundMatch());
143: Assert.isFalse(_searcher.beforeFirst());
144: Assert.isFalse(_searcher.afterLast());
145:
146: search(values, SearchTarget.ANY);
147: Assert.isTrue(_searcher.foundMatch());
148: Assert.isFalse(_searcher.beforeFirst());
149: Assert.isFalse(_searcher.afterLast());
150:
151: search(values, SearchTarget.HIGHEST);
152: Assert.areEqual(1, _searcher.cursor());
153: Assert.isTrue(_searcher.foundMatch());
154: Assert.isFalse(_searcher.beforeFirst());
155: Assert.isFalse(_searcher.afterLast());
156: }
157:
158: public void testTwoValuesLowMatch() {
159: int[] values = new int[] { 9, 10 };
160: search(values, SearchTarget.LOWEST);
161: Assert.areEqual(0, _searcher.cursor());
162: Assert.isTrue(_searcher.foundMatch());
163: Assert.isFalse(_searcher.beforeFirst());
164: Assert.isFalse(_searcher.afterLast());
165:
166: search(values, SearchTarget.ANY);
167: Assert.areEqual(0, _searcher.cursor());
168: Assert.isTrue(_searcher.foundMatch());
169: Assert.isFalse(_searcher.beforeFirst());
170: Assert.isFalse(_searcher.afterLast());
171:
172: search(values, SearchTarget.HIGHEST);
173: Assert.areEqual(0, _searcher.cursor());
174: Assert.isTrue(_searcher.foundMatch());
175: Assert.isFalse(_searcher.beforeFirst());
176: Assert.isFalse(_searcher.afterLast());
177: }
178:
179: public void testTwoValuesHighMatch() {
180: int[] values = new int[] { 6, 9 };
181: search(values, SearchTarget.LOWEST);
182: Assert.areEqual(1, _searcher.cursor());
183: Assert.isTrue(_searcher.foundMatch());
184: Assert.isFalse(_searcher.beforeFirst());
185: Assert.isFalse(_searcher.afterLast());
186:
187: search(values, SearchTarget.ANY);
188: Assert.areEqual(1, _searcher.cursor());
189: Assert.isTrue(_searcher.foundMatch());
190: Assert.isFalse(_searcher.beforeFirst());
191: Assert.isFalse(_searcher.afterLast());
192:
193: search(values, SearchTarget.HIGHEST);
194: Assert.areEqual(1, _searcher.cursor());
195: Assert.isTrue(_searcher.foundMatch());
196: Assert.isFalse(_searcher.beforeFirst());
197: Assert.isFalse(_searcher.afterLast());
198: }
199:
200: public void testTwoValuesInBetween() {
201: int[] values = new int[] { 8, 10 };
202: search(values, SearchTarget.LOWEST);
203: Assert.areEqual(0, _searcher.cursor());
204: Assert.isFalse(_searcher.foundMatch());
205: Assert.isFalse(_searcher.beforeFirst());
206: Assert.isFalse(_searcher.afterLast());
207:
208: search(values, SearchTarget.ANY);
209: Assert.areEqual(0, _searcher.cursor());
210: Assert.isFalse(_searcher.foundMatch());
211: Assert.isFalse(_searcher.beforeFirst());
212: Assert.isFalse(_searcher.afterLast());
213:
214: search(values, SearchTarget.HIGHEST);
215: Assert.areEqual(0, _searcher.cursor());
216: Assert.isFalse(_searcher.foundMatch());
217: Assert.isFalse(_searcher.beforeFirst());
218: Assert.isFalse(_searcher.afterLast());
219: }
220:
221: public void testTwoValuesLower() {
222: int[] values = new int[] { 7, 8 };
223: search(values, SearchTarget.LOWEST);
224: Assert.areEqual(1, _searcher.cursor());
225: Assert.isFalse(_searcher.foundMatch());
226: Assert.isFalse(_searcher.beforeFirst());
227: Assert.isTrue(_searcher.afterLast());
228:
229: search(values, SearchTarget.ANY);
230: Assert.areEqual(1, _searcher.cursor());
231: Assert.isFalse(_searcher.foundMatch());
232: Assert.isFalse(_searcher.beforeFirst());
233: Assert.isTrue(_searcher.afterLast());
234:
235: search(values, SearchTarget.HIGHEST);
236: Assert.areEqual(1, _searcher.cursor());
237: Assert.isFalse(_searcher.foundMatch());
238: Assert.isFalse(_searcher.beforeFirst());
239: Assert.isTrue(_searcher.afterLast());
240: }
241:
242: public void testTwoValuesHigher() {
243: int[] values = new int[] { 10, 11 };
244: search(values, SearchTarget.LOWEST);
245: Assert.areEqual(0, _searcher.cursor());
246: Assert.isFalse(_searcher.foundMatch());
247: Assert.isTrue(_searcher.beforeFirst());
248: Assert.isFalse(_searcher.afterLast());
249:
250: search(values, SearchTarget.ANY);
251: Assert.areEqual(0, _searcher.cursor());
252: Assert.isFalse(_searcher.foundMatch());
253: Assert.isTrue(_searcher.beforeFirst());
254: Assert.isFalse(_searcher.afterLast());
255:
256: search(values, SearchTarget.HIGHEST);
257: Assert.areEqual(0, _searcher.cursor());
258: Assert.isFalse(_searcher.foundMatch());
259: Assert.isTrue(_searcher.beforeFirst());
260: Assert.isFalse(_searcher.afterLast());
261: }
262:
263: private int search(int[] values, SearchTarget target) {
264: _searcher = new Searcher(target, values.length);
265: while (_searcher.incomplete()) {
266: _searcher.resultIs(values[_searcher.cursor()] - SEARCH_FOR);
267: }
268: return _searcher.cursor();
269: }
270:
271: private final int lowMatch(int[] values) {
272: for (int i = 0; i < values.length; i++) {
273: if (values[i] == SEARCH_FOR) {
274: return i;
275: }
276: if (values[i] > SEARCH_FOR) {
277: if (i == 0) {
278: return 0;
279: }
280: return i - 1;
281: }
282: ;
283: }
284: throw new IllegalArgumentException("values");
285: }
286:
287: private final int highMatch(int[] values) {
288: for (int i = values.length - 1; i >= 0; i--) {
289: if (values[i] <= SEARCH_FOR) {
290: return i;
291: }
292: }
293: throw new IllegalArgumentException("values");
294: }
295:
296: public void setUp() throws Exception {
297: _searcher = null;
298: }
299:
300: public void tearDown() throws Exception {
301:
302: }
303:
304: }
|