| package org.apache.jcs.utils.struct; |
| |
| /* |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| */ |
| |
| import org.apache.commons.logging.Log; |
| import org.apache.commons.logging.LogFactory; |
| |
| /** |
| * This maintains a sorted array with a preferential replacement policy when full. |
| * <p> |
| * Insertion time is n, search is log(n) |
| * <p> |
| * Clients must manage thread safety on previous version. I synchronized the public methods to add |
| * easy thread safety. I synchronized all public methods that make modifications. |
| */ |
| public class SortedPreferentialArray |
| { |
| /** The logger */ |
| private static final Log log = LogFactory.getLog( SortedPreferentialArray.class ); |
| |
| /** prefer large means that the smallest will be removed when full. */ |
| private boolean preferLarge = true; |
| |
| /** maximum number allowed */ |
| private int maxSize = 0; |
| |
| /** The currency number */ |
| private int curSize = 0; |
| |
| /** The primary array */ |
| private Comparable[] array; |
| |
| /** the number that have been inserted. */ |
| private int insertCnt = 0; |
| |
| /** |
| * Consruct the array with the maximum size. |
| * <p> |
| * @param maxSize int |
| */ |
| public SortedPreferentialArray( int maxSize ) |
| { |
| this.maxSize = maxSize; |
| array = new Comparable[maxSize]; |
| } |
| |
| /** |
| * If the array is full this will remove the smallest if preferLarge==true and if obj is bigger, |
| * or the largest if preferLarge=false and obj is smaller than the largest. |
| * <p> |
| * @param obj Object |
| */ |
| public synchronized void add( Comparable obj ) |
| { |
| if ( obj == null ) |
| { |
| return; |
| } |
| |
| if ( curSize < maxSize ) |
| { |
| insert( obj ); |
| return; |
| } |
| if ( preferLarge ) |
| { |
| // insert if obj is larger than the smallest |
| Comparable sma = getSmallest(); |
| if ( obj.compareTo( sma ) > 0 ) |
| { |
| insert( obj ); |
| return; |
| } |
| // obj is less than or equal to the smallest. |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( "New object is smaller than or equal to the smallest" ); |
| } |
| return; |
| } |
| // Not preferLarge |
| Comparable lar = getLargest(); |
| // insert if obj is smaller than the largest |
| int diff = obj.compareTo( lar ); |
| if ( diff > 0 || diff == 0 ) |
| { |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( "New object is larger than or equal to the largest" ); |
| } |
| return; |
| } |
| // obj is less than the largest. |
| insert( obj ); |
| return; |
| } |
| |
| /** |
| * Returns the largest without removing it from the array. |
| * <p> |
| * @return Comparable |
| */ |
| public synchronized Comparable getLargest() |
| { |
| return array[curSize - 1]; |
| } |
| |
| /** |
| * Returns the smallest element without removing it from the array. |
| * <p> |
| * @return Comparable |
| */ |
| public synchronized Comparable getSmallest() |
| { |
| return array[0]; |
| } |
| |
| /** |
| * Insert looks for the nearest largest. It then determines which way to shuffle depending on |
| * the preference. |
| * <p> |
| * @param obj Comparable |
| */ |
| private void insert( Comparable obj ) |
| { |
| try |
| { |
| int nLar = findNearestLargerEqualOrLastPosition( obj ); |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( "nLar = " + nLar + " obj = " + obj ); |
| } |
| |
| if ( nLar == curSize ) |
| { |
| // this next check should be unnecessary |
| // findNearestLargerPosition should only return the curSize if |
| // there is |
| // room left. Check to be safe |
| if ( curSize < maxSize ) |
| { |
| array[nLar] = obj; |
| curSize++; |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( this.dumpArray() ); |
| } |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( "Inserted object at the end of the array" ); |
| } |
| return; |
| } // end if not full |
| } |
| |
| boolean isFull = false; |
| if ( curSize == maxSize ) |
| { |
| isFull = true; |
| } |
| |
| // The array is full, we must replace |
| // remove smallest or largest to determine whether to |
| // shuffle left or right to insert |
| if ( preferLarge ) |
| { |
| if ( isFull ) |
| { |
| // is full, prefer larger, remove smallest by shifting left |
| int pnt = nLar - 1; // set iteration stop point |
| for ( int i = 0; i < pnt; i++ ) |
| { |
| array[i] = array[i + 1]; |
| } |
| // use nLar-1 for insertion point |
| array[nLar - 1] = obj; |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( "Inserted object at " + ( nLar - 1 ) ); |
| } |
| } |
| else |
| { |
| // not full, shift right from spot |
| int pnt = nLar; // set iteration stop point |
| for ( int i = curSize; i > pnt; i-- ) |
| { |
| array[i] = array[i - 1]; |
| } |
| // use nLar-1 for insertion point |
| array[nLar] = obj; |
| curSize++; |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( "Inserted object at " + ( nLar ) ); |
| } |
| } |
| } |
| else |
| { |
| // prefer smaller, remove largest by shifting right |
| // use nLar for insertion point |
| int pnt = nLar + 1; |
| if ( !isFull ) |
| { |
| pnt = nLar; |
| } |
| for ( int i = curSize; i > pnt; i-- ) |
| { |
| array[i] = array[i - 1]; |
| } |
| array[nLar] = obj; |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( "Inserted object at " + nLar ); |
| } |
| } |
| |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( this.dumpArray() ); |
| } |
| } |
| catch ( Exception e ) |
| { |
| log.error( "Insertion problem" + this.dumpArray(), e ); |
| } |
| |
| insertCnt++; |
| if ( insertCnt % 100 == 0 ) |
| { |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( this.dumpArray() ); |
| } |
| } |
| } |
| |
| /** |
| * Determines whether the preference is for large or small. |
| * <p> |
| * @param pref boolean |
| */ |
| public synchronized void setPreferLarge( boolean pref ) |
| { |
| preferLarge = pref; |
| } |
| |
| /** |
| * Returns and removes the nearer larger or equal object from the aray. |
| * <p> |
| * @param obj Comparable |
| * @return Comparable, null if arg is null or none was found. |
| */ |
| public synchronized Comparable takeNearestLargerOrEqual( Comparable obj ) |
| { |
| if ( obj == null ) |
| { |
| return null; |
| } |
| |
| Comparable retVal = null; |
| try |
| { |
| int pos = findNearestOccupiedLargerOrEqualPosition( obj ); |
| if ( pos == -1 ) |
| { |
| return null; |
| } |
| |
| try |
| { |
| retVal = array[pos]; |
| remove( pos ); |
| } |
| catch ( Exception e ) |
| { |
| log.error( "Problem removing from array. pos [" + pos + "] " + obj, e ); |
| } |
| |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( "obj = " + obj + " || retVal = " + retVal ); |
| } |
| } |
| catch ( Exception e ) |
| { |
| log.error( "Take problem" + this.dumpArray(), e ); |
| } |
| return retVal; |
| } |
| |
| /** |
| * Returns the current size of the array. |
| * <p> |
| * @return int |
| */ |
| public synchronized int size() |
| { |
| return this.curSize; |
| } |
| |
| /** |
| * This determines the position in the array that is occupied by an object that is larger or |
| * equal to the argument. If none exists, -1 is returned. |
| * <p> |
| * @param obj Object |
| * @return Object |
| */ |
| private int findNearestOccupiedLargerOrEqualPosition( Comparable obj ) |
| { |
| if ( curSize == 0 ) |
| { |
| // nothing in the array |
| return -1; |
| } |
| |
| // this gives us an insert position. |
| int pos = findNearestLargerEqualOrLastPosition( obj ); |
| |
| // see if the previous will do to handle the empty insert spot position |
| if ( pos == curSize ) |
| { // && curSize < maxSize ) { |
| // pos will be > 0 if it equals curSize, we check for this above. |
| if ( obj.compareTo( array[pos - 1] ) <= 0 ) |
| { |
| pos = pos - 1; |
| } |
| else |
| { |
| pos = -1; |
| } |
| } |
| else |
| { |
| // the find nearest, returns the last, since it is used by insertion. |
| if ( obj.compareTo( array[pos] ) > 0 ) |
| { |
| return -1; |
| } |
| } |
| |
| return pos; |
| } |
| |
| /** |
| * This method determines the position where an insert should take place for a given object. |
| * With some additional checking, this can also be used to find an object matching or greater |
| * than the argument. |
| * <p> |
| * If the array is not full and the current object is larger than all the rest the first open |
| * slot at the end will be returned. |
| * <p> |
| * NOTE: If the object is larger than the largest and it is full, it will return the last position. |
| * <p> |
| * If the array is empty, the first spot is returned. |
| * <p> |
| * If the object is smaller than all the rests, the first position is returned. The caller must |
| * decide what to do given the preference. |
| * <p> |
| * Returns the position of the object nearest to or equal to the larger object. |
| * <p> |
| * If you want to find the takePosition, you have to calculate it. |
| * findNearestOccupiedLargerOrEqualPosition will calculate this for you. |
| * <p> |
| * @param obj Comparable |
| * @return int |
| */ |
| private int findNearestLargerEqualOrLastPosition( Comparable obj ) |
| { |
| // do nothing if a null was passed in |
| if ( obj == null ) |
| { |
| return -1; |
| } |
| |
| // return the first spot if the array is empty |
| if ( curSize <= 0 ) |
| { |
| return 0; |
| } |
| |
| // mark the numer to be returned, the greaterPos as unset |
| int greaterPos = -1; |
| // prepare for a binary search |
| int curPos = ( curSize - 1 ) / 2; |
| int prevPos = -1; |
| |
| try |
| { |
| // set the loop exit flag to false |
| boolean done = false; |
| |
| // check the ends |
| // return insert position 0 if obj is smaller |
| // than the smallest. the caller can determine what to |
| // do with this, depending on the preference setting |
| if ( obj.compareTo( getSmallest() ) <= 0 ) |
| { |
| // LESS THAN OR EQUAL TO SMALLEST |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( obj + " is smaller than or equal to " + getSmallest() ); |
| } |
| greaterPos = 0; |
| done = true; |
| // return greaterPos; |
| } |
| else |
| { |
| // GREATER THAN SMALLEST |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( obj + " is bigger than " + getSmallest() ); |
| } |
| |
| // return the largest position if obj is larger |
| // than the largest. the caller can determine what to |
| // do with this, depending on the preference setting |
| if ( obj.compareTo( getLargest() ) >= 0 ) |
| { |
| if ( curSize == maxSize ) |
| { |
| // there is no room left in the array, return the last |
| // spot |
| greaterPos = curSize - 1; |
| done = true; |
| } |
| else |
| { |
| // there is room left in the array |
| greaterPos = curSize; |
| done = true; |
| } |
| } |
| else |
| { |
| // the obj is less than or equal to the largest, so we know that the |
| // last item is larger or equal |
| greaterPos = curSize - 1; |
| } |
| } |
| |
| // ///////////////////////////////////////////////////////////////////// |
| // begin binary search for insertion spot |
| while ( !done ) |
| { |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( "\n curPos = " + curPos + "; greaterPos = " + greaterPos + "; prevpos = " + prevPos ); |
| } |
| |
| // get out of loop if we have come to the end or passed it |
| if ( curPos == prevPos || curPos >= curSize ) |
| { |
| done = true; |
| break; |
| } |
| else |
| |
| // EQUAL TO |
| // object at current position is equal to the obj, use this, |
| // TODO could avoid some shuffling if I found a lower pos. |
| if ( array[curPos].compareTo( obj ) == 0 ) |
| { |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( array[curPos] + " is equal to " + obj ); |
| } |
| greaterPos = curPos; |
| done = true; |
| break; |
| } |
| else |
| |
| // GREATER THAN |
| // array object at current position is greater than the obj, go |
| // left |
| if ( array[curPos].compareTo( obj ) > 0 ) |
| { |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( array[curPos] + " is greater than " + obj ); |
| } |
| // set the smallest greater equal to the current position |
| greaterPos = curPos; |
| // set the current position to |
| // set the previous position to the current position |
| // We could have an integer overflow, but this array could |
| // never get that large. |
| int newPos = Math.min( curPos, ( curPos + prevPos ) / 2 ); |
| prevPos = curPos; |
| curPos = newPos; |
| } |
| else |
| |
| // LESS THAN |
| // the object at the current position is smaller, go right |
| if ( array[curPos].compareTo( obj ) < 0 ) |
| { |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( array[curPos] + " is less than " + obj ); |
| } |
| if ( ( greaterPos != -1 ) && greaterPos - curPos < 0 ) |
| { |
| done = true; |
| break; // return greaterPos; |
| } |
| else |
| { |
| int newPos = 0; |
| if ( prevPos > curPos ) |
| { |
| newPos = Math.min( ( curPos + prevPos ) / 2, curSize ); |
| } |
| else if ( prevPos == -1 ) |
| { |
| newPos = Math.min( ( curSize + curPos ) / 2, curSize ); |
| } |
| prevPos = curPos; |
| curPos = newPos; |
| } |
| } |
| } // end while |
| // ///////////////////////////////////////////////////////////////////// |
| |
| if ( log.isDebugEnabled() ) |
| { |
| log.debug( "Greater Position is [" + greaterPos + "]" + " array[greaterPos] [" + array[greaterPos] |
| + "]" ); |
| } |
| } |
| catch ( Exception e ) |
| { |
| log.error( "\n curPos = " + curPos + "; greaterPos = " + greaterPos + "; prevpos = " + prevPos + " " |
| + this.dumpArray(), e ); |
| } |
| |
| return greaterPos; |
| } |
| |
| /** |
| * Removes the item from the array at the specified position. The remaining items to the right |
| * are shifted left. |
| * <p> |
| * @param position int |
| * @throw IndexOutOfBoundsException if position is out of range. |
| */ |
| private void remove( int position ) |
| { |
| if ( position >= curSize || position < 0 ) |
| { |
| throw new IndexOutOfBoundsException( "position=" + position + " must be less than curSize=" + curSize ); |
| } |
| curSize--; |
| |
| if ( position < curSize ) |
| { |
| try |
| { |
| System.arraycopy( array, position + 1, array, position, ( curSize - position ) ); |
| } |
| catch ( IndexOutOfBoundsException ibe ) |
| { |
| // throw this, log details for debugging. This shouldn't happen. |
| log.warn( "Caught index out of bounds exception. " |
| + "called 'System.arraycopy( array, position + 1, array, position, (curSize - position) );' " |
| + "array.lengh [" + array.length + "] position [" + position + "] curSize [" + curSize + "]" ); |
| throw ibe; |
| } |
| } |
| return; |
| } |
| |
| /** |
| * Debugging method to return a human readable display of array data. |
| * <p> |
| * @return String representation of the contents. |
| */ |
| protected synchronized String dumpArray() |
| { |
| StringBuffer buf = new StringBuffer(); |
| buf.append( "\n ---------------------------" ); |
| buf.append( "\n curSize = " + curSize ); |
| buf.append( "\n array.length = " + array.length ); |
| buf.append( "\n ---------------------------" ); |
| buf.append( "\n Dump:" ); |
| for ( int i = 0; i < curSize; i++ ) |
| { |
| buf.append( "\n " + i + "=" + array[i] ); |
| } |
| return buf.toString(); |
| } |
| } |