/**
* Data Structures and Algorithms
* Book Reference: Data Structures and Algorithms in Java 2nd Ed by Robert Lafore
*
* Iterators are not implemented for Data Structures available in Java 1.4 and Java 1.5
*/
import java.util.Comparator;
import java.util.Iterator;
/**
* Data Structures and Algorithms
* Book Reference: Data Structures and Algorithms in Java 2nd Ed by Robert Lafore
*
* Iterators are not implemented for Data Structures available in Java 1.4 and Java 1.5
*/
public class
DSAlgorithm {
public static void ArraySearchTest() {
Integer a[] = new Integer[] {
new Integer(1), new Integer(3), new Integer(5),
new Integer(7), new Integer(11)};
System.out.println("Linear Search found index=" + ArraySearch.OrderedLinearSearch(a, new Integer(3)));
System.out.println("Binary Search found index=" + ArraySearch.BinarySearch(a, new Integer(3)));
}
public static void SortTest() {
Integer a[] = new Integer[] {
new Integer(7), new Integer(11), new Integer(5),
new Integer(3), new Integer(1)};
Integer b[] = new Integer[a.length];
System.out.println("Before Sort");
PrintArray(a);
System.arraycopy(a, 0, b, 0, a.length);
Sort.BubbleSort(b);
System.out.println("After BubbleSort");
PrintArray(b);
System.arraycopy(a, 0, b, 0, a.length);
Sort.SelectionSort(b);
System.out.println("After SelectionSort");
PrintArray(b);
Sort.InsertionSort(b);
System.out.println("After InsertionSort");
PrintArray(b);
}
public static void PrintArray(Object[] a) {
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + ",");
}
System.out.println("");
}
public static void StackTest() {
Stack stack = new Stack(2);
stack.push(new Integer(10));
stack.push(new Integer(11));
// stack.push(new Integer(12)); will throw RuntimeException
if (stack.isFull())
System.out.println("Stack is full");
Integer i = (Integer) stack.pop();
System.out.println("Stack popped=" + i);
}
public static void QueueTest() {
Queue queue = new Queue(2);
queue.insert(new Integer(10));
queue.insert(new Integer(11));
// queue.insert(new Integer(12)); will throw RuntimeException
if (queue.isFull())
System.out.println("Queue is empty");
Integer i = (Integer) queue.remove();
System.out.println("Queue removed=" + i);
queue.remove();
queue.insert(new Integer(10));
queue.insert(new Integer(11));
//queue.insert(new Integer(12)); //throw queue is full exception
}
public static void LinkedListTest() {
LinkedList a1 = new LinkedList(new Integer(10));
LinkedList a2 = new LinkedList(new Integer(11));
LinkedList a3 = new LinkedList(new Integer(12));
a1.setNext(a2); a2.setNext(a3);
System.out.print("LinkedList=");
for (Iterator it = a1.iterator(); it.hasNext();) {
System.out.print(it.next() + ",");
}
System.out.println();
}
public static void main(String[] args) {
ArraySearchTest();
SortTest();
StackTest();
QueueTest();
LinkedListTest();
}
}
/**
*/
class ArraySearch {
/**
* O(N/2)
*/
public static int OrderedLinearSearch(Comparable[] array, Comparable key) {
for (int i = 0; i < array.length-1; ++i) {
int comp = array[i].compareTo(key);
if (comp == 0)
return i;
if (comp > 0) // terminate loop if current item > key
return -1;
}
return -1;
}
/**
* Big O Notation we remove constants so instead of saying N^2/2 we will save N^2
*
* Watch for O(N^2) which goes up exponentiatly
* binary search in ordered array O(log base 2(N))
* Note log2(N) * 3.322 = log10(N)
* n=2^o where o is number of steps for binary search
* search in ordered collection
*/
public static int BinarySearch(Comparable[] array, Comparable key) {
int start = 0;
int end = array.length -1;
int index;
while (start <= end) {
index = (start + end) / 2;
int comp = array[index].compareTo(key);
if (comp == 0)
return index;
if (comp < 0) // in upper half
start = index + 1;
if (comp > 0) // lower half
end = index - 1;
}
return -1; // or
//throw new java.util.NoSuchElementException();
}
}
class Sort {
private static void Swap(Comparable[] array, int i, int j) {
Comparable temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* simplest sort, loop and keep swapping so that
* largest element is at the end of the array
* loops
* (N-1) + (N-2) ... + 1 = N*(N-1)/2
* O(N^2)
*/
public static void BubbleSort(Comparable[] array) {
for (int i = array.length-1; i > 0; i--) {
for (int j = 0; j < i; ++j)
if (array[j].compareTo(array[j+1]) > 0)
Swap(array, j, j+1);
}
}
/**
* Sort so that smallest element is at the left
* Requires only N swaps
* O(N^2) requires fewer swaps than Bubble Sort
*/
public static void SelectionSort(Comparable[] array) {
for (int i = 0; i < array.length-1; i++) {
int min = i;
for (int j = i+1; j < array.length; ++j)
if (array[j].compareTo(array[min]) < 0)
min = j;
Swap(array, i, min);
}
}
/**
* We partially sort
* We do copys not swap which are faster
* O(N^2) possible faster than Selection Sort
*/
public static void InsertionSort(Comparable[] array) {
for (int i = 1; i < array.length; i++) {
Comparable temp = array[i];
int j = i;
while (j > 0 && array[j-1].compareTo(temp) >= 0) {
array[j] = array[j-1]; // shift item right
--j;
}
array[j] = temp;
}
}
}
/**
* Retreive elements in First in Last Out Fashion
* Recursive code can be replace by Stack usage
* e.g use for reversing word
* All operations are O(1)
*/
class Stack {
Object[] elements;
int top=-1;
int max;
public Stack(int max) {
elements = new Object[max];
this.max = max;
}
public boolean isEmpty() { return top == -1 ? true : false; }
public boolean isFull() { return top == max ? true : false; }
public void push(Object o) {
if (isFull())
throw new RuntimeException("Stack is full");
++top;
elements[top] = o;
}
public Object pop() {
if (isEmpty())
throw new RuntimeException("Stack is empty");
Object o = elements[top];
--top;
return o;
}
// get element without poping
public Object peek() {
if (isEmpty())
throw new RuntimeException("Stack is empty");
Object o = elements[top];
return o;
}
}
/**
* Circular Queue
* DeQueue is double ended queue allows insertion at end or start
* PriorityQueue element has priority e.g Operating System Process scheduler
* We can implement the ordering calling the Comparator.compareTo
*
* All operations are O(1)
*/
class Queue {
Object[] elements;
int max;
int front = 0;
int rear = 0;
int n=-1;
public Queue(int max) {
elements = new Object[max];
this.max = max;
}
public boolean isEmpty() { return (n == -1) ? true : false; }
public boolean isFull() { return ((n+1) == max) ? true : false; }
public void insert(Object o) {
if (isFull())
throw new RuntimeException("Queue is full");
elements[front] = o;
++front;
if (front >= max) front = 0;
++n;
System.out.println("insert front=" + front + " rear="+rear + " n=" + n);
}
public Object remove() {
if (isEmpty())
throw new RuntimeException("Queue is empty");
Object o = elements[rear];
++rear;
if (rear >= max) rear = 0;
--n;
System.out.println("remove front=" + front + " rear="+rear + " n=" + n);
return o;
}
public Object peek() {
if (isEmpty())
throw new RuntimeException("Queue is empty");
Object o = elements[rear];
return o;
}
}
class LinkedList {
Object o;
LinkedList next;
public LinkedList(Object o) { this.o = o; }
public LinkedList getNext() { return next; }
public void setNext(LinkedList next) {
this.next = next;
}
public Object getObject() {
return o;
}
public Iterator iterator() {
return new LinkedListIterator(this);
}
}
class LinkedListIterator implements Iterator {
LinkedList start;
LinkedList list;
public LinkedListIterator(LinkedList list) {
this.list = list;
start = list;
}
public boolean hasNext() {
return list != null ? true : false;
}
public Object next() {
if (!hasNext())
throw new RuntimeException("No more elements in linked list");
Object o = list.getObject();
list = list.next;
return o;
}
public void remove() {
LinkedList curr = start;
LinkedList prev = start;
while (curr.getNext() != null) {
if (curr == list)
prev.setNext(curr.getNext());
prev = curr;
curr = curr.getNext();
}
}
}
// simple Person object to illustrate usage of collections
// and to show that if an object uses the Set or Map collection it
// should implement equals and hashCode
class Person implements Comparable, Comparator, Cloneable {
private String name;
private int age;
public Person(String name, int age) { this.name = name; this.age = age; }
/**
* Override Object.equals
**/
public boolean equals(Object obj)
{
System.out.println("in Person.equals");
if (obj instanceof Person) // if obj is null instanceof returns false
{
Person person = (Person) obj;
return person.name.equals(name) && person.age == age;
}
else return false;
}
/**
* From interface Comparator
* Compares its two arguments for order. Returns a negative integer, zero, or
* a positive integer as the first argument is less than, equal to,
* or greater than the second.
**/
public int compare(Object o1, Object o2) {
Person p1 = (Person) o1;
Person p2 = (Person) o2;
int ret = p1.getName().compareTo(p2.getName());
if (ret == 0 && p1.getAge() != p2.getAge())
ret = p1.getAge() < p2.getAge() ? -1 : 1;
return ret;
}
/**
* from interface Comparable
* Called by Arrays.sort()
* @param o
* @return
*/
public int compareTo(Object o)
{
Person p = (Person) o;
int ret = p.getName().compareTo(getName());
if (ret == 0 && p.getAge() != getAge())
ret = p.getAge() < getAge() ? -1 : 1;
return ret;
}
/**
* The general contract of hashCode is:
* Algorithm from Effective java
*/
public int hashCode() {
System.out.println("in Person.hashCode");
int result = 17; // start with some random number
result = 37 * result + name.hashCode();
result = 37 * result + age;
return result;
}
/**
* Create copy of Person
* x.clone != x
* x.clone().equals(x)
* @return copy of this object
* @throws java.lang.CloneNotSupportedException
*/
public Object clone() throws CloneNotSupportedException
{
Person p = (Person) super.clone();
p.name = name;
p.age = age;
return p;
}
public String getName() { return name; }
public int getAge() { return age; }
public String toString() { return "name=" + name + ",age=" + age; }
}