//ArrayListADT
public interface ArrayListADT {
public boolean isEmpty(); //Method to determine whether the list is empty.
public boolean isFull(); //Method to determine whether the list is full.
public int listSize(); //Method to return the number of elements in the list.
public int maxListSize(); //Method to return the maximum size of the list.
public void print(); //Method to output the elements of the list.
public boolean isItemAtEqual(int location, int item); //Method to determine whether item is the same as the item in the list at location.
public void insertAt(int location, int insertItem); //Method to insert insertItem in the list at the position
public void insertEnd(int insertItem); //Method to insert insertItem at the end of the list.
public void removeAt(int location); //Method to remove the item from the list at location.
public int retrieveAt(int location); //Method to retrieve the element from the list at location.
public void replaceAt(int location, int repItem); //Method to replace the element in the list at location with repItem.
public void clearList(); //Method to remove all the elements from the list.
public int search(int searchItem); //Method to determine whether searchItem is in the list.
public void remove(int removeItem); //Method to remove an item from the list.
}
//ArrayList class
public abstract class ArrayListClass implements ArrayListADT {
protected int length; //to store the length of the list
protected int maxSize; //to store the maximum size of the list
protected int[] list; //array to hold the list elements
//Default constructor
public ArrayListClass() {
maxSize = 100;
length = 0;
list = new int[maxSize];
}
//Alternate Constructor
public ArrayListClass(int size) {
if(size <= 0) {
System.err.println("The array size must be positive. Creating an array of size 100.");
maxSize = 100;
}
else
maxSize = size;
length = 0;
list = new int[maxSize];
}
public boolean isEmpty() {
return (length == 0);
}
public boolean isFull() {
return (length == maxSize);
}
public int listSize() {
return length;
}
public int maxListSize() {
return maxSize;
}
public void print() {
for (int i = 0; i < length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
public boolean isItemAtEqual(int location, int item) {
if (location < 0 || location >= length) {
System.err.println("The location of the item to be compared is out of range.");
return false;
}
return list[location]== item;
}
public void clearList() {
for (int i = 0; i < length; i++)
list[i] = 0;
length = 0;
System.gc(); //invoke the Java garbage collector
}
public void removeAt(int location) {
if (location < 0 || location >= length)
System.err.println("The location of the item to be removed is out of range.");
else {
for(int i = location; i < length - 1; i++)
list[i] = list[i + 1];
length--;
}
}
public int retrieveAt(int location) {
if (location < 0 || location >= length) {
System.err.println("The location of the item to be retrieved is out of range.");
return 0;
}
else
return list[location];
}
public abstract void insertAt(int location, int insertItem);
public abstract void insertEnd(int insertItem);
public abstract void replaceAt(int location, int repItem);
public abstract int search(int searchItem);
public abstract void remove(int removeItem);
}
//OrderedArrayList
public class OrderedArrayList extends ArrayListClass{
public OrderedArrayList() {
super();
}
public OrderedArrayList(int size) {
super(size);
}
//implementation for abstract methods defined in ArrayListClass
//ordered list --> binary search
public int search(int item) {
int first = 0;
int last = length - 1;
int middle = -1;
while (first <= last) {
middle = (first + last) / 2;
if (list[middle] == item)
return middle;
else
if (list[middle] > item)
last = middle - 1;
else
first = middle + 1;
}
return -1;
}
public void insert(int item) {
int loc;
boolean found = false;
if (length == 0) //list is empty
list[length++] = item; //insert item and increment length
else if (length == maxSize) //list is full
System.err.println("Cannot insert in a full list.");
else {
for (loc = 0; loc < length; loc++) {
if (list[loc] >= item) {
found = true;
break;
}
}
//starting at the end, shift right
for (int i = length; i > loc; i--)
list[i] = list[i - 1];
list[loc] = item; //insert in place
length++;
}
}
/* Another version for insert:
public void insert(int item) {
int loc;
boolean found = false;
if (length == 0) //list is empty
list[length++] = item; //insert item and increment length
else if (length == maxSize) //list is full
System.err.println("Cannot insert in a full list.");
else {
int i = length - 1;
while (i >= 0 && list[i] > item) {
list[i + 1] = list[i];
i--;
}
list[i + 1] = item; // Insert item
length++;
}
} */
public void insertAt(int location, int item) {
if (location < 0 || location >= maxSize)
System.err.println("The position of the item to be inserted is out of range.");
else if (length == maxSize) //the list is full
System.err.println("Cannot insert in a full list.");
else {
System.out.println("Cannot do it, this is a sorted list. Doing insert in place (call to insert).");
insert(item);
}
}
public void insertEnd(int item) {
if (length == maxSize) //the list is full
System.err.println("Cannot insert in a full list.");
else {
System.out.println("Cannot do it, this is a sorted list. Doing insert in place (call to insert).");
insert(item);
}
}
public void replaceAt(int location, int item) {
//the list is sorted!
//is actually removing the element at location and inserting item in place
if (location < 0 || location >= length)
System.err.println("The position of the item to be replaced is out of range.");
else {
removeAt(location);//method in ArrayListClass
insert(item);
}
}
public void remove(int item) {
int loc;
if (length == 0)
System.err.println("Cannot delete from an empty list.");
else {
loc = search(item);
if (loc != -1)
removeAt(loc);//method in ArrayListClass
else
System.out.println("The item to be deleted is not in the list.");
}
}
/*Another version for remove:
public void remove(T item) {
int loc;
if (length == 0)
System.err.println("Cannot delete from an empty list.");
else {
loc = search(item);
if (loc != -1) {
for(int i = loc; i < length - 1; i++)
list[i] = list[i + 1]; //shift left
length--;
}
else
System.out.println("The item to be deleted is not in the list.");
}
} */
public OrderedArrayList merge(OrderedArrayList otherList) {
OrderedArrayList result = new OrderedArrayList();
int i = 0;
int j = 0;
while (i < length && j < otherList.length) {
if (list[i] <= otherList.list[j]) {
result.list[result.length++] = list[i++];
} else {
result.list[result.length++] = otherList.list[j++];
}
}
while (i < length) {
result.list[result.length++] = list[i++];
}
while (j < otherList.length) {
result.list[result.length++] = otherList.list[j++];
}
return result;
}
public OrderedArrayList[] split(int key) {
OrderedArrayList[] result = new OrderedArrayList[2];
result[0] = new OrderedArrayList();
result[1] = new OrderedArrayList();
for (int i = 0; i < length; i++) {
int value = list[i];
if (value < key)
result[0].list[result[0].length++] = value;
else
result[1].list[result[1].length++] = value;
}
return result;
}
}
// Main
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
OrderedArrayList list1 = new OrderedArrayList();
OrderedArrayList list2 = new OrderedArrayList();
OrderedArrayList result = new OrderedArrayList();
list1 = getNums(scanner, "list1");
list2 = getNums(scanner, "list2");
System.out.println("First list is:\n");
list1.print();
System.out.println("\nSecond list is:\n");
list2.print();
result = list1.merge(list2);
System.out.println("The merged list is:\n");
result.print();
int key = getInt(scanner, "Enter key for split:" );
OrderedArrayList[] splitResult = result.split(key);
System.out.println("The first list is:\n");
splitResult[0].print();
System.out.println("The second list is:\n");
splitResult[1].print();
}
public static OrderedArrayList getNums(Scanner sc, String file) {
OrderedArrayList list = new OrderedArrayList();
boolean found = false;
while (!found) {
try {
System.out.println("Please input the name of the file to be opened for " + file + ":");
String fileName = sc.nextLine();
Scanner fileSc = new Scanner(new File(fileName));
while (fileSc.hasNext()) {
if (fileSc.hasNextInt()) {
list.insert(fileSc.nextInt());
} else {
fileSc.next();
}
}
fileSc.close();
found = true;
} catch (FileNotFoundException e) {
System.out.println("File not found");
}
}
return list;
}
public static int getInt(Scanner sc, String prompt) {
System.out.println(prompt);
while (!sc.hasNextInt()) {
sc.next();
System.out.print("Not an integer! try again: ");
}
return sc.nextInt();
}
}
//List 1
13 c v b 25 34 x x 67 56 10 a a 20 27 2 a s 5 1 45 59
//List 2
73 29 c c c 14 87 72 100 200 c c c 127 22 15 19 c v v v 145 159 78