|
1
21 package com.db4o.db4ounit.common.btree;
22
23 import com.db4o.inside.btree.*;
24
25 import db4ounit.*;
26
27
28 public class SearcherLowestHighestTestCase implements TestCase, TestLifeCycle{
29
30 private Searcher _searcher;
31
32 private static final int SEARCH_FOR = 9;
33
34 private static final int[] EVEN_EVEN_VALUES = new int[] {4, 9, 9, 9, 9, 11, 13, 17};
35
36 private static final int[] EVEN_ODD_VALUES = new int[] {4, 5, 9, 9, 9, 11, 13, 17};
37
38 private static final int[] ODD_EVEN_VALUES = new int[] {4, 9, 9, 9, 9, 11, 13};
39
40 private static final int[] ODD_ODD_VALUES = new int[] {4, 5, 9, 9, 9, 11, 13};
41
42 private static final int[] NO_MATCH_EVEN = new int[] {4, 5, 10, 10, 10, 11};
43
44 private static final int[] NO_MATCH_ODD = new int[] {4, 5, 10, 10, 10, 11, 13};
45
46
47 private static final int[][] MATCH_VALUES = new int[][]{
48 EVEN_EVEN_VALUES,
49 EVEN_ODD_VALUES,
50 ODD_EVEN_VALUES,
51 ODD_ODD_VALUES
52 };
53
54 private static final int[][] NO_MATCH_VALUES = new int[][]{
55 NO_MATCH_EVEN,
56 NO_MATCH_ODD
57 };
58
59 private static final SearchTarget[] ALL_TARGETS = new SearchTarget[]{SearchTarget.LOWEST, SearchTarget.ANY, SearchTarget.HIGHEST};
60
61 public void testMatch(){
62 for (int i = 0; i < MATCH_VALUES.length; i++) {
63 int[] values = MATCH_VALUES[i];
64
65 int lo = lowMatch(values);
66 search(values, SearchTarget.LOWEST);
67 Assert.areEqual(lo, _searcher.cursor());
68 Assert.isTrue(_searcher.foundMatch());
69
70 int hi = highMatch(values);
71 search(values, SearchTarget.HIGHEST);
72 Assert.areEqual(hi, _searcher.cursor());
73 Assert.isTrue(_searcher.foundMatch());
74 }
75 }
76
77 public void testNoMatch(){
78 for (int i = 0; i < NO_MATCH_VALUES.length; i++) {
79 int[] values = NO_MATCH_VALUES[i];
80
81 int lo = lowMatch(values);
82 search(values, SearchTarget.LOWEST);
83 Assert.areEqual(lo, _searcher.cursor());
84 Assert.isFalse(_searcher.foundMatch());
85
86 int hi = highMatch(values);
87 search(values, SearchTarget.HIGHEST);
88 Assert.areEqual(hi, _searcher.cursor());
89 Assert.isFalse(_searcher.foundMatch());
90 }
91 }
92
93 public void testEmpty(){
94 int[] values = new int[]{};
95 for (int i = 0; i < ALL_TARGETS.length; i++) {
96 search(values, ALL_TARGETS[i]);
97 Assert.areEqual(0, _searcher.cursor());
98 Assert.isFalse(_searcher.foundMatch());
99 Assert.isFalse(_searcher.beforeFirst());
100 Assert.isFalse(_searcher.afterLast());
101 }
102 }
103
104 public void testOneValueMatch(){
105 int[] values = new int[]{9};
106 for (int i = 0; i < ALL_TARGETS.length; i++) {
107 search(values, ALL_TARGETS[i]);
108 Assert.areEqual(0, _searcher.cursor());
109 Assert.isTrue(_searcher.foundMatch());
110 Assert.isFalse(_searcher.beforeFirst());
111 Assert.isFalse(_searcher.afterLast());
112 }
113 }
114
115 public void testOneValueLower(){
116 int[] values = new int[]{8};
117 for (int i = 0; i < ALL_TARGETS.length; i++) {
118 search(values, ALL_TARGETS[i]);
119 Assert.areEqual(0, _searcher.cursor());
120 Assert.isFalse(_searcher.foundMatch());
121 Assert.isFalse(_searcher.beforeFirst());
122 Assert.isTrue(_searcher.afterLast());
123 }
124 }
125
126 public void testOneValueHigher(){
127 int[] values = new int[]{8};
128 for (int i = 0; i < ALL_TARGETS.length; i++) {
129 search(values, ALL_TARGETS[i]);
130 Assert.areEqual(0, _searcher.cursor());
131 Assert.isFalse(_searcher.foundMatch());
132 Assert.isFalse(_searcher.beforeFirst());
133 Assert.isTrue(_searcher.afterLast());
134 }
135 }
136
137 public void testTwoValuesMatch(){
138 int[] values = new int[]{9, 9};
139 search(values, SearchTarget.LOWEST);
140 Assert.areEqual(0, _searcher.cursor());
141 Assert.isTrue(_searcher.foundMatch());
142 Assert.isFalse(_searcher.beforeFirst());
143 Assert.isFalse(_searcher.afterLast());
144
145 search(values, SearchTarget.ANY);
146 Assert.isTrue(_searcher.foundMatch());
147 Assert.isFalse(_searcher.beforeFirst());
148 Assert.isFalse(_searcher.afterLast());
149
150 search(values, SearchTarget.HIGHEST);
151 Assert.areEqual(1, _searcher.cursor());
152 Assert.isTrue(_searcher.foundMatch());
153 Assert.isFalse(_searcher.beforeFirst());
154 Assert.isFalse(_searcher.afterLast());
155 }
156
157 public void testTwoValuesLowMatch(){
158 int[] values = new int[]{9, 10};
159 search(values, SearchTarget.LOWEST);
160 Assert.areEqual(0, _searcher.cursor());
161 Assert.isTrue(_searcher.foundMatch());
162 Assert.isFalse(_searcher.beforeFirst());
163 Assert.isFalse(_searcher.afterLast());
164
165 search(values, SearchTarget.ANY);
166 Assert.areEqual(0, _searcher.cursor());
167 Assert.isTrue(_searcher.foundMatch());
168 Assert.isFalse(_searcher.beforeFirst());
169 Assert.isFalse(_searcher.afterLast());
170
171 search(values, SearchTarget.HIGHEST);
172 Assert.areEqual(0, _searcher.cursor());
173 Assert.isTrue(_searcher.foundMatch());
174 Assert.isFalse(_searcher.beforeFirst());
175 Assert.isFalse(_searcher.afterLast());
176 }
177
178 public void testTwoValuesHighMatch(){
179 int[] values = new int[]{6, 9};
180 search(values, SearchTarget.LOWEST);
181 Assert.areEqual(1, _searcher.cursor());
182 Assert.isTrue(_searcher.foundMatch());
183 Assert.isFalse(_searcher.beforeFirst());
184 Assert.isFalse(_searcher.afterLast());
185
186 search(values, SearchTarget.ANY);
187 Assert.areEqual(1, _searcher.cursor());
188 Assert.isTrue(_searcher.foundMatch());
189 Assert.isFalse(_searcher.beforeFirst());
190 Assert.isFalse(_searcher.afterLast());
191
192 search(values, SearchTarget.HIGHEST);
193 Assert.areEqual(1, _searcher.cursor());
194 Assert.isTrue(_searcher.foundMatch());
195 Assert.isFalse(_searcher.beforeFirst());
196 Assert.isFalse(_searcher.afterLast());
197 }
198
199 public void testTwoValuesInBetween(){
200 int[] values = new int[]{8, 10};
201 search(values, SearchTarget.LOWEST);
202 Assert.areEqual(0, _searcher.cursor());
203 Assert.isFalse(_searcher.foundMatch());
204 Assert.isFalse(_searcher.beforeFirst());
205 Assert.isFalse(_searcher.afterLast());
206
207 search(values, SearchTarget.ANY);
208 Assert.areEqual(0, _searcher.cursor());
209 Assert.isFalse(_searcher.foundMatch());
210 Assert.isFalse(_searcher.beforeFirst());
211 Assert.isFalse(_searcher.afterLast());
212
213 search(values, SearchTarget.HIGHEST);
214 Assert.areEqual(0, _searcher.cursor());
215 Assert.isFalse(_searcher.foundMatch());
216 Assert.isFalse(_searcher.beforeFirst());
217 Assert.isFalse(_searcher.afterLast());
218 }
219
220 public void testTwoValuesLower(){
221 int[] values = new int[]{7, 8};
222 search(values, SearchTarget.LOWEST);
223 Assert.areEqual(1, _searcher.cursor());
224 Assert.isFalse(_searcher.foundMatch());
225 Assert.isFalse(_searcher.beforeFirst());
226 Assert.isTrue(_searcher.afterLast());
227
228 search(values, SearchTarget.ANY);
229 Assert.areEqual(1, _searcher.cursor());
230 Assert.isFalse(_searcher.foundMatch());
231 Assert.isFalse(_searcher.beforeFirst());
232 Assert.isTrue(_searcher.afterLast());
233
234 search(values, SearchTarget.HIGHEST);
235 Assert.areEqual(1, _searcher.cursor());
236 Assert.isFalse(_searcher.foundMatch());
237 Assert.isFalse(_searcher.beforeFirst());
238 Assert.isTrue(_searcher.afterLast());
239 }
240
241 public void testTwoValuesHigher(){
242 int[] values = new int[]{10, 11};
243 search(values, SearchTarget.LOWEST);
244 Assert.areEqual(0, _searcher.cursor());
245 Assert.isFalse(_searcher.foundMatch());
246 Assert.isTrue(_searcher.beforeFirst());
247 Assert.isFalse(_searcher.afterLast());
248
249 search(values, SearchTarget.ANY);
250 Assert.areEqual(0, _searcher.cursor());
251 Assert.isFalse(_searcher.foundMatch());
252 Assert.isTrue(_searcher.beforeFirst());
253 Assert.isFalse(_searcher.afterLast());
254
255 search(values, SearchTarget.HIGHEST);
256 Assert.areEqual(0, _searcher.cursor());
257 Assert.isFalse(_searcher.foundMatch());
258 Assert.isTrue(_searcher.beforeFirst());
259 Assert.isFalse(_searcher.afterLast());
260 }
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 throw new IllegalArgumentException  ("values");
284 }
285
286 private final int highMatch(int[] values){
287 for (int i = values.length - 1; i >= 0; i--) {
288 if(values[i] <= SEARCH_FOR){
289 return i;
290 }
291 }
292 throw new IllegalArgumentException ("values");
293 }
294
295 public void setUp() throws Exception {
296 _searcher = null;
297 }
298
299 public void tearDown() throws Exception {
300
301 }
302
303 }
304 |
Popular Tags |
Java API By Example, From Geeks To Geeks.