asmuts 2004/07/15 18:28:22
Modified: src/java/org/apache/jcs/utils/struct
SortedPreferentialArray.java
Log:
working without problems, could be two operations more efficient
testing method in main
Revision Changes Path
1.2 +285 -123
jakarta-turbine-jcs/src/java/org/apache/jcs/utils/struct/SortedPreferentialArray.java
Index: SortedPreferentialArray.java
===================================================================
RCS file:
/home/cvs/jakarta-turbine-jcs/src/java/org/apache/jcs/utils/struct/SortedPreferentialArray.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- SortedPreferentialArray.java 14 Jul 2004 03:33:05 -0000 1.1
+++ SortedPreferentialArray.java 16 Jul 2004 01:28:22 -0000 1.2
@@ -1,5 +1,21 @@
package org.apache.jcs.utils.struct;
+/*
+ * Copyright 2001-2004 The Apache Software Foundation.
+ *
+ * Licensed 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;
@@ -19,12 +35,14 @@
private static final Log log =
LogFactory.getLog(SortedPreferentialArray.class);
- // prefer large means that the smalles will be removed when full.
+ // prefer large means that the smallest will be removed when full.
private boolean preferLarge = true;
private int maxSize = 0;
private int curSize = 0;
private Comparable[] array;
+ private int insertCnt = 0;
+
/**
* Consruct the array with the maximum size.
*
@@ -113,84 +131,115 @@
*/
private void insert(Comparable obj)
{
- int nLar = findNearestLargerPositionForInsert(obj);
-
- if (nLar == curSize)
+ try
{
- // this next check should be unnecessary
- // findNearestLargerPosition should only return the curSize if there is
- // room left. Check to be safe
- if (curSize < maxSize)
+ int nLar = findNearestLargerOrEqualPosition(obj);
+ if (log.isDebugEnabled())
{
- array[curSize] = obj;
- curSize++;
- if (log.isDebugEnabled())
- {
- log.debug(this.dumpArray());
- }
- if (log.isDebugEnabled())
- {
- log.debug("Inserted object at the end of the array");
- }
- return;
+ log.debug("nLar = " + nLar + " obj = " + obj);
}
- } // 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)
- {
- // prefer larger, remove smallest by shifting left
- // use nLar-1 for insertion point
- int pnt = nLar;
- if (!isFull)
+ if (nLar == curSize)
{
- pnt = nLar + 1;
- }
- for (int i = 0; i < pnt; i++)
- {
- array[i] = array[i + 1];
+ // 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
}
- array[nLar - 1] = obj;
- if (log.isDebugEnabled())
+
+ boolean isFull = false;
+ if (curSize == maxSize)
{
- log.debug("Inserted object at " + (nLar - 1));
+ isFull = true;
}
- }
- else
- {
- // prefer smaller, remove largest by shifting right
- // use nLar for insertion point
- int pnt = nLar + 1;
- if (!isFull)
+
+ // The array is full, we must replace
+ // remove smallest or largest to determine whether to
+ // shuffle left or right to insert
+ if (preferLarge)
{
- pnt = nLar;
+ 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));
+ }
+ }
}
- for (int i = curSize - 1; i > pnt; i--)
+ else
{
- array[i] = array[i - 1];
+ // 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);
+ }
}
- array[nLar] = obj;
+
if (log.isDebugEnabled())
{
- log.debug("Inserted object at " + nLar);
+ log.debug(this.dumpArray());
}
}
+ catch (Exception e)
+ {
+ log.error("Insertion problem" + this.dumpArray(), e);
+ }
- //} // end if full
-
- // TODO handle case where the new item is less than the largest and the
- // array is not full.
-
- if (log.isDebugEnabled())
+ insertCnt++;
+ if (insertCnt % 100 == 0)
{
- log.debug(this.dumpArray());
+ if (log.isInfoEnabled())
+ {
+ log.info(this.dumpArray());
+ }
}
} // end insert
@@ -198,7 +247,6 @@
/**
* Determines whether the preference is for large or small.
*
- *
* @param pref boolean
*/
public void setPreferLarge(boolean pref)
@@ -207,39 +255,48 @@
}
/**
- * Returns and removes the nearerLarger from the aray
+ * Returns and removes the nearer larger or equal object from the aray.
*
* @param obj Comparable
* @return Comparable
*/
public Comparable takeNearestLargerOrEqual(Comparable obj)
{
- int pos = findNearestOccupiedLargerOrEqualPosition(obj);
- if (pos == -1)
- {
- return null;
- }
-
Comparable retVal = null;
try
{
- retVal = array[pos];
- remove(pos);
+ int pos = findNearestOccupiedLargerOrEqualPosition(obj);
+ if (pos == -1)
+ {
+ return null;
+ }
+
+ try
+ {
+ retVal = array[pos];
+ remove(pos);
+ }
+ catch (Exception e)
+ {
+ log.error(e);
+ }
+
+ if (log.isDebugEnabled())
+ {
+ log.debug("obj = " + obj + " || retVal = " + retVal);
+ }
}
catch (Exception e)
{
- log.error(e);
- }
-
- if (log.isDebugEnabled())
- {
- log.debug("obj = " + obj + " || retVal = " + retVal);
+ log.error("Take problem" + this.dumpArray(), e);
}
-
return retVal;
}
/**
+ * 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.
*
* @param obj Object
* @return Object
@@ -253,7 +310,7 @@
}
// this gives us an insert position.
- int pos = findNearestLargerPositionForInsert(obj);
+ int pos = findNearestLargerOrEqualPosition(obj);
// see if the previous will do to handle the empty insert spot position
if (pos == curSize)
{ //&& curSize < maxSize ) {
@@ -270,114 +327,165 @@
return pos;
}
- private void remove(int position)
- {
- // suffle left from removal point
- for (int i = position; i < curSize - 1; i++)
- {
- array[i] = array[i + 1];
- }
- curSize--;
- }
-
/**
+ * 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.
+ *
* 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.
*
- * If you want to find the takePosition, you have to calculate it.
- *
* If the object is larger than the largest and it is full, it
* will return the last position.
*
- * Returns the position of the nearest to or equal to the larger object.
- * Returns -1 if the object is null.
+ * If the array is empty, the first spot is returned.
+ *
+ * If the object is smaller than all the rests, the first position is
+ * returned. The caller must decide what to do given the preference.
+ *
+ * Returns the position of the object nearest to or equal to the larger object.
+ *
+ * If you want to find the takePosition, you have to calculate it.
+ * findNearestOccupiedLargerOrEqualPosition will calculate this for you
*
* @param obj Comparable
* @return int
*/
- private int findNearestLargerPositionForInsert(Comparable obj)
+ private int findNearestLargerOrEqualPosition(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
{
-
- int curPos = (curSize - 1) / 2;
- int prevPos = -1;
+ // 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;
}
-
- if (obj.compareTo(getLargest()) >= 0)
+ else
{
- if (curSize == maxSize)
+ //GREATER THAN SMALLEST
+ if (log.isDebugEnabled())
{
- greaterPos = curSize - 1;
- done = true;
+ 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
{
- greaterPos = curSize;
- done = true;
+ // the obj is less than the largest, so we know that the last
+ // item is larger
+ greaterPos = curSize - 1;
}
}
- else
- {
- greaterPos = curSize - 1;
- }
+ ///////////////////////////////////////////////////////////////////////
+ // begin binary search for insertion spot
while (!done)
{
if (log.isDebugEnabled())
{
- log.debug("curPos = " + curPos + "; greaterPos = " + greaterPos +
+ log.debug("\n curPos = " + curPos + "; greaterPos = " + greaterPos +
"; prevpos = " + prevPos);
}
- if (curPos == prevPos)
+ // get out of loop if we have come to the end or passed it
+ if (curPos == prevPos || curPos >= curSize)
{
done = true;
break;
}
- // object at current position is equakl to the obj, use this,
+ 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;
}
- // object at current position is greater than the obj, go left
- if (array[curPos].compareTo(obj) >= 0)
+ else
+
+ // GREATER THAN
+ // array object at current position is greater than the obj, go left
+ if (array[curPos].compareTo(obj) > 0)
{
- // set the smalelst greater equal to the current position
+ 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
- int newPos = curPos + prevPos / 2;
+ 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)
{
- // the object at the current position is smaller, go right
- if ( ( (greaterPos != -1) && greaterPos - curPos < 0))
+ if (log.isDebugEnabled())
+ {
+ log.debug(array[curPos] + " is less than " + obj);
+ }
+ if ( (greaterPos != -1) && greaterPos - curPos < 0)
{
done = true;
break; //return greaterPos;
@@ -387,35 +495,61 @@
int newPos = 0;
if (prevPos > curPos)
{
- newPos = (curPos + prevPos) / 2;
+ newPos = Math.min( (curPos + prevPos) / 2, curSize);
}
else
if (prevPos == -1)
{
- newPos = (curSize + curPos) / 2;
+ newPos = Math.min( (curSize + curPos) / 2, curSize);
}
prevPos = curPos;
curPos = newPos;
}
}
} // end while
+ ///////////////////////////////////////////////////////////////////////
if (log.isDebugEnabled())
{
- log.debug("Greater Position is [" + greaterPos + "]");
- log.debug("array[greaterPos] [" + array[greaterPos] + "]");
+ log.debug("Greater Position is [" + greaterPos + "]" +
+ " array[greaterPos] [" + array[greaterPos] + "]");
}
}
catch (Exception e)
{
- log.error(this.dumpArray(), e);
+ log.error("\n curPos = " + curPos + "; greaterPos = " + greaterPos +
+ "; prevpos = " + prevPos + " " + this.dumpArray(), e);
}
return greaterPos;
}
/**
- * Debugging method
+ * Removes the item from the array at the specified position. The remaining
+ * items to the right are shifted left.
+ * @param position int
+ */
+ private void remove(int position)
+ {
+ try
+ {
+ // suffle left from removal point
+ int end = curSize - 1;
+ for (int i = position; i < end; i++)
+ {
+ array[i] = array[i + 1];
+ }
+ curSize--;
+ }
+ catch (Exception e)
+ {
+ log.error("Remove problem" + this.dumpArray(), e);
+ }
+
+ }
+
+ /**
+ * Debugging method to return a human readable display of array data.
*/
private String dumpArray()
{
@@ -430,6 +564,34 @@
buf.append("\n " + i + "=" + array[i]);
}
return buf.toString();
+ }
+
+ /**
+ * Simple testing program.
+ *
+ * @param args String[]
+ */
+ public static void main(String args[])
+ {
+
+ SortedPreferentialArray array = new SortedPreferentialArray(25);
+ //array.setPreferLarge( false );
+ array.setPreferLarge( true );
+ String[] elem =
+ {
+ "10", "11", "01", "02", "03", "04", "05", "08", "07",
+ "06", "09", "12", "13", "15", "14", "20", "25", "29", "28", "16", "17",
+ "96", "00", "72", "39", "55", "44", "26", "22", "59", "38", "16", "27"};
+
+ for (int i = 0; i < elem.length; i++)
+ {
+ array.add(elem[i]);
+ System.out.println(array.dumpArray());
+ }
+
+ //String t = "01";
+ //System.out.print(t.compareTo("10"));
+
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
