1 package org.apache.jcs.utils.struct;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 public class SortedPreferentialArray
34 {
35 /*** The logger */
36 private static final Log log = LogFactory.getLog( SortedPreferentialArray.class );
37
38 /*** prefer large means that the smallest will be removed when full. */
39 private boolean preferLarge = true;
40
41 /*** maximum number allowed */
42 private int maxSize = 0;
43
44 /*** The currency number */
45 private int curSize = 0;
46
47 /*** The primary array */
48 private Comparable[] array;
49
50 /*** the number that have been inserted. */
51 private int insertCnt = 0;
52
53 /***
54 * Consruct the array with the maximum size.
55 * <p>
56 * @param maxSize int
57 */
58 public SortedPreferentialArray( int maxSize )
59 {
60 this.maxSize = maxSize;
61 array = new Comparable[maxSize];
62 }
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 if ( obj == null )
73 {
74 return;
75 }
76
77 if ( curSize < maxSize )
78 {
79 insert( obj );
80 return;
81 }
82 if ( preferLarge )
83 {
84
85 Comparable sma = getSmallest();
86 if ( obj.compareTo( sma ) > 0 )
87 {
88 insert( obj );
89 return;
90 }
91
92 if ( log.isDebugEnabled() )
93 {
94 log.debug( "New object is smaller than or equal to the smallest" );
95 }
96 return;
97 }
98
99 Comparable lar = getLargest();
100
101 int diff = obj.compareTo( lar );
102 if ( diff > 0 || diff == 0 )
103 {
104 if ( log.isDebugEnabled() )
105 {
106 log.debug( "New object is larger than or equal to the largest" );
107 }
108 return;
109 }
110
111 insert( obj );
112 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 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 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 int nLar = findNearestLargerEqualOrLastPosition( obj );
146 if ( log.isDebugEnabled() )
147 {
148 log.debug( "nLar = " + nLar + " obj = " + obj );
149 }
150
151 if ( nLar == curSize )
152 {
153
154
155
156
157 if ( curSize < maxSize )
158 {
159 array[nLar] = obj;
160 curSize++;
161 if ( log.isDebugEnabled() )
162 {
163 log.debug( this.dumpArray() );
164 }
165 if ( log.isDebugEnabled() )
166 {
167 log.debug( "Inserted object at the end of the array" );
168 }
169 return;
170 }
171 }
172
173 boolean isFull = false;
174 if ( curSize == maxSize )
175 {
176 isFull = true;
177 }
178
179
180
181
182 if ( preferLarge )
183 {
184 if ( isFull )
185 {
186
187 int pnt = nLar - 1;
188 for ( int i = 0; i < pnt; i++ )
189 {
190 array[i] = array[i + 1];
191 }
192
193 array[nLar - 1] = obj;
194 if ( log.isDebugEnabled() )
195 {
196 log.debug( "Inserted object at " + ( nLar - 1 ) );
197 }
198 }
199 else
200 {
201
202 int pnt = nLar;
203 for ( int i = curSize; i > pnt; i-- )
204 {
205 array[i] = array[i - 1];
206 }
207
208 array[nLar] = obj;
209 curSize++;
210 if ( log.isDebugEnabled() )
211 {
212 log.debug( "Inserted object at " + ( nLar ) );
213 }
214 }
215 }
216 else
217 {
218
219
220 int pnt = nLar + 1;
221 if ( !isFull )
222 {
223 pnt = nLar;
224 }
225 for ( int i = curSize; i > pnt; i-- )
226 {
227 array[i] = array[i - 1];
228 }
229 array[nLar] = obj;
230 if ( log.isDebugEnabled() )
231 {
232 log.debug( "Inserted object at " + nLar );
233 }
234 }
235
236 if ( log.isDebugEnabled() )
237 {
238 log.debug( this.dumpArray() );
239 }
240 }
241 catch ( Exception e )
242 {
243 log.error( "Insertion problem" + this.dumpArray(), e );
244 }
245
246 insertCnt++;
247 if ( insertCnt % 100 == 0 )
248 {
249 if ( log.isDebugEnabled() )
250 {
251 log.debug( this.dumpArray() );
252 }
253 }
254 }
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 preferLarge = pref;
264 }
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 if ( obj == null )
275 {
276 return null;
277 }
278
279 Comparable retVal = null;
280 try
281 {
282 int pos = findNearestOccupiedLargerOrEqualPosition( obj );
283 if ( pos == -1 )
284 {
285 return null;
286 }
287
288 try
289 {
290 retVal = array[pos];
291 remove( pos );
292 }
293 catch ( Exception e )
294 {
295 log.error( "Problem removing from array. pos [" + pos + "] " + obj, e );
296 }
297
298 if ( log.isDebugEnabled() )
299 {
300 log.debug( "obj = " + obj + " || retVal = " + retVal );
301 }
302 }
303 catch ( Exception e )
304 {
305 log.error( "Take problem" + this.dumpArray(), e );
306 }
307 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 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 if ( curSize == 0 )
330 {
331
332 return -1;
333 }
334
335
336 int pos = findNearestLargerEqualOrLastPosition( obj );
337
338
339 if ( pos == curSize )
340 {
341
342 if ( obj.compareTo( array[pos - 1] ) <= 0 )
343 {
344 pos = pos - 1;
345 }
346 else
347 {
348 pos = -1;
349 }
350 }
351 else
352 {
353
354 if ( obj.compareTo( array[pos] ) > 0 )
355 {
356 return -1;
357 }
358 }
359
360 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
389 if ( obj == null )
390 {
391 return -1;
392 }
393
394
395 if ( curSize <= 0 )
396 {
397 return 0;
398 }
399
400
401 int greaterPos = -1;
402
403 int curPos = ( curSize - 1 ) / 2;
404 int prevPos = -1;
405
406 try
407 {
408
409 boolean done = false;
410
411
412
413
414
415 if ( obj.compareTo( getSmallest() ) <= 0 )
416 {
417
418 if ( log.isDebugEnabled() )
419 {
420 log.debug( obj + " is smaller than or equal to " + getSmallest() );
421 }
422 greaterPos = 0;
423 done = true;
424
425 }
426 else
427 {
428
429 if ( log.isDebugEnabled() )
430 {
431 log.debug( obj + " is bigger than " + getSmallest() );
432 }
433
434
435
436
437 if ( obj.compareTo( getLargest() ) >= 0 )
438 {
439 if ( curSize == maxSize )
440 {
441
442
443 greaterPos = curSize - 1;
444 done = true;
445 }
446 else
447 {
448
449 greaterPos = curSize;
450 done = true;
451 }
452 }
453 else
454 {
455
456
457 greaterPos = curSize - 1;
458 }
459 }
460
461
462
463 while ( !done )
464 {
465 if ( log.isDebugEnabled() )
466 {
467 log.debug( "\n curPos = " + curPos + "; greaterPos = " + greaterPos + "; prevpos = " + prevPos );
468 }
469
470
471 if ( curPos == prevPos || curPos >= curSize )
472 {
473 done = true;
474 break;
475 }
476 else
477
478
479
480
481 if ( array[curPos].compareTo( obj ) == 0 )
482 {
483 if ( log.isDebugEnabled() )
484 {
485 log.debug( array[curPos] + " is equal to " + obj );
486 }
487 greaterPos = curPos;
488 done = true;
489 break;
490 }
491 else
492
493
494
495
496 if ( array[curPos].compareTo( obj ) > 0 )
497 {
498 if ( log.isDebugEnabled() )
499 {
500 log.debug( array[curPos] + " is greater than " + obj );
501 }
502
503 greaterPos = curPos;
504
505
506
507
508 int newPos = Math.min( curPos, ( curPos + prevPos ) / 2 );
509 prevPos = curPos;
510 curPos = newPos;
511 }
512 else
513
514
515
516 if ( array[curPos].compareTo( obj ) < 0 )
517 {
518 if ( log.isDebugEnabled() )
519 {
520 log.debug( array[curPos] + " is less than " + obj );
521 }
522 if ( ( greaterPos != -1 ) && greaterPos - curPos < 0 )
523 {
524 done = true;
525 break;
526 }
527 else
528 {
529 int newPos = 0;
530 if ( prevPos > curPos )
531 {
532 newPos = Math.min( ( curPos + prevPos ) / 2, curSize );
533 }
534 else if ( prevPos == -1 )
535 {
536 newPos = Math.min( ( curSize + curPos ) / 2, curSize );
537 }
538 prevPos = curPos;
539 curPos = newPos;
540 }
541 }
542 }
543
544
545 if ( log.isDebugEnabled() )
546 {
547 log.debug( "Greater Position is [" + greaterPos + "]" + " array[greaterPos] [" + array[greaterPos]
548 + "]" );
549 }
550 }
551 catch ( Exception e )
552 {
553 log.error( "\n curPos = " + curPos + "; greaterPos = " + greaterPos + "; prevpos = " + prevPos + " "
554 + this.dumpArray(), e );
555 }
556
557 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 if ( position >= curSize || position < 0 )
570 {
571 throw new IndexOutOfBoundsException( "position=" + position + " must be less than curSize=" + curSize );
572 }
573 curSize--;
574
575 if ( position < curSize )
576 {
577 try
578 {
579 System.arraycopy( array, position + 1, array, position, ( curSize - position ) );
580 }
581 catch ( IndexOutOfBoundsException ibe )
582 {
583
584 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 throw ibe;
588 }
589 }
590 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 StringBuffer buf = new StringBuffer();
601 buf.append( "\n ---------------------------" );
602 buf.append( "\n curSize = " + curSize );
603 buf.append( "\n array.length = " + array.length );
604 buf.append( "\n ---------------------------" );
605 buf.append( "\n Dump:" );
606 for ( int i = 0; i < curSize; i++ )
607 {
608 buf.append( "\n " + i + "=" + array[i] );
609 }
610 return buf.toString();
611 }
612 }