null exception problem

[connor7777]

Hi guys:

We've been weeding out errors off of a java->c# project and have managed to redeem most of our code with the exception of one bug that we for some reason cannot pin down.


This is a pretty simple error (and yet we cant fix it) and only read on if you have what they call the "wary eye"



The following is an implementation of Linked List class for any item "E" (that also implements IMatchable for itself). It defines "LinkedList" as a recursive datatype with no separate "Cell" or "Node" class, much the same as say for instance ML's Programming language's lists.

The tail cell has empty sublist represented by "null" in C#, like ML's "nil". The empty list cannot be "null", cuz as you may know, "null" is not an object in C# (compared to java), so the empty list is represented as a list with null sublist and null info field.


When the program is run and one too many IsEmpty() calls are made and it flips out for some reason. I am giving here the entire code and a dry-run of sorts.


I am probably going to say this again, somewhere later here but I believe that in this particular implementation of linkedlist, the problem lies in the way in which the constructors (the three constructors for Linked List) have been defined-------->


Here's the latest version of the code (were still working on it):


CODE

using System;

public interface IMatchable<E> where E : IMatchable<E> {

bool Matches(E rhs);

}

class LL<E> where E : IMatchable<E> {
E info;
LL<E> rest;

// it has an info and a rest

static E DEF = default(E);

public LL(E x, LL<E> L) {

info = x; rest = L;

}

public LL() : this(DEF, null) {

}

public LL(E x) : this(x, null) {
//this(x,null); okay in java but not allowed in C#
}

public bool IsEmpty() {
return (info.Equals(DEF) && rest == null);
}

public bool IsUnit() {
return (rest == null);
}

/** Add object x to list. Put it in front. */
public void Add(E x) {

if (IsEmpty()) {
info = x;

}

else

{
rest = new LL<E>(info,rest); //rest = this;->infinite recursion
info = x;
}

}

public E Retrieve(E x) {

if (IsEmpty()) {
//return null; //Done in similar Java code, but illegal here

return DEF; // this is why we created DEF


}

else if (x.Matches(info)) {

return info;

}

else {
return rest.Retrieve(x);
}
}

public E LastItem()


{ //Coded the ML way. No side-effects.
return IsUnit() ? info : rest.LastItem();
}


public override string ToString() {

return "[o | o]--->" + (IsEmpty() ? null : info.ToString()) + "\n"
+ " | \n"
+ " | \n"
+ " V \n"
+ rest;

}
}


struct MyInt : IMatchable<MyInt>

{

int value;
public MyInt(int x) { this.value = x; }

public bool Equals(MyInt rhs) {
return value == rhs.value;

}

public bool Matches(MyInt rhs)

{
return Equals(rhs);
}


public override string ToString() { return ""+value; }

}


class Animal : IMatchable<Animal> {
string name;
string color;


public Animal(string name, string color) {
this.name = name; this.color = color;
}


public Animal() : this("","") { }


public Animal(string name) : this(name,"") { }


public bool Matches(Animal rhs){
return name.Equals(rhs.name);

}

public override string ToString() {
return GetType() + ":" + name + ":" + color;
}
}

class Dog : Animal, IMatchable<Dog> {

string pedigree;

public Dog(string name, string color, string pedigree) : base(name, color) {
this.pedigree = pedigree;
}

public Dog(string name) : this(name, "color?", "") { }


public bool Matches(Dog rhs) {
//return (name.Equals(rhs.name) && pedigree.Equals(rhs.pedigree));
return (base.Matches(rhs) && pedigree.Equals(rhs.pedigree));
}
public override string ToString() {
return base.ToString() + ":" + pedigree;
}
}

class Cat : Animal, IMatchable<Cat> {
public Cat(string name, string color) : base(name, color) { }
public Cat(string name) : this(name, "color?") { }
//public bool Matches(Animal rhs) {
public bool Matches(Cat rhs) {
return base.Matches(rhs);
}
public override string ToString() {
return base.ToString();
}
}


struct Day : IMatchable<Day> {
public enum DAY {
Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday
}
DAY day;
public Day(DAY day) { this.day = day; }

public bool Matches(Day rhs) {
return day.Equals(rhs.day);
}
}




As you can probably tell, Cat Dog and the Day enum are only used to test the code. this here is the part that tests the code:



CODE

public class LLclient {
/** Test code.
*/
public static void Main(string[] args) {

Dog ghostDog = default(Dog);

Console.WriteLine("Can the default(Dog) bark? " + ghostDog);

Dog spot = new Dog("Spot");
Dog fido = new Dog("Fido");
Dog alba = new Dog("Alba", "white", "AKC");
Cat ella = new Cat("Ella", "gray");
Cat tomo = new Cat("Tomo");

LL<Animal> pets = new LL<Animal>(spot);

pets.Add(ella);
pets.Add(alba);
pets.Add(fido);

Animal dogorcat = pets.Retrieve(new Animal("Alba"));

Console.WriteLine("Which animal did we get? " + dogorcat);

Animal mystery = pets.Retrieve(new Dog("Ella"));

Console.WriteLine("\nDid we retrieve a cat via a Dog object?");
Console.WriteLine("The mystery animal is: " + mystery);

mystery = pets.Retrieve(new Cat("Ella"));

Console.WriteLine("The mystery animal now is: " + mystery);

Console.WriteLine("\nNow what will tomo retrieve?");
Animal ghost = pets.Retrieve(tomo);





The output looks something like this when i ask for what tomo will retrieve when it calls retrieve() ?

GLib: Cannot convert message: Conversion from character set 'UTF-8' to '646' is not supported.

Unhandled Exception: System.NullReferenceException: Object reference not set to an instance of the object



The error happens when you try and retrieve tomo, owing to the face that there have been one too many calls to retrieve and ergo, isempty.



The reason why this has happened, i believe has roots in what the problem is with one of the three constructors and the way in which theyve been defined.



Any ideas that you may have about this. ...are encouraged smile.gif Thanx

[Mathstar]

Wow! Goodluck with it!

[WingedPanther]

Have you traced through the code in a debugger?