Skip to content

Instantly share code, notes, and snippets.

@Charlesmendez

Charlesmendez/ArrayBag.java

Last active December 10, 2021 22:24
Show Gist options
  • Save Charlesmendez/62701da3d5873755d85d7d45a65ae916 to your computer and use it in GitHub Desktop.
Save Charlesmendez/62701da3d5873755d85d7d45a65ae916 to your computer and use it in GitHub Desktop.
Download ZIP
Harvard Data Structures
Raw
ArrayBag.java
package bag;
/*
* ArrayBag.java
*
* Computer Science E-22
*
* Modified by: <your name>, <your e-mail address>
*/
import java.util.*;
/**
* An implementation of the Bag ADT using an array.
*/
public class ArrayBag implements Bag {
/**
* The array used to store the items in the bag.
*/
private Object[] items;
/**
* The number of items in the bag.
*/
private int numItems;
public static final int DEFAULT_MAX_SIZE = 50;
/**
* Constructor with no parameters - creates a new, empty ArrayBag with
* the default maximum size.
*/
public ArrayBag() {
this.items = new Object[DEFAULT_MAX_SIZE];
this.numItems = 0;
}
/**
* A constructor that creates a new, empty ArrayBag with the specified
* maximum size.
*/
public ArrayBag(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize must be > 0");
}
this.items = new Object[maxSize];
this.numItems = 0;
}
/**
* numItems - accessor method that returns the number of items
* in this ArrayBag.
*/
public int numItems() {
return this.numItems;
}
/**
* add - adds the specified item to this ArrayBag. Returns true if there
* is room to add it, and false otherwise.
* Throws an IllegalArgumentException if the item is null.
*/
public boolean add(Object item) {
if (item == null) {
throw new IllegalArgumentException("item must be non-null");
} else if (this.numItems == this.items.length) {
return false; // no more room!
} else {
this.items[this.numItems] = item;
this.numItems++;
return true;
}
}
/**
* remove - removes one occurrence of the specified item (if any)
* from this ArrayBag. Returns true on success and false if the
* specified item (i.e., an object equal to item) is not in this ArrayBag.
*/
public boolean remove(Object item) {
for (int i = 0; i < this.numItems; i++) {
if (this.items[i].equals(item)) {
// Shift the remaining items left by one.
for (int j = i; j < this.numItems - 1; j++) {
this.items[j] = this.items[j + 1];
}
this.items[this.numItems - 1] = null;
this.numItems--;
return true;
}
}
return false; // item not found
}
/**
* contains - returns true if the specified item is in the Bag, and
* false otherwise.
*/
public boolean contains(Object item) {
for (int i = 0; i < this.numItems; i++) {
if (this.items[i].equals(item)) {
return true;
}
}
return false;
}
/**
* containsAll - does this ArrayBag contain all of the items in
* otherBag? Returns false if otherBag is null or empty.
*/
public boolean containsAll(Bag otherBag) {
if (otherBag == null || otherBag.numItems() == 0) {
return false;
}
Object[] otherItems = otherBag.toArray();
for (int i = 0; i < otherItems.length; i++) {
if (! this.contains(otherItems[i])) {
return false;
}
}
return true;
}
/**
* grab - returns a reference to a randomly chosen item in this ArrayBag.
*/
public Object grab() {
if (this.numItems == 0) {
throw new IllegalStateException("the bag is empty");
}
int whichOne = (int)(Math.random() * this.numItems);
return this.items[whichOne];
}
/**
* toArray - return an array containing the current contents of the bag
*/
public Object[] toArray() {
Object[] copy = new Object[this.numItems];
for (int i = 0; i < this.numItems; i++) {
copy[i] = this.items[i];
}
return copy;
}
/**
* toString - converts this ArrayBag into a string that can be printed.
* Overrides the version of this method inherited from the Object class.
*/
public String toString() {
String str = "{";
for (int i = 0; i < this.numItems; i++) {
str = str + this.items[i];
if (i != this.numItems - 1) {
str += ", ";
}
}
str = str + "}";
return str;
}
/**
* capacity - return the maximum number of items that the ArrayBag is able to hold
*/
public int capacity() {
return DEFAULT_MAX_SIZE;
}
/**
* isEmpty - returns true if the ArrayBag is empty, and false otherwise.
*/
public boolean isEmpty() {
if (this.numItems == 0) {
return true;
}
return false;
}
/**
* numOccur - returns the number of times that the parameter item occurs in the called ArrayBag.
*/
public int numOccur(Object item) {
int count = 0;
for (int i = 0; i < this.numItems; i++) {
if (this.items[i].equals(item)) {
count++;
}
}
return count;
}
/**
* addItems - attempts to add to the called ArrayBag all of the items found in the parameter other.
*/
public boolean addItems(Bag other) {
if (other == null) {
throw new IllegalStateException("the bag is null");
}
if (other.numItems() == 0) {
return true;
}
int available_space = this.items.length - this.numItems();
if (available_space >= other.numItems()) {
for (int i = 0; i < other.numItems(); i++) {
this.add(other.toArray()[i]);
}
return true;
}
return false;
}
/**
* equals - should determine if the called ArrayBag is equal to the parameter other.
*/
public boolean equals(Bag other) {
int counter_bag1 = 0;
int[] bag1_result = new int[this.numItems()];
for (int i = 0; i < this.numItems; i++) {
bag1_result[counter_bag1] = this.numOccur(this.items[i]);
counter_bag1++;
}
Arrays.sort(bag1_result);
int counter_bag2 = 0;
int[] bag2_result = new int[other.numItems()];
for (int i = 0; i < other.numItems(); i++) {
bag2_result[counter_bag2] = other.numOccur(other.toArray()[i]);
counter_bag2++;
}
Arrays.sort(bag2_result);
if (other == null || this.items == null) {
return false;
}
if (bag1_result.length != bag2_result.length) {
return false;
}
for (int i = 0; i < bag1_result.length; i++) {
if (bag1_result[i] != bag2_result[i]) {
return false;
}
}
return true;
}
/* Test the ArrayBag implementation. */
public static void main(String[] args) {
// Create a Scanner object for user input.
Scanner scan = new Scanner(System.in);
// Create an ArrayBag named bag1.
System.out.print("size of bag 1: ");
int size = scan.nextInt();
ArrayBag bag1 = new ArrayBag(size);
scan.nextLine(); // consume the rest of the line
// Read in strings, add them to bag1, and print out bag1.
String itemStr;
for (int i = 0; i < size; i++) {
System.out.print("item " + i + ": ");
itemStr = scan.nextLine();
bag1.add(itemStr);
}
System.out.println("bag 1 = " + bag1);
System.out.println();
// Select a random item and print it.
Object item = bag1.grab();
System.out.println("grabbed " + item);
System.out.println();
// Iterate over the objects in bag1, printing them one per
// line.
Object[] items = bag1.toArray();
for (int i = 0; i < items.length; i++) {
System.out.println(items[i]);
}
System.out.println();
// Get an item to remove from bag1, remove it, and reprint the bag.
System.out.print("item to remove: ");
itemStr = scan.nextLine();
if (bag1.contains(itemStr)) {
bag1.remove(itemStr);
}
System.out.println("bag 1 = " + bag1);
System.out.println();
// Prints the maximum number of items that the ArrayBag is able to hold
System.out.println("Maximum number of items ArrayBag is able to hold: " + bag1.capacity());
System.out.println();
// Checks if the bag is empty
System.out.println("The bag is empty: " + bag1.isEmpty());
System.out.println();
// Prints number of times that the parameter item occurs in the called ArrayBag.
System.out.println("Number of times the parameter is in the Bag: " + bag1.numOccur(item));
System.out.println();
// Create an ArrayBag named bag2.
System.out.print("size of other bag: ");
int size_other = scan.nextInt();
ArrayBag bag2 = new ArrayBag(size_other);
scan.nextLine(); // consume the rest of the line
// Read in strings, add them to bag other, and print out bag other.
String itemStr_other;
for (int i = 0; i < size_other; i++) {
System.out.print("item " + i + ": ");
itemStr_other = scan.nextLine();
bag2.add(itemStr_other);
}
System.out.println("other bag = " + bag2);
System.out.println();
// Iterate over the objects in bag1, printing them one per
// line.
Object[] items_other = bag2.toArray();
for (int i = 0; i < items_other.length; i++) {
System.out.println(items_other[i]);
}
System.out.println();
System.out.println("bag1: " + bag1);
System.out.println("bag2: " + bag2);
System.out.println();
// attempts to add to the called ArrayBag(bag1) all of the items found in the parameter other(bag2).
System.out.println("Could it add items of Bag1 to Bag2?: " + bag1.addItems(bag2));
System.out.println();
System.out.println("The new bag1: " + bag1);
System.out.println();
// should determine if the called ArrayBag is equal (true) to the parameter other.
System.out.println("Bag1 equals to Bag2?: " + bag1.equals(bag2));
System.out.println();
}
}
Raw
Bag.java
package bag;
/*
* Bag.java
*
* Computer Science E-22, Harvard University
*
* Modified by: <your name>, <your e-mail address>
*/
/**
* An interface for the Bag ADT.
*/
public interface Bag {
int length = 0;
/**
* adds the specified item to the Bag. Returns true on success
* and false if there is no more room in the Bag.
*/
boolean add(Object item);
/**
* removes one occurrence of the specified item (if any) from the
* Bag. Returns true on success and false if the specified item
* (i.e., an object equal to item) is not in the Bag.
*/
boolean remove(Object item);
/**
* returns true if the specified item is in the Bag, and false
* otherwise.
*/
boolean contains(Object item);
/**
* returns true if the calling object contain all of the items in
* otherBag, and false otherwise. Also returns false if otherBag
* is null or empty.
*/
boolean containsAll(Bag otherBag);
/**
* returns the number of items in the Bag.
*/
int numItems();
/**
* grab - returns a reference to a randomly chosen in the Bag.
*/
Object grab();
/**
* toArray - return an array containing the current contents of the bag
*/
Object[] toArray();
/**
* capacity - returns the maximum number of items that the ArrayBag is able to hold
*/
public int capacity();
/**
* isEmpty - returns true if the ArrayBag is empty, and false otherwise.
*/
public boolean isEmpty();
/**
* numOccur - returns the number of times that the parameter item occurs in the called ArrayBag.
*/
public int numOccur(Object item);
/**
* addItems - attempts to add to the called ArrayBag all of the items found in the parameter other.
*/
public boolean addItems(Bag other);
/**
* equals - should determine if the called ArrayBag is equal to the parameter other.
*/
public boolean equals(Bag other);
}
Raw
Graph.java
/*
* Graph.java
*
* Computer Science E-22, Harvard University
*/
import java.io.*;
import java.util.*;
/**
* An implementation of a Graph ADT.
*/
public class Graph {
/*
* Vertex - a private inner class for representing a vertex.
*/
private class Vertex {
private String id;
private Edge edges; // adjacency list, sorted by edge cost
private Vertex next; // next Vertex in linked list
private boolean encountered;
private boolean done;
private Vertex parent; // preceding vertex in path from root
private double cost; // cost of shortest known path
private Vertex(String id) {
this.id = id;
cost = Double.POSITIVE_INFINITY;
}
/*
* reinit - reset the starting values of the fields used by
* the various algorithms, removing any values set by previous
* uses of the algorithms.
*/
private void reinit() {
done = false;
encountered = false;
parent = null;
cost = Double.POSITIVE_INFINITY;
}
/*
* addToAdjacencyList - add the specified edge to the
* adjacency list for this vertex.
*/
private void addToAdjacencyList(Edge e) {
/* Add to the front of the list. */
e.next = edges;
edges = e;
}
/*
* pathString - returns a string that specifies the path from
* the root of the current spanning tree (if there is one) to
* this vertex. If this method is called after performing
* Dijkstra's algorithm, the returned string will specify the
* shortest path.
*/
private String pathString() {
String str;
if (parent == null) {
str = id; /* base case: this vertex is the root */
} else {
str = parent.pathString() + " -> " + id;
}
return str;
}
/*
* toString - returns a string representation of the vertex
* of the following form:
* vertex v:
* edge to vi (cost = c1i)
* edge to vj (cost = c1j)
* ...
*/
public String toString() {
String str = "vertex " + id + ":\n";
/*
* Iterate over the edges, adding a line to the string for
* each of them.
*/
Edge e = edges;
while (e != null) {
// Note: we have to use just the id field of the
// end vertex, or else we'll get infinite recursion!
str += "\tedge to " + e.end.id;
str += " (cost = " + e.cost + ")\n";
e = e.next;
}
return str;
}
}
/*
* Edge - a private inner class for representing an edge.
*/
private class Edge {
private Vertex start;
private Vertex end;
private double cost;
private Edge next; // next Edge in adjacency list
private Edge(Vertex start, Vertex end, double cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
}
/******* Graph instance variables and method start here. *********/
/* A linked list of the vertices in the graph. */
private Vertex vertices;
/*
* reinitVertices - private helper method that resets the starting
* state of all of the vertices in the graph, removing any values
* set by previous uses of the algorithms.
*/
private void reinitVertices() {
Vertex v = vertices;
while (v != null) {
v.reinit();
v = v.next;
}
}
/*
* getVertex - private helper method that returns a reference to
* the vertex with the specified id. If the vertex isn't
* in the graph, it returns null.
*/
private Vertex getVertex(String id) {
Vertex v = vertices;
while (v != null && !v.id.equals(id)) {
v = v.next;
}
return v;
}
/*
* addVertex - private helper method that adds a vertex with
* the specified id and returns a reference to it.
*/
private Vertex addVertex(String id) {
Vertex v = new Vertex(id);
/* Add to the front of the list. */
v.next = vertices;
vertices = v;
return v;
}
/**
* addEdge - add an edge with the specified cost, and with start
* and end vertices that have the specified IDs. The edge will
* be stored in the adjacency list of the start vertex. If a
* specified vertex isn't already part of the graph, it will be
* added, too.
*/
public void addEdge(String startVertexID, String endVertexID, double cost) {
Vertex start = getVertex(startVertexID);
if (start == null) {
start = addVertex(startVertexID);
}
Vertex end = getVertex(endVertexID);
if (end == null) {
end = addVertex(endVertexID);
}
Edge e = new Edge(start, end, cost);
start.addToAdjacencyList(e);
}
/**
* toString - returns a concatenation of the string
* representations of all of the vertices in the graph.
*/
public String toString() {
String str = "";
Vertex v = vertices;
while (v != null) {
str += v;
v = v.next;
}
return str;
}
/**
* initFromFile - initialize a graph using the information in the
* specified file. The file should be a text file consisting of
* lines that specify the edges of the graph in the following form:
* <start vertex data> <end vertex data> <cost>
*/
public void initFromFile(String fileName) {
String lineString = "";
try {
/* This Scanner will scan the file, one line at a time. */
Scanner file = new Scanner(new File(fileName));
/* Parse the file, one line at a time. */
while (file.hasNextLine()) {
lineString = file.nextLine();
Scanner line = new Scanner(lineString);
String startID = line.next();
String endID = line.next();
double cost = line.nextDouble();
addEdge(startID, endID, cost);
}
} catch (IOException e) {
System.out.println("Error accessing " + fileName);
System.exit(1);
} catch (NoSuchElementException e) {
System.out.println("invalid input line: " + lineString);
System.exit(1);
}
}
/**
* depthFirstTrav - perform a depth-first traversal starting from
* the vertex with the specified ID. After making sure that the
* start vertex exists, it makes an initial call to the recursive
* method dfTrav, which does the actual traversal.
*/
public void depthFirstTrav(String originID) {
reinitVertices();
/* Get the specified start vertex. */
Vertex start = getVertex(originID);
if (start == null) {
throw new IllegalArgumentException("no such vertex: " + originID);
}
/* Start the recursion rolling... */
dfTrav(start, null);
}
/*
* dfTrav - a recursive method used to perform a depth-first
* traversal, starting from the specified vertex v. The parent
* parameter specifies v's parent in the depth-first spanning
* tree. In the initial invocation, the value of parent should be
* null, because the starting vertex is the root of the spanning
* tree.
*/
private static void dfTrav(Vertex v, Vertex parent) {
/* Visit v. */
System.out.println(v.id);
v.done = true;
v.parent = parent;
Edge e = v.edges;
while (e != null) {
Vertex w = e.end;
if (!w.done) {
dfTrav(w, v);
}
e = e.next;
}
}
/**
* breadthFirstTrav - perform a breadth-first traversal starting from
* the vertex with the specified ID.
*/
public void breadthFirstTrav(String originID) {
reinitVertices();
/* Get the specified start vertex. */
Vertex origin = getVertex(originID);
if (origin == null) {
throw new IllegalArgumentException("no such vertex: " + originID);
}
bfTrav(origin);
}
private static void bfTrav(Vertex origin) {
/* Mark the origin as encountered, and add it to the queue. */
origin.encountered = true;
origin.parent = null;
Queue<Vertex> q = new LLQueue<Vertex>();
q.insert(origin);
while (!q.isEmpty()) {
/* Remove a vertex v and visit it. */
Vertex v = q.remove();
System.out.println(v.id);
/* Add v's unencountered neighbors to the queue. */
Edge e = v.edges;
while (e != null) {
Vertex w = e.end;
if (!w.encountered) {
w.encountered = true;
w.parent = v;
q.insert(w);
}
e = e.next;
}
}
}
/**
* dijkstra - apply Dijkstra's algorithm starting from the
* specified origin vertex to find the shortest path from the
* origin to all other vertices that can be reached from the
* origin.
*
* The method prints the vertices in the order in which they are
* finalized. For each vertex v, it lists the total cost of the
* shortest path from the origin to v, as well as v's parent
* vertex. Tracing back along the parents gives the shortest
* path.
*/
public void dijkstra(String originID) {
/* This will give all vertices an infinite cost. */
reinitVertices();
/* Get the origin and set its cost to 0. */
Vertex origin = getVertex(originID);
if (origin == null) {
throw new IllegalArgumentException("no such vertex: " + originID);
}
origin.cost = 0;
while (true) {
/* Find the unfinalized vertex with the minimal cost. */
Vertex w = null;
Vertex v = vertices;
while (v != null) {
if (!v.done && (w == null || v.cost < w.cost)) {
w = v;
}
v = v.next;
}
/*
* If there are no unfinalized vertices, or if all of the
* unfinalized vertices are unreachable from the origin
* (which is the case if the w.cost is infinite), then
* we're done.
*/
if (w == null || w.cost == Double.POSITIVE_INFINITY) {
return;
}
/* Finalize w. */
System.out.println("\tfinalizing " + w.id + " (cost = " + w.cost +
(w.parent == null ? ")" : ", parent = " + w.parent.id + ")"));
System.out.println("\t\tpath = " + w.pathString());
w.done = true;
/* Try to improve the estimates of w's unfinalized neighbors. */
Edge e = w.edges;
while (e != null) {
Vertex x = e.end;
if (!x.done) {
double cost_via_w = w.cost + e.cost;
if (cost_via_w < x.cost) {
x.cost = cost_via_w;
x.parent = w;
}
}
e = e.next;
}
}
}
/**
* prim - apply Prim's algorithm starting from the specified
* vertex to find a minimum spanning tree for the graph.
* The method assumes that the graph is connected.
*
* The "done" instance variable is used to divide the vertices
* into two sets. Initially, the origin is in one set (the one
* containing vertices for which done == true), and all other
* vertices are in a second set (the one containing vertices for
* which done == false). We repeatedly add the lowest-cost edge
* joining a vertex in the first set to a vertex in the second
* set, and then we move the vertex in the second set to the first
* set by setting its done field to true.
*/
public void prim(String originID) {
reinitVertices();
/* Get the origin and mark it as done. */
Vertex origin = getVertex(originID);
if (origin == null) {
throw new IllegalArgumentException("no such vertex: " + originID);
}
origin.done = true;
while (true) {
/*
* Find the minimal-cost edge linking a done vertex with
* one that isn't done.
*/
Edge edgeToAdd = null;
Vertex v = vertices;
while (v != null) {
if (v.done) {
Edge e = v.edges;
while (e != null) {
if (!e.end.done &&
(edgeToAdd == null || e.cost < edgeToAdd.cost)) {
edgeToAdd = e;
}
e = e.next;
}
}
v = v.next;
}
/*
* If no such edge exists, we're done.
*/
if (edgeToAdd == null) {
return;
}
/* Add the edge and mark its end vertex done. */
System.out.println("\tadding edge (" + edgeToAdd.start.id + ", " +
edgeToAdd.end.id + ")");
edgeToAdd.end.parent = edgeToAdd.start;
edgeToAdd.end.done = true;
}
}
/**
* write a simple Java method that takes two Vertex objects as parameters and determines if the vertices are adjacent.
* The method should return true if the vertices are adjacent, and false if they are not adjacent. Keep in mind that
* the edges in the graph may be directed, which means that you may need to check both vertices’ adjacency lists.
*/
public boolean areAdjacent(Vertex v1, Vertex v2) {
Edge v1_edge = v1.edges;
Edge v2_edge = v2.edges;
while (v1_edge != null) {
if (v1_edge.end == v2) {
return true;
}
v1_edge = v1_edge.next;
}
while (v2_edge != null) {
if (v2_edge.end == v1) {
return true;
}
v2_edge = v2_edge.next;
}
return false;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Graph g = new Graph();
System.out.print("Graph info file: ");
String fileName = in.nextLine();
g.initFromFile(fileName);
System.out.print("starting point: ");
String start = in.nextLine();
System.out.println("depth-first traversal from " + start + ":");
g.depthFirstTrav(start);
System.out.println("breadth-first traversal from " + start + ":");
g.breadthFirstTrav(start);
System.out.println("Dijkstra's algorithm from " + start + ":");
g.dijkstra(start);
System.out.println("Prim's algorithm from " + start + ":");
g.prim(start);
// test areAdjacent()
Vertex v1 = g.getVertex("A");
Vertex v2 = g.getVertex("B");
System.out.println("areAdjacent(A, B) = " + g.areAdjacent(v1, v2));
}
}
Raw
heap.java
/*
* Heap.java
*
* Computer Science E-22
*
* Modifications and additions by:
* name:
* username:
*/
import java.util.*;
/**
* Heap - a generic collection class that implements
* a max-at-top heap using an array
*/
public class Heap<T extends Comparable<T>> {
private T[] contents;
private int numItems;
public Heap(int maxSize) {
contents = (T[])new Comparable[maxSize];
numItems = 0;
}
public Heap(T[] arr) {
// Note that we don't copy the array, so that heapsort can
// sort the array in place.
contents = arr;
numItems = arr.length;
makeHeap();
}
/*
* makeHeap - turn the elements in the contents array into a
* representation of a max-at-top heap.
*/
private void makeHeap() {
int last = contents.length - 1;
int parentOfLast = (last - 1)/2;
for (int i = parentOfLast; i >= 0; i--) {
siftDown(i);
}
}
/**
* insert - add the specified item to the heap and sift it up
* into its proper position.
*/
public void insert(T item) {
if (numItems == contents.length) {
// grow the array
T[] newContents = (T[])new Comparable[contents.length * 2];
System.arraycopy(contents, 0, newContents, 0, numItems);
contents = newContents;
}
contents[numItems] = item;
siftUp(numItems);
numItems++;
}
/**
* remove and return the item at the top of the heap, and adjust
* the remaining items so that we still have a heap.
*/
public T remove() {
if (numItems == 0) {
throw new NoSuchElementException();
}
T toRemove = contents[0];
// Move the element currently the end of the heap to the top
// and sift it into place.
contents[0] = contents[numItems - 1];
numItems--;
siftDown(0);
return toRemove;
}
/**
* isEmpty - does the heap currently have no items?
*/
public boolean isEmpty() {
return (numItems == 0);
}
/**
* toString - create a string representation of the heap of the form
* { ( root ) ( items in level 1 ) ( items in level 2 ) ... }
*/
public String toString() {
String str = "{ ";
int start = 0;
int levelSize = 1;
while (start < numItems) {
// print all of the items at the current level of the tree
str += "( ";
for (int i = start; i < start + levelSize && i < numItems; i++)
str += (contents[i] + " ");
str += ") ";
// move down to the next level
start += levelSize;
levelSize *= 2;
}
str += "}";
return str;
}
/*
* siftDown - sift the element in contents[i] down into its
* correct position in the heap.
*/
// private void siftDown(int i) {
// // Store a reference to the element being sifted.
// T toSift = contents[i];
// // Find where the sifted element belongs.
// int parent = i;
// int child = 2 * parent + 1;
// while (child < numItems) {
// // If the right child is bigger, compare with it.
// if (child < numItems - 1 &&
// contents[child].compareTo(contents[child + 1]) < 0) {
// child = child + 1;
// }
// // Check if we're done.
// if (toSift.compareTo(contents[child]) >= 0) {
// break;
// }
// // If not, move child up and move down one level in the tree.
// contents[parent] = contents[child];
// parent = child;
// child = 2 * parent + 1;
// }
// contents[parent] = toSift;
// }
/*
* Re write siftDown to use recursion instead of a loop.
*/
private void siftDown(int i) {
// Store a reference to the element being sifted.
T toSift = contents[i];
// Find where the sifted element belongs.
int parent = i;
int child = 2 * parent + 1;
if (child < numItems - 1 && contents[child].compareTo(contents[child + 1]) < 0) {
child = child + 1;
}
if (child < numItems && toSift.compareTo(contents[child]) < 0) {
contents[parent] = contents[child];
parent = child;
child = 2 * parent + 1;
if (child < numItems - 1 && contents[child].compareTo(contents[child + 1]) < 0) {
child = child + 1;
}
}
contents[parent] = toSift;
if (parent != i) {
siftDown(parent);
}
}
/*
* siftUp - sift the element in contents[i] up into its
* correct position in the heap.
*/
private void siftUp(int i) {
// Store a reference to the element being sifted.
T toSift = contents[i];
// Find where the sifted element belongs.
int child = i;
while (child > 0) {
int parent = (child - 1)/2;
// Check if we're done.
if (toSift.compareTo(contents[parent]) <= 0) {
break;
}
// If not, move parent down and move up one level in the tree.
contents[child] = contents[parent];
child = parent;
}
contents[child] = toSift;
}
public static void main(String[] args) {
System.out.println("Testing Heap");
System.out.println();
System.out.println("Testing siftDown() from problem 8");
System.out.println();
Integer [] arr = {20, 35, 17, 42, 50, 18, 32};
Heap<Integer> heap = new Heap<Integer>(arr);
System.out.println("Before:");
System.out.println(heap.toString());
heap.remove();
System.out.println("After:");
System.out.println(heap.toString());
System.out.println();
}
}
Raw
higway_graph.txt
Albany Worcester 134
Worcester Albany 134
Boston Worcester 44
Worcester Boston 44
Boston Providence 49
Providence Boston 49
Boston Portsmouth 54
Portsmouth Boston 54
Boston Concord 74
Concord Boston 74
Concord Worcester 63
Worcester Concord 63
Concord Portland 84
Portland Concord 84
NewYork Providence 185
Providence NewYork 185
Portland Portsmouth 39
Portsmouth Portland 39
Portsmouth Worcester 83
Worcester Portsmouth 83
Providence Worcester 42
Worcester Providence 42
Raw
LinkedTree.java
/*
* LinkedTree.java
*
* Computer Science E-22
*
* Modifications and additions by:
* name:
* username:
*/
import java.util.*;
/*
* LinkedTree - a class that represents a binary tree containing data
* items with integer keys. If the nodes are inserted using the
* insert method, the result will be a binary search tree.
*/
public class LinkedTree {
// An inner class for the nodes in the tree
private class Node {
private int key; // the key field
private LLList data; // list of data values for this key
private Node left; // reference to the left child/subtree
private Node right; // reference to the right child/subtree
private Node parent; // reference to the parent. NOT YET MAINTAINED!
private Node(int key, Object data) {
this.key = key;
this.data = new LLList();
this.data.addItem(data, 0);
this.left = null;
this.right = null;
this.parent = null;
}
}
// the root of the tree as a whole
private Node root;
public LinkedTree() {
root = null;
}
/*
* Prints the keys of the tree in the order given by a preorder traversal.
* Invokes the recursive preorderPrintTree method to do the work.
*/
public void preorderPrint() {
if (root != null) {
preorderPrintTree(root);
}
System.out.println();
}
/*
* Recursively performs a preorder traversal of the tree/subtree whose root is
* specified, printing the keys of the visited nodes. Note that the parameter is
* *not* necessarily the root of the entire tree.
*/
private static void preorderPrintTree(Node root) {
System.out.print(root.key + " ");
if (root.left != null) {
preorderPrintTree(root.left);
}
if (root.right != null) {
preorderPrintTree(root.right);
}
}
/*
* Prints the keys of the tree in the order given by a postorder traversal.
* Invokes the recursive postorderPrintTree method to do the work.
*/
public void postorderPrint() {
if (root != null) {
postorderPrintTree(root);
}
System.out.println();
}
/*
* Recursively performs a postorder traversal of the tree/subtree whose root is
* specified, printing the keys of the visited nodes. Note that the parameter is
* *not* necessarily the root of the entire tree.
*/
private static void postorderPrintTree(Node root) {
if (root.left != null) {
postorderPrintTree(root.left);
}
if (root.right != null) {
postorderPrintTree(root.right);
}
System.out.print(root.key + " ");
}
/*
* Prints the keys of the tree in the order given by an inorder traversal.
* Invokes the recursive inorderPrintTree method to do the work.
*/
public void inorderPrint() {
if (root != null) {
inorderPrintTree(root);
}
System.out.println();
}
/*
* Recursively performs an inorder traversal of the tree/subtree whose root is
* specified, printing the keys of the visited nodes. Note that the parameter is
* *not* necessarily the root of the entire tree.
*/
private static void inorderPrintTree(Node root) {
if (root.left != null) {
inorderPrintTree(root.left);
}
System.out.print(root.key + " ");
if (root.right != null) {
inorderPrintTree(root.right);
}
}
/*
* Inner class for temporarily associating a node's depth with the node, so that
* levelOrderPrint can print the levels of the tree on separate lines.
*/
private class NodePlusDepth {
private Node node;
private int depth;
private NodePlusDepth(Node node, int depth) {
this.node = node;
this.depth = depth;
}
}
/*
* Prints the keys of the tree in the order given by a level-order traversal.
*/
public void levelOrderPrint() {
LLQueue<NodePlusDepth> q = new LLQueue<NodePlusDepth>();
// Insert the root into the queue if the root is not null.
if (root != null) {
q.insert(new NodePlusDepth(root, 0));
}
// We continue until the queue is empty. At each step,
// we remove an element from the queue, print its value,
// and insert its children (if any) into the queue.
// We also keep track of the current level, and add a newline
// whenever we advance to a new level.
int level = 0;
while (!q.isEmpty()) {
NodePlusDepth item = q.remove();
if (item.depth > level) {
System.out.println();
level++;
}
System.out.print(item.node.key + " ");
if (item.node.left != null) {
q.insert(new NodePlusDepth(item.node.left, item.depth + 1));
}
if (item.node.right != null) {
q.insert(new NodePlusDepth(item.node.right, item.depth + 1));
}
}
System.out.println();
}
/*
* Searches for the specified key in the tree. If it finds it, it returns the
* list of data items associated with the key. Invokes the recursive searchTree
* method to perform the actual search.
*/
public LLList search(int key) {
Node n = searchTree(root, key);
if (n == null) {
return null;
} else {
return n.data;
}
}
/*
* Recursively searches for the specified key in the tree/subtree whose root is
* specified. Note that the parameter is *not* necessarily the root of the
* entire tree.
*/
private static Node searchTree(Node root, int key) {
if (root == null) {
return null;
} else if (key == root.key) {
return root;
} else if (key < root.key) {
return searchTree(root.left, key);
} else {
return searchTree(root.right, key);
}
}
/*
* Inserts the specified (key, data) pair in the tree so that the tree remains a
* binary search tree.
*/
public void insert(int key, Object data) {
// Find the parent of the new node.
Node parent = null;
Node trav = root;
while (trav != null) {
if (trav.key == key) {
trav.data.addItem(data, 0);
return;
}
parent = trav;
if (key < trav.key) {
trav = trav.left;
} else {
trav = trav.right;
}
}
// Insert the new node.
Node newNode = new Node(key, data);
// When a Node object is first inserted in the tree, you should set its parent
// field to point to the appropriate parent node.
newNode.parent = parent;
if (parent == null) { // the tree was empty
root = newNode;
} else if (key < parent.key) {
parent.left = newNode;
} else {
parent.right = newNode;
}
}
/*
* FOR TESTING: Processes the integer keys in the specified array from left to
* right, adding a node for each of them to the tree. The data associated with
* each key is a string based on the key.
*/
public void insertKeys(int[] keys) {
for (int i = 0; i < keys.length; i++) {
insert(keys[i], "data for key " + keys[i]);
}
}
/*
* Deletes the node containing the (key, data) pair with the specified key from
* the tree and return the associated data item.
*/
public LLList delete(int key) {
// Find the node to be deleted and its parent.
Node parent = null;
Node trav = root;
while (trav != null && trav.key != key) {
parent = trav;
if (key < trav.key) {
trav = trav.left;
} else {
trav = trav.right;
}
}
// Delete the node (if any) and return the removed data item.
if (trav == null) { // no such key
return null;
} else {
LLList removedData = trav.data;
deleteNode(trav, parent);
return removedData;
}
}
/*
* Deletes the node specified by the parameter toDelete. parent specifies the
* parent of the node to be deleted.
*/
private void deleteNode(Node toDelete, Node parent) {
if (toDelete.left != null && toDelete.right != null) {
// Case 3: toDelete has two children.
// Find a replacement for the item we're deleting -- as well as
// the replacement's parent.
// We use the smallest item in toDelete's right subtree as
// the replacement.
Node replaceParent = toDelete;
Node replace = toDelete.right;
while (replace.left != null) {
replaceParent = replace;
replace = replace.left;
}
// Replace toDelete's key and data with those of the
// replacement item.
toDelete.key = replace.key;
toDelete.data = replace.data;
// Recursively delete the replacement item's old node.
// It has at most one child, so we don't have to
// worry about infinite recursion.
deleteNode(replace, replaceParent);
} else {
// Cases 1 and 2: toDelete has 0 or 1 child
Node toDeleteChild;
if (toDelete.left != null) {
toDeleteChild = toDelete.left;
} else {
toDeleteChild = toDelete.right; // null if it has no children
}
if (toDelete == root) {
root = toDeleteChild;
} else if (toDelete.key < parent.key) {
parent.left = toDeleteChild;
} else {
parent.right = toDeleteChild;
}
}
}
/* Returns a preorder iterator for this tree. */
public LinkedTreeIterator preorderIterator() {
return new PreorderIterator();
}
/*
* inner class for a preorder iterator IMPORTANT: You will not be able to
* actually use objects from this class to perform a preorder iteration until
* you have modified the LinkedTree methods so that they maintain the parent
* fields in the Nodes.
*/
private class PreorderIterator implements LinkedTreeIterator {
private Node nextNode;
private PreorderIterator() {
// The traversal starts with the root node.
nextNode = root;
}
public boolean hasNext() {
return (nextNode != null);
}
public int next() {
if (nextNode == null) {
throw new NoSuchElementException();
}
// Store a copy of the key to be returned.
int key = nextNode.key;
// Advance nextNode.
if (nextNode.left != null) {
nextNode = nextNode.left;
} else if (nextNode.right != null) {
nextNode = nextNode.right;
} else {
// We've just visited a leaf node.
// Go back up the tree until we find a node
// with a right child that we haven't seen yet.
Node parent = nextNode.parent;
Node child = nextNode;
while (parent != null && (parent.right == child || parent.right == null)) {
child = parent;
parent = parent.parent;
}
if (parent == null) {
nextNode = null; // the traversal is complete
} else {
nextNode = parent.right;
}
}
return key;
}
}
/*
* "wrapper method" for the recursive numSmallerInTree() method from PS 4,
* Problem 1
*/
public int numSmaller(int t) {
if (root == null) { // root is the root of the entire tree
return 0;
}
return numSmallerInTree(root, t);
}
/*
* write a more efficient version of this method. Your new method should avoid
* visiting nodes unnecessarily. In the same way that the search for a key
* doesn’t consider every node in the tree, your method should avoid considering
* subtrees that couldn’t contain values less than the threshold. Like the
* original version of the method above, your revised method should also be
* recursive.
*/
private static int numSmallerInTree(Node root, int t) {
if (root == null) {
return 0;
}
int numSmaller = 0;
if (root.key < t) {
numSmaller = 1 + numSmallerInTree(root.left, t) + numSmallerInTree(root.right, t);
} else {
numSmaller = numSmallerInTree(root.left, t);
}
return numSmaller;
}
/*
* Write a non-static sumKeysTo(int key) method that takes takes an integer key
* as its only parameter and that uses uses iteration to determine and return
* the sum of the keys on the path from the root node to the node with the
* specified key, including the key itself. Your method should take advantage of
* the fact that the tree is a binary search tree, and it should avoid
* considering subtrees that couldn’t contain the specified key. It should
* return 0 if the specified key is not found in the tree.
*/
public int sumKeysTo(int key) {
int counter = 0;
Node trav = root;
while (trav != null && trav.key != key) {
if (key < trav.key) {
counter += trav.key;
trav = trav.left;
} else {
counter += trav.key;
trav = trav.right;
}
}
if (trav == null) {
return 0;
} else {
return counter + trav.key;
}
}
/*
* a private static method called numLeafNodesInTree() that takes a reference to
* a Node object as its only parameter; it should use recursion to find and
* return the number of leaf nodes in the binary search tree or subtree whose
* root node is specified by the parameter. Make sure that your method correctly
* handles empty trees/subtrees – i.e., cases in which the value of the
* parameter root is null.
*/
private static int numLeafNodesInTree(Node root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int rest = numLeafNodesInTree(root.left) + numLeafNodesInTree(root.right);
return rest;
}
/*
* a public non-static method called numLeafNodes() that takes no parameters and
* that returns the number of leaf nodes in the entire tree. This method should
* serve as a “wrapper” method for numLeafNodesInTree(). It should make the
* initial call to that method – passing in the root of the tree as a whole –
* and it should return whatever value that method returns.
*/
public int numLeafNodes() {
return numLeafNodesInTree(root);
}
/*
* Write a non-static method deleteSmallest() that takes no parameters and that
* uses iteration to find and delete the node containing the smallest key in the
* tree; it should also return the value of the key whose node was deleted. If
* the tree is empty when the method is called, the method should return -1.
* deleteSmallest() method may not call any of the other LinkedTree methods
* (including the delete() method), and it may not use any helper methods.
* Rather, this method must take all of the necessary steps on its own –
* including correctly handling any child that the smallest node may have.
*/
public int deleteSmallest() {
Node trav = root;
int smallest;
if (root == null) {
return -1;
}
Node parent = root;
Node trailing = root;
if (trav.left == null && trav.right == null) {
smallest = root.key;
root = null;
return -1;
} else if (trav.left == null) {
trav = trav.right;
root = trav;
trailing = parent;
} else {
trav = root;
}
while (trav.left != null && trailing.left != null) {
parent = trav;
trav = trav.left;
}
if (trailing.left == null) {
smallest = trailing.key;
} else {
smallest = trav.key;
}
if (trav.left == null && trav.right == null) {
parent.left = null;
} else {
if (trav.right != null) {
if (root.left == null) {
trailing = trav;
parent.right = trav.right;
} else {
parent.left = trav.right;
trailing = parent;
}
}
}
return smallest;
}
/*
* you will add support for more flexible tree traversals by implementing an
* iterator for our LinkedTree class. You should use an inner class to implement
* the iterator, and it should implement the following interface: public
* interface LinkedTreeIterator { Are there other nodes to see in this
* traversal? boolean hasNext(); Return the value of the key in the next node in
* the traversal, and advance the position of the iterator. int next(); } There
* are a number of types of binary-tree iterators that we could implement. We
* have given you the implementation of a preorder iterator (the inner class
* PreorderIterator), and you will implement a postorder iterator for this
* problem. Your postorder iterator class should implement the hasNext() and
* next() methods so that, given a reference named tree to an arbitrary
* LinkedTree object, the following code will perform a complete postorder
* traversal of the corresponding tree: LinkedTreeIterator iter =
* tree.postorderIterator(); while (iter.hasNext()) { int key = iter.next(); do
* something with key } In theory, one approach to implementing a tree iterator
* would be to perform a full recursive traversal of the tree when the iterator
* is first created and to insert the visited nodes in an auxiliary data
* structure (e.g., a list). The iterator would then iterate over that data
* structure to perform the traversal. You should not use this approach. In
* order for an iterator to work, it’s necessary for each node to maintain a
* reference to its parent in the tree. These parent references will allow the
* iterator to work its way back up the tree.
*/
public LinkedTreeIterator postorderIterator() {
return new PostorderIterator();
}
private class PostorderIterator implements LinkedTreeIterator {
private Node nextNode;
public PostorderIterator() {
nextNode = root;
while (true) {
if (nextNode.left != null) {
nextNode = nextNode.left;
} else if (nextNode.right != null) {
nextNode = nextNode.right;
} else {
break;
}
}
}
public boolean hasNext() {
return nextNode != null;
}
/*
* Implement the next() method in your iterator class. Make sure that it
* includes support for situations in which it is necessary to follow one or
* more parent links back up the tree, as well as situations in which there are
* no additional nodes to visit. If the user calls the next() method when there
* are no remaining nodes to visit, the method should throw a
* NoSuchElementException
*/
public int next() {
Node parent = nextNode.parent;
Node trav = nextNode;
if (nextNode == null) {
throw new NoSuchElementException();
} else if (parent == null) {
nextNode = null;
return trav.key;
}
int key = trav.key;
if (nextNode.right != null && nextNode.parent != root && nextNode.parent.right == null) {
nextNode = parent;
while (nextNode.left != null && nextNode.left != trav) {
nextNode = nextNode.left;
}
} else {
if (parent.right != null && parent.right.key != key) {
trav = parent.right;
if (parent == root && trav.right != null) {
nextNode = trav.right;
while (nextNode.left != null) {
nextNode = nextNode.left;
}
} else {
nextNode = parent.right;
trav = nextNode;
while (true) {
if (trav.right != null) {
nextNode = nextNode.right;
parent = nextNode;
trav = nextNode;
} else if (trav.left != null) {
nextNode = nextNode.left;
parent = nextNode;
trav = nextNode;
} else {
break;
}
}
}
} else {
nextNode = parent;
}
}
return key;
}
}
public static void main(String[] args) {
System.out.println("--- Testing numSmaller()/numSmallerInTree() from Problem 1 ---");
System.out.println();
System.out.println("(0) Testing on tree from Problem 4, num smaller than 45");
try {
LinkedTree tree = new LinkedTree();
int[] keys = { 37, 26, 42, 13, 35, 56, 30, 47, 70 };
tree.insertKeys(keys);
int results = tree.numSmaller(45);
System.out.println("actual results:");
System.out.println(results);
System.out.println("expected results:");
System.out.println(6);
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(results == 6);
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
/*
* Add at least two unit tests for each method from Problem 6. Test a variety of
* different cases. Follow the same format that we have used above.
*/
System.out.println(); // include a blank line between tests
System.out.println("--- Testing sumKeysTo() from Problem 6 ---");
System.out.println();
System.out.println("(0) Testing on tree from Problem 6, sum of keys up to 50");
try {
LinkedTree tree = new LinkedTree();
int[] keys = { 37, 26, 42, 13, 35, 56, 30, 47, 70 };
tree.insertKeys(keys);
int results = tree.sumKeysTo(50);
System.out.println("actual results:");
System.out.println(results);
System.out.println("expected results:");
System.out.println(0);
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(results == 0);
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
System.out.println("--- Second test of sumKeysTo() from Problem 6 ---");
System.out.println();
System.out.println("(0) Testing on tree from Problem 6, sum of keys up to 56");
try {
LinkedTree tree = new LinkedTree();
int[] keys = { 37, 26, 42, 13, 35, 56, 30, 47, 70 };
tree.insertKeys(keys);
int results = tree.sumKeysTo(56);
System.out.println("actual results:");
System.out.println(results);
System.out.println("expected results:");
System.out.println(135);
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(results == 135);
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
System.out.println("--- Testing numLeafNodes() from Problem 6 ---");
System.out.println();
System.out.println("(0) Testing on tree from Problem 6, number of leafs in a tree");
try {
LinkedTree tree = new LinkedTree();
int[] keys = { 37, 26, 42, 13, 35, 56, 30, 47, 70 };
tree.insertKeys(keys);
int results = tree.numLeafNodes();
System.out.println("actual results:");
System.out.println(results);
System.out.println("expected results:");
System.out.println(4);
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(results == 4);
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
System.out.println("--- Second test of numLeafNodes() from Problem 6 ---");
System.out.println();
System.out.println("(0) Testing on tree from Problem 6, number of leafs in a tree");
try {
LinkedTree tree = new LinkedTree();
int results = tree.numLeafNodes();
System.out.println("actual results:");
System.out.println(results);
System.out.println("expected results:");
System.out.println(0);
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(results == 0);
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
System.out.println("--- Test of deleteSmallest() from Problem 6 ---");
System.out.println();
System.out.println("(0) Testing on tree from Problem 6, delete smallest");
try {
LinkedTree tree = new LinkedTree();
int[] keys = { 37, 26, 42, 13, 35, 56, 30, 47, 70 };
tree.insertKeys(keys);
int results = tree.deleteSmallest();
System.out.println("actual results:");
System.out.println(results);
System.out.println("expected results:");
System.out.println(13);
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(results == 13);
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
System.out.println("--- Second test of deleteSmallest() from Problem 6 ---");
System.out.println();
System.out.println("(0) Testing on tree from Problem 6, delete smallest");
try {
LinkedTree tree = new LinkedTree();
int[] keys = { 37, 26, 42, 13, 35, 56, 30, 47, 70 };
tree.insertKeys(keys);
int results = tree.deleteSmallest();
int results2 = tree.deleteSmallest();
System.out.println("actual results:");
System.out.println(results2);
System.out.println("expected results:");
System.out.println(26);
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(results2 == 26);
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
System.out.println("--- Testing preorderIterator() from Problem 6 ---");
System.out.println();
System.out.println("(0) Testing on tree from Problem 6, preorderIterator");
try {
LinkedTree tree = new LinkedTree();
int[] keys = { 37, 26, 42, 13, 35, 56, 30, 47, 70 };
tree.insertKeys(keys);
LinkedTreeIterator results = tree.preorderIterator();
System.out.println("actual results:");
while (results.hasNext()) {
System.out.print(results.next() + " ");
}
System.out.println();
System.out.println("expected results:");
System.out.println("37 26 13 35 30 42 56 47 70");
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(results.next() == 37 && results.next() == 26 && results.next() == 13
&& results.next() == 35 && results.next() == 30 && results.next() == 42 && results.next() == 56
&& results.next() == 47 && results.next() == 70);
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
// preorderPrintTree() prints the tree in preorder
System.out.println("--- Testing preorderPrintTree() ---");
System.out.println();
System.out.println("(0) Testing on tree, preorderPrintTree");
try {
LinkedTree tree = new LinkedTree();
int[] keys = { 37, 26, 42, 13, 35, 56, 30, 47, 70 };
tree.insertKeys(keys);
System.out.println("actual results:");
preorderPrintTree(tree.root);
System.out.println();
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(true);
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
// postorderPrint() prints the tree in preorder
System.out.println("--- Testing postorderPrint() ---");
System.out.println();
System.out.println("(0) Testing on tree, postorderPrint()");
try {
LinkedTree tree = new LinkedTree();
int[] keys = {26, 12, 32, 4, 18, 28};
tree.insertKeys(keys);
System.out.println("actual results:");
tree.postorderPrint();
System.out.println();
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(true);
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
System.out.println("--- Testing postorderIterator() from Problem 7 ---");
System.out.println();
System.out.println("(0) Testing on tree from Problem 7, postorderIterator");
try {
LinkedTree tree = new LinkedTree();
int[] keys = { 37, 26, 42, 13, 35, 56, 30, 47, 70 };
int[] keys2 = { 13, 30, 35, 26, 47, 70, 56, 42, 37 };
tree.insertKeys(keys);
LinkedTreeIterator results = tree.postorderIterator();
System.out.println("actual results:");
int index = 0;
while (results.hasNext()) {
int results2 = results.next();
System.out.print(results2 + " ");
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(results2 == keys2[index]);
index++;
}
System.out.println();
System.out.println("expected results:");
System.out.println("13, 30, 35, 26, 47, 70, 56, 42, 37");
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
System.out.println("--- Second postorderIterator() from Problem 7 ---");
System.out.println();
System.out.println("(0) Testing on tree from Problem 7, postorderIterator");
try {
LinkedTree tree = new LinkedTree();
int[] keys = {26, 12, 32, 4, 18, 28};
int[] keys2 = {4, 18, 12, 28, 32, 26};
tree.insertKeys(keys);
LinkedTreeIterator results = tree.postorderIterator();
System.out.println("actual results:");
int index = 0;
while (results.hasNext()) {
int results2 = results.next();
System.out.print(results2 + " ");
System.out.print("MATCHES EXPECTED RESULTS?: ");
System.out.println(results2 == keys2[index]);
index++;
}
System.out.println();
System.out.println("expected results:");
System.out.println("4, 18, 12, 28, 32, 26");
} catch (Exception e) {
System.out.println("INCORRECTLY THREW AN EXCEPTION: " + e);
}
System.out.println(); // include a blank line between tests
}
}
Raw
linkedtreeiterator.java
/*
* LinkedTreeIterator.java
*
* Computer Science E-22
*
* YOU SHOULD *NOT* NEED TO MODIFY THIS FILE.
*/
/**
* An interface that describes the functionality that must be supported
* by classes that implement iterators for LinkedTree objects.
*/
public interface LinkedTreeIterator {
// Are there other nodes to see in this traversal?
boolean hasNext();
// Return the value of the key in the next node in the
// traversal, and advance the position of the iterator.
int next();
}
Raw
LLQueue.java
/*
* LLQueue.java
*
* Computer Science E-22
*/
/*
* A generic class that implements our Queue interface using a linked list.
*/
public class LLQueue<T> implements Queue<T> {
// Inner class for a node. We use an inner class so that the LLQueue
// methods can access the fields of the nodes.
private class Node {
private T item;
private Node next;
private Node(T i, Node n) {
item = i;
next = n;
}
}
// the fields of the LLQueue object
private Node front; // the node containing the item at the front
private Node rear; // the node containing the item at the rear
/*
* Constructs an LLQueue object for a queue that is initially
* empty.
*/
public LLQueue() {
front = null;
rear = null;
}
/*
* isEmpty - returns true if the queue is empty, and false otherwise
*/
public boolean isEmpty() {
return (front == null);
}
/*
* isFull - always returns false, because the linked list can
* grow indefinitely and thus the queue is never full.
*/
public boolean isFull() {
return false;
}
/*
* insert - adds the specified item at the rear of the queue.
* Always returns true, because the linked list is never full.
*/
public boolean insert(T item) {
Node newNode = new Node(item, null);
if (isEmpty()) {
front = newNode;
rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
return true;
}
/*
* remove - removes the item at the front of the queue and returns a
* reference to the removed object. Returns null if the queue is
* empty.
*/
public T remove() {
if (isEmpty()) {
return null;
}
T removed = front.item;
if (front == rear) { // removing the only item
front = null;
rear = null;
} else {
front = front.next;
}
return removed;
}
/*
* peek - returns a reference to the item at the front of the queue
* without removing it. Returns null if the queue is empty.
*/
public T peek() {
if (isEmpty()) {
return null;
}
return front.item;
}
/*
* toString - converts the stack into a String of the form
* {front, one-after-front, two-after-front, ...}
*/
public String toString() {
String str = "{";
Node trav = front;
while (trav != null) {
str = str + trav.item;
if (trav.next != null)
str = str + ", ";
trav = trav.next;
}
str = str + "}";
return str;
}
}
Raw
ModeFinder.java
import java.util.*;
public class ModeFinder {
public static int findMode(int[] arr) {
ModeFinder.quickSort(arr);
int current_val = arr[0]; // this is the current element's value
int most_freq_val = 0; // Stores the value of the element which has the most freq
int freq_of_current_val = 1; // this is the freq of the current val
int freq_of_most_freq_val = 0; // this is the freq of the most_freq_val
int v = 0;
for (int i = 1; i < arr.length; i++) {
v = arr[i];
if (v == current_val) {
freq_of_current_val = freq_of_current_val + 1;
}
else{
if (freq_of_most_freq_val < freq_of_current_val) {
freq_of_most_freq_val = freq_of_current_val;
most_freq_val = current_val;
}
else if (freq_of_most_freq_val==freq_of_current_val) {
if (current_val<most_freq_val) {
most_freq_val = current_val;
}
}
current_val = v;
freq_of_current_val = 1;
}
}
if (freq_of_most_freq_val < freq_of_current_val) {
freq_of_most_freq_val = freq_of_current_val;
most_freq_val = current_val;
}
else if (freq_of_most_freq_val==freq_of_current_val) {
if (current_val<most_freq_val) {
most_freq_val = current_val;
}
}
current_val = v;
freq_of_current_val = 1;
return most_freq_val;
}
/* Swap method*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/* partition - helper method for qSort */
public static int partition(int[] arr, int first, int last) {
int pivot = arr[(first + last)/2];
int i = first - 1; // index going left to right
int j = last + 1; // index going right to left
while (true) {
// moving from left to right, find an element >= the pivot
do {
i++;
} while (arr[i] < pivot);
// moving from right to left, find an element <= the pivot
do {
j--;
} while (arr[j] > pivot);
// If the indices still haven't met or crossed,
// swap the elements so that they end up in the correct subarray.
// Otherwise, the partition is complete and we return j.
if (i < j) {
swap(arr, i, j);
} else {
return j; // index of last element in the left subarray
}
}
}
/* qSort - recursive method that does the work for quickSort */
private static void qSort(int[] arr, int first, int last) {
int split = partition(arr, first, last);
if (first < split) {
qSort(arr, first, split); // left subarray
}
if (last > split + 1) {
qSort(arr, split + 1, last); // right subarray
}
}
/** quicksort */
public static void quickSort(int[] arr) {
qSort(arr, 0, arr.length - 1);
}
public static void main(String[] args) {
int[] arr = {7, 5, 3, 5, 7, 11, 11};
System.out.println(ModeFinder.findMode(arr));
}
}
Raw
printOddsRecur.java
//Prints Odds in a Linked list with recurssion
import java.util.*;
public class IntNode {
private int val;
private IntNode next;
public IntNode(int val, IntNode n) {
this.val = val;
this.next = n;
}
public static int length(IntNode n) {
if (n == null) {
return 0;
} else {
int lenRest = length(n.next);
return 1 + lenRest;
}
}
public static void printOddsRecur(IntNode n) {
if (n == null) {
return;
}
if (n.val % 2 == 0) {
printOddsRecur(n.next);
}
else {
System.out.println(n.val);
printOddsRecur(n.next);
}
}
public static void main(String[] args) {
IntNode str1 = null;
//System.out.println(IntNode.length(str1));
IntNode node1 = new IntNode(2, null);
str1 = node1;
//System.out.println(IntNode.length(str1));
IntNode node2 = new IntNode(2, null);
node1.next = node2;
IntNode node3 = new IntNode(4, null);
node2.next = node3;
//System.out.println(IntNode.length(str1));
IntNode.printOddsRecur(str1);
}
}
Raw
Problem7.java
// takes a sorted array of integers and removes whatever elements are necessary to ensure that no item appears more than once.
public class Problem7 {
public static int removeDups(int[] arr) {
int count = 0;
int temp = arr[0];
for (int i = 0 + 1; i < arr.length; i++) {
if (arr[i-1] == 0 && arr[i] != temp) {
temp = arr[i];
arr[i - count] = arr[i];
arr[i] = 0;
continue;
}
if (arr[i] != temp) {
temp = arr[i];
continue;
}
if (arr[i] == temp) {
temp = arr[i];
count++;
arr[i] = 0;
continue;
}
}
return arr.length - count;
}
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,5};
System.out.println(Problem7.removeDups(arr));
}
}
Raw
problem8.java
// Sorts 2 arrays takes two arrays of integers as parameters and uses an approach based on merging to find and
// return the intersection of the two arrays.
// Contains helpers for different sorting algorithms.
import java.util.*;
public class Problem8 {
public static int[] findIntersect(int[] arr1, int[] arr2) {
Problem8.quickSort(arr1);
Problem8.quickSort(arr2);
int arr1_length = arr1.length;
int arr2_length = arr2.length;
int[] new_Array;
if (arr1_length <= arr2_length) {
new_Array = new int[arr1_length];
} else {
new_Array = new int[arr2_length];
}
int i = 0; // index into arr1
int j = 0; // index into arr2
int k = 0; // index into temp
while (i <= arr1.length - 1 && j <= arr2.length - 1) {
if (arr1[i] != arr2[j]) {
if (i == arr1.length - 1 && j == arr2.length - 1 ) {
break;
}
if (arr1[i] < arr2[j]) {
i++;
} else {
j++;
}
} else {
if (i == arr1.length - 1 && j == arr2.length - 1 ) {
new_Array[k] = arr1[i];
break;
} else {
new_Array[k] = arr1[i];
i++;
k++;
j++;
}
}
}
return new_Array;
}
/* Swap method */
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/* partition - helper method for qSort */
public static int partition(int[] arr, int first, int last) {
int pivot = arr[(first + last) / 2];
int i = first - 1; // index going left to right
int j = last + 1; // index going right to left
while (true) {
// moving from left to right, find an element >= the pivot
do {
i++;
} while (arr[i] < pivot);
// moving from right to left, find an element <= the pivot
do {
j--;
} while (arr[j] > pivot);
// If the indices still haven't met or crossed,
// swap the elements so that they end up in the correct subarray.
// Otherwise, the partition is complete and we return j.
if (i < j) {
swap(arr, i, j);
} else {
return j; // index of last element in the left subarray
}
}
}
/* qSort - recursive method that does the work for quickSort */
private static void qSort(int[] arr, int first, int last) {
int split = partition(arr, first, last);
if (first < split) {
qSort(arr, first, split); // left subarray
}
if (last > split + 1) {
qSort(arr, split + 1, last); // right subarray
}
}
/** quicksort */
public static void quickSort(int[] arr) {
qSort(arr, 0, arr.length - 1);
}
public static void main(String[] args) {
int[] arr1 = {2, 3, 4, 5};
int[] arr2 = {1, 3, 5};
System.out.println(Arrays.toString(Problem8.findIntersect(arr1, arr2)));
}
}
Raw
pset3problem5.java
/*
* StringNode.java
*
* Computer Science E-22
*
* modified by:
* name:
* email:
*/
import java.io.*;
import java.util.*;
/**
* A class for representing a string using a linked list.
* Each character of the string is stored in a separate node.
*
* This class represents one node of the linked list. The string as a
* whole is represented by storing a reference to the first node in
* the linked list. The methods in this class are static methods that
* take a reference to a string linked-list as a parameter. This
* approach allows us to use recursion to write many of the methods,
* and it also allows the methods to handle empty strings, which are
* represented using a value of null.
*/
public class StringNode {
char ch;
StringNode next;
/**
* Constructor
*/
public StringNode(char c, StringNode n) {
this.ch = c;
this.next = n;
}
/**
* getNode - private helper method that returns a reference to
* node i in the given linked-list string. If the string is too
* short or if the user passes in a negative i, the method returns null.
*/
private static StringNode getNode(StringNode str, int i) {
if (i < 0 || str == null) { // base case 1: not found
return null;
} else if (i == 0) { // base case 2: just found
return str;
} else {
return getNode(str.next, i - 1);
}
}
/*****************************************************
* Public methods (in alphabetical order)
*****************************************************/
/**
* charAt - returns the character at the specified index of the
* specified linked-list string, where the first character has
* index 0. If the index i is < 0 or i > length - 1, the method
* will end up throwing an IllegalArgumentException.
*/
public static char charAt(StringNode str, int i) {
if (str == null) {
throw new IllegalArgumentException("the string is empty");
}
StringNode node = getNode(str, i);
if (node != null) {
return node.ch;
} else {
throw new IllegalArgumentException("invalid index: " + i);
}
}
/**
* convert - converts a standard Java String object to a linked-list
* string and returns a reference to the linked-list string
*/
public static StringNode convert(String s) {
if (s.length() == 0) {
return null;
}
StringNode firstNode = new StringNode(s.charAt(0), null);
StringNode prevNode = firstNode;
StringNode nextNode;
for (int i = 1; i < s.length(); i++) {
nextNode = new StringNode(s.charAt(i), null);
prevNode.next = nextNode;
prevNode = nextNode;
}
return firstNode;
}
/**
* copy - returns a copy of the given linked-list string
*/
public static StringNode copy(StringNode str) {
StringNode headNode = null;
StringNode prevNode = null;
StringNode trav = null;
StringNode last = null;
trav = str;
StringNode node = new StringNode(trav.ch, null);
headNode = node;
last = node;
while (trav.next != null) {
trav = trav.next;
StringNode newNode = new StringNode(trav.ch, null);
prevNode = newNode;
last.next = prevNode;
last = last.next;
}
return headNode;
}
/**
* deleteChar - deletes character i in the given linked-list string and
* returns a reference to the resulting linked-list string
*/
public static StringNode deleteChar(StringNode str, int i) {
if (str == null) {
throw new IllegalArgumentException("string is empty");
} else if (i < 0) {
throw new IllegalArgumentException("invalid index: " + i);
} else if (i == 0) {
str = str.next;
} else {
StringNode prevNode = getNode(str, i-1);
if (prevNode != null && prevNode.next != null) {
prevNode.next = prevNode.next.next;
} else {
throw new IllegalArgumentException("invalid index: " + i);
}
}
return str;
}
/**
* insertChar - inserts the character ch before the character
* currently in position i of the specified linked-list string.
* Returns a reference to the resulting linked-list string.
*/
public static StringNode insertChar(StringNode str, int i, char ch) {
StringNode newNode, prevNode;
if (i < 0) {
throw new IllegalArgumentException("invalid index: " + i);
} else if (i == 0) {
newNode = new StringNode(ch, str);
str = newNode;
} else {
prevNode = getNode(str, i - 1);
if (prevNode != null) {
newNode = new StringNode(ch, prevNode.next);
prevNode.next = newNode;
} else {
throw new IllegalArgumentException("invalid index: " + i);
}
}
return str;
}
/**
* insertSorted - inserts character ch in the correct position
* in a sorted list of characters (i.e., a sorted linked-list string)
* and returns a reference to the resulting list.
*/
public static StringNode insertSorted(StringNode str, char ch) {
StringNode newNode, trail, trav;
// Find where the character belongs.
trail = null;
trav = str;
while (trav != null && trav.ch < ch) {
trail = trav;
trav = trav.next;
}
// Create and insert the new node.
newNode = new StringNode(ch, trav);
if (trail == null) {
// We never advanced the prev and trav references, so
// newNode goes at the start of the list.
str = newNode;
} else {
trail.next = newNode;
}
return str;
}
/**
* length - recursively determines the number of characters in the
* linked-list string to which str refers
*/
public static int length(StringNode str) {
StringNode trav = str;
int counter = 0;
while (trav != null) {
trav = trav.next;
counter++;
}
return counter;
}
/**
* numOccur - find the number of occurrences of the character
* ch in the linked list to which str refers
*/
public static int numOccur(StringNode str, char ch) {
if (str == null) {
return 0;
}
int numInRest = numOccur(str.next, ch);
if (str.ch == ch) {
return 1 + numInRest;
} else {
return numInRest;
}
}
/**
* print - recursively writes the specified linked-list string to
* System.out
*/
public static void print(StringNode str) {
if (str == null) {
return;
} else {
System.out.print(str.ch);
print(str.next);
}
}
/**
* printReverse - recursively writes the reverse of the specified
* linked-list string to System.out
*/
public static void printReverse(StringNode str) {
int str_length = length(str);
char[] char_array = new char[str_length];
StringNode trav = str;
int i = 0;
while (trav != null) {
i = i + 1;
char_array[char_array.length - i] = trav.ch;
trav = trav.next;
}
System.out.println(Arrays.toString(char_array));
}
/**
* read - reads a string from an input stream and returns a
* reference to a linked list containing the characters in the string
*/
public static StringNode read(InputStream in) throws IOException {
char ch = (char)in.read();
if (ch == '\n') { // string ends when we hit a newline character
return null;
} else {
StringNode restOfString = read(in);
StringNode first = new StringNode(ch, restOfString);
return first;
}
}
/**
* removeFirst - takes the linked-list string specified by str and
* removes the first occurrence (if any) of the character ch in
* that string.
*/
public static StringNode removeFirst(StringNode str, char ch) {
StringNode trav = str;
StringNode trail = null;
if (str == null) {
return str;
}
if (str.ch == ch) {
trail = trav;
trav = trav.next;
trail.next = trav.next;
removeFirst(str.next, ch);
return str;
}
else {
trail = trav;
trav = trav.next;
removeFirst(str.next, ch);
return str;
}
}
/**
* toString - creates and returns the Java string that
* the current StringNode represents. Note that this
* method -- unlike the others -- is a non-static method.
* Thus, it will not work for empty strings, since they
* are represented by a value of null, and we can't use
* null to invoke this method.
*/
public String toString() {
String str = "";
StringNode trav = this; // start trav on the current node
while (trav != null) {
str = str + trav.ch;
trav = trav.next;
}
return str;
}
/**
* toUpperCase - converts all of the characters in the specified
* linked-list string to upper case. Modifies the list itself,
* rather than creating a new list.
*/
public static void toUpperCase(StringNode str) {
if (str == null) {
return;
} else {
str.ch = Character.toUpperCase(str.ch);
toUpperCase(str.next);
}
}
public static void main(String[] args) throws IOException {
StringNode copy, str, str1, str2, str3;
String line;
int n;
char ch;
// convert, print, and toUpperCase
str = StringNode.convert("fine");
System.out.print("Here's a string: ");
StringNode.print(str);
System.out.println();
System.out.print("Here it is in upper-case letters: ");
StringNode.toUpperCase(str);
StringNode.print(str);
System.out.println();
System.out.println();
Scanner in = new Scanner(System.in);
// read, toString, length, and printReverse.
System.out.print("Type a string: ");
String s = in.nextLine();
str1 = StringNode.convert(s);
System.out.print("Your string is: ");
System.out.println(str1); // implicit toString call
System.out.print("\nHere it is reversed: ");
StringNode.printReverse(str1);
System.out.println("\nIts length is " + StringNode.length(str1) +
" characters.");
// charAt
n = -1;
while (n < 0) {
System.out.print("\nWhat # character to get (>= 0)? ");
n = in.nextInt();
in.nextLine();
}
try {
ch = StringNode.charAt(str1, n);
System.out.println("That character is " + ch);
} catch (IllegalArgumentException e) {
System.out.println("The string is too short.");
}
// deleteChar and copy
n = -1;
while (n < 0) {
System.out.print("\nWhat # character to delete (>= 0)? ");
n = in.nextInt();
in.nextLine();
}
copy = StringNode.copy(str1);
try {
str1 = StringNode.deleteChar(str1, n);
StringNode.print(str1);
} catch (IllegalArgumentException e) {
System.out.println("The string is too short.");
}
System.out.print("\nUnchanged copy: ");
StringNode.print(copy);
System.out.println();
// insertChar
n = -1;
while (n < 0) {
System.out.print("\nWhat # character to insert before (>= 0)? ");
n = in.nextInt();
in.nextLine();
}
System.out.print("What character to insert? ");
line = in.nextLine();
ch = line.charAt(0);
try {
str1 = StringNode.insertChar(str1, n, ch);
StringNode.print(str1);
System.out.println();
} catch (IllegalArgumentException e) {
System.out.println("The string is too short.");
}
// removeFirst
System.out.print("What character to remove first occurrence of? ");
line = in.nextLine();
ch = line.charAt(0);
try {
str1 = StringNode.removeFirst(str1, ch);
StringNode.print(str1);
System.out.println();
} catch (IllegalArgumentException e) {
System.out.println("The string is too short.");
}
// insertSorted
System.out.print("\nType a string of chars in alphabetical order: ");
s = in.nextLine();
str3 = StringNode.convert(s);
System.out.print("What character to insert in order? ");
line = in.nextLine();
str3 = StringNode.insertSorted(str3, line.charAt(0));
StringNode.print(str3);
System.out.println();
}
}
Raw
Queue.java
/*
* Queue.java
*
* Computer Science E-22
*/
/*
* A generic interface that defines a simple ADT for a queue of
* objects of a particular type T.
*/
public interface Queue<T> {
/*
* adds the specified item to the rear of the queue. Returns false
* if the list is full, and true otherwise.
*/
boolean insert(T item);
/*
* removes the item at the front of the queue and returns a
* reference to the removed object. Returns null is the queue is
* empty.
*/
T remove();
/*
* returns a reference to the item at the front of the queue without
* removing it. Returns null is the queue is empty.
*/
T peek();
/* returns true if the queue is empty, and false otherwise */
boolean isEmpty();
/* returns true if the queue is full, and false otherwise */
boolean isFull();
}
Raw
remall.java
// Program that takes a char and removes it from a linked list
import java.util.*;
public class DNode {
private char ch;
private DNode next;
private DNode prev;
public DNode(char c, DNode n, DNode p) {
this.ch = c;
this.next = n;
this.prev = p;
}
public static int length(DNode n) {
if (n == null) {
return 0;
} else {
int lenRest = length(n.next);
return 1 + lenRest;
}
}
/**
* print - recursively writes the specified linked-list string to
* System.out
*/
public static void print(DNode str) {
if (str == null) {
return;
} else {
System.out.print(str.ch);
print(str.next);
}
}
public static DNode remAll(DNode str, char charInput) {
DNode trav = str;
while (trav != null) {
if (trav.ch == charInput) {
if (trav.prev == null) {
trav = trav.next;
str = trav;
trav.prev = null;
continue;
}
if (trav.next == null) {
trav = trav.prev;
trav.next.prev = null;
trav.next = null;
}
else {
trav.prev.next = trav.next;
trav.next.prev = trav.next.prev.prev;
trav = trav.next;
}
} else {
trav = trav.next;
}
}
return str;
}
public static void main(String[] args) {
DNode n = null;
DNode node1 = new DNode('s', null, null);
//System.out.println(DNode.length(n));
DNode node2 = new DNode('e', null, null);
n = node2;
node2.prev = node1;
node1.next = node2;
DNode node3 = new DNode('t', null, null);
n.next = node3;
node3.prev = n;
DNode m = new DNode('a', null, null);
m.next = n.next;
m.prev = n;
n.next = m;
n.next.prev = m;
System.out.println(DNode.length(node1));
DNode.print(n);
System.out.println();
//Pset 3 problem 4. Remove all
DNode str = null;
DNode firstNode = new DNode('b', null, null);
str = firstNode;
DNode secondNode = new DNode('a', null, firstNode);
firstNode.next = secondNode;
firstNode = secondNode.prev;
DNode thirdNode = new DNode('l', null, secondNode);
secondNode.next = thirdNode;
secondNode = thirdNode.prev;
DNode fourthNode = new DNode('l', null, thirdNode);
thirdNode.next = fourthNode;
thirdNode = fourthNode.prev;
DNode.print(str);
System.out.println();
DNode.print(remAll(str, 'l'));
//DNode.print(str);
System.out.println();
}
}
Raw
Reverse.java
import java.util.*;
class Reverse {
private Object[] arr;
private int i;
public Reverse() {
this.arr = new Object[5];
this.i = 0;
}
public static void printReverse(Object[] arr, int i) {
if (arr == null || i <= 0) {
System.out.print(((String) arr[0]).charAt(0));
} else {
System.out.print(((String) arr[0]).charAt(i));
printReverse(arr, i - 1);
}
}
public static void main(String[] args) {
Object[] arr = {"Carlos"};
// The int in the parameter refers to the amount of characters in the array
Reverse.printReverse(arr, 5);
}
}
Raw
StringRecursion.java
import java.util.*;
// The only built-in String methods that you may use are charAt, length, equals, and substring
// Do not use any global variables — i.e., variables that are declared outside of a method.
public class StringRecursion {
// This method should use recursion to print the individual characters in the string str, separated by spaces.
// For example, printWithSpaces("space") should print: s p a c e
private static int indexOf;
public static void printWithSpaces(String str) {
if ( str == null || str.equals("")) {
System.out.println();
return;
}
System.out.print(str.charAt(0) + " ");
printWithSpaces(str.substring(1));
}
// This method should use recursion to return the string that is formed by “weaving” together the characters
// in the strings str1 and str2 to create a single string.
// For example: weave("aaaa", "bbbb") should return the string "abababab"
public static String weave(String str1, String str2) {
if (str1 == null || str2 == null) {
throw new IllegalArgumentException("Can't be null");
}
if (str1.equals("") && str2.equals("")) {
return "";
}
if (str1.equals("")) {
return str2;
}
if (str2.equals("")) {
return str1;
}
else {
String rest = weave(str1.substring(1), str2.substring(1));
return ""+str1.charAt(0) + str2.charAt(0) + rest;
}
}
// This method should use recursion to find and return the index of the first occurrence of the character ch in the string str,
// or -1 if ch does not occur in str. For example:
// indexOf('b', "Rabbit") should return 2
// indexOf('P', "Rabbit") should return -1
public static int indexOf(char ch, String str) {
if ( str == null || str.equals("")) {
return -1;
} else {
int rest = indexOf(ch, str.substring(1));
if (str.charAt(rest + 1) != ch) {
return - 1;
}
if (str.charAt(0) != ch) {
return rest + 1;
}
}
return 0;
}
public static void main(String[] args) {
StringRecursion.printWithSpaces("space");
String output = StringRecursion.weave("Carlos", "Anabelle");
System.out.println(output);
int output2 = StringRecursion.indexOf('r', "carlos");
System.out.println(output2);
}
}
Raw
test.java
class test {
public static int mystery(int a, int b) {
if (a <= b) {
return a;
} else {
int myst_rest = mystery(a - 3, b + 1);
return b + myst_rest;
}
}
public static void main(String[] args) {
System.out.println(mystery(10, 1));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment