1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
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 import java.util.Iterator;
27
28 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
29 import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
30
31
32 /**
33 * A holder to store the Values
34 *
35 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
36 * @param <V> The value type
37 */
38 /* No qualifier*/abstract class AbstractValueHolder<V> implements ValueHolder<V>
39 {
40 /** The BTree storing multiple value, if we have more than one value */
41 protected BTree<V, V> valueBtree;
42
43 /** The array storing from 1 to N values */
44 protected V[] valueArray;
45
46 /** The Value serializer */
47 protected ElementSerializer<V> valueSerializer;
48
49 /** The configuration for the array <-> BTree switch. Default to 1 */
50 protected int valueThresholdUp = 1;
51 protected int valueThresholdLow = 1;
52
53 protected int nbArrayElems;
54
55
56 /**
57 * {@inheritDoc}
58 */
59 public boolean isSubBtree()
60 {
61 return valueBtree != null;
62 }
63
64
65 /**
66 * Create a clone of this instance
67 */
68 public ValueHolder<V> clone() throws CloneNotSupportedException
69 {
70 ValueHolder<V> copy = ( ValueHolder<V> ) super.clone();
71
72 return copy;
73 }
74
75
76 /**
77 * @return a cursor on top of the values
78 */
79 public ValueCursor<V> getCursor()
80 {
81 if ( valueBtree != null )
82 {
83 return new ValueBTreeCursor<V>( valueBtree );
84 }
85 else
86 {
87 return new ValueArrayCursor<V>( valueArray );
88 }
89 }
90
91
92 /**
93 * Find the position of a given value in the array, or the position where we
94 * would insert the element (in this case, the position will be negative).
95 * As we use a 0-based array, the negative position for 0 is -1.
96 * -1 means the element can be added in position 0
97 * -2 means the element can be added in position 1
98 * ...
99 */
100 private int findPos( V value )
101 {
102 if ( valueArray.length == 0 )
103 {
104 return -1;
105 }
106
107 // Do a search using dichotomy
108 int pivot = valueArray.length / 2;
109 int low = 0;
110 int high = valueArray.length - 1;
111 Comparator<V> comparator = valueSerializer.getComparator();
112
113 while ( high > low )
114 {
115 switch ( high - low )
116 {
117 case 1:
118 // We have 2 elements
119 int result = comparator.compare( value, valueArray[pivot] );
120
121 if ( result == 0 )
122 {
123 return pivot;
124 }
125
126 if ( result < 0 )
127 {
128 if ( pivot == low )
129 {
130 return -( low + 1 );
131 }
132 else
133 {
134 result = comparator.compare( value, valueArray[low] );
135
136 if ( result == 0 )
137 {
138 return low;
139 }
140
141 if ( result < 0 )
142 {
143 return -( low + 1 );
144 }
145 else
146 {
147 return -( low + 2 );
148 }
149 }
150 }
151 else
152 {
153 if ( pivot == high )
154 {
155 return -( high + 2 );
156 }
157 else
158 {
159 result = comparator.compare( value, valueArray[high] );
160
161 if ( result == 0 )
162 {
163 return high;
164 }
165
166 if ( result < 0 )
167 {
168 return -( high + 1 );
169 }
170 else
171 {
172 return -( high + 2 );
173 }
174 }
175 }
176
177 default:
178 // We have 3 elements
179 result = comparator.compare( value, valueArray[pivot] );
180
181 if ( result == 0 )
182 {
183 return pivot;
184 }
185
186 if ( result < 0 )
187 {
188 high = pivot - 1;
189 }
190 else
191 {
192 low = pivot + 1;
193 }
194
195 pivot = ( high + low ) / 2;
196
197 continue;
198 }
199 }
200
201 int result = comparator.compare( value, valueArray[pivot] );
202
203 if ( result == 0 )
204 {
205 return pivot;
206 }
207
208 if ( result < 0 )
209 {
210 return -( pivot + 1 );
211 }
212 else
213 {
214 return -( pivot + 2 );
215 }
216 }
217
218
219 /**
220 * Check if the array of values contains a given value
221 */
222 private boolean arrayContains( V value )
223 {
224 if ( valueArray.length == 0 )
225 {
226 return false;
227 }
228
229 // Do a search using dichotomy
230 return findPos( value ) >= 0;
231 }
232
233
234 /**
235 * Check if the subBtree contains a given value
236 */
237 protected boolean btreeContains( V value )
238 {
239 try
240 {
241 return valueBtree.hasKey( value );
242 }
243 catch ( IOException e )
244 {
245 // TODO Auto-generated catch block
246 e.printStackTrace();
247 return false;
248 }
249 catch ( KeyNotFoundException knfe )
250 {
251 knfe.printStackTrace();
252 return false;
253 }
254 }
255
256
257 /**
258 * {@inheritDoc}
259 */
260 public boolean contains( V checkedValue )
261 {
262 if ( valueArray == null )
263 {
264 return btreeContains( checkedValue );
265 }
266 else
267 {
268 return arrayContains( checkedValue );
269 }
270 }
271
272
273 /**
274 * Create a new Sub-BTree to store the values.
275 */
276 protected abstract void createSubTree();
277
278
279 /**
280 * Manage a new Sub-BTree .
281 */
282 protected abstract void manageSubTree();
283
284
285 /**
286 * Add the value in an array
287 */
288 private void addInArray( final V value )
289 {
290 // We have to check that we have reached the threshold or not
291 if ( size() >= valueThresholdUp )
292 {
293 // Ok, transform the array into a btree
294 createSubTree();
295
296 Iterator<Tuple<V, V>> valueIterator = new Iterator<Tuple<V, V>>()
297 {
298 int pos = 0;
299
300
301 @Override
302 public Tuple<V, V> next()
303 {
304 // We can now return the found value
305 if ( pos == valueArray.length )
306 {
307 // Special case : deal with the added value
308 pos++;
309
310 return new Tuple<V, V>( value, value );
311 }
312 else
313 {
314 V oldValue = valueArray[pos];
315 pos++;
316
317 return new Tuple<V, V>( oldValue, oldValue );
318 }
319 }
320
321
322 @Override
323 public boolean hasNext()
324 {
325 // Check that we have at least one element to read
326 return pos < valueArray.length + 1;
327 }
328
329
330 @Override
331 public void remove()
332 {
333 }
334
335 };
336
337 try
338 {
339 BulkLoader.load( valueBtree, valueIterator, valueArray.length );
340 }
341 catch ( IOException e )
342 {
343 // TODO Auto-generated catch block
344 e.printStackTrace();
345 }
346
347 manageSubTree();
348
349 // And make the valueArray to be null now
350 valueArray = null;
351 }
352 else
353 {
354 // Create the array if it's null
355 if ( valueArray == null )
356 {
357 valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), 1 );
358 nbArrayElems = 1;
359 valueArray[0] = value;
360 }
361 else
362 {
363 // check that the value is not already present in the ValueHolder
364 int pos = findPos( value );
365
366 if ( pos >= 0 )
367 {
368 // The value exists : nothing to do
369 return;
370 }
371
372 // Ok, we just have to insert the new element at the right position
373 // We transform the position to a positive value
374 pos = -( pos + 1 );
375 // First, copy the array
376 V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length + 1 );
377
378 System.arraycopy( valueArray, 0, newValueArray, 0, pos );
379 newValueArray[pos] = value;
380 System.arraycopy( valueArray, pos, newValueArray, pos + 1, valueArray.length - pos );
381
382 // And switch the arrays
383 valueArray = newValueArray;
384 }
385 }
386 }
387
388
389 /**
390 * Add the value in the subBTree
391 */
392 private void addInBtree( V value )
393 {
394 try
395 {
396 valueBtree.insert( value, null );
397 }
398 catch ( IOException e )
399 {
400 // TODO Auto-generated catch block
401 e.printStackTrace();
402 }
403 }
404
405
406 /**
407 * {@inheritDoc}
408 */
409 public void add( V value )
410 {
411 if ( valueBtree == null )
412 {
413 addInArray( value );
414 }
415 else
416 {
417 addInBtree( value );
418 }
419 }
420
421
422 /**
423 * {@inheritDoc}
424 */
425 @Override
426 public V replaceValueArray( V newValue )
427 {
428 if ( isSubBtree() )
429 {
430 throw new IllegalStateException( "method is not applicable for the duplicate B-Trees" );
431 }
432
433 V tmp = valueArray[0];
434
435 nbArrayElems = 1;
436 valueArray[0] = newValue;
437
438 return tmp;
439 }
440
441 }