The others classes
Code:
public class OrderedArrayList extends ArrayListClass
{
//default constructor
public OrderedArrayList()
{
super();
}
//constructor with a parameter
public OrderedArrayList(int size)
{
super(size);
}
//copy constructor
public OrderedArrayList(OrderedArrayList otherList)
{
super(otherList);
}
//Method to insert insertItem in the list at the proper
//place. However, first the list is searched to
//see if the item to be inserted is already in the list.
//Postcondition: insertItem is inserted and length++
// If insertItem is already in the list or the list
// is full, an appropriate message is output.
public void insert(DataElement insertItem)
{
int first = 0;
int last = length - 1;
int mid = 0;
boolean found = false;
if(length == 0) //list is empty
{
list[0] = insertItem.getCopy();
length++;
}
else
if(length == maxSize)
System.err.println("Cannot insert into a full list.");
else
{
while(first <= last && !found)
{
mid = (first + last) / 2;
if(list[mid].equals(insertItem))
found = true;
else
if(list[mid].compareTo(insertItem) > 0)
last = mid - 1;
else
first = mid + 1;
}//end while
if(found)
System.err.println("The insert item is already in the list. "
+ "Duplicates are not allowed.");
else
{
if(list[mid].compareTo(insertItem) < 0)
mid++;
insertAt(mid, insertItem);
}
}
}//end insert
public int binarySearch(DataElement[] list, DataElement item)
{
return binarySearch(list, item, 0, list.length - 1);
}
private int binarySearch(DataElement[] list, DataElement item, int first, int last)
{
if (first > last)
return -1; //base case for unsuccessful search
int mid = (first + last) / 2; //index for next probe
if (list[mid].compareTo(item) < 0)
return binarySearch(list, item, first, mid + 1); //base case for successful search
else
if (list[mid].compareTo(item) > 0)
return binarySearch(list, item, first, mid -1);
else
return mid;
}
}//end binarySearch
public class IntElement extends DataElement
{
protected int num;
//default constructor
public IntElement()
{
num = 0;
}
//constructor with a parameter
public IntElement(int x)
{
num = x;
}
//copy constructor
public IntElement(IntElement otherElement)
{
num = otherElement.num;
}
//Method to set the value of the instance variable num.
//Postcondition: num = x;
public void setNum(int x)
{
num = x;
}
//Method to return the value of the instance variable num.
//Postcondition: The value of num is returned.
public int getNum()
{
return num;
}
public boolean equals(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
return (num == temp.num);
}
public int compareTo(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
return (num - temp.num);
}
public void makeCopy(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
num = temp.num;
}
public DataElement getCopy()
{
IntElement temp = new IntElement(num);
return temp;
}
public String toString()
{
return String.valueOf(num);
}
}
public abstract class DataElement
{
public abstract boolean equals(DataElement otherElement);
//Method to determine whether two objects contain the
//same data.
//Postcondition: Returns true if this object contains the
// same data as the object otherElement;
// otherwise, it returns false.
public abstract int compareTo(DataElement otherElement);
//Method to compare two objects.
//Postcondition: Returns a value < 0 if this object is
// less than the object otherElement;
// Returns 0 if this object is the same as
// the object otherElement.
// Returns a value > 0 if this object is
// greater than the object otherElement.
public abstract void makeCopy(DataElement otherElement);
//Method to copy otherElement into this object.
//Postcondition: The data of otherElement is copied into
// this object.
public abstract DataElement getCopy();
//Method to return a copy of this object.
//Postcondition: A copy of this object is created and
// a reference of the copy is returned.
}
import java.io.*;
import java.util.*;
public class TestProgRecursiveBinarySearch
{
static BufferedReader keyboard = new
BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException
{
OrderedArrayList intList
= new OrderedArrayList();
OrderedArrayList temp =
new OrderedArrayList();
IntElement num = new IntElement();
int counter;
int position;
StringTokenizer tokenizer;
System.out.print("Enter 16 integers on the " + "same line: ");
System.out.flush();
tokenizer = new
StringTokenizer(keyboard.readLine());
for(counter = 0; counter < 16; counter++)
{
num.setNum(Integer.parseInt(tokenizer.nextToken()));
intList.insert(num);
}
temp.copyList(intList);
System.out.println();
System.out.print("The list you " + "entered is: ");
intList.print();
System.out.println();
System.out.print("Enter the num to " + "be deleted: ");
System.out.flush();
num.setNum(Integer.parseInt(keyboard.readLine()));
System.out.println();
System.out.print("Enter the position of " + "the num to be deleted: ");
System.out.flush();
position = Integer.parseInt(keyboard.readLine());
System.out.println();
intList.removeAt(position);
System.out.println("After removing the " + "element at position "
+ position
+ ", intList:");
intList.print();
System.out.println();
System.out.print("Enter the search " + "item: ");
System.out.flush();
num.setNum(Integer.parseInt(keyboard.readLine()));
System.out.println();
for (int i = 0; i < 16; i++)
System.out.println("Item found" + i + " at " + binarySearch(intList num));
}
}