You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@myfaces.apache.org by ma...@apache.org on 2008/08/20 22:02:52 UTC
svn commit: r687432 - in /myfaces/trinidad/trunk_1.2.x/trinidad-api/src:
main/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImpl.java
test/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImplTest.java
Author: matzew
Date: Wed Aug 20 13:02:52 2008
New Revision: 687432
URL: http://svn.apache.org/viewvc?rev=687432&view=rev
Log:
TRINIDAD-1185 - Problems with the iterator implementation in RowSetTreeImpl class
Thx to Kamran Kashanian for his patch.
Modified:
myfaces/trinidad/trunk_1.2.x/trinidad-api/src/main/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImpl.java
myfaces/trinidad/trunk_1.2.x/trinidad-api/src/test/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImplTest.java
Modified: myfaces/trinidad/trunk_1.2.x/trinidad-api/src/main/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImpl.java
URL: http://svn.apache.org/viewvc/myfaces/trinidad/trunk_1.2.x/trinidad-api/src/main/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImpl.java?rev=687432&r1=687431&r2=687432&view=diff
==============================================================================
--- myfaces/trinidad/trunk_1.2.x/trinidad-api/src/main/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImpl.java (original)
+++ myfaces/trinidad/trunk_1.2.x/trinidad-api/src/main/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImpl.java Wed Aug 20 13:02:52 2008
@@ -26,9 +26,12 @@
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
+import java.util.Map;
import java.util.Map.Entry;
import java.util.NoSuchElementException;
import java.util.Set;
+import java.util.Stack;
+
import org.apache.myfaces.trinidad.logging.TrinidadLogger;
/**
@@ -82,7 +85,10 @@
@Override
public Iterator<Object> iterator()
{
- return new PathIterator();
+ if(_root.isDefaultContained)
+ return new PathIterator();
+ else
+ return new NodeIterator();
}
/**
@@ -537,6 +543,43 @@
}
}
+ /**
+ * Check for "default contained" nodes in the set
+ * @return true if there are "default contained" nodes
+ */
+ private boolean _containsDefaultNodes()
+ {
+ if(_root.isDefaultContained)
+ return true;
+
+ SetLoop loop = new SetLoop()
+ {
+ protected boolean next(Object rowKey, Node<Object> value)
+ {
+ return value.isDefaultContained;
+ }
+ };
+ return loop.run(_root);
+ }
+
+ /**
+ * Utility to dump Node attributes
+ */
+ private void _dumpFlags()
+ {
+ System.out.println("root " + _root.isDefaultContained + " " + _root.isDifferent);
+ SetLoop loop = new SetLoop()
+ {
+ protected boolean next(Object rowKey, Node<Object> value)
+ {
+ System.out.println(rowKey + " " + value.isDefaultContained + " " + value.isDifferent);
+ return false;
+ }
+ };
+ loop.run(_root);
+ }
+
+
// Needs to be Serializable and Cloneable - but HashMap already is
private static final class Node<K> extends HashMap<K, Node<K>>
/* implements Serializable, Cloneable */
@@ -626,11 +669,42 @@
}
}
- private final class PathIterator implements Iterator<Object>
+ /**
+ * Loop (depth first) over the set or a subset and call a callback function
+ * for each node
+ */
+ private static abstract class SetLoop
+ {
+ public SetLoop()
+ {
+ }
+
+ public boolean run (Node<Object> set)
+ {
+ for(Entry<Object, Node<Object>> en : set.entrySet())
+ {
+ Object keyEnt = en.getKey();
+ Node<Object> subset = en.getValue();
+ if(next(keyEnt, subset))
+ return true;
+ if(run(subset))
+ return true;
+ }
+ return false;
+ }
+
+ protected abstract boolean next(Object rowKey, Node<Object> value );
+ }
+
+ private class PathIterator implements Iterator<Object>
{
PathIterator()
{
- _value = _next(); // initialize;
+ _value = isEmpty() ? null : nextItem(); // initialize;
+ }
+
+ PathIterator(Object noop)
+ {
}
public Object next()
@@ -638,7 +712,7 @@
if (!hasNext())
throw new NoSuchElementException();
Object value = _value;
- _value = _next();
+ _value = nextItem();
return value;
}
@@ -652,22 +726,13 @@
throw new UnsupportedOperationException();
}
- private boolean _containsSubtree(Object rowkey)
+
+ protected Object nextItem()
{
- Search search = new Search()
- {
- @Override
- protected Node<Object> notFound(Node<Object> parent, Object rowkey)
- {
- return parent.isDefaultContained ? parent : null;
- }
- };
- Node<Object> current = search.find(rowkey);
- return (current != null) &&
- ((!current.isEmpty()) || current.isDefaultContained);
+ return nextModelKey(0);
}
- private Object _next()
+ protected Object nextModelKey(int minDepth)
{
TreeModel model = getCollectionModel();
if (model == null)
@@ -680,7 +745,7 @@
while(true)
{
boolean searchChildren = _containsSubtree(_currPath);
- boolean hasMore = _advanceToNextItem(model, 0, searchChildren);
+ boolean hasMore = _advanceToNextItem(model, minDepth, searchChildren);
if (!hasMore)
return null;
@@ -694,9 +759,92 @@
}
}
- private Object _value;
- private Object _currPath = null;
+ private boolean _containsSubtree(Object rowkey)
+ {
+ Search search = new Search()
+ {
+ @Override
+ protected Node<Object> notFound(Node<Object> parent, Object rowkey)
+ {
+ return parent.isDefaultContained ? parent : null;
+ }
+ };
+ Node<Object> current = search.find(rowkey);
+ return (current != null) &&
+ ((!current.isEmpty()) || current.isDefaultContained);
+ }
+
+ protected Object _value;
+ protected Object _currPath = null;
}
+
+ /**
+ * An iterator which avoids looping over the model by default (like the
+ * PathIterator does). Instead NodeIterator loops over the model only for nodes that are "default contained".
+ * Otherwise, it just does a depth first walk of the set and returns "isDifferent" nodes.
+ */
+ private class NodeIterator extends PathIterator
+ {
+ public NodeIterator()
+ {
+ super(null);
+ _currIterator = _root.entrySet().iterator();
+ _value = isEmpty() ? null : nextItem(); // initialize;
+ }
+
+ protected Object nextItem()
+ {
+ Object nextKey = null;
+
+ while(((nextKey = _nextEntry()) == null) && _iteratorStack.size() > 0)
+ if(_currPath == null)
+ _currIterator = _iteratorStack.pop();
+ return nextKey;
+ }
+
+ private Object _nextEntry()
+ {
+ Object nextKey = null;
+ if(_currPath != null)
+ {
+ nextKey = nextModelKey(_minDepth);
+ if(nextKey == null)
+ {
+ _currPath = null;
+ _nextEntry();
+ }
+ }
+ else
+ {
+ Map.Entry<Object, Node<Object>> nextNode;
+ while(nextKey == null && _currIterator.hasNext())
+ {
+ nextNode = _currIterator.next();
+ if(_isContained(nextNode.getKey()))
+ nextKey = nextNode.getKey();
+ _iteratorStack.push(_currIterator);
+ _currIterator = nextNode.getValue().entrySet().iterator();
+ if(nextNode.getValue().isDefaultContained)
+ {
+ _currPath = nextNode.getKey();
+ TreeModel model = getCollectionModel();
+ Object oldPath = model.getRowKey();
+ model.setRowKey(_currPath);
+ _minDepth = model.getDepth()+1;
+ model.setRowKey(oldPath);
+ return nextKey;
+ }
+ }
+ }
+ return nextKey;
+ }
+
+ private Stack<Iterator <Map.Entry<Object, Node<Object>>>> _iteratorStack =
+ new Stack<Iterator <Map.Entry<Object, Node<Object>>>>();
+ private Iterator <Map.Entry<Object, Node<Object>>> _currIterator;
+ private int _minDepth;
+ }
+
private Node<Object> _root;
private transient TreeModel _model = null;
Modified: myfaces/trinidad/trunk_1.2.x/trinidad-api/src/test/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImplTest.java
URL: http://svn.apache.org/viewvc/myfaces/trinidad/trunk_1.2.x/trinidad-api/src/test/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImplTest.java?rev=687432&r1=687431&r2=687432&view=diff
==============================================================================
--- myfaces/trinidad/trunk_1.2.x/trinidad-api/src/test/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImplTest.java (original)
+++ myfaces/trinidad/trunk_1.2.x/trinidad-api/src/test/java/org/apache/myfaces/trinidad/model/RowKeySetTreeImplTest.java Wed Aug 20 13:02:52 2008
@@ -80,9 +80,9 @@
// there is no requirement that the paths come out in the following
// order. However, I want to make writing this test easy, so
// I am taking advantage of the order:
+ assertEquals(_20, iter.next());
assertEquals(_0, iter.next());
assertEquals(_011, iter.next());
- assertEquals(_20, iter.next());
assertFalse(iter.hasNext());
}