1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.mavibot.btree;
21
22
23 import java.io.IOException;
24 import java.lang.reflect.Array;
25 import java.util.Comparator;
26
27 import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
28
29
30
31
32
33
34
35
36
37 {
38
39 protected BTree<V, V> valueBtree;
40
41
42 protected V[] valueArray;
43
44
45 protected ElementSerializer<V> valueSerializer;
46
47
48 protected int valueThresholdUp = 1;
49 protected int valueThresholdLow = 1;
50
51 protected int nbArrayElems;
52
53
54
55
56
57 public boolean isSubBtree()
58 {
59 return valueBtree != null;
60 }
61
62
63
64
65
66 public ValueHolder<V> clone() throws CloneNotSupportedException
67 {
68 ValueHolder<V> copy = ( ValueHolder<V> ) super.clone();
69
70 return copy;
71 }
72
73
74
75
76
77 public ValueCursor<V> getCursor()
78 {
79 if ( valueBtree != null )
80 {
81 return new ValueBTreeCursor<V>( valueBtree );
82 }
83 else
84 {
85 return new ValueArrayCursor<V>( valueArray );
86 }
87 }
88
89
90
91
92
93
94
95
96
97
98 private int findPos( V value )
99 {
100 if ( valueArray.length == 0 )
101 {
102 return -1;
103 }
104
105
106 int pivot = valueArray.length / 2;
107 int low = 0;
108 int high = valueArray.length - 1;
109 Comparator<V> comparator = valueSerializer.getComparator();
110
111 while ( high > low )
112 {
113 switch ( high - low )
114 {
115 case 1:
116
117 int result = comparator.compare( value, valueArray[pivot] );
118
119 if ( result == 0 )
120 {
121 return pivot;
122 }
123
124 if ( result < 0 )
125 {
126 if ( pivot == low )
127 {
128 return -( low + 1 );
129 }
130 else
131 {
132 result = comparator.compare( value, valueArray[low] );
133
134 if ( result == 0 )
135 {
136 return low;
137 }
138
139 if ( result < 0 )
140 {
141 return -( low + 1 );
142 }
143 else
144 {
145 return -( low + 2 );
146 }
147 }
148 }
149 else
150 {
151 if ( pivot == high )
152 {
153 return -( high + 2 );
154 }
155 else
156 {
157 result = comparator.compare( value, valueArray[high] );
158
159 if ( result == 0 )
160 {
161 return high;
162 }
163
164 if ( result < 0 )
165 {
166 return -( high + 1 );
167 }
168 else
169 {
170 return -( high + 2 );
171 }
172 }
173 }
174
175 default:
176
177 result = comparator.compare( value, valueArray[pivot] );
178
179 if ( result == 0 )
180 {
181 return pivot;
182 }
183
184 if ( result < 0 )
185 {
186 high = pivot - 1;
187 }
188 else
189 {
190 low = pivot + 1;
191 }
192
193 pivot = ( high + low ) / 2;
194
195 continue;
196 }
197 }
198
199 int result = comparator.compare( value, valueArray[pivot] );
200
201 if ( result == 0 )
202 {
203 return pivot;
204 }
205
206 if ( result < 0 )
207 {
208 return -( pivot + 1 );
209 }
210 else
211 {
212 return -( pivot + 2 );
213 }
214 }
215
216
217
218
219
220 private boolean arrayContains( V value )
221 {
222 if ( valueArray.length == 0 )
223 {
224 return false;
225 }
226
227
228 return findPos( value ) >= 0;
229 }
230
231
232
233
234
235 protected boolean btreeContains( V value )
236 {
237 try
238 {
239 return valueBtree.hasKey( value );
240 }
241 catch ( IOException e )
242 {
243
244 e.printStackTrace();
245 return false;
246 }
247 }
248
249
250
251
252
253 public boolean contains( V checkedValue )
254 {
255 if ( valueArray == null )
256 {
257 return btreeContains( checkedValue );
258 }
259 else
260 {
261 return arrayContains( checkedValue );
262 }
263 }
264
265
266
267
268
269 protected abstract void createSubTree();
270
271
272
273
274
275 private void addInArray( V value )
276 {
277
278 if ( size() >= valueThresholdUp )
279 {
280
281 createSubTree();
282
283 try
284 {
285 for ( V val : valueArray )
286 {
287
288
289 valueBtree.insert( val, null );
290 }
291
292
293 nbArrayElems = 0;
294 valueArray = null;
295
296
297 valueBtree.insert( value, null );
298 }
299 catch ( IOException e )
300 {
301
302 e.printStackTrace();
303 }
304 }
305 else
306 {
307
308 if ( valueArray == null )
309 {
310 valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), 1 );
311 nbArrayElems = 1;
312 valueArray[0] = value;
313 }
314 else
315 {
316
317 int pos = findPos( value );
318
319 if ( pos >= 0 )
320 {
321
322 return;
323 }
324
325
326
327 pos = -( pos + 1 );
328
329 V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length + 1 );
330
331 System.arraycopy( valueArray, 0, newValueArray, 0, pos );
332 newValueArray[pos] = value;
333 System.arraycopy( valueArray, pos, newValueArray, pos + 1, valueArray.length - pos );
334
335
336 valueArray = newValueArray;
337 }
338 }
339 }
340
341
342
343
344
345 private void addInBtree( V value )
346 {
347 try
348 {
349 valueBtree.insert( value, null );
350 }
351 catch ( IOException e )
352 {
353
354 e.printStackTrace();
355 }
356 }
357
358
359
360
361
362 public void add( V value )
363 {
364 if ( valueBtree == null )
365 {
366 addInArray( value );
367 }
368 else
369 {
370 addInBtree( value );
371 }
372 }
373 }