%line | %branch | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
org.apache.jcs.utils.struct.SortedPreferentialArray |
|
|
1 | package org.apache.jcs.utils.struct; |
|
2 | ||
3 | /* |
|
4 | * Licensed to the Apache Software Foundation (ASF) under one |
|
5 | * or more contributor license agreements. See the NOTICE file |
|
6 | * distributed with this work for additional information |
|
7 | * regarding copyright ownership. The ASF licenses this file |
|
8 | * to you under the Apache License, Version 2.0 (the |
|
9 | * "License"); you may not use this file except in compliance |
|
10 | * with the License. You may obtain a copy of the License at |
|
11 | * |
|
12 | * http://www.apache.org/licenses/LICENSE-2.0 |
|
13 | * |
|
14 | * Unless required by applicable law or agreed to in writing, |
|
15 | * software distributed under the License is distributed on an |
|
16 | * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
|
17 | * KIND, either express or implied. See the License for the |
|
18 | * specific language governing permissions and limitations |
|
19 | * under the License. |
|
20 | */ |
|
21 | ||
22 | import org.apache.commons.logging.Log; |
|
23 | import org.apache.commons.logging.LogFactory; |
|
24 | ||
25 | /** |
|
26 | * This maintains a sorted array with a preferential replacement policy when full. |
|
27 | * <p> |
|
28 | * Insertion time is n, search is log(n) |
|
29 | * <p> |
|
30 | * Clients must manage thread safety on previous version. I synchronized the public methods to add |
|
31 | * easy thread safety. I synchronized all public methods that make modifications. |
|
32 | */ |
|
33 | 1 | public class SortedPreferentialArray |
34 | { |
|
35 | /** The logger */ |
|
36 | 161 | private static final Log log = LogFactory.getLog( SortedPreferentialArray.class ); |
37 | ||
38 | /** prefer large means that the smallest will be removed when full. */ |
|
39 | 566 | private boolean preferLarge = true; |
40 | ||
41 | /** maximum number allowed */ |
|
42 | 566 | private int maxSize = 0; |
43 | ||
44 | /** The currency number */ |
|
45 | 566 | private int curSize = 0; |
46 | ||
47 | /** The primary array */ |
|
48 | private Comparable[] array; |
|
49 | ||
50 | /** the number that have been inserted. */ |
|
51 | 566 | private int insertCnt = 0; |
52 | ||
53 | /** |
|
54 | * Consruct the array with the maximum size. |
|
55 | * <p> |
|
56 | * @param maxSize int |
|
57 | */ |
|
58 | 12 | public SortedPreferentialArray( int maxSize ) |
59 | 554 | { |
60 | 566 | this.maxSize = maxSize; |
61 | 566 | array = new Comparable[maxSize]; |
62 | 566 | } |
63 | ||
64 | /** |
|
65 | * If the array is full this will remove the smallest if preferLarge==true and if obj is bigger, |
|
66 | * or the largest if preferLarge=false and obj is smaller than the largest. |
|
67 | * <p> |
|
68 | * @param obj Object |
|
69 | */ |
|
70 | public synchronized void add( Comparable obj ) |
|
71 | { |
|
72 | 228241 | if ( obj == null ) |
73 | { |
|
74 | 8 | return; |
75 | } |
|
76 | ||
77 | 228174 | if ( curSize < maxSize ) |
78 | { |
|
79 | 214795 | insert( obj ); |
80 | 214805 | return; |
81 | } |
|
82 | 13335 | if ( preferLarge ) |
83 | { |
|
84 | // insert if obj is larger than the smallest |
|
85 | 13335 | Comparable sma = getSmallest(); |
86 | 13335 | if ( obj.compareTo( sma ) > 0 ) |
87 | { |
|
88 | 13328 | insert( obj ); |
89 | 13328 | return; |
90 | } |
|
91 | // obj is less than or equal to the smallest. |
|
92 | 7 | if ( log.isDebugEnabled() ) |
93 | { |
|
94 | 0 | log.debug( "New object is smaller than or equal to the smallest" ); |
95 | } |
|
96 | 7 | return; |
97 | } |
|
98 | // Not preferLarge |
|
99 | 0 | Comparable lar = getLargest(); |
100 | // insert if obj is smaller than the largest |
|
101 | 0 | int diff = obj.compareTo( lar ); |
102 | 0 | if ( dclass="keyword">iff > 0 || dclass="keyword">iff == 0 ) |
103 | { |
|
104 | 0 | if ( log.isDebugEnabled() ) |
105 | { |
|
106 | 0 | log.debug( "New object is larger than or equal to the largest" ); |
107 | } |
|
108 | 0 | return; |
109 | } |
|
110 | // obj is less than the largest. |
|
111 | 0 | insert( obj ); |
112 | 0 | return; |
113 | } |
|
114 | ||
115 | /** |
|
116 | * Returns the largest without removing it from the array. |
|
117 | * <p> |
|
118 | * @return Comparable |
|
119 | */ |
|
120 | public synchronized Comparable getLargest() |
|
121 | { |
|
122 | 312532 | return array[curSize - 1]; |
123 | } |
|
124 | ||
125 | /** |
|
126 | * Returns the smallest element without removing it from the array. |
|
127 | * <p> |
|
128 | * @return Comparable |
|
129 | */ |
|
130 | public synchronized Comparable getSmallest() |
|
131 | { |
|
132 | 373509 | return array[0]; |
133 | } |
|
134 | ||
135 | /** |
|
136 | * Insert looks for the nearest largest. It then determines which way to shuffle depending on |
|
137 | * the preference. |
|
138 | * <p> |
|
139 | * @param obj Comparable |
|
140 | */ |
|
141 | private void insert( Comparable obj ) |
|
142 | { |
|
143 | try |
|
144 | { |
|
145 | 228173 | int nLar = findNearestLargerEqualOrLastPosition( obj ); |
146 | 228194 | if ( log.isDebugEnabled() ) |
147 | { |
|
148 | 0 | log.debug( "nLar = " + nLar + " obj = " + obj ); |
149 | } |
|
150 | ||
151 | 228243 | if ( nLar == curSize ) |
152 | { |
|
153 | // this next check should be unnecessary |
|
154 | // findNearestLargerPosition should only return the curSize if |
|
155 | // there is |
|
156 | // room left. Check to be safe |
|
157 | 203457 | if ( curSize < maxSize ) |
158 | { |
|
159 | 203341 | array[nLar] = obj; |
160 | 203423 | curSize++; |
161 | 203312 | if ( log.isDebugEnabled() ) |
162 | { |
|
163 | 0 | log.debug( this.dumpArray() ); |
164 | } |
|
165 | 203407 | if ( log.isDebugEnabled() ) |
166 | { |
|
167 | 0 | log.debug( "Inserted object at the end of the array" ); |
168 | } |
|
169 | 203410 | return; |
170 | } // end if not full |
|
171 | } |
|
172 | ||
173 | 24786 | boolean isFull = false; |
174 | 24786 | if ( curSize == maxSize ) |
175 | { |
|
176 | 13328 | isFull = true; |
177 | } |
|
178 | ||
179 | // The array is full, we must replace |
|
180 | // remove smallest or largest to determine whether to |
|
181 | // shuffle left or right to insert |
|
182 | 24786 | if ( preferLarge ) |
183 | { |
|
184 | 24786 | if ( isFull ) |
185 | { |
|
186 | // is full, prefer larger, remove smallest by shifting left |
|
187 | 13328 | int pnt = nLar - 1; // set iteration stop point |
188 | 65909352 | for ( int i = 0; i < pnt; i++ ) |
189 | { |
|
190 | 65896024 | array[i] = array[i + 1]; |
191 | } |
|
192 | // use nLar-1 for insertion point |
|
193 | 13328 | array[nLar - 1] = obj; |
194 | 13328 | if ( log.isDebugEnabled() ) |
195 | { |
|
196 | 0 | log.debug( "Inserted object at " + ( nLar - 1 ) ); |
197 | } |
|
198 | 13311 | } |
199 | else |
|
200 | { |
|
201 | // not full, shift right from spot |
|
202 | 11458 | int pnt = nLar; // set iteration stop point |
203 | 7548282 | for ( int i = curSize; i > pnt; i-- ) |
204 | { |
|
205 | 7536824 | array[i] = array[i - 1]; |
206 | } |
|
207 | // use nLar-1 for insertion point |
|
208 | 11458 | array[nLar] = obj; |
209 | 11458 | curSize++; |
210 | 11458 | if ( log.isDebugEnabled() ) |
211 | { |
|
212 | 0 | log.debug( "Inserted object at " + ( nLar ) ); |
213 | } |
|
214 | } |
|
215 | 11422 | } |
216 | else |
|
217 | { |
|
218 | // prefer smaller, remove largest by shifting right |
|
219 | // use nLar for insertion point |
|
220 | 0 | int pnt = nLar + 1; |
221 | 0 | if ( !isFull ) |
222 | { |
|
223 | 0 | pnt = nLar; |
224 | } |
|
225 | 0 | for ( int i = curSize; i > pnt; i-- ) |
226 | { |
|
227 | 0 | array[i] = array[i - 1]; |
228 | } |
|
229 | 0 | array[nLar] = obj; |
230 | 0 | if ( log.isDebugEnabled() ) |
231 | { |
|
232 | 0 | log.debug( "Inserted object at " + nLar ); |
233 | } |
|
234 | } |
|
235 | ||
236 | 24786 | if ( log.isDebugEnabled() ) |
237 | { |
|
238 | 0 | log.debug( this.dumpArray() ); |
239 | } |
|
240 | } |
|
241 | 0 | catch ( Exception e ) |
242 | { |
|
243 | 0 | log.error( "Insertion problem" + this.dumpArray(), e ); |
244 | 24733 | } |
245 | ||
246 | 24786 | insertCnt++; |
247 | 24786 | if ( insertCnt % 100 == 0 ) |
248 | { |
|
249 | 227 | if ( log.isDebugEnabled() ) |
250 | { |
|
251 | 0 | log.debug( this.dumpArray() ); |
252 | } |
|
253 | } |
|
254 | 24786 | } |
255 | ||
256 | /** |
|
257 | * Determines whether the preference is for large or small. |
|
258 | * <p> |
|
259 | * @param pref boolean |
|
260 | */ |
|
261 | public synchronized void setPreferLarge( boolean pref ) |
|
262 | { |
|
263 | 96 | preferLarge = pref; |
264 | 96 | } |
265 | ||
266 | /** |
|
267 | * Returns and removes the nearer larger or equal object from the aray. |
|
268 | * <p> |
|
269 | * @param obj Comparable |
|
270 | * @return Comparable, null if arg is null or none was found. |
|
271 | */ |
|
272 | public synchronized Comparable takeNearestLargerOrEqual( Comparable obj ) |
|
273 | { |
|
274 | 245266 | if ( obj == null ) |
275 | { |
|
276 | 8 | return null; |
277 | } |
|
278 | ||
279 | 245245 | Comparable retVal = null; |
280 | try |
|
281 | { |
|
282 | 245239 | int pos = findNearestOccupiedLargerOrEqualPosition( obj ); |
283 | 245273 | if ( pos == -1 ) |
284 | { |
|
285 | 129013 | return null; |
286 | } |
|
287 | ||
288 | try |
|
289 | { |
|
290 | 116221 | retVal = array[pos]; |
291 | 116221 | remove( pos ); |
292 | } |
|
293 | 0 | catch ( Exception e ) |
294 | { |
|
295 | 0 | log.error( "Problem removing from array. pos [" + pos + "] " + obj, e ); |
296 | 116207 | } |
297 | ||
298 | 116221 | if ( log.isDebugEnabled() ) |
299 | { |
|
300 | 0 | log.debug( "obj = " + obj + " || retVal = " + retVal ); |
301 | } |
|
302 | } |
|
303 | 0 | catch ( Exception e ) |
304 | { |
|
305 | 0 | log.error( "Take problem" + this.dumpArray(), e ); |
306 | 116207 | } |
307 | 116221 | return retVal; |
308 | } |
|
309 | ||
310 | /** |
|
311 | * Returns the current size of the array. |
|
312 | * <p> |
|
313 | * @return int |
|
314 | */ |
|
315 | public synchronized int size() |
|
316 | { |
|
317 | 48663 | return this.curSize; |
318 | } |
|
319 | ||
320 | /** |
|
321 | * This determines the position in the array that is occupied by an object that is larger or |
|
322 | * equal to the argument. If none exists, -1 is returned. |
|
323 | * <p> |
|
324 | * @param obj Object |
|
325 | * @return Object |
|
326 | */ |
|
327 | private int findNearestOccupiedLargerOrEqualPosition( Comparable obj ) |
|
328 | { |
|
329 | 245218 | if ( curSize == 0 ) |
330 | { |
|
331 | // nothing in the array |
|
332 | 67919 | return -1; |
333 | } |
|
334 | ||
335 | // this gives us an insert position. |
|
336 | 177346 | int pos = findNearestLargerEqualOrLastPosition( obj ); |
337 | ||
338 | // see if the previous will do to handle the empty insert spot position |
|
339 | 177346 | if ( pos == curSize ) |
340 | { // && curSize < maxSize ) { |
|
341 | // pos will be > 0 if it equals curSize, we check for this above. |
|
342 | 109017 | if ( obj.compareTo( array[pos - 1] ) <= 0 ) |
343 | { |
|
344 | 61107 | pos = pos - 1; |
345 | 61102 | } |
346 | else |
|
347 | { |
|
348 | 47910 | pos = -1; |
349 | } |
|
350 | 47908 | } |
351 | else |
|
352 | { |
|
353 | // the find nearest, returns the last, since it is used by insertion. |
|
354 | 68329 | if ( obj.compareTo( array[pos] ) > 0 ) |
355 | { |
|
356 | 13215 | return -1; |
357 | } |
|
358 | } |
|
359 | ||
360 | 164131 | return pos; |
361 | } |
|
362 | ||
363 | /** |
|
364 | * This method determines the position where an insert should take place for a given object. |
|
365 | * With some additional checking, this can also be used to find an object matching or greater |
|
366 | * than the argument. |
|
367 | * <p> |
|
368 | * If the array is not full and the current object is larger than all the rest the first open |
|
369 | * slot at the end will be returned. |
|
370 | * <p> |
|
371 | * NOTE: If the object is larger than the largest and it is full, it will return the last position. |
|
372 | * <p> |
|
373 | * If the array is empty, the first spot is returned. |
|
374 | * <p> |
|
375 | * If the object is smaller than all the rests, the first position is returned. The caller must |
|
376 | * decide what to do given the preference. |
|
377 | * <p> |
|
378 | * Returns the position of the object nearest to or equal to the larger object. |
|
379 | * <p> |
|
380 | * If you want to find the takePosition, you have to calculate it. |
|
381 | * findNearestOccupiedLargerOrEqualPosition will calculate this for you. |
|
382 | * <p> |
|
383 | * @param obj Comparable |
|
384 | * @return int |
|
385 | */ |
|
386 | private int findNearestLargerEqualOrLastPosition( Comparable obj ) |
|
387 | { |
|
388 | // do nothing if a null was passed in |
|
389 | 405528 | if ( obj == null ) |
390 | { |
|
391 | 0 | return -1; |
392 | } |
|
393 | ||
394 | // return the first spot if the array is empty |
|
395 | 405549 | if ( curSize <= 0 ) |
396 | { |
|
397 | 45315 | return 0; |
398 | } |
|
399 | ||
400 | // mark the numer to be returned, the greaterPos as unset |
|
401 | 359950 | int greaterPos = -1; |
402 | // prepare for a binary search |
|
403 | 359956 | int curPos = ( curSize - 1 ) / 2; |
404 | 360275 | int prevPos = -1; |
405 | ||
406 | try |
|
407 | { |
|
408 | // set the loop exit flag to false |
|
409 | 360163 | boolean done = false; |
410 | ||
411 | // check the ends |
|
412 | // return insert position 0 if obj is smaller |
|
413 | // than the smallest. the caller can determine what to |
|
414 | // do with this, depending on the preference setting |
|
415 | 360123 | if ( obj.compareTo( getSmallest() ) <= 0 ) |
416 | { |
|
417 | // LESS THAN OR EQUAL TO SMALLEST |
|
418 | 47568 | if ( log.isDebugEnabled() ) |
419 | { |
|
420 | 0 | log.debug( obj + " is smaller than or equal to " + getSmallest() ); |
421 | } |
|
422 | 47568 | greaterPos = 0; |
423 | 47568 | done = true; |
424 | // return greaterPos; |
|
425 | 47562 | } |
426 | else |
|
427 | { |
|
428 | // GREATER THAN SMALLEST |
|
429 | 312706 | if ( log.isDebugEnabled() ) |
430 | { |
|
431 | 0 | log.debug( obj + " is bigger than " + getSmallest() ); |
432 | } |
|
433 | ||
434 | // return the largest position if obj is larger |
|
435 | // than the largest. the caller can determine what to |
|
436 | // do with this, depending on the preference setting |
|
437 | 312707 | if ( obj.compareTo( getLargest() ) >= 0 ) |
438 | { |
|
439 | 293608 | if ( curSize == maxSize ) |
440 | { |
|
441 | // there is no room left in the array, return the last |
|
442 | // spot |
|
443 | 26447 | greaterPos = curSize - 1; |
444 | 26447 | done = true; |
445 | 26441 | } |
446 | else |
|
447 | { |
|
448 | // there is room left in the array |
|
449 | 266947 | greaterPos = curSize; |
450 | 267159 | done = true; |
451 | } |
|
452 | 266969 | } |
453 | else |
|
454 | { |
|
455 | // the obj is less than or equal to the largest, so we know that the |
|
456 | // last item is larger or equal |
|
457 | 19100 | greaterPos = curSize - 1; |
458 | } |
|
459 | } |
|
460 | ||
461 | // ///////////////////////////////////////////////////////////////////// |
|
462 | // begin binary search for insertion spot |
|
463 | 438510 | while ( !done ) |
464 | { |
|
465 | 97398 | if ( log.isDebugEnabled() ) |
466 | { |
|
467 | 0 | log.debug( "\n curPos = " + curPos + "; greaterPos = " + greaterPos + "; prevpos = " + prevPos ); |
468 | } |
|
469 | ||
470 | // get out of loop if we have come to the end or passed it |
|
471 | 97398 | if ( curPos == prevPos || curPos >= curSize ) |
472 | { |
|
473 | 11599 | done = true; |
474 | 11599 | break; |
475 | } |
|
476 | else |
|
477 | ||
478 | // EQUAL TO |
|
479 | // object at current position is equal to the obj, use this, |
|
480 | // TODO could avoid some shuffling if I found a lower pos. |
|
481 | 85799 | if ( array[curPos].compareTo( obj ) == 0 ) |
482 | { |
|
483 | 7501 | if ( log.isDebugEnabled() ) |
484 | { |
|
485 | 0 | log.debug( array[curPos] + " is equal to " + obj ); |
486 | } |
|
487 | 7501 | greaterPos = curPos; |
488 | 7501 | done = true; |
489 | 7501 | break; |
490 | } |
|
491 | else |
|
492 | ||
493 | // GREATER THAN |
|
494 | // array object at current position is greater than the obj, go |
|
495 | // left |
|
496 | 78298 | if ( array[curPos].compareTo( obj ) > 0 ) |
497 | { |
|
498 | 26594 | if ( log.isDebugEnabled() ) |
499 | { |
|
500 | 0 | log.debug( array[curPos] + " is greater than " + obj ); |
501 | } |
|
502 | // set the smallest greater equal to the current position |
|
503 | 26594 | greaterPos = curPos; |
504 | // set the current position to |
|
505 | // set the previous position to the current position |
|
506 | // We could have an integer overflow, but this array could |
|
507 | // never get that large. |
|
508 | 26594 | int newPos = Math.min( curPos, ( curPos + prevPos ) / 2 ); |
509 | 26594 | prevPos = curPos; |
510 | 26594 | curPos = newPos; |
511 | 26564 | } |
512 | else |
|
513 | ||
514 | // LESS THAN |
|
515 | // the object at the current position is smaller, go right |
|
516 | 51704 | if ( array[curPos].compareTo( obj ) < 0 ) |
517 | { |
|
518 | 51704 | if ( log.isDebugEnabled() ) |
519 | { |
|
520 | 0 | log.debug( array[curPos] + " is less than " + obj ); |
521 | } |
|
522 | 51704 | if ( ( greaterPos != -1 ) && greaterPos - curPos < 0 ) |
523 | { |
|
524 | 0 | done = true; |
525 | 0 | break; // return greaterPos; |
526 | } |
|
527 | else |
|
528 | { |
|
529 | 51704 | int newPos = 0; |
530 | 51704 | if ( prevPos > curPos ) |
531 | { |
|
532 | 26994 | newPos = Math.min( ( curPos + prevPos ) / 2, curSize ); |
533 | 26845 | } |
534 | 24710 | else if ( prevPos == -1 ) |
535 | { |
|
536 | 5146 | newPos = Math.min( ( curSize + curPos ) / 2, curSize ); |
537 | } |
|
538 | 51704 | prevPos = curPos; |
539 | 51704 | curPos = newPos; |
540 | } |
|
541 | 51381 | } |
542 | } // end while |
|
543 | // ///////////////////////////////////////////////////////////////////// |
|
544 | ||
545 | 360275 | if ( log.isDebugEnabled() ) |
546 | { |
|
547 | 0 | log.debug( "Greater Position is [" + greaterPos + "]" + " array[greaterPos] [" + array[greaterPos] |
548 | + "]" ); |
|
549 | } |
|
550 | } |
|
551 | 0 | catch ( Exception e ) |
552 | { |
|
553 | 0 | log.error( "\n curPos = " + curPos + "; greaterPos = " + greaterPos + "; prevpos = " + prevPos + " " |
554 | + this.dumpArray(), e ); |
|
555 | 360171 | } |
556 | ||
557 | 360274 | return greaterPos; |
558 | } |
|
559 | ||
560 | /** |
|
561 | * Removes the item from the array at the specified position. The remaining items to the right |
|
562 | * are shifted left. |
|
563 | * <p> |
|
564 | * @param position int |
|
565 | * @throw IndexOutOfBoundsException if position is out of range. |
|
566 | */ |
|
567 | private void remove( int position ) |
|
568 | { |
|
569 | 116221 | if ( position >= curSize || position < 0 ) |
570 | { |
|
571 | 0 | throw new IndexOutOfBoundsException( "position=" + position + " must be less than curSize=" + curSize ); |
572 | } |
|
573 | 116221 | curSize--; |
574 | ||
575 | 116221 | if ( position < curSize ) |
576 | { |
|
577 | try |
|
578 | { |
|
579 | 8084 | System.arraycopy( array, position + 1, array, position, ( curSize - position ) ); |
580 | } |
|
581 | 0 | catch ( IndexOutOfBoundsException ibe ) |
582 | { |
|
583 | // throw this, log details for debugging. This shouldn't happen. |
|
584 | 0 | log.warn( "Caught index out of bounds exception. " |
585 | + "called 'System.arraycopy( array, position + 1, array, position, (curSize - position) );' " |
|
586 | + "array.lengh [" + array.length + "] position [" + position + "] curSize [" + curSize + "]" ); |
|
587 | 0 | throw ibe; |
588 | 8082 | } |
589 | } |
|
590 | 116221 | return; |
591 | } |
|
592 | ||
593 | /** |
|
594 | * Debugging method to return a human readable display of array data. |
|
595 | * <p> |
|
596 | * @return String representation of the contents. |
|
597 | */ |
|
598 | protected synchronized String dumpArray() |
|
599 | { |
|
600 | 576 | StringBuffer buf = new StringBuffer(); |
601 | 576 | buf.append( "\n ---------------------------" ); |
602 | 576 | buf.append( "\n curSize = " + curSize ); |
603 | 576 | buf.append( "\n array.length = " + array.length ); |
604 | 576 | buf.append( "\n ---------------------------" ); |
605 | 576 | buf.append( "\n Dump:" ); |
606 | 6312 | for ( int i = 0; i < curSize; i++ ) |
607 | { |
|
608 | 5736 | buf.append( "\n " + i + "=" + array[i] ); |
609 | } |
|
610 | 576 | return buf.toString(); |
611 | } |
|
612 | } |
This report is generated by jcoverage, Maven and Maven JCoverage Plugin. |