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 public class SortedPreferentialArray<T extends Comparable<? super T>>
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 final T[] array;
49
50 /** the number that have been inserted. */
51 private int insertCnt = 0;
52
53 /**
54 * Construct 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 = (T[]) 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(T 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 // insert if obj is larger than the smallest
85 T sma = getSmallest();
86 if ( obj.compareTo( sma ) > 0 )
87 {
88 insert( obj );
89 return;
90 }
91 // obj is less than or equal to the smallest.
92 if ( log.isDebugEnabled() )
93 {
94 log.debug( "New object is smaller than or equal to the smallest" );
95 }
96 return;
97 }
98 // Not preferLarge
99 T lar = getLargest();
100 // insert if obj is smaller than the largest
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 // obj is less than the largest.
111 insert( obj );
112 }
113
114 /**
115 * Returns the largest without removing it from the array.
116 * <p>
117 * @return Comparable
118 */
119 public synchronized T getLargest()
120 {
121 return array[curSize - 1];
122 }
123
124 /**
125 * Returns the smallest element without removing it from the array.
126 * <p>
127 * @return Comparable
128 */
129 public synchronized T getSmallest()
130 {
131 return array[0];
132 }
133
134 /**
135 * Insert looks for the nearest largest. It then determines which way to shuffle depending on
136 * the preference.
137 * <p>
138 * @param obj Comparable
139 */
140 private void insert(T obj)
141 {
142 try
143 {
144 int nLar = findNearestLargerEqualOrLastPosition( obj );
145 if ( log.isDebugEnabled() )
146 {
147 log.debug( "nLar = " + nLar + " obj = " + obj );
148 }
149
150 if ( nLar == curSize )
151 {
152 // this next check should be unnecessary
153 // findNearestLargerPosition should only return the curSize if
154 // there is
155 // room left. Check to be safe
156 if ( curSize < maxSize )
157 {
158 array[nLar] = obj;
159 curSize++;
160 if ( log.isDebugEnabled() )
161 {
162 log.debug( this.dumpArray() );
163 }
164 if ( log.isDebugEnabled() )
165 {
166 log.debug( "Inserted object at the end of the array" );
167 }
168 return;
169 } // end if not full
170 }
171
172 boolean isFull = false;
173 if ( curSize == maxSize )
174 {
175 isFull = true;
176 }
177
178 // The array is full, we must replace
179 // remove smallest or largest to determine whether to
180 // shuffle left or right to insert
181 if ( preferLarge )
182 {
183 if ( isFull )
184 {
185 // is full, prefer larger, remove smallest by shifting left
186 int pnt = nLar - 1; // set iteration stop point
187 for ( int i = 0; i < pnt; i++ )
188 {
189 array[i] = array[i + 1];
190 }
191 // use nLar-1 for insertion point
192 array[nLar - 1] = obj;
193 if ( log.isDebugEnabled() )
194 {
195 log.debug( "Inserted object at " + ( nLar - 1 ) );
196 }
197 }
198 else
199 {
200 // not full, shift right from spot
201 int pnt = nLar; // set iteration stop point
202 for ( int i = curSize; i > pnt; i-- )
203 {
204 array[i] = array[i - 1];
205 }
206 // use nLar-1 for insertion point
207 array[nLar] = obj;
208 curSize++;
209 if ( log.isDebugEnabled() )
210 {
211 log.debug( "Inserted object at " + ( nLar ) );
212 }
213 }
214 }
215 else
216 {
217 // prefer smaller, remove largest by shifting right
218 // use nLar for insertion point
219 int pnt = nLar + 1;
220 if ( !isFull )
221 {
222 pnt = nLar;
223 }
224 for ( int i = curSize; i > pnt; i-- )
225 {
226 array[i] = array[i - 1];
227 }
228 array[nLar] = obj;
229 if ( log.isDebugEnabled() )
230 {
231 log.debug( "Inserted object at " + nLar );
232 }
233 }
234
235 if ( log.isDebugEnabled() )
236 {
237 log.debug( this.dumpArray() );
238 }
239 }
240 catch ( Exception e )
241 {
242 log.error( "Insertion problem" + this.dumpArray(), e );
243 }
244
245 insertCnt++;
246 if ( insertCnt % 100 == 0 )
247 {
248 if ( log.isDebugEnabled() )
249 {
250 log.debug( this.dumpArray() );
251 }
252 }
253 }
254
255 /**
256 * Determines whether the preference is for large or small.
257 * <p>
258 * @param pref boolean
259 */
260 public synchronized void setPreferLarge( boolean pref )
261 {
262 preferLarge = pref;
263 }
264
265 /**
266 * Returns and removes the nearer larger or equal object from the aray.
267 * <p>
268 * @param obj Comparable
269 * @return Comparable, null if arg is null or none was found.
270 */
271 public synchronized T takeNearestLargerOrEqual( T obj )
272 {
273 if ( obj == null )
274 {
275 return null;
276 }
277
278 T retVal = null;
279 try
280 {
281 int pos = findNearestOccupiedLargerOrEqualPosition( obj );
282 if ( pos == -1 )
283 {
284 return null;
285 }
286
287 try
288 {
289 retVal = array[pos];
290 remove( pos );
291 }
292 catch ( Exception e )
293 {
294 log.error( "Problem removing from array. pos [" + pos + "] " + obj, e );
295 }
296
297 if ( log.isDebugEnabled() )
298 {
299 log.debug( "obj = " + obj + " || retVal = " + retVal );
300 }
301 }
302 catch ( Exception e )
303 {
304 log.error( "Take problem" + this.dumpArray(), e );
305 }
306 return retVal;
307 }
308
309 /**
310 * Returns the current size of the array.
311 * <p>
312 * @return int
313 */
314 public synchronized int size()
315 {
316 return this.curSize;
317 }
318
319 /**
320 * This determines the position in the array that is occupied by an object that is larger or
321 * equal to the argument. If none exists, -1 is returned.
322 * <p>
323 * @param obj Object
324 * @return Object
325 */
326 private int findNearestOccupiedLargerOrEqualPosition(T obj)
327 {
328 if ( curSize == 0 )
329 {
330 // nothing in the array
331 return -1;
332 }
333
334 // this gives us an insert position.
335 int pos = findNearestLargerEqualOrLastPosition( obj );
336
337 // see if the previous will do to handle the empty insert spot position
338 if ( pos == curSize )
339 { // && curSize < maxSize ) {
340 // pos will be > 0 if it equals curSize, we check for this above.
341 if ( obj.compareTo(array[pos - 1] ) <= 0 )
342 {
343 pos = pos - 1;
344 }
345 else
346 {
347 pos = -1;
348 }
349 }
350 else
351 {
352 // the find nearest, returns the last, since it is used by insertion.
353 if ( obj.compareTo(array[pos] ) > 0 )
354 {
355 return -1;
356 }
357 }
358
359 return pos;
360 }
361
362 /**
363 * This method determines the position where an insert should take place for a given object.
364 * With some additional checking, this can also be used to find an object matching or greater
365 * than the argument.
366 * <p>
367 * If the array is not full and the current object is larger than all the rest the first open
368 * slot at the end will be returned.
369 * <p>
370 * NOTE: If the object is larger than the largest and it is full, it will return the last position.
371 * <p>
372 * If the array is empty, the first spot is returned.
373 * <p>
374 * If the object is smaller than all the rests, the first position is returned. The caller must
375 * decide what to do given the preference.
376 * <p>
377 * Returns the position of the object nearest to or equal to the larger object.
378 * <p>
379 * If you want to find the takePosition, you have to calculate it.
380 * findNearestOccupiedLargerOrEqualPosition will calculate this for you.
381 * <p>
382 * @param obj Comparable
383 * @return int
384 */
385 private int findNearestLargerEqualOrLastPosition(T obj)
386 {
387 // do nothing if a null was passed in
388 if ( obj == null )
389 {
390 return -1;
391 }
392
393 // return the first spot if the array is empty
394 if ( curSize <= 0 )
395 {
396 return 0;
397 }
398
399 // mark the numer to be returned, the greaterPos as unset
400 int greaterPos = -1;
401 // prepare for a binary search
402 int curPos = ( curSize - 1 ) / 2;
403 int prevPos = -1;
404
405 try
406 {
407 // set the loop exit flag to false
408 boolean done = false;
409
410 // check the ends
411 // return insert position 0 if obj is smaller
412 // than the smallest. the caller can determine what to
413 // do with this, depending on the preference setting
414 if ( obj.compareTo( getSmallest() ) <= 0 )
415 {
416 // LESS THAN OR EQUAL TO SMALLEST
417 if ( log.isDebugEnabled() )
418 {
419 log.debug( obj + " is smaller than or equal to " + getSmallest() );
420 }
421 greaterPos = 0;
422 done = true;
423 // return greaterPos;
424 }
425 else
426 {
427 // GREATER THAN SMALLEST
428 if ( log.isDebugEnabled() )
429 {
430 log.debug( obj + " is bigger than " + getSmallest() );
431 }
432
433 // return the largest position if obj is larger
434 // than the largest. the caller can determine what to
435 // do with this, depending on the preference setting
436 if ( obj.compareTo( getLargest() ) >= 0 )
437 {
438 if ( curSize == maxSize )
439 {
440 // there is no room left in the array, return the last
441 // spot
442 greaterPos = curSize - 1;
443 done = true;
444 }
445 else
446 {
447 // there is room left in the array
448 greaterPos = curSize;
449 done = true;
450 }
451 }
452 else
453 {
454 // the obj is less than or equal to the largest, so we know that the
455 // last item is larger or equal
456 greaterPos = curSize - 1;
457 }
458 }
459
460 // /////////////////////////////////////////////////////////////////////
461 // begin binary search for insertion spot
462 while ( !done )
463 {
464 if ( log.isDebugEnabled() )
465 {
466 log.debug( "\n curPos = " + curPos + "; greaterPos = " + greaterPos + "; prevpos = " + prevPos );
467 }
468
469 // get out of loop if we have come to the end or passed it
470 if ( curPos == prevPos || curPos >= curSize )
471 {
472 done = true;
473 break;
474 }
475 else
476
477 // EQUAL TO
478 // object at current position is equal to the obj, use this,
479 // TODO could avoid some shuffling if I found a lower pos.
480 if ((array[curPos]).compareTo( obj ) == 0 )
481 {
482 if ( log.isDebugEnabled() )
483 {
484 log.debug( array[curPos] + " is equal to " + obj );
485 }
486 greaterPos = curPos;
487 done = true;
488 break;
489 }
490 else
491
492 // GREATER THAN
493 // array object at current position is greater than the obj, go
494 // left
495 if ((array[curPos]).compareTo( obj ) > 0 )
496 {
497 if ( log.isDebugEnabled() )
498 {
499 log.debug( array[curPos] + " is greater than " + obj );
500 }
501 // set the smallest greater equal to the current position
502 greaterPos = curPos;
503 // set the current position to
504 // set the previous position to the current position
505 // We could have an integer overflow, but this array could
506 // never get that large.
507 int newPos = Math.min( curPos, ( curPos + prevPos ) / 2 );
508 prevPos = curPos;
509 curPos = newPos;
510 }
511 else
512
513 // LESS THAN
514 // the object at the current position is smaller, go right
515 if ((array[curPos]).compareTo( obj ) < 0 )
516 {
517 if ( log.isDebugEnabled() )
518 {
519 log.debug( array[curPos] + " is less than " + obj );
520 }
521 if ( ( greaterPos != -1 ) && greaterPos - curPos < 0 )
522 {
523 done = true;
524 break; // return greaterPos;
525 }
526 else
527 {
528 int newPos = 0;
529 if ( prevPos > curPos )
530 {
531 newPos = Math.min( ( curPos + prevPos ) / 2, curSize );
532 }
533 else if ( prevPos == -1 )
534 {
535 newPos = Math.min( ( curSize + curPos ) / 2, curSize );
536 }
537 prevPos = curPos;
538 curPos = newPos;
539 }
540 }
541 } // end while
542 // /////////////////////////////////////////////////////////////////////
543
544 if ( log.isDebugEnabled() )
545 {
546 log.debug( "Greater Position is [" + greaterPos + "]" + " array[greaterPos] [" + array[greaterPos]
547 + "]" );
548 }
549 }
550 catch ( Exception e )
551 {
552 log.error( "\n curPos = " + curPos + "; greaterPos = " + greaterPos + "; prevpos = " + prevPos + " "
553 + this.dumpArray(), e );
554 }
555
556 return greaterPos;
557 }
558
559 /**
560 * Removes the item from the array at the specified position. The remaining items to the right
561 * are shifted left.
562 * <p>
563 * @param position int
564 * @throw IndexOutOfBoundsException if position is out of range.
565 */
566 private void remove( int position )
567 {
568 if ( position >= curSize || position < 0 )
569 {
570 throw new IndexOutOfBoundsException( "position=" + position + " must be less than curSize=" + curSize );
571 }
572 curSize--;
573
574 if ( position < curSize )
575 {
576 try
577 {
578 System.arraycopy( array, position + 1, array, position, ( curSize - position ) );
579 }
580 catch ( IndexOutOfBoundsException ibe )
581 {
582 // throw this, log details for debugging. This shouldn't happen.
583 log.warn( "Caught index out of bounds exception. "
584 + "called 'System.arraycopy( array, position + 1, array, position, (curSize - position) );' "
585 + "array.lengh [" + array.length + "] position [" + position + "] curSize [" + curSize + "]" );
586 throw ibe;
587 }
588 }
589 }
590
591 /**
592 * Debugging method to return a human readable display of array data.
593 * <p>
594 * @return String representation of the contents.
595 */
596 protected synchronized String dumpArray()
597 {
598 StringBuffer buf = new StringBuffer();
599 buf.append( "\n ---------------------------" );
600 buf.append( "\n curSize = " + curSize );
601 buf.append( "\n array.length = " + array.length );
602 buf.append( "\n ---------------------------" );
603 buf.append( "\n Dump:" );
604 for ( int i = 0; i < curSize; i++ )
605 {
606 buf.append( "\n " + i + "=" + array[i] );
607 }
608 return buf.toString();
609 }
610 }