Sunday, December 21, 2008

Sorted Arraylist in Java


public class SortedArrayList implements Dictionary {

//number of items in the array
private int mNumberItems=0;

private DictionaryItem mItems[] = new DictionaryItem[10];
/*expand array
* -checks to see if array needs expansion, if so, it builds a new array
*/
private void expandArray()
{
if (checkExpandArray())
{
DictionaryItem newarray[] = new DictionaryItem[mItems.length*2];
System.arraycopy(mItems,0,newarray,0,mNumberItems); // copy all items into the new array
mItems = newarray;
}
}
/*checkExpandArray
*-if the numberofitems in the array is getting large, increase the size of the array to make room for another item
*/
private boolean checkExpandArray()
{
if (mNumberItems+1>=mItems.length)
{
return true;
}
return false;
}
/*insert
* -see update, same functionality, just drops the return value
*/
public void insert(Comparable key, Object data) {
update(key,data);

}
/*InsertIntoArray
* -Copies the data over in the array to make room
* -then slips the new value into that index
*/
private void insertIntoArray(int index, DictionaryItem item)
{
System.arraycopy(mItems,index,mItems,index+1,mNumberItems-index); // copy all items infront of the index
mItems[index] = item;
}
/*getIndexForKey
* does a linear search to find out where a certain key should be inserted
*/
private int getIndexForKey(Comparable key)
{
int i;
for(i=0;i<= mNumberItems-1;i++)
{
DictionaryItem curr = mItems[i];

if(curr.getKey().compareTo(key) >=0)
{
return i;
}
}
return mNumberItems;
}
/*getKeyAt
* -returns the key at a certain index
*/
private Object getKeyAt(int index)
{
return mItems[index].getKey();
}
/*lookupIndexForKey
* -does a binary search for a certain index location
* -returns -1 if value not found
*/
private int lookupIndexForKey(Comparable key)
{
return auxBinSearch(key,0,mNumberItems-1);
}
/*auxBinSearch
* -is the aux recursive method to implement the binary search
*/
private int auxBinSearch(Comparable key, int startindex,int endindex)
{
if (startindex > endindex) return -1;
int mid = (startindex + endindex)/2;

if (key.compareTo(getKeyAt(mid))==0) return mid;
if (key.compareTo(getKeyAt(mid))<0)
return auxBinSearch(key,startindex,mid-1); //go left
else
return auxBinSearch(key,mid+1,endindex);//go right

}


/*update
* -provides update functionality (insert, and replace
* returns true if it replaced
* returns false if inserted new record
*/
public boolean update(Comparable key, Object data) {

int insertindex=lookupIndexForKey(key);

if (insertindex!=-1)
{
mItems[insertindex] = new DictionaryItem(key,data);
return true;
}

//now we have to insert
//perform linear search and get insert location
insertindex= getIndexForKey(key);

expandArray();

insertIntoArray(insertindex,new DictionaryItem(key,data));
mNumberItems++;
return false;



}
/*lookup
* -uses a binary search to retrieve an object
* returns the Object if found
* return null if not found
*/
public Object lookup(Comparable key) {
int index = lookupIndexForKey(key);

if (index <0 || index > mNumberItems-1) return null;
return mItems[index].getData();
}
/*size
*-returns number of items in the array
*/
public int size() {
return mNumberItems;
}

/*print
* spits out the sorted arraylist contents
*/
public void print(PrintWriter p) {
//p.println("Printing Sorted ArrayList");
for(DictionaryItem curr: mItems )
{
if(curr!=null)
{
p.print(curr.getKey());
p.print(" ");
p.println(curr.getData());
}
}

}

}

1 comment:

mlaw said...

Why so complex? Just wrap or extend an ArrayList:

public class SortedArrayList<E extends Comparable<? super E>> extends ArrayList<E> {
public boolean add(E e) {
this.add(Math.abs(Collections.binarySearch(this, e)), e);
return true;
}

public boolean addAll(Collection<? extends E> c) {
for (E e: c) {
add(e);
}
return true;
}
}