java and ADTs

[Alex]

hi anyone good with abstract data types in java?

we're given a list ADT and have to use it to create and implement a Queue and Stack ADTs... i've already defined them but am not sure how to go about using and modifying the lists' methods...

say, the isEmpty() method is fine and i want to use it as is, but the clear() method i'd like to modify somewhat, how do i do that without changing the actual method in the original list ADT?


thx!

 

[Descartes]

Derive from it and override the base class' implementation.

A little code would help as well.

 

[Alex]

Originally posted by: Descartes
Derive from it and override the base class' implementation.

A little code would help as well.

ok so in List.java:

public List()
{
clear();

} // constructor



/*
* ---------------------------------------------------------
* clear
* - Resets state of list to "empty".
* ---------------------------------------------------------
* PRE:
* void
* ---------------------------------------------------------
* POST:
* list is empty; returns number of elements that were
* in the list (int)
* Number of elements that were in the list (int)
* ---------------------------------------------------------
* EXCEPTION:
* void
* ---------------------------------------------------------
*/
public int clear()
{
int old_size = size; // Return value

head = current = null;
position = size = 0;

return(old_size);

} // clear

public void head()
{
if (head != null)
{
current = head;
position = 1;
}

} // head





so the head() method is fine, i want to use it as is, but for the clear() method, for instance, i dont want it to return anything.

so in my Queue.java how should i do this? it extends the list, so should i even bother writing out the head() method again or do i just call it when i need it?
and how would i go about redefining the clear() method? just rewrite it?

thx!

 

[Descartes]

Originally posted by: franguinho

Originally posted by: Descartes
Derive from it and override the base class' implementation.

A little code would help as well.

ok so in List.java:

public List()
{
clear();

} // constructor



/*
* ---------------------------------------------------------
* clear
* - Resets state of list to "empty".
* ---------------------------------------------------------
* PRE:
* void
* ---------------------------------------------------------
* POST:
* list is empty; returns number of elements that were
* in the list (int)
* Number of elements that were in the list (int)
* ---------------------------------------------------------
* EXCEPTION:
* void
* ---------------------------------------------------------
*/
public int clear()
{
int old_size = size; // Return value

head = current = null;
position = size = 0;

return(old_size);

} // clear

public void head()
{
if (head != null)
{
current = head;
position = 1;
}

} // head





so the head() method is fine, i want to use it as is, but for the clear() method, for instance, i dont want it to return anything.

so in my Queue.java how should i do this? it extends the list, so should i even bother writing out the head() method again or do i just call it when i need it?
and how would i go about redefining the clear() method? just rewrite it?

thx!

No need to rewrite head(). head() will be in Queue's base class, so the interface of Queue will include the implementation of head() from List. You indicated that you don't want clear() to actually clear the list, so you'd override it in Queue as follows:

public class Queue extends List
{
public int clear()
{
return 0; // or whatever you might want to return
}
}

Then in your consuming code:

List l = new Queue();
l.clear(); // returns 0, doesn't clear list

Of course, "hiding" the implementation in this way is indicative of a problem in your class derivation hierarchy, but you specifically requested to do the above.

Hope that helps.

 

[Alex]

Thanks that did help, and well we were told to do it this way, extending list in our queue and stack...

One thing though that i'm having trouble with: what's the difference between the actual queue and the interface? in the textbook it mentions interfaces all the time but would i even need one for what im trying to do? thx!


EDIT: oh and when i define clear() in the queue, does it add to the existing clear() method from the list, or does it create an entirely new one?

 

[Descartes]

Originally posted by: franguinho
Thanks that did help, and well we were told to do it this way, extending list in our queue and stack...

One thing though that i'm having trouble with: what's the difference between the actual queue and the interface? in the textbook it mentions interfaces all the time but would i even need one for what im trying to do? thx!

There are usually two uses of the word interface; often used interchangeably. When I refer to a class' interface, I refer to the interface that the consumer of your class uses. This is an entirely disparate concept from an interface construct. Consider the following class:

