View Javadoc

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
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              // insert if obj is larger than the smallest
85              Comparable 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          Comparable 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         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                 // 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                 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                 } // end if not full
171             }
172 
173             boolean isFull = false;
174             if ( curSize == maxSize )
175             {
176                 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             if ( preferLarge )
183             {
184                 if ( isFull )
185                 {
186                     // is full, prefer larger, remove smallest by shifting left
187                     int pnt = nLar - 1; // set iteration stop point
188                     for ( int i = 0; i < pnt; i++ )
189                     {
190                         array[i] = array[i + 1];
191                     }
192                     // use nLar-1 for insertion point
193                     array[nLar - 1] = obj;
194                     if ( log.isDebugEnabled() )
195                     {
196                         log.debug( "Inserted object at " + ( nLar - 1 ) );
197                     }
198                 }
199                 else
200                 {
201                     // not full, shift right from spot
202                     int pnt = nLar; // set iteration stop point
203                     for ( int i = curSize; i > pnt; i-- )
204                     {
205                         array[i] = array[i - 1];
206                     }
207                     // use nLar-1 for insertion point
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                 // prefer smaller, remove largest by shifting right
219                 // use nLar for insertion point
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             // nothing in the array
332             return -1;
333         }
334 
335         // this gives us an insert position.
336         int pos = findNearestLargerEqualOrLastPosition( obj );
337 
338         // see if the previous will do to handle the empty insert spot position
339         if ( pos == curSize )
340         { // && curSize < maxSize ) {
341             // pos will be > 0 if it equals curSize, we check for this above.
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             // the find nearest, returns the last, since it is used by insertion.
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         // do nothing if a null was passed in
389         if ( obj == null )
390         {
391             return -1;
392         }
393 
394         // return the first spot if the array is empty
395         if ( curSize <= 0 )
396         {
397             return 0;
398         }
399 
400         // mark the numer to be returned, the greaterPos as unset
401         int greaterPos = -1;
402         // prepare for a binary search
403         int curPos = ( curSize - 1 ) / 2;
404         int prevPos = -1;
405 
406         try
407         {
408             // set the loop exit flag to false
409             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             if ( obj.compareTo( getSmallest() ) <= 0 )
416             {
417                 // LESS THAN OR EQUAL TO SMALLEST
418                 if ( log.isDebugEnabled() )
419                 {
420                     log.debug( obj + " is smaller than or equal to " + getSmallest() );
421                 }
422                 greaterPos = 0;
423                 done = true;
424                 // return greaterPos;
425             }
426             else
427             {
428                 // GREATER THAN SMALLEST
429                 if ( log.isDebugEnabled() )
430                 {
431                     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                 if ( obj.compareTo( getLargest() ) >= 0 )
438                 {
439                     if ( curSize == maxSize )
440                     {
441                         // there is no room left in the array, return the last
442                         // spot
443                         greaterPos = curSize - 1;
444                         done = true;
445                     }
446                     else
447                     {
448                         // there is room left in the array
449                         greaterPos = curSize;
450                         done = true;
451                     }
452                 }
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                     greaterPos = curSize - 1;
458                 }
459             }
460 
461             // /////////////////////////////////////////////////////////////////////
462             // begin binary search for insertion spot
463             while ( !done )
464             {
465                 if ( log.isDebugEnabled() )
466                 {
467                     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                 if ( curPos == prevPos || curPos >= curSize )
472                 {
473                     done = true;
474                     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                 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                 // GREATER THAN
494                 // array object at current position is greater than the obj, go
495                 // left
496                 if ( array[curPos].compareTo( obj ) > 0 )
497                 {
498                     if ( log.isDebugEnabled() )
499                     {
500                         log.debug( array[curPos] + " is greater than " + obj );
501                     }
502                     // set the smallest greater equal to the current position
503                     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                     int newPos = Math.min( curPos, ( curPos + prevPos ) / 2 );
509                     prevPos = curPos;
510                     curPos = newPos;
511                 }
512                 else
513 
514                 // LESS THAN
515                 // the object at the current position is smaller, go right
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; // return greaterPos;
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             } // end while
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                 // throw this, log details for debugging. This shouldn't happen.
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 }