public final class SimpleComparableList implements SimpleListADT<java.lang.Comparable> {
private int size;
private int currentPosition;
private int capacity;
private Object data;
private final int DEFAULT_CAPACITY = 100;
private String[] dataArray;
private int[] linksArray;
private int[] freeListArray;
public static void main(String [ ] args){
}
public SimpleComparableList(){
this.capacity = DEFAULT_CAPACITY;
this.currentPosition = 1;
this.dataArray = new String[capacity];
this.linksArray = new int[capacity];
this.freeListArray = new int[capacity];
}
public SimpleComparableList(int capacity){
// Constructs and initializes a list that is empty. Current list size is
// zero and current position is set to one.
this.capacity = capacity;
this.currentPosition = 1;
this.dataArray = new String[capacity];
this.linksArray = new int[capacity];
this.freeListArray = new int[capacity];
}
@Override
public boolean empty() {
//throw new UnsupportedOperationException("Not supported yet.");
return (this.size == 0);
}
@Override
public boolean full() {
//throw new UnsupportedOperationException("Not supported yet.");
return (this.size >= this.capacity);
}
@Override
public void insertItem(Comparable item) {
this.insertItem(item, currentPosition);
}
@Override
public void insertItem(Comparable item, int position) {
//throw new UnsupportedOperationException("Not supported yet.");
if (!(this.full())){
print "error, array is full";
}else{
for(int i = 0; i < freeListArray.length; i++){ //find first free location
if(freeListArray[i] != NULL){
break;
}
linksArray[i] = freeListArray[i]; //put location in links
dataArray[links[i]] = item; //put item into data
temp = linksArray[i];
linksArray[dataArray[temp]] = -1; //show where end of array is
}
}
}
@Override
public void removeItem() {
//throw new UnsupportedOperationException("Not supported yet.");
this.removeItem(this.currentPosition);
}
@Override
public void removeItem(int position) {
//throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public void removeAll() {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public int getCurrentListSize() {
return this.size;
}
@Override
public int getCurrentMaxSize() {
return this.capacity;
}
@Override
public int getCurrentPosition() {
return this.currentPosition;
}
@Override
public String getItem() {
throw new UnsupportedOperationException("Not supported yet.");
}
@Override
public void setCurrentPosition(int position) {
//throw new UnsupportedOperationException("Not supported yet.");
if (position > this.size)
position = this.size;
if (position < 1) position = 1;
currentPosition = position;
}
@Override
public void next() {
//throw new UnsupportedOperationException("Not supported yet.");
// Increment only the current position of this list if it is not already the
// last position.
if (this.currentPosition < this.size){
currentPosition++;
}else{
throw new SimpleListException
("Can't increase current on the list");
}
}
@Override
public void prev() {
//throw new UnsupportedOperationException("Not supported yet.");
if (this.currentPosition > 1){
this.currentPosition--;
}else{
throw new SimpleListException
("Can't decrease current on the list");
}
}
@Override
public void sortList() {
throw new UnsupportedOperationException("Not supported yet.");
}
public void quickSort(int array[], int start, int end){
int i = start; // index of left-to-right scan
int k = end; // index of right-to-left scan
if (end - start >= 1){ // check that there are at least two elements to sort
int pivot = array[start]; // set the pivot as the first element in the partition
while (k > i){ // while the scan indices from left and right have not met,
while (array[i] <= pivot && i <= end && k > i) // from the left, look for the first
i++; // element greater than the pivot
while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
k--; // element not greater than the pivot
if(k > i) // if the left seekindex is still smaller than
swap(array, i, k); // the right index, swap the corresponding elements
}
swap(array, start, k); // after the indices have crossed, swap the last element in
// the left partition with the pivot
quickSort(array, start, k - 1); // quicksort the left partition
quickSort(array, k + 1, end); // quicksort the right partition
}
else{return;} // if there is only one element in the partition, do not do any sorting
// the array is sorted, so exit
}
public void swap(int array[], int index1, int index2) {
// pre: array is full and index1, index2 < array.length
// post: the values at indices 1 and 2 have been swapped
int temp = array[index1]; // store the first value in a temp
array[index1] = array[index2]; // copy the value of the second into the first
array[index2] = temp; // copy the value of the temp into the second
}
}