public class Foo
{
public int Foo1() { // implementation }
public int Foo2() { // implementation }
private int Foo3() { // implementation }
}

In the above, the class' interface consists of 2 public members which happen to be methods: Foo1 and Foo2. Note that Foo3 is not part of the interface because it is encapsulated within the class. Now, lets look at the interface construct:

public interface IFooable
{
int FooYou();
}

Now lets implement IFooable in Foo

public class Foo implements IFooable
{
// IFooable implementation
public int FooYou() { // implementation }

public int Foo1() { // implementation }
public int Foo2() { // implementation }
private int Foo3() { // implementation }
}

Now the class Foo's interface consists of 3 members, all methods: FooYou, Foo1, and Foo2. So, Foo's external interface includes the implementation of the IFooable interface. Does that make sense?

EDIT: oh and when i define clear() in the queue, does it add to the existing clear() method from the list, or does it create an entirely new one?

No, using polymorphism the method will be called on the class instance to which your variable references. Consider the following:

List l = new List();
l.clear()

That will obviously call List.clear() as your variable 'l' refers to an instance of List. Now look at the following:

List l = new Queue();
l.clear()

That will call Queue.clear() (if the override exists) as your variable 'l' refers to an instance of Queue. This is polymorphic behavior. You are able to use List to refer to an instance of Queue as Queue is a subclass of List. This is sometimes referred to as downcasting, as you are casting down the class hierarchy (from List to the subclass Queue). The same can be said for interfaces a class implements:

IFooable f = new Foo()
f.FooYou();

'f' refers to an instance of Foo because Foo implements IFooable. Note that referring to a class instance through an interface means that *only* the interface of the interface implemented will be used; in other words, you only have FooYou visible to the reference.

Hope that didn't make it too confusing.

 

[Alex]

hmmm i think i can see it...

so for your last example,

Fooable f = new Foo()
f.FooYou();

when you call f.FooYou() it calls the FooYou method here:

public class Foo implements IFooable
{
// IFooable implementation
public int FooYou() { // implementation }

public int Foo1() { // implementation }
public int Foo2() { // implementation }
private int Foo3() { // implementation }
}

what i dont get is:

ok so in teh interface IFooable do you actually decalare the funtcion FooYou() or do you leave it as an abstract?
if you DO declare it, then what would you write in the IFooable implementation to leave it untouched? or do you not even have to write it:

for instance:

public interface IFooable
{
int FooYou();
}

public class Foo implements IFooable
{
public int Foo1() { // implementation }
public int Foo2() { // implementation }
private int Foo3() { // implementation }
}


would this work:
IFooable f = new Foo();
f.FooYou()

even though FooYou() isnt explicitly decalred in the class, but its decalred in the interface implemented by the class?

sorry if im not being consistent with my java vocab...

 

[Descartes]

Originally posted by: franguinho
hmmm i think i can see it...

so for your last example,

Fooable f = new Foo()
f.FooYou();

when you call f.FooYou() it calls the FooYou method here:

public class Foo implements IFooable
{
// IFooable implementation
public int FooYou() { // implementation }

public int Foo1() { // implementation }
public int Foo2() { // implementation }
private int Foo3() { // implementation }
}

what i dont get is:

ok so in teh interface IFooable do you actually decalare the funtcion FooYou() or do you leave it as an abstract?
if you DO declare it, then what would you write in the IFooable implementation to leave it untouched?

There is only a declaration in an interface, not a definition. A definition is where the implementation actually resides. An interface isn't even abstract, it can't have *any* implementation. An interface's purpose is to merely declare a "contract" that all implementing classes must adhere to. Check your Java book for more explanation on what an interface is...

or do you not even have to write it:

for instance:

public interface IFooable
{
int FooYou();
}

public class Foo implements IFooable
{
public int Foo1() { // implementation }
public int Foo2() { // implementation }
private int Foo3() { // implementation }
}


would this work:
IFooable f = new Foo();
f.FooYou()

even though FooYou() isnt explicitly decalred in the class, but its decalred in the interface implemented by the class?

sorry if im not being consistent with my java vocab...

No, that won't work. If you implement an interface, you have to actually implement it. The keyword "implements" in Java means that your class is saying it wants to actually implement an interface; therefore, it must implement the entire contract declared by the interface.

Interfaces are generally used to exhibit like behavior between unrelated classes. They're also used to allow multiple inheritance of interface, as Java/C#/etc. only allow single implementation inheritance. As you've probably heard, class derivation/generalization exhibits the is-a relationship; a Queue is a List, for example. This can't be said for interfaces, however. Consider an example in .NET (C#):

public class SomeRandomClass : IDisposable
{
public void IDisposable.Dispose() { // implementation}
}

IDisposable is an interface that classes implement to allow consumers to cleanup the resources allocated throughout the duration of the class instance. SomeRandomClass is not IDisposable, it merely exhibits the behavior of IDisposable.

It's always hard to explain when/when not to use an interface, so perhaps your Java book might be of better help. Once you finally grok interfaces, however, you know when to use them.

 

[Alex]

hmm ya i guess i better go back to the book for that one

what i dont get is whats the point of implementing an interface, if youre going to rewrite all of that interfaces methods?

couldnt i just have

public class Foo
{
private int FooYou() [implementation]
private int Foo1() [implementation]
private int Foo2() [implementation]
}

and it would work exactly like that one you outlined earlier on that implements the IFooable interface?

 

[Descartes]

Originally posted by: franguinho
hmm ya i guess i better go back to the book for that one

what i dont get is whats the point of implementing an interface, if youre going to rewrite all of that interfaces methods?

couldnt i just have

public class Foo
{
private int FooYou() [implementation]
private int Foo1() [implementation]
private int Foo2() [implementation]
}

and it would work exactly like that one you outlined earlier on that implements the IFooable interface?

Like all things in computer-science, "why" is the difficult part. You could flatten out a class hierarchy into a single monolithic class and not worry about all the inherent issues, but "why" you don't takes considerable knowledge of OO. Also note that you declared everything private, so that effectively exhibits nothing; no consumer can access any of your members.

In the above case, say you wanted to have class NewFoo (excuse the HORRIBLY contrived examples, but I'm trying to use class names that have little meaning to you already) that also needs to exhibit the behavior of IFooable. Certainly you could add the method FooYou() to NewFoo, but then you lose out on any polymorphic capabilities with respect to interfaces. In other words, you can't have a method like the following:

public void ProcessFooable(IFooable f)
{
f.FooYou();
}

A good book on OO will help elucide this for you. I would get a good book on OO with Java examples, because the interface didn't exist in C++ (which is what most of the previous OO books used). C++ did have pure-abstract classes with pure-virtual methods, but there are differences.

 

[Alex]

yah im definitely trying to understand intricate OO conecepts without really fully grasping the concept of OO programming...

im goin on an 8 hour busride to ottawa this weekend and i figure i could really read my textbook from scratch...

thx for your effort all day!