So, I'm really baffled by this. I'm working on a homework assignment that involves creating a Heap class and a PriorityQueue class that implement interfaces. Two of the interfaces are for the Heap and PriorityQueue classes, and the third is a Gradable interface that just has a toArray() method.
Heap.java
public class Heap<T extends Comparable<? super T>> implements HeapInterface<T>,
Gradable<T> {
private T[] heapArray = (T[]) new Comparable[10];
private int heapSize = 0;
@Override
public void add(T item) {
if (item == null) {
throw new IllegalArgumentException();
} else if (size() == heapArray.length - 1){
resize();
}
heapSize++;
heapArray[heapSize] = item;
int i = heapSize;
upHeap(i);
}
@Override
public boolean isEmpty() {
return (heapSize == 0);
}
@Override
public T peek() {
return heapArray[1];
}
@Override
public T remove() {
if (size() == 0) {
return null;
} else {
T returnMin = peek();
swap(1, heapSize);
heapArray[heapSize] = null;
heapSize--;
heapify(1);
return returnMin;
}
}
@Override
public int size() {
return heapSize;
}
@Override
public T[] toArray() {
return heapArray;
}
/**
* Doubles the size of the backing array
* Big O - O(n)
*/
private void resize() {
T[] heapCopy = (T[]) new Comparable[(heapArray.length) * 2];
for (int i = 1; i < heapArray.length; i++) {
heapCopy[i] = heapArray[i];
}
heapArray = heapCopy;
}
/**
* Swaps the elements at the specified indices
* Big O - O(1)
* @param the indices to swap
*/
private void swap(int i, int j) {
T tempElement = heapArray[i];
heapArray[i] = heapArray[j];
heapArray[j] = tempElement;
}
/**
* Returns the left child index of the specified position
* Big O - O(1)
* @param index
* @return the left child index
*/
private int getLeft(int i) {
return 2 * i;
}
/**
* Returns the right child index of the specified position
* Big O - O(1)
* @param index
* @return the right child index
*/
private int getRight(int i) {
return 2 * i + 1;
}
/**
* Returns the parent index of the specified position
* Big O - O(1)
* @param index
* @return the parent index
*/
private int getParent(int i) {
return (i) / 2;
}
/**
* Readjusts the heap by going down the heap to ensure heap property is
* maintained
* Big O - O(log(n))
* @param the index to start at
*/
private void downHeap(int i) {
int left = getLeft(i);
int right = getRight(i);
while (left < heapSize) {
int pos = left;
if (heapArray[right].compareTo(heapArray[left]) < 0) {
pos = right;
}
if (heapArray[pos].compareTo(heapArray[i]) < 0) {
swap(pos, i);
left = getLeft(pos);
right = getRight(pos);
i = pos;
} else {
left = heapSize;
}
}
}
/**
* Readjusts the heap by going up the heap to ensure heap property is
* maintained
* Big O - O(log(n))
* @param the index to start at
*/
private void upHeap(int i) {
int parent = getParent(i);
while ((i > 0) && (heapArray[parent].compareTo(heapArray[i]) > 0)) {
swap(parent, i);
i = parent;
parent = getParent(i);
}
}
/**
* Readjusts the heap by going down the heap to ensure heap property is
* maintained
* Big O - O(log(n))
* @param the index to start at
*/
private void heapify(int i) {
int left = getLeft(i);
int right = getRight(i);
int pos;
if ((left < heapSize) && (heapArray[left].compareTo(heapArray[i]) < 0)) {
pos = left;
} else {
pos = i;
}
if ((right < heapSize) && (heapArray[right].compareTo(heapArray[pos]) < 0)) {
pos = right;
}
if (pos != i) {
swap(i, pos);
heapify(pos);
}
}
/**
* Readjusts the heap, beginning at height/2, by going down the heap to
* ensure heap property is maintained
* Big O - O(log(n))
*/
private void buildHeap() {
for (int i = heapSize / 2; i > 0; i--) {
heapify(i);
}
}
}
PriorityQueue.java
public class PriorityQueue<T extends Comparable<? super T>> implements
PriorityQueueInterface<T>, Gradable<T> {
private Heap<T> priorityHeap;
@Override
public void insert(T item) {
priorityHeap.add(item);
}
@Override
public T findMin() {
return priorityHeap.peek();
}
@Override
public T deleteMin() {
return priorityHeap.remove();
}
@Override
public boolean isEmpty() {
return priorityHeap.isEmpty();
}
@Override
public void makeEmpty() {
priorityHeap = new Heap<T>();
}
@Override
public T[] toArray() {
priorityHeap.toArray();
}
}
Gradable.java
public interface Gradable<T> {
/**
* Returns the backing array of the data structure INCLUDING ANY EMPTY
* SPACES THAT MAY BE AT THE END.
* This should be a 1-line method; just return the backing array exactly as
* it is.
*
* @return the backing array of the data structure
*/
public T[] toArray();
}
HeapInterface.java
public interface HeapInterface<T extends Comparable<? super T>> {
/**
* Adds item to this heap
* Should throw IllegalArgumentException if item is null
* Big O - O(log(n))
* @param item the item to be added
*/
public void add(T item);
/**
* Checks if the heap is empty or not
* Big O - O(1)
* @return true if this heap is empty, false otherwise
*/
public boolean isEmpty();
/**
* Returns the minimum element of the heap without modifying the heap
* Big O - O(1)
* @return the minimum element of this heap
*/
public T peek();
/**
* Removes and returns the minimum element of this heap
* Big O - O(log(n))
* @return the minimum element of this heap
*/
public T remove();
/**
* The size of the heap
* Big O - O(1)
* @return the number of elements in this heap
*/
public int size();
}
PriorityQueueInterface.java
public interface PriorityQueueInterface<T extends Comparable<? super T>> {
/**
* Inserts an element in order in the Priority Queue
* Should throw IllegalArgumentException if item == null
* Big O - O(log(n))
* @param item the item to be inserted, it should be a data that does have
* an order property
*/
public void insert(T item);
/**
* returns the minimum value without changing the priority queue
* Should return null if queue is empty
* Big O - O(1)
* @return the minimum value without changing the priority queue
*/
public T findMin();
/**
* deletes and return the smallest item in the structure
* Big O - O(log(n))
* @return the minimum value
*/
public T deleteMin();
/**
* Checks if the queue is empty or not
* Big O - O(1)
* @return true if queue is empty, else false
*/
public boolean isEmpty();
/**
* Makes the queue empty
* Big O - O(1)
*/
public void makeEmpty();
}
But every time I compile, I get these errors:
>javac Heap.java
Heap.java:1: error: cannot find symbol
public class Heap<T extends Comparable<? super T>> implements HeapInterface<T>,
^
symbol: class HeapInterface
Heap.java:2: error: cannot find symbol
Gradable<T> {
^
symbol: class Gradable
Heap.java:7: error: method does not override or implement a method from a supert
ype
@Override
^
Heap.java:20: error: method does not override or implement a method from a super
type
@Override
^
Heap.java:25: error: method does not override or implement a method from a super
type
@Override
^
Heap.java:30: error: method does not override or implement a method from a super
type
@Override
^
Heap.java:44: error: method does not override or implement a method from a super
type
@Override
^
Heap.java:49: error: method does not override or implement a method from a super
type
@Override
^
Note: Heap.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
8 errors
>PriorityQueue.java
PriorityQueue.java:2: error: cannot find symbol
PriorityQueueInterface<T>, Gradable<T> {
^
symbol: class PriorityQueueInterface
PriorityQueue.java:2: error: cannot find symbol
PriorityQueueInterface<T>, Gradable<T> {
^
symbol: class Gradable
PriorityQueue.java:4: error: cannot find symbol
private Heap<T> priorityHeap;
^
symbol: class Heap
location: class PriorityQueue<T>
where T is a type-variable:
T extends Comparable<? super T> declared in class PriorityQueue
PriorityQueue.java:6: error: method does not override or implement a method from
a supertype
@Override
^
PriorityQueue.java:11: error: method does not override or implement a method fro
m a supertype
@Override
^
PriorityQueue.java:16: error: method does not override or implement a method fro
m a supertype
@Override
^
PriorityQueue.java:21: error: method does not override or implement a method fro
m a supertype
@Override
^
PriorityQueue.java:26: error: method does not override or implement a method fro
m a supertype
@Override
^
PriorityQueue.java:28: error: cannot find symbol
priorityHeap = new Heap<T>();
^
symbol: class Heap
location: class PriorityQueue<T>
where T is a type-variable:
T extends Comparable<? super T> declared in class PriorityQueue
PriorityQueue.java:31: error: method does not override or implement a method fro
m a supertype
@Override
^
10 errors
I'm not sure what's causing this, as the three interface classes that the compiler cannot find (HeapInterface, Gradable, and PriorityQueueInterface) are in the same directory as Heap and PriorityQueue. Just to note, I'm using Eclipse to write the code and then cmd prompt to compile the code. I am not allowed to modify the interface classes or add any new public methods to Heap or PriorityQueue. Any help would be appreciated.
You are only compiling a single source file with your command.
> javac Heap.java
If you are compiling this way you need to specify all of the source files. Here is an example using a version of Java 7.
$ls
Gradable.java HeapInterface.java Heap.java PriorityQueueInterface.java PriorityQueue.java
$~/jdk1.7.0/bin/javac -version
javac 1.7.0_60
$~/jdk1.7.0/bin/javac Gradable.java HeapInterface.java Heap.java PriorityQueueInterface.java PriorityQueue.java
Note: Heap.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
$ls
Gradable.class Gradable.java Heap.class HeapInterface.class HeapInterface.java Heap.java PriorityQueue.class PriorityQueueInterface.class PriorityQueueInterface.java PriorityQueue.java
The Java compiler also supports many more options.
$~/jdk1.7.0/bin/javac -help
Usage: javac <options> <source files>
where possible options include:
-g Generate all debugging info
-g:none Generate no debugging info
-g:{lines,vars,source} Generate only some debugging info
-nowarn Generate no warnings
-verbose Output messages about what the compiler is doing
-deprecation Output source locations where deprecated APIs are used
-classpath <path> Specify where to find user class files and annotation processors
-cp <path> Specify where to find user class files and annotation processors
-sourcepath <path> Specify where to find input source files
-bootclasspath <path> Override location of bootstrap class files
-extdirs <dirs> Override location of installed extensions
-endorseddirs <dirs> Override location of endorsed standards path
-proc:{none,only} Control whether annotation processing and/or compilation is done.
-processor <class1>[,<class2>,<class3>...] Names of the annotation processors to run; bypasses default discovery process
-processorpath <path> Specify where to find annotation processors
-d <directory> Specify where to place generated class files
-s <directory> Specify where to place generated source files
-implicit:{none,class} Specify whether or not to generate class files for implicitly referenced files
-encoding <encoding> Specify character encoding used by source files
-source <release> Provide source compatibility with specified release
-target <release> Generate class files for specific VM version
-version Version information
-help Print a synopsis of standard options
-Akey[=value] Options to pass to annotation processors
-X Print a synopsis of nonstandard options
-J<flag> Pass <flag> directly to the runtime system
-Werror Terminate compilation if warnings occur
@<filename> Read options and filenames from file