Help with LinkedBinarySearchTree and table implementation

Bunto_dog said:

I don't understand why do I keep getting the errors after executing MyMap.java
[ATTACH]3008[/ATTACH]
[ATTACH]3009[/ATTACH]
[ATTACH]3010[/ATTACH]
[ATTACH]3011[/ATTACH]
Thanks
Bunto

Hi Bunto,

I threw your classes into a new project in my Eclipse IDE, and there were two things that I noticed right away:

BinarySearchTreeA.java should be named BinarySearchTreeADT.java
LinkedBinarySearc.java should be named LinkedBinarySearchTree.java

Now these may simply be enforcements by Eclipse, however I have always been under the impression that generally speaking the Java compiler also enforces the rule that the .java file be named the exact same as the outer-most contained class, interface, or other entity. Someone can correct me on that.

Allowing Eclipse to help me a little more I found these errors:

In LinkedBinarySearchTree.java:
- Lines 100, 151, 168, 367 -- ElementNotFoundException cannot be resolved as a type. If this exception is defined in your code, I'm not finding it anywhere, and it's not in the default Java classpath.
- Lines 303, 308, 413 -- EmptyCollectionException cannot be resolved as a type. If this exception is defined in your code, I'm not finding it anywhere, and it's not in the default Java classpath.

There are five or six other errors that all hinge on those two classes existing. Once they're found, those should go away. In my case I created two mock classes to substitute for these two exceptions:

public class ElementNotFoundException extends Exception {

	public ElementNotFoundException() {
		super();
	}

	public ElementNotFoundException(String arg0) {
		super(arg0);
	}

	public ElementNotFoundException(Throwable arg0) {
		super(arg0);
	}

	public ElementNotFoundException(String arg0, Throwable arg1) {
		super(arg0, arg1);
	}

}

public class EmptyCollectionException extends Exception {

	public EmptyCollectionException() {
		super();
	}

	public EmptyCollectionException(String message) {
		super(message);
	}

	public EmptyCollectionException(Throwable cause) {
		super(cause);
	}

	public EmptyCollectionException(String message, Throwable cause) {
		super(message, cause);
	}

}

Then I went back to your code. Looking at it some more, I found these problems.

When you declare a method with throws Exception you must actually throw the exception somewhere in the code. Also don't catch the exception in the method, because that is the reason you are declaring the throws directive.
In LinkedBinarySearchTree.java main was throwing the ElementNotFoundException at line 460, so you need to catch it somewhere in there. Eclipse is handy because it recommends fixes and automates fixing this sort of problem
Your interface did not match the implementation in the case of BinarySearchTreeADT -- when throws is part of the method declaration in the implementation, it must be part of the definition in the interface and vise-versa.
MyMap line 19 throws an exception, so I added to the end of the method declaration: throws ElementNotFoundException
Same thing on line 106 in MyMap.java

Overall, you just need to go and audit your code a little bit before you begin compiling. So here are some things to remember:

When you implement an interface it must comply to the contract perfectly. If you need a throws directive on an interface implementation, ensure that it is also in the interface definition.
Don't catch the exception you want your method to throw inside the same method.

Now for the run. When I run your code with the above things fixed, this is what I see:

Insert Carver and Nordstromg.
Insert Carver again.
Contains Carver:
Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;
	at MyMap.keyList(MyMap.java:48)
	at MyMap.containsKey(MyMap.java:69)
	at MyMap.main(MyMap.java:115)

So the first thing I need to do is take a look at MyMap.java line 48. Which looks like:

 KeyType[] keyarray = (KeyType[]) new Object[items.size()];

From here if I know the code path to get to that point I can go a look to see where I'm causing the problems. The problem is that I cannot cast an array of Object to an array of KeyType:

(KeyType[]) new Object[items.size];

The reason for this appears to be that KeyType is being passed as a generic argument to MyMap. You do have one thing going here however. Because you have required KeyType to extend Comparable, you can change that whole line to:

Comparable[] keyarray = new Comparable[items.size()];

This is called programming against an interface, which I can see you are trying to do. You probably just forgot to do it there.

Hopefully that helps.

By the way after that there are more issues. Use the same process to determine how to fix them.

Nathan