traversing LinkedList
Author
So I've scoured through the Java API Specification covering the LinkedList list structure, and I'm still confused.
I want to run a simple traversal through the list, and check each node for a particular condition. This is the best that I've come up with so far:
LinkedList list = new LinkedList();
/* pretend I just populated the list full of Widgets */
ListerIterator iter = new ListIterator();
iter = list.listIterator();
while(iter.hasNext())
{
if(iter.next().x_val == 1) { /* blah */ }
else if(iter.next().x_val == 2) { /* blah */ }
// ... etc.
}
The problem is, every time I call iter.next(), I think I'm stepping one node further through the list. Ergo the node I'm checking in the first 'if' statement is not the same node I'm checking in the second 'else if' statement.
How do I check the same node without stepping further through the list???
Notice that Iterator.next() is an accessor with a side effect: It first steps to the next node of the list, and returns that. There is no other accessor defined. So you have to follow SiCrane's suggestion:
BTW: Such a behaviour is sometimes a topic of discussion about good programming style, so I don't wonder if you (hisDudeness) have a problem with it. People like Booch have mentioned that it would be better to have distinct "extractors" and "manipulators", like in
However, that way is not such efficient as the actual implementation, and sometimes suffers from initial value problems.
while(iter.hasNext()){ final Widget current = (Widget)iter.next(); if(current.x_val == 1) { /* blah */ } else if(current.x_val == 2) { /* blah */ } // ... etc.}BTW: Such a behaviour is sometimes a topic of discussion about good programming style, so I don't wonder if you (hisDudeness) have a problem with it. People like Booch have mentioned that it would be better to have distinct "extractors" and "manipulators", like in
interface Iterator { // manipulator: steps to next node public void next(); // extractor: the value of the current node public Object current();}However, that way is not such efficient as the actual implementation, and sometimes suffers from initial value problems.
Author
SiCrane & haegarr -- thank you!
Unfortunately my original post was a little too vague. Let me better explain the scenario:
I have a base class called AtomicExpression. It's a wrapper class for all of its children, which, naturally, are extensions of this class. Examples of these child classes are: Variable, Number, SymbolicConstant, etc. (I'm writing a math program, yuck.) So all of these classes extend AtomicExpression.
I'm storing math formulas in a LinkedList. For instance, let's take a simple expression such as "3 + 4":
Number three = new Number(3);
BinaryOp plus = new BinaryOp('+');
Number four = new Number(4);
LinkedList list = new LinkedList();
list.add(three);
list.add(plus);
list.add(four);
ListIterator iter = new ListIterator();
iter = list.listIterator();
AtomicExpression stepNode = new AtomicExpression();
while(iter.hasNext())
{
stepNode = (AtomicExpression)iter.next(); // thank you SiCrane & haegarr!!!
if(stepNode instanceof Number) {}
else if(stepNode instanceof BinaryOp) {}
// ... etc.
}
The problem is, now I'm worred that when I cast the Object returned in iter.next into an AtomicExpression, that the data members and info contained in Number, BinaryOp and Number (respectively) will be lost.
Since I have now been forced to typecast stepNode back into the wrapping parent class, how can I chec for what data type each node in the list is?
Unfortunately my original post was a little too vague. Let me better explain the scenario:
I have a base class called AtomicExpression. It's a wrapper class for all of its children, which, naturally, are extensions of this class. Examples of these child classes are: Variable, Number, SymbolicConstant, etc. (I'm writing a math program, yuck.) So all of these classes extend AtomicExpression.
I'm storing math formulas in a LinkedList. For instance, let's take a simple expression such as "3 + 4":
Number three = new Number(3);
BinaryOp plus = new BinaryOp('+');
Number four = new Number(4);
LinkedList list = new LinkedList();
list.add(three);
list.add(plus);
list.add(four);
ListIterator iter = new ListIterator();
iter = list.listIterator();
AtomicExpression stepNode = new AtomicExpression();
while(iter.hasNext())
{
stepNode = (AtomicExpression)iter.next(); // thank you SiCrane & haegarr!!!
if(stepNode instanceof Number) {}
else if(stepNode instanceof BinaryOp) {}
// ... etc.
}
The problem is, now I'm worred that when I cast the Object returned in iter.next into an AtomicExpression, that the data members and info contained in Number, BinaryOp and Number (respectively) will be lost.
Since I have now been forced to typecast stepNode back into the wrapping parent class, how can I chec for what data type each node in the list is?
The way you've posted is already one possible solution:
while(iter.hasNext()) { stepNode = (AtomicExpression)iter.next(); // thank you SiCrane & haegarr!!! if(stepNode instanceof Number) { Number number = (Number)stepNode; // do something with number } else if(stepNode instanceof BinaryOp) { BinaryOp op = (BinaryOp)stepNode; // do something with op } // ... etc. }
However, if I'm allowed to make a totally other suggestion (I make it anyway ;-)
One of the big issues of OOP is to avoid exact knowledge of types. This could be reached by polymorphism. If you look at the iterative solution above, you'll see that evaluating an expression is somewhat problematic since you must remember previous states of evaluation.
A way to solve this problem would be letting the classes itself decide what to do. I don't know whether your problem is of such a structure, but please have a look at this:
As you could see here, the expression isn't modelled as a sequence but as a tree. This reflects immediately also bracketing. It also allows functions like min() or max() or floor() or ... whatever.
In parallel to evaluate() also a toString() may be implemented to transfer the expression back to a string. Other such things are possible, too.
EDIT: Bugs in accessing super class fields corrected.
[Edited by - haegarr on December 1, 2005 12:47:51 PM]
One of the big issues of OOP is to avoid exact knowledge of types. This could be reached by polymorphism. If you look at the iterative solution above, you'll see that evaluating an expression is somewhat problematic since you must remember previous states of evaluation.
A way to solve this problem would be letting the classes itself decide what to do. I don't know whether your problem is of such a structure, but please have a look at this:
public abstract class Expressionextends Object { public abstract float evaluate();}public class Numberextends Expression { public Number(float withValue) { this.value = withValue; } private float value; public float evaluate() { return this.value; }}public class BinaryOpextends Expression { public BinaryOp(Expression atLeft,Expression atRight) { this.left = atLeft; this.right = atRight; } public Expression leftExpression() { return this.left; } private Expression left; public Expression rightExpression() { return this.right; } private Expression right;}public class BinaryPlusextends BinaryOp { public BinaryPlus(Expression atLeft,Expression atRight) { super(atLeft,atRight); } public float evaluate() { return leftExpression() + rightExpression(); }}public class BinaryMinusextends BinaryOp { public BinaryMinus(Expression atLeft,Expression atRight) { super(atLeft,atRight); } public float evaluate() { return leftExpression() - rightExpression(); }}As you could see here, the expression isn't modelled as a sequence but as a tree. This reflects immediately also bracketing. It also allows functions like min() or max() or floor() or ... whatever.
In parallel to evaluate() also a toString() may be implemented to transfer the expression back to a string. Other such things are possible, too.
EDIT: Bugs in accessing super class fields corrected.
[Edited by - haegarr on December 1, 2005 12:47:51 PM]
You could, of course, do something similar with a linked list, but not in such an easy way. If you insist on the list paradigm, I suggest something like this:
Then you could do something like
Notice that, although looking smarter at the moment, this solution is less flexible in comparison to the tree solution, since each next funtionality (e.g. toString()) needs support from outside (also the stack is such a support).
(I've written this from mind, so please forgive me if there were syntax errors. Notice furthur that some state checking has to be implemented, of course, to detect usage errors.)
[Edited by - haegarr on December 1, 2005 12:03:57 PM]
public abstract class Expressionextends Object { public abstract void evaluate(Stack stack);}public class Numberextends Expression { public Number(float withValue) { this.value = withValue; } private float value; public void evaluate(Stack stack) { stack.push(this.value); }}public class BinaryPlusextends Expression { public void evaluate(Stack stack) { float result = stack.pop() + stack.pop(); stack.push(result); }}public class BinaryMinusextends Expression { public float evaluate(Stack stack) { float result = stack.pop() - stack.pop(); stack.push(result); }}Then you could do something like
Stack stack = new Stack();while(iter.hasNext()) { final Expression expression = (Expression)iter.next(); expression.evaluate(stack);}System.out.prinln((float)stack.pop());Notice that, although looking smarter at the moment, this solution is less flexible in comparison to the tree solution, since each next funtionality (e.g. toString()) needs support from outside (also the stack is such a support).
(I've written this from mind, so please forgive me if there were syntax errors. Notice furthur that some state checking has to be implemented, of course, to detect usage errors.)
[Edited by - haegarr on December 1, 2005 12:03:57 PM]
In Java, that cast will not "slice" the object like it would in C++ - no worries. The necessary layer of indirection is managed for you under the hood.
On the other hand, if you're going to do an instanceof check anyway, there's no real point in the cast to AtomicExpression (all it will accomplish is to throw ClassCastException if you put some other kind of Object into your LinkedList - of course, that's a problem too, but it would be nicer to catch it at compile-time... *). You really should be making use of polymorphism here.
* In Java 1.5, the new 'generics' feature allows for specifying a LinkedList<AtomicExpression> , similar in effect (although not nearly the same in implementation) as C++ templates. Older versions do not support this, so when you up-cast to Object, the type information is lost indefinitely. Although actually, all the generics really do at runtime is automate the down-cast :s but at least it allows for some compile-time error checking.
On the other hand, if you're going to do an instanceof check anyway, there's no real point in the cast to AtomicExpression (all it will accomplish is to throw ClassCastException if you put some other kind of Object into your LinkedList - of course, that's a problem too, but it would be nicer to catch it at compile-time... *). You really should be making use of polymorphism here.
* In Java 1.5, the new 'generics' feature allows for specifying a LinkedList<AtomicExpression> , similar in effect (although not nearly the same in implementation) as C++ templates. Older versions do not support this, so when you up-cast to Object, the type information is lost indefinitely. Although actually, all the generics really do at runtime is automate the down-cast :s but at least it allows for some compile-time error checking.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
