CSC212: Computer Science.
TEXTBOOK: Object-Oriented Data Structures Using Java
TEXTBOOK: Source Code
|
|
package ch10.circles;
public class SortCircle
{
public int xValue;
public int yValue;
public int radius;
public boolean solid;
}
|
|
|
//----------------------------------------------------------------------------
// Sorts.java by Dale/Joyce/Weems Chapter 10
//
// Test harness used to run sorting algorithms.
//----------------------------------------------------------------------------
import java.util.*;
import java.text.DecimalFormat;
public class Sorts
{
static final int SIZE = 50; // size of array to be sorted
static int[] values = new int[SIZE]; // values to be sorted
static void initValues()
// Initializes the values array with random integers from 0 to 99.
{
Random rand = new Random();
for (int index = 0; index < SIZE; index++)
values[index] = Math.abs(rand.nextInt()) % 100;
}
static public boolean isSorted()
// Returns true if the array values are sorted and false otherwise.
{
boolean sorted = true;
for (int index = 0; index < (SIZE - 1); index++)
if (values[index] > values[index + 1])
sorted = false;
return sorted;
}
static public void swap(int index1, int index2)
// Precondition: index1 and index2 are >= 0 and < SIZE.
//
// Swaps the integers at locations index1 and index2 of the values array.
{
int temp = values[index1];
values[index1] = values[index2];
values[index2] = temp;
}
static public void printValues()
// Prints all the values integers.
{
int value;
DecimalFormat fmt = new DecimalFormat("00");
System.out.println("The values array is:");
for (int index = 0; index < SIZE; index++)
{
value = values[index];
if (((index + 1) % 10) == 0)
System.out.println(fmt.format(value));
else
System.out.print(fmt.format(value) + " ");
}
System.out.println();
}
/////////////////////////////////////////////////////////////////
//
// Selection Sort
static int minIndex(int startIndex, int endIndex)
// Returns the index of the smallest value in
// values[startIndex]..values[endIndex].
{
int indexOfMin = startIndex;
for (int index = startIndex + 1; index <= endIndex; index++)
if (values[index] < values[indexOfMin])
indexOfMin = index;
return indexOfMin;
}
static void selectionSort()
// Sorts the values array using the selection sort algorithm.
{
int endIndex = SIZE - 1;
for (int current = 0; current < endIndex; current++)
swap(current, minIndex(current, endIndex));
}
/////////////////////////////////////////////////////////////////
//
// Bubble Sort
static void bubbleUp(int startIndex, int endIndex)
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex].
{
for (int index = endIndex; index > startIndex; index--)
if (values[index] < values[index - 1])
swap(index, index - 1);
}
static void bubbleSort()
// Sorts the values array using the bubble sort algorithm.
{
int current = 0;
while (current < (SIZE - 1))
{
bubbleUp(current, SIZE - 1);
current++;
}
}
/////////////////////////////////////////////////////////////////
//
// Short Bubble Sort
static boolean bubbleUp2(int startIndex, int endIndex)
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex].
//
// Returns false if a swap was made; otherwise, returns true.
{
boolean sorted = true;
for (int index = endIndex; index > startIndex; index--)
if (values[index] < values[index - 1])
{
swap(index, index - 1);
sorted = false;
}
return sorted;
}
static void shortBubble()
// Sorts the values array using the bubble sort algorithm.
// The process stops as soon as values is sorted.
{
int current = 0;
boolean sorted = false;
while ((current < (SIZE - 1)) && !sorted)
{
sorted = bubbleUp2(current, SIZE - 1);
current++;
}
}
/////////////////////////////////////////////////////////////////
//
// Insertion Sort
static void insertItem(int startIndex, int endIndex)
// Upon completion, values[0]..values[endIndex] are sorted.
{
boolean finished = false;
int current = endIndex;
boolean moreToSearch = true;
while (moreToSearch && !finished)
{
if (values[current] < values[current - 1])
{
swap(current, current - 1);
current--;
moreToSearch = (current != startIndex);
}
else
finished = true;
}
}
static void insertionSort()
// Sorts the values array using the insertion sort algorithm.
{
for (int count = 1; count < SIZE; count++)
insertItem(0, count);
}
/////////////////////////////////////////////////////////////////
//
// Merge Sort
static void merge (int leftFirst, int leftLast, int rightFirst, int rightLast)
// Preconditions: values[leftFirst]..values[leftLast] are sorted.
// values[rightFirst]..values[rightLast] are sorted.
//
// Sorts values[leftFirst]..values[rightLast] by merging the two subarrays.
{
int[] tempArray = new int [SIZE];
int index = leftFirst;
int saveFirst = leftFirst; // to remember where to copy back
while ((leftFirst <= leftLast) && (rightFirst <= rightLast))
{
if (values[leftFirst] < values[rightFirst])
{
tempArray[index] = values[leftFirst];
leftFirst++;
}
else
{
tempArray[index] = values[rightFirst];
rightFirst++;
}
index++;
}
while (leftFirst <= leftLast)
// Copy remaining items from left half.
{
tempArray[index] = values[leftFirst];
leftFirst++;
index++;
}
while (rightFirst <= rightLast)
// Copy remaining items from right half.
{
tempArray[index] = values[rightFirst];
rightFirst++;
index++;
}
for (index = saveFirst; index <= rightLast; index++)
values[index] = tempArray[index];
}
static void mergeSort(int first, int last)
// Sorts the values array using the merge sort algorithm.
{
if (first < last)
{
int middle = (first + last) / 2;
mergeSort(first, middle);
mergeSort(middle + 1, last);
merge(first, middle, middle + 1, last);
}
}
/////////////////////////////////////////////////////////////////
//
// Quick Sort
static int split(int first, int last)
{
int splitVal = values[first];
int saveF = first;
boolean onCorrectSide;
first++;
do
{
onCorrectSide = true;
while (onCorrectSide) // move first toward last
if (values[first] > splitVal)
onCorrectSide = false;
else
{
first++;
onCorrectSide = (first <= last);
}
onCorrectSide = (first <= last);
while (onCorrectSide) // move last toward first
if (values[last] <= splitVal)
onCorrectSide = false;
else
{
last--;
onCorrectSide = (first <= last);
}
if (first < last)
{
swap(first, last);
first++;
last--;
}
} while (first <= last);
swap(saveF, last);
return last;
}
static void quickSort(int first, int last)
{
if (first < last)
{
int splitPoint;
splitPoint = split(first, last);
// values[first]..values[splitPoint - 1] <= splitVal
// values[splitPoint] = splitVal
// values[splitPoint+1]..values[last] > splitVal
quickSort(first, splitPoint - 1);
quickSort(splitPoint + 1, last);
}
}
/////////////////////////////////////////////////////////////////
//
// Heap Sort
static int newHole(int hole, int lastIndex, int item)
// If either child of hole is larger than item this returns the index
// of the larger child; otherwise it returns the index of hole.
{
int left = (hole * 2) + 1;
int right = (hole * 2) + 2;
if (left > lastIndex)
// hole has no children
return hole;
else
if (left == lastIndex)
// hole has left child only
if (item < values[left])
// item < left child
return left;
else
// item >= left child
return hole;
else
// hole has two children
if (values[left] < values[right])
// left child < right child
if (values[right] <= item)
// right child <= item
return hole;
else
// item < right child
return right;
else
// left child >= right child
if (values[left] <= item)
// left child <= item
return hole;
else
// item < left child
return left;
}
static void reheapDown(int item, int root, int lastIndex)
// Precondition: Current root position is "empty".
//
// Inserts item into the tree and ensures shape and order properties.
{
int hole = root; // current index of hole
int newhole; // index where hole should move to
newhole = newHole(hole, lastIndex, item); // find next hole
while (newhole != hole)
{
values[hole] = values[newhole]; // move value up
hole = newhole; // move hole down
newhole = newHole(hole, lastIndex, item); // find next hole
}
values[hole] = item; // fill in the final hole
}
static void heapSort()
// Sorts the values array using the heap sort algorithm.
{
int index;
// Convert the array of values into a heap.
for (index = SIZE/2 - 1; index >= 0; index--)
reheapDown(values[index], index, SIZE - 1);
// Sort the array.
for (index = SIZE - 1; index >=1; index--)
{
swap(0, index);
reheapDown(values[0], 0, index - 1);
}
}
/////////////////////////////////////////////////////////////////
//
// Main
public static void main(String[] args)
{
initValues();
printValues();
System.out.println("values is sorted: " + isSorted());
System.out.println();
// make call to sorting method here (just remove //)
// selectionSort();
// bubbleSort();
// shortBubble();
// insertionSort();
// mergeSort(0, SIZE - 1);
// quickSort(0, SIZE - 1);
// heapSort();
printValues();
System.out.println("values is sorted: " + isSorted());
System.out.println();
}
}
|
|
|
//----------------------------------------------------------------------------
// Sorts2.java by Dale/Joyce/Weems Chapter 10
//
// Test harness used to run sorting algorithms that use Comparator.
//----------------------------------------------------------------------------
import java.util.*;
import java.text.DecimalFormat;
import ch10.circles.*;
public class Sorts2
{
static final int SIZE = 6; // size of array to be sorted
static SortCircle[] values = new SortCircle[SIZE]; // values to be sorted
static void initValues()
// Initializes the values array with random circles.
{
Random rand = new Random();
for (int index = 0; index < SIZE; index++)
{
values[index] = new SortCircle();
values[index].xValue = Math.abs(rand.nextInt()) % 100;
values[index].yValue = Math.abs(rand.nextInt()) % 100;
values[index].radius = Math.abs(rand.nextInt()) % 100;
values[index].solid = ((Math.abs(rand.nextInt()) % 2) == 0);
}
}
static public void swap(int index1, int index2)
// Swaps the SortCircles at locations index1 and index2 of array values.
{
SortCircle temp = values[index1];
values[index1] = values[index2];
values[index2] = temp;
}
static public void printValues()
// Prints all the values integers.
{
SortCircle value;
DecimalFormat fmt = new DecimalFormat("00");
System.out.println("The values array is:");
System.out.println();
System.out.println(" x y r solid");
System.out.println("-- -- -- -----");
for (int index = 0; index < SIZE; index++)
{
value = values[index];
System.out.print(fmt.format(value.xValue) + " ");
System.out.print(fmt.format(value.yValue) + " ");
System.out.print(fmt.format(value.radius) + " ");
System.out.print(value.solid);
System.out.println();
}
System.out.println();
}
static int minIndex(int startIndex, int endIndex, Comparator comp)
// Returns the index of the smallest value in
// values[startIndex]..values[endIndex]
// based on the Comparator comp.
{
int indexOfMin = startIndex;
for (int index = startIndex + 1; index <= endIndex; index++)
if (comp.compare(values[index],values[indexOfMin]) < 0)
indexOfMin = index;
return indexOfMin;
}
static void selectionSort(Comparator comp)
// Sorts the values array using the selection sort algorithm.
{
int endIndex = SIZE - 1;
for (int current = 0; current < endIndex; current++)
swap(current, minIndex(current, endIndex, comp));
}
public static void main(String[] args)
{
Comparator xComp = new Comparator()
{
public int compare(SortCircle a, SortCircle b)
{
return (a.xValue - b.xValue);
}
};
Comparator yComp = new Comparator()
{
public int compare(SortCircle a, SortCircle b)
{
return (a.yValue - b.yValue);
}
};
initValues();
printValues();
selectionSort(xComp);
printValues();
selectionSort(yComp);
printValues();
}
}
|
|
|
//----------------------------------------------------------------------------
// BSTNode.java by Dale/Joyce/Weems Chapter 8
//
// Implements Comparable nodes for a binary search tree.
//----------------------------------------------------------------------------
package support;
public class BSTNode>
{
// Used to hold references to BST nodes for the linked implementation
protected T info; // The info in a BST node
protected BSTNode left; // A link to the left child node
protected BSTNode right; // A link to the right child node
public BSTNode(T info)
{
this.info = info;
left = null;
right = null;
}
public void setInfo(T info)
// Sets info of this BSTNode.
{
this.info = info;
}
public T getInfo()
// Returns info of this BSTNode.
{
return info;
}
public void setLeft(BSTNode link)
// Sets left link of this BSTNode.
{
left = link;
}
public void setRight(BSTNode link)
// Sets right link of this BSTNode.
{
right = link;
}
public BSTNode getLeft()
// Returns left link of this BSTNode.
{
return left;
}
public BSTNode getRight()
// Returns right link of this BSTNode.
{
return right;
}
}
|
|
|
//----------------------------------------------------------------------
// Customer.java by Dale/Joyce/Weems Chapter 5
//
// Supports customer objects having arrival, service, and finish time
// attributes. Responsible for computing and returning wait time.
//----------------------------------------------------------------------
package support;
public class Customer
{
protected int arrivalTime;
protected int serviceTime;
protected int finishTime;
public Customer(int arrivalTime, int serviceTime)
{
this.arrivalTime = arrivalTime;
this.serviceTime = serviceTime;
}
public int getArrivalTime()
{
return arrivalTime;
}
public int getServiceTime()
{
return serviceTime;
}
public void setFinishTime(int time)
{
finishTime = time;
}
public int getFinishTime()
{
return finishTime;
}
public int getWaitTime()
{
return (finishTime - arrivalTime - serviceTime);
}
}
|
|
|
//----------------------------------------------------------------------
// CustomerGenerator.java by Dale/Joyce/Weems Chapter 5
//
// Generates a sequence of random Customer objects based on the
// constructor arguments for min and max interarrival and service times.
// Assumes a flat distribution of both interarrival and service times.
// Assumes time starts at 0.
//----------------------------------------------------------------------
package support;
import java.util.Random;
public class CustomerGenerator
{
protected int minIAT; // minimum inter-arrival time
protected int maxIAT; // maximum inter-arrival time
protected int minST; // minimum service time
protected int maxST; // maximum service time
protected int currTime = 0; // current time
Random rand = new Random(); // to generate random numbers
public CustomerGenerator (int minIAT, int maxIAT, int minST, int maxST)
// Preconditions: all arguments >= 0
// minIAT <= maxIAT
// minST <= maxST
{
this.minIAT = minIAT;
this.maxIAT = maxIAT;
this.minST = minST;
this.maxST = maxST;
}
public void reset()
{
currTime = 0;
}
public Customer nextCustomer()
// Creates and returns the next random customer.
{
int IAT; // next inter-arrival time
int ST; // next service time
IAT = minIAT + rand.nextInt(maxIAT - minIAT + 1);
ST = minST + rand.nextInt(maxST - minST + 1);
currTime = currTime + IAT; // updates current time to the arrival
// time of next customer
Customer next = new Customer(currTime, ST);
return next;
}
}
|
|
|
//----------------------------------------------------------------------------
// DLLNode.java by Dale/Joyce/Weems Chapter 7
//
// Implements nodes for a doubly linked list.
//----------------------------------------------------------------------------
package support;
public class DLLNode extends LLNode
{
private DLLNode back;
public DLLNode(T info)
{
super(info);
back = null;
}
public void setBack(DLLNode back)
// Sets back link of this DLLNode.
{
this.back = back;
}
public DLLNode getBack()
// Returns back link of this DLLNode.
{
return back;
}
}
|
|
|
//----------------------------------------------------------------------
// Flights.java by Dale/Joyce/Weems Chapter 9
//
// Supports flight objects having a "from" vertex, a "to" vertex, and a
// distance. Allows flights to be compared based on their distances.
//----------------------------------------------------------------------
package support;
public class Flight implements Comparable
{
protected String fromVertex;
protected String toVertex;
protected int distance;
public Flight(String fromVertex, String toVertex, int distance)
{
this.fromVertex = fromVertex;
this.toVertex = toVertex;
this.distance = distance;
}
public String getFromVertex()
{
return fromVertex;
}
public String getToVertex()
{
return toVertex;
}
public int getDistance()
{
return distance;
}
public void setFromVertex(String vertex)
{
fromVertex = vertex;
}
public void setToVertex(String vertex)
{
toVertex = vertex;
}
public void setDistance(int distance)
{
this.distance = distance;
}
public int compareTo(Flight other)
{
return (other.distance - this.distance); // shorter is better
}
public String toString()
{
return (fromVertex + " " + toVertex + " " + distance);
}
}
|
|
|
//----------------------------------------------------------------------
// Golfer.java by Dale/Joyce/Weems Chapter 6
//
// Supports golfer objects having a name and a score.
// Allows golfers to be compared based on their scores.
//----------------------------------------------------------------------
package support;
public class Golfer implements Comparable
{
protected String name;
protected int score;
public Golfer(String name, int score)
{
this.name = name;
this.score = score;
}
public String getName()
{
return name;
}
public int getScore()
{
return score;
}
public int compareTo(Golfer other)
{
if (this.score < other.score)
return -1;
else
if (this.score == other.score)
return 0;
else
return +1;
}
public String toString()
{
return (score + ": " + name);
}
}
|
|
|
//----------------------------------------------------------------------------
// LLNode.java by Dale/Joyce/Weems Chapter 3
//
// Implements nodes for a Linked List.
//----------------------------------------------------------------------------
package support;
public class LLNode
{
private LLNode link;
private T info;
public LLNode(T info)
{
this.info = info;
link = null;
}
public void setInfo(T info)
// Sets info of this LLNode.
{
this.info = info;
}
public T getInfo()
// Returns info of this LLONode.
{
return info;
}
public void setLink(LLNode link)
// Sets link of this LLNode.
{
this.link = link;
}
public LLNode getLink()
// Returns link of this LLNode.
{
return link;
}
}
|
|
|
//----------------------------------------------------------------------
// RankCardDeck.java by Dale/Joyce/Weems Chapter 5
//
// Models a deck of cards.
// Returns a random card upon request.
// Cards are represented by rank only .. an integer between 0 and 12.
//----------------------------------------------------------------------
package support;
import java.util.Random;
public class RankCardDeck
{
private static final int numCards = 52;
protected int[] carddeck = new int[numCards];
protected int curCardPos = 0; // position of the next card to be dealt
protected Random rand = new Random(); // to generate random numbers
public RankCardDeck()
{
for (int i = 0; i < numCards; i++)
carddeck[i] = i / 4; // there are 4 cards of each rank
}
public void shuffle()
// Randomizes the order of the cards in the deck and resets the
// position of the current card to card 0.
{
int randLoc; // random location in card deck
int temp; // for swap of cards
for (int i = (numCards - 1); i > 0; i--)
{
randLoc = rand.nextInt(i); // random integer between 0 and i - 1
temp = carddeck[randLoc];
carddeck[randLoc] = carddeck[i];
carddeck[i] = temp;
}
curCardPos = 0;
}
public boolean hasMoreCards()
// Returns true if there are still cards left to be dealt;
// otherwise, returns false.
{
return (curCardPos != numCards);
}
public int nextCard()
// Precondition: curCardPos != numCards
//
// Models a card being dealt by returning an integer representing
// its rank and incrementing the position of the current card.
{
curCardPos = curCardPos + 1;
return (carddeck[curCardPos - 1]);
}
}
|
|
|
//----------------------------------------------------------------------
// SerSong.java by Dale/Joyce/Weems Chapter 6
//
// Supports song objects having a name and a duration.
// Implements Serializable.
//----------------------------------------------------------------------
package support;
import java.io.*;
import java.text.*;
public class SerSong implements Serializable
{
protected String name;
protected int duration; // in seconds
DecimalFormat fmt = new DecimalFormat("00"); // to format seconds
public SerSong(String name, int seconds)
{
this.name = name;
duration = seconds;
}
public SerSong(String name, int minutes, int seconds)
{
this.name = name;
duration = (60 * minutes) + seconds;
}
public String getName()
{
return name;
}
public int getDuration()
{
return duration;
}
public String toString()
{
return (name + " " + (duration / 60) + ":"
+ fmt.format(duration % 60));
}
}
|
|
|
//----------------------------------------------------------------------
// Song.java by Dale/Joyce/Weems Chapter 6
//
// Supports song objects having a name and a duration.
//----------------------------------------------------------------------
package support;
import java.text.*;
public class Song
{
protected String name;
protected int duration; // in seconds
DecimalFormat fmt = new DecimalFormat("00"); // to format seconds
public Song(String name, int seconds)
{
this.name = name;
duration = seconds;
}
public Song(String name, int minutes, int seconds)
{
this.name = name;
duration = (60 * minutes) + seconds;
}
public String getName()
{
return name;
}
public int getDuration()
{
return duration;
}
public String toString()
{
return (name + " " + (duration / 60) + ":"
+ fmt.format(duration % 60));
}
}
|