jackrabbit-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mdue...@apache.org
Subject svn commit: r981597 [1/2] - in /jackrabbit/trunk: jackrabbit-core/src/test/java/org/apache/jackrabbit/core/integration/ jackrabbit-core/src/test/resources/org/apache/jackrabbit/core/integration/ jackrabbit-jcr-commons/ jackrabbit-jcr-commons/src/main/j...
Date Mon, 02 Aug 2010 16:56:11 GMT
Author: mduerig
Date: Mon Aug  2 16:56:10 2010
New Revision: 981597

URL: http://svn.apache.org/viewvc?rev=981597&view=rev
Log:
JCR-2688: Provide utility for handling large number of child nodes

Added:
    jackrabbit/trunk/jackrabbit-core/src/test/java/org/apache/jackrabbit/core/integration/ItemSequenceTest.java
    jackrabbit/trunk/jackrabbit-core/src/test/java/org/apache/jackrabbit/core/integration/TreeTraverserTest.java
    jackrabbit/trunk/jackrabbit-core/src/test/resources/org/apache/jackrabbit/core/integration/
    jackrabbit/trunk/jackrabbit-core/src/test/resources/org/apache/jackrabbit/core/integration/words.txt
    jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/
    jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/BTreeManager.java
    jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/ItemSequence.java
    jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/NodeSequence.java
    jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/PropertySequence.java
    jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/Rank.java
    jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/Sequence.java
    jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/SizedIterator.java
    jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/TreeManager.java
    jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/TreeTraverser.java
    jackrabbit/trunk/jackrabbit-jcr-commons/src/test/java/flat/
    jackrabbit/trunk/jackrabbit-jcr-commons/src/test/java/flat/RankTest.java
Modified:
    jackrabbit/trunk/jackrabbit-jcr-commons/pom.xml

Added: jackrabbit/trunk/jackrabbit-core/src/test/java/org/apache/jackrabbit/core/integration/ItemSequenceTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-core/src/test/java/org/apache/jackrabbit/core/integration/ItemSequenceTest.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-core/src/test/java/org/apache/jackrabbit/core/integration/ItemSequenceTest.java (added)
+++ jackrabbit/trunk/jackrabbit-core/src/test/java/org/apache/jackrabbit/core/integration/ItemSequenceTest.java Mon Aug  2 16:56:10 2010
@@ -0,0 +1,278 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package org.apache.jackrabbit.core.integration;
+
+import org.apache.jackrabbit.JcrConstants;
+import org.apache.jackrabbit.flat.BTreeManager;
+import org.apache.jackrabbit.flat.ItemSequence;
+import org.apache.jackrabbit.flat.NodeSequence;
+import org.apache.jackrabbit.flat.PropertySequence;
+import org.apache.jackrabbit.flat.Rank;
+import org.apache.jackrabbit.flat.TreeManager;
+import org.apache.jackrabbit.flat.TreeTraverser;
+import org.apache.jackrabbit.test.AbstractJCRTest;
+
+import javax.jcr.Node;
+import javax.jcr.NodeIterator;
+import javax.jcr.Property;
+import javax.jcr.PropertyIterator;
+import javax.jcr.RepositoryException;
+import javax.jcr.ValueFactory;
+import javax.jcr.nodetype.NodeType;
+
+import java.io.BufferedReader;
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.LinkedList;
+import java.util.List;
+
+public class ItemSequenceTest extends AbstractJCRTest {
+    private Node testNode;
+
+    @Override
+    public void setUp() throws Exception {
+        super.setUp();
+        testNode = testRootNode.addNode("ItemSequenceTest", NodeType.NT_UNSTRUCTURED);
+        superuser.save();
+    }
+
+    public void testNodeSequence() throws RepositoryException, IOException {
+        Comparator<String> order = Rank.<String>comparableComparator();
+        TreeManager treeManager = new BTreeManager(testNode, 5, 10, order, true);
+        NodeSequence nodes = ItemSequence.createNodeSequence(treeManager);
+
+        List<String> words = loadWords();
+        Collections.shuffle(words);
+
+        addAll(nodes, words);
+        checkTreeProperty(testNode, 5, 10, order);
+        checkOrder(nodes, order);
+
+        Collections.shuffle(words);
+        checkLookup(nodes, words);
+
+        Collections.shuffle(words);
+        List<String> toRemove = take(words.size()/5, words);
+        removeAll(nodes, toRemove);
+        checkNotFound(nodes, toRemove);
+        checkLookup(nodes, words);
+
+        removeAll(nodes, words);
+        checkEmpty(nodes);
+    }
+
+    public void testPropertySequence() throws RepositoryException, IOException {
+        Comparator<String> order = Rank.<String>comparableComparator();
+        TreeManager treeManager = new BTreeManager(testNode, 2, 4, order, true);
+        PropertySequence properties = ItemSequence.createPropertySequence(treeManager);
+
+        List<String> words = loadWords();
+        Collections.shuffle(words);
+
+        ValueFactory vFactory = testNode.getSession().getValueFactory();
+        addAll(properties, words, vFactory);
+        checkTreeProperty(testNode, 2, 4, order);
+
+        Collections.shuffle(words);
+        checkLookup(properties, words);
+
+        Collections.shuffle(words);
+        List<String> toRemove = take(words.size()/5, words);
+        removeAll(properties, toRemove);
+        checkNotFound(properties, toRemove);
+        checkLookup(properties, words);
+
+        removeAll(properties, words);
+        checkEmpty(properties);
+    }
+
+    // -----------------------------------------------------< internal >---
+
+    private static List<String> loadWords() throws FileNotFoundException, IOException {
+        InputStreamReader wordList = new InputStreamReader(ItemSequenceTest.class.getResourceAsStream("words.txt"));
+        BufferedReader wordReader = new BufferedReader(wordList);
+
+        List<String> words = new LinkedList<String>();
+        String word = wordReader.readLine();
+        while (word != null) {
+            words.add(word);
+            word = wordReader.readLine();
+        }
+        return words;
+    }
+
+    /**
+     * Remove first <code>count</code> items from <code>list</code> and return them
+     * in as a separate list.
+     */
+    private static <T> List<T> take(int count, List<T> list) {
+        List<T> removed = new LinkedList<T>();
+        for (int k = 0; k < count; k++) {
+            removed.add(list.remove(0));
+        }
+        return removed;
+    }
+
+    private static void addAll(NodeSequence nodes, List<String> words) throws RepositoryException {
+        for (String name : words) {
+            nodes.addNode(name, NodeType.NT_UNSTRUCTURED);
+        }
+    }
+
+    private static void addAll(PropertySequence properties, List<String> words, ValueFactory vFactory)
+            throws RepositoryException {
+
+        for (String name : words) {
+            properties.addProperty(name, vFactory.createValue(name + " value"));
+        }
+    }
+
+    private static void checkTreeProperty(Node root, int minChildren, int maxChildren, Comparator<String> order)
+            throws RepositoryException {
+
+        int depth = -1;
+
+        for (Node node : new TreeTraverser(root)) {
+            String parentName = node.getName();
+
+            if (node.hasNodes()) {
+                int childCount = 0;
+                for (NodeIterator nodes = node.getNodes(); nodes.hasNext(); ) {
+                    Node child = nodes.nextNode();
+                    childCount++;
+                    if (!root.isSame(node)) {
+                        assertTrue("Mismatching order: node " + node + " contains child " + child,
+                                order.compare(parentName, child.getName()) <= 0);
+                    }
+                }
+                if (!root.isSame(node)) {
+                    assertTrue("Node " + node + " should have at least " + minChildren + " child nodes",
+                            minChildren <= childCount);
+                }
+                assertTrue("Node " + node + " should have no more than " + maxChildren + " child nodes",
+                        maxChildren >= childCount);
+            }
+
+            else {
+                if (depth == -1) {
+                    depth = node.getDepth();
+                }
+                else {
+                    assertEquals("Node " + node + " has depth " + node.getDepth() + " instead of " + depth,
+                            depth, node.getDepth());
+                }
+
+                int propCount = 0;
+                for (PropertyIterator properties = node.getProperties(); properties.hasNext(); ) {
+                    Property property = properties.nextProperty();
+                    String propertyName = property.getName();
+                    if (!JcrConstants.JCR_PRIMARYTYPE.equals(propertyName)) {
+                        propCount++;
+                        assertTrue("Mismatching order: node " + node + " contains property " + property,
+                                order.compare(parentName, propertyName) <= 0);
+                    }
+                }
+
+                if (propCount > 0) {
+                    assertTrue("Node " + node + " should have at least " + minChildren + " properties",
+                            minChildren <= propCount);
+                    assertTrue("Node" + node + " should have no more than " + maxChildren + " properties",
+                            maxChildren >= propCount);
+                }
+            }
+
+        }
+    }
+
+    private static void checkOrder(NodeSequence nodes, Comparator<String> order) throws RepositoryException {
+        Node p = null;
+        for (Node n : nodes) {
+            if (p != null) {
+                assertTrue("Mismatching order: node " + p + " should occur before node " + n,
+                        order.compare(p.getName(), n.getName()) < 0);
+            }
+            p = n;
+        }
+    }
+
+    private static void checkLookup(NodeSequence nodes, List<String> keys) throws RepositoryException {
+        for (String key : keys) {
+            assertTrue("Missing key: " + key, nodes.hasItem(key));
+            Node node = nodes.getItem(key);
+            assertEquals("Key " + key + " does not match name of node " + node, key, node.getName());
+        }
+    }
+
+    private static void checkLookup(PropertySequence properties, List<String> keys) throws RepositoryException {
+        for (String key : keys) {
+            assertTrue("Missing key: " + key, properties.hasItem(key));
+            Property property = properties.getItem(key);
+            assertEquals("Key " + key + " does not match name of property " + property, key, property.getName());
+        }
+    }
+
+    private static void checkNotFound(NodeSequence nodes, List<String> keys) throws RepositoryException {
+        for (String key : keys) {
+            assertFalse("NodeSequence should not contain key " + key, nodes.hasItem(key));
+            try {
+                nodes.getItem(key);
+                fail("NodeSequence should not contain key " + key);
+            }
+            catch (RepositoryException expected) { }
+        }
+    }
+
+    private static void checkNotFound(PropertySequence properties, List<String> keys) throws RepositoryException {
+        for (String key : keys) {
+            assertFalse("PropertySequence should not contain key " + key, properties.hasItem(key));
+            try {
+                properties.getItem(key);
+                fail("PropertySequence should not contain key " + key);
+            }
+            catch (RepositoryException expected) { }
+        }
+    }
+
+
+    private static void removeAll(NodeSequence nodes, List<String> words) throws RepositoryException {
+        for (String name : words) {
+            nodes.removeNode(name);
+        }
+    }
+
+    private static void removeAll(PropertySequence properties, List<String> words) throws RepositoryException {
+        for (String name : words) {
+            properties.removeProperty(name);
+        }
+    }
+
+    private static void checkEmpty(NodeSequence nodes) throws RepositoryException {
+        for (Node n : nodes) {
+            fail("NodeSqeuence should be empty but found " + n.getPath());
+        }
+    }
+
+    private static void checkEmpty(PropertySequence properties) throws RepositoryException {
+        for (Property p : properties) {
+            fail("PropertySqeuence should be empty but found " + p.getPath());
+        }
+    }
+
+}

Added: jackrabbit/trunk/jackrabbit-core/src/test/java/org/apache/jackrabbit/core/integration/TreeTraverserTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-core/src/test/java/org/apache/jackrabbit/core/integration/TreeTraverserTest.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-core/src/test/java/org/apache/jackrabbit/core/integration/TreeTraverserTest.java (added)
+++ jackrabbit/trunk/jackrabbit-core/src/test/java/org/apache/jackrabbit/core/integration/TreeTraverserTest.java Mon Aug  2 16:56:10 2010
@@ -0,0 +1,260 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package org.apache.jackrabbit.core.integration;
+
+import org.apache.commons.collections.Predicate;
+import org.apache.commons.collections.Transformer;
+import org.apache.commons.collections.iterators.EmptyIterator;
+import org.apache.commons.collections.iterators.FilterIterator;
+import org.apache.commons.collections.iterators.SingletonIterator;
+import org.apache.commons.collections.iterators.TransformIterator;
+import org.apache.jackrabbit.JcrConstants;
+import org.apache.jackrabbit.flat.TreeTraverser;
+import org.apache.jackrabbit.test.AbstractJCRTest;
+
+import javax.jcr.Item;
+import javax.jcr.Node;
+import javax.jcr.Property;
+import javax.jcr.RepositoryException;
+import javax.jcr.nodetype.NodeType;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+
+import junit.framework.AssertionFailedError;
+
+public class TreeTraverserTest extends AbstractJCRTest {
+    private Node testNode;
+
+    private final TreeTraverser.ErrorHandler errorHandler = new TreeTraverser.ErrorHandler() {
+        public void call(Item item, RepositoryException exception) {
+            throw (AssertionFailedError) new AssertionFailedError().initCause(exception);
+        }
+    };
+
+    private final List<String> nodes = Arrays.asList(
+        "",
+        "a",
+        "a/b",
+        "a/a",
+        "a/c",
+        "b",
+        "c",
+        "d",
+        "d/a",
+        "d/a/b",
+        "d/a/b/c",
+        "d/a/b/c/d",
+        "d/a/b/c/d/e",
+        "d/a/b/c/d/e/f",
+        "e"
+    );
+
+    private final Set<String> properties = new HashSet<String>() {{
+        add("v");
+        add("w");
+        add("x");
+        add("a/v");
+        add("a/w");
+        add("a/x");
+        add("a/a/a");
+        add("d/a/b/c/d/e/f/q");
+    }};
+
+    private final List<String> leaves = new LinkedList<String>();
+
+    @Override
+    public void setUp() throws Exception {
+        super.setUp();
+        testNode = testRootNode.addNode("TreeTraverserTest", NodeType.NT_UNSTRUCTURED);
+        superuser.save();
+
+        // Determine leave nodes
+        outer:
+        for (String node : nodes) {
+            for (String other : nodes) {
+                if (other.startsWith(node) && !other.equals(node)) {
+                    continue outer;
+                }
+            }
+            leaves.add(node);
+        }
+    }
+
+    public void testTraverseNodesEmpty() throws RepositoryException {
+        TreeTraverser traverser = new TreeTraverser(testNode, errorHandler, TreeTraverser.InclusionPolicy.ALL);
+        checkNodes(traverser, singleton(""), testNode.getPath());
+    }
+
+    public void testTraverseLeavesEmpty() throws RepositoryException {
+        TreeTraverser traverser = new TreeTraverser(testNode, errorHandler, TreeTraverser.InclusionPolicy.LEAVES);
+        checkNodes(traverser, singleton(""), testNode.getPath());
+    }
+
+    public void testTraverseNodes() throws RepositoryException {
+        addNodes(testNode, nodes);
+        TreeTraverser traverser = new TreeTraverser(testNode, errorHandler, TreeTraverser.InclusionPolicy.ALL);
+        checkNodes(traverser, nodes.iterator(), testNode.getPath());
+    }
+
+    public void testTraverseLeaves() throws RepositoryException {
+        addNodes(testNode, nodes);
+        TreeTraverser traverser = new TreeTraverser(testNode, errorHandler, TreeTraverser.InclusionPolicy.LEAVES);
+        checkNodes(traverser, leaves.iterator(), testNode.getPath());
+    }
+
+    public void testTraversePropertiesEmpty() throws RepositoryException {
+        Iterator<Node> nodeIt = TreeTraverser.nodeIterator(testNode);
+        Iterator<Property> propertyIt = TreeTraverser.propertyIterator(nodeIt);
+        checkProperties(propertyIt, TreeTraverserTest.<String>empty(), testNode.getPath());
+
+        addNodes(testNode, nodes);
+        checkProperties(propertyIt, TreeTraverserTest.<String>empty(), testNode.getPath());
+    }
+
+    public void testTraverseProperties() throws RepositoryException {
+        addNodes(testNode, nodes);
+        addProperties(testNode, properties);
+        Iterator<Node> nodeIt = TreeTraverser.nodeIterator(testNode);
+        Iterator<Property> propertyIt = TreeTraverser.propertyIterator(nodeIt);
+
+        checkProperties(propertyIt, properties.iterator(), testNode.getPath());
+    }
+
+    // -----------------------------------------------------< internal >---
+
+    private static void addNodes(Node root, Iterable<String> nodes) throws RepositoryException {
+        for (String name : nodes) {
+            if (!"".equals(name)) {
+                root.addNode(name);
+            }
+        }
+        root.getSession().save();
+    }
+
+    private static void addProperties(Node root, Iterable<String> properties) throws RepositoryException {
+        for (String name : properties) {
+            int i = name.lastIndexOf('/');
+            Node n;
+            String propName;
+            if (i <= 0) {
+                n = root;
+                propName = name;
+            }
+            else {
+                n = root.getNode(name.substring(0, i));
+                propName = name.substring(i + 1);
+            }
+            n.setProperty(propName, propName + " value");
+        }
+        root.getSession().save();
+    }
+
+    private static void checkNodes(TreeTraverser treeTraverser, Iterator<String> expectedNodes, String pathPrefix)
+            throws RepositoryException {
+
+        for (Node node : treeTraverser) {
+            assertTrue("No more nodes. Expected " + node, expectedNodes.hasNext());
+            assertEquals(cat(pathPrefix, expectedNodes.next()), node.getPath());
+        }
+
+        assertFalse(expectedNodes.hasNext());
+    }
+
+    private static void checkProperties(Iterator<Property> actualProperties,
+            Iterator<String> expectedProperties, String pathPrefix) {
+
+        List<String> actualPaths = toList(property2Path(removeIgnored(actualProperties)));
+        List<String> expectedPaths = toList(cat(pathPrefix, expectedProperties));
+
+        Collections.sort(actualPaths);
+        Collections.sort(expectedPaths);
+
+        assertEquals(expectedPaths, actualPaths);
+    }
+
+    @SuppressWarnings("unchecked")
+    private static Iterator<Property> removeIgnored(Iterator<Property> properties) {
+        return new FilterIterator(properties, new Predicate() {
+            public boolean evaluate(Object object) {
+                try {
+                    Property property = (Property) object;
+                    return !JcrConstants.JCR_PRIMARYTYPE.equals(property.getName());
+                }
+                catch (RepositoryException e) {
+                    throw (AssertionFailedError) new AssertionFailedError().initCause(e);
+                }
+            }
+        });
+    }
+
+    @SuppressWarnings("unchecked")
+    private static Iterator<String> property2Path(Iterator<Property> properties) {
+        return new TransformIterator(properties, new Transformer() {
+            public Object transform(Object input) {
+                try {
+                    return ((Property) input).getPath();
+                }
+                catch (RepositoryException e) {
+                    throw (AssertionFailedError) new AssertionFailedError().initCause(e);
+                }
+            }
+        });
+    }
+
+    private static <T> List<T> toList(Iterator<T> iterator) {
+        List<T> list = new LinkedList<T>();
+        while (iterator.hasNext()) {
+            list.add(iterator.next());
+        }
+        return list;
+    }
+
+    private static String cat(String s1, String s2) {
+        if ("".equals(s2)) {
+            return s1;
+        }
+        else {
+            return s1 + "/" + s2;
+        }
+    }
+
+    @SuppressWarnings("unchecked")
+    private static Iterator<String> cat(final String s, Iterator<String> strings) {
+        return new TransformIterator(strings, new Transformer() {
+            public Object transform(Object input) {
+                return cat(s, (String) input);
+            }
+        });
+    }
+
+    @SuppressWarnings("unchecked")
+    private static <T> Iterator<T> singleton(T element) {
+        return new SingletonIterator(element);
+    }
+
+    @SuppressWarnings("unchecked")
+    private static <T> Iterator<T> empty() {
+        return EmptyIterator.INSTANCE;
+    }
+
+}

Added: jackrabbit/trunk/jackrabbit-core/src/test/resources/org/apache/jackrabbit/core/integration/words.txt
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-core/src/test/resources/org/apache/jackrabbit/core/integration/words.txt?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-core/src/test/resources/org/apache/jackrabbit/core/integration/words.txt (added)
+++ jackrabbit/trunk/jackrabbit-core/src/test/resources/org/apache/jackrabbit/core/integration/words.txt Mon Aug  2 16:56:10 2010
@@ -0,0 +1,518 @@
+a
+able
+about
+above
+access
+achieve
+achieved
+actual
+actually
+adding
+addition
+additional
+address
+adds
+again
+all
+allow
+allowed
+allows
+along
+also
+an
+analogous
+analyze
+and
+another
+any
+anymore
+applicable
+application
+apply
+approach
+arbitrary
+are
+argument
+arguments
+arithmetic
+around
+art
+article
+articles
+as
+ascii
+ask
+at
+authors
+automatically
+available
+base
+basically
+be
+becomes
+before
+behind
+belong
+better
+blog
+boiled
+both
+bound
+bounds
+branches
+but
+by
+calculus
+call
+callable
+called
+calling
+calls
+came
+can
+cannot
+carried
+carry
+case
+cases
+casted
+casts
+certain
+church
+closest
+code
+collection
+comes
+comment
+compile
+compiler
+complain
+complains
+composes
+concretes
+constraint
+constructing
+contract
+conversion
+conversions
+convert
+converted
+convertible
+converting
+converts
+correct
+correspond
+corresponding
+could
+create
+credits
+current
+decided
+define
+defines
+defining
+degree
+depth
+depths
+designing
+despite
+detail
+details
+determine
+did
+difficulties
+directly
+discuss
+discussed
+disparate
+dispatch
+dispatched
+dispatcher
+do
+does
+don't
+done
+double
+down
+dropped
+due
+each
+earlier
+easily
+easy
+eating
+editor
+effect
+effectively
+either
+element
+employed
+employers
+emulate
+enable
+encode
+encoded
+encoding
+encodings
+end
+entire
+equal
+erases
+erasure
+error
+evaluate
+even
+every
+exactly
+existential
+expands
+expected
+explain
+explicitly
+express
+extension
+fact
+failed
+far
+finally
+find
+finds
+fine
+first
+fit
+fixed
+follow
+following
+follows
+for
+form
+formatted
+former
+from
+full
+function
+further
+general
+generalization
+generalize
+generalized
+generic
+generics
+gentle
+give
+given
+goals
+got
+guess
+had
+handle
+handling
+has
+have
+having
+helps
+henry
+here
+hidden
+higher
+how
+however
+i
+idea
+if
+implement
+implementation
+implemented
+implicit
+implicitly
+impression
+in
+indeed
+individual
+induction
+infix
+information
+inherent
+initial
+inside
+instance
+instances
+instantiated
+instead
+int
+integer
+interested
+into
+ints
+involved
+is
+issue
+issues
+it
+iteratively
+its
+itself
+java
+jcr
+just
+keeps
+kind
+kinds
+lambda
+last
+later
+latter
+lattice
+least
+leaves
+legal
+lets
+library
+like
+limitations
+limited
+limits
+line
+lines
+list
+lists
+look
+looks
+matching
+matter
+may
+me
+means
+mechanism
+mention
+mentioned
+meta
+method
+methods
+might
+mimic
+mind
+more
+much
+multiplication
+my
+natural
+need
+new
+next
+nicely
+no
+nodes
+not
+noted
+now
+nth
+null
+number
+numbers
+numerals
+nutshell
+objects
+of
+on
+once
+one
+only
+open
+operations
+operator
+operators
+or
+order
+original
+originally
+other
+outputs
+over
+overloading
+page
+paper
+parameter
+parameters
+pass
+passed
+passes
+passing
+pattern
+picture
+pimp
+place
+playing
+plays
+plus
+pointing
+polymorphic
+pose
+possible
+post
+posted
+pre
+preparation
+previous
+print
+probably
+problem
+problematic
+programming
+properties
+proposed
+provided
+puzzle
+random
+rather
+recently
+recursive
+related
+reports
+represent
+representing
+requirement
+respective
+responsible
+restrict
+restricted
+restriction
+result
+return
+returns
+reuse
+revisited
+right
+rights
+safe
+safety
+same
+saved
+say
+scala
+scale
+scarify
+scenes
+scope
+searches
+second
+sections
+see
+seems
+select
+serve
+shortcoming
+shots
+should
+show
+showed
+shows
+signature
+similar
+similarly
+simpler
+simplified
+simply
+since
+so
+solution
+some
+source
+special
+specialized
+specific
+specifying
+stands
+step
+still
+string
+strings
+structural
+structure
+structures
+stumbled
+stupid
+subsequently
+succeed
+successor
+such
+supply
+switch
+syntax
+system
+t
+take
+taken
+takes
+target
+technique
+terms
+that
+the
+their
+them
+themselves
+then
+theory
+there
+these
+things
+think
+third
+this
+thus
+time
+to
+topic
+towards
+treated
+tree
+trick
+tried
+trouble
+try
+two
+type
+typed
+types
+under
+understand
+understanding
+until
+up
+upper
+us
+use
+used
+using
+value
+values
+version
+view
+want
+wanted
+ware
+was
+way
+ways
+we
+well
+what
+when
+where
+which
+while
+whole
+whose
+why
+will
+with
+without
+work
+works
+wrapped
+write
+wrote
+yet
+you
+zero
\ No newline at end of file

Modified: jackrabbit/trunk/jackrabbit-jcr-commons/pom.xml
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-jcr-commons/pom.xml?rev=981597&r1=981596&r2=981597&view=diff
==============================================================================
--- jackrabbit/trunk/jackrabbit-jcr-commons/pom.xml (original)
+++ jackrabbit/trunk/jackrabbit-jcr-commons/pom.xml Mon Aug  2 16:56:10 2010
@@ -71,6 +71,10 @@
       <artifactId>json</artifactId>
       <scope>test</scope>
     </dependency>
+    <dependency>
+    	<groupId>commons-collections</groupId>
+    	<artifactId>commons-collections</artifactId>
+    </dependency>
   </dependencies>
 
 </project>

Added: jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/BTreeManager.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/BTreeManager.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/BTreeManager.java (added)
+++ jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/BTreeManager.java Mon Aug  2 16:56:10 2010
@@ -0,0 +1,424 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package org.apache.jackrabbit.flat;
+
+
+import org.apache.commons.collections.Predicate;
+import org.apache.commons.collections.iterators.FilterIterator;
+import org.apache.jackrabbit.JcrConstants;
+
+import javax.jcr.Item;
+import javax.jcr.Node;
+import javax.jcr.NodeIterator;
+import javax.jcr.Property;
+import javax.jcr.PropertyIterator;
+import javax.jcr.RepositoryException;
+
+import java.util.Comparator;
+import java.util.Iterator;
+
+/**
+ * <p>
+ * This {@link TreeManager} implementation provides B+-tree like behavior. That
+ * is items of a sequence (i.e. {@link NodeSequence} or {@link PropertySequence})
+ * are mapped to a sub-tree in JCR in a way such that only leave nodes carry
+ * actual values, the sub-tree is always balanced and ordered. This
+ * implementation does in contrast to a full B+-tree implementation <em>not</em>
+ * join nodes after deletions. This does not affect the order of items and also
+ * leaves the tree balanced wrt. its depths. It might however result in a sparse
+ * tree. That is, the tree might get unbalanced wrt. its weights.
+ * </p>
+ *
+ * <p>
+ * The nodes in the JCR sub tree are arranged such that any node named <code>x</code>
+ * only contains child nodes with names greater or equal to <code>x</code>.
+ * The implementation keeps the child nodes in the sub tree ordered if the
+ * respective node type supports ordering of child nodes.
+ * Ordering is always wrt. to a {@link Comparator} on the respective keys.
+ * For lexical order this arrangement corresponds to how words are arranged in a multi
+ * volume encyclopedia.
+ * </p>
+ *
+ * <p>
+ * Example usage:
+ *
+ * <pre>
+ * // Create a new TreeManager instance rooted at node. Splitting of nodes takes place
+ * // when the number of children of a node exceeds 40 and is done such that each new
+ * // node has at least 40 child nodes. The keys are ordered according to the natural
+ * // order of java.lang.String.
+ * TreeManager treeManager = new BTreeManager(node, 20, 40, Rank.&lt;String&gt;comparableComparator(), true);
+ *
+ * // Create a new NodeSequence with that tree manager
+ * NodeSequence nodes = ItemSequence.createNodeSequence(treeManager);
+ *
+ * // Add nodes with key &quot;jcr&quot; and &quot;day&quot;
+ * nodes.addNode(&quot;jcr&quot;, NodeType.NT_UNSTRUCTURED);
+ * nodes.addNode(&quot;day&quot;, NodeType.NT_UNSTRUCTURED);
+ *
+ * // Iterate over the node in the sequence.
+ * // Prints &quot;day jcr &quot;
+ * for (Node n : nodes) {
+ *     System.out.print(n.getName() + &quot; &quot;);
+ * }
+ *
+ * // Retrieve node with key &quot;jcr&quot;
+ * Node n = nodes.getItem(&quot;jcr&quot;);
+ *
+ * // Remove node with key &quot;day&quot;
+ * nodes.removeNode(&quot;day&quot;);
+ * </pre>
+ *
+ * </p>
+ */
+public class BTreeManager implements TreeManager {
+    private final Node root;
+    private final int minChildren;
+    private final int maxChildren;
+    private final Comparator<String> order;
+    private final boolean autoSave;
+    private final Comparator<Item> itemOrder;
+
+    /**
+     * Create a new {@link BTreeManager} rooted at Node <code>root</code>.
+     *
+     * @param root the root of the JCR sub-tree where the items of the sequence
+     *            are stored.
+     * @param minChildren minimal number of children for a node after splitting.
+     * @param maxChildren maximal number of children for a node after which
+     *            splitting occurs.
+     * @param order order according to which the keys are stored
+     * @param autoSave determines whether the current session is saved after
+     *            add/delete operations.
+     * @throws RepositoryException
+     */
+    public BTreeManager(Node root, int minChildren, int maxChildren, Comparator<String> order, boolean autoSave)
+            throws RepositoryException {
+        super();
+
+        if (root == null) {
+            throw new IllegalArgumentException("root must not be null");
+        }
+        if (minChildren <= 0) {
+            throw new IllegalArgumentException("minChildren must be positive");
+        }
+        if (maxChildren > Integer.MAX_VALUE) {
+            throw new IllegalArgumentException("maxChildren must not exceed " + Integer.MAX_VALUE);
+        }
+        if (2 * minChildren < maxChildren) {
+            throw new IllegalArgumentException("maxChildren must be at least twice minChildren");
+        }
+        if (order == null) {
+            throw new IllegalArgumentException("order must not be null");
+        }
+
+        this.root = root;
+        this.minChildren = minChildren;
+        this.maxChildren = maxChildren;
+        this.order = order;
+        this.autoSave = autoSave;
+        this.itemOrder = new Comparator<Item>() {
+            public int compare(Item i1, Item i2) {
+                try {
+                    return BTreeManager.this.order.compare(i1.getName(), i2.getName());
+                }
+                catch (RepositoryException e) {
+                    throw new WrappedRepositoryException(e);
+                }
+            }
+        };
+    }
+
+    /**
+     * This implementations splits <code>node</code> when its number of child
+     * nodes exceeds the maximum number specified in the constructor. Splitting
+     * is done such that after the split each of the new child nodes contains at
+     * least as many nodes as specified in the constructor.
+     *
+     * @see org.apache.jackrabbit.flat.TreeManager#split(org.apache.jackrabbit.flat.ItemSequence,
+     *      javax.jcr.Node, javax.jcr.Node)
+     */
+    public void split(ItemSequence itemSequence, Node node, Node cause) throws RepositoryException {
+        SizedIterator<Node> childNodes = getNodes(node);
+        int count = (int) childNodes.getSize();
+        if (count >= 0 && count <= maxChildren) {
+            return;
+        }
+
+        split(node, new Rank<Node>(childNodes, Node.class, count, itemOrder), itemSequence);
+    }
+
+    /**
+     * This implementations splits <code>node</code> when its number of
+     * properties exceeds the maximum number specified in the constructor.
+     * Splitting is done such that after the split each of the new child nodes
+     * contains at least as many nodes as specified in the constructor.
+     *
+     * @see org.apache.jackrabbit.flat.TreeManager#split(org.apache.jackrabbit.flat.ItemSequence,
+     *      javax.jcr.Node, javax.jcr.Property)
+     */
+    public void split(ItemSequence itemSequence, Node node, Property cause) throws RepositoryException {
+        SizedIterator<Property> properties = getProperties(node);
+        int count = (int) properties.getSize();
+        if (count >= 0 && count <= maxChildren) {
+            return;
+        }
+
+        split(node, new Rank<Property>(properties, Property.class, count, itemOrder), itemSequence);
+    }
+
+    /**
+     * This implementation does not actually join any nodes. It does however
+     * delete <code>node</code> if {@link #getNodes(Node)} returns an empty
+     * iterator. It does further recursively delete any parent of
+     * <code>node</code> which does not have any child node.
+     *
+     * @see org.apache.jackrabbit.flat.TreeManager#join(org.apache.jackrabbit.flat.ItemSequence,
+     *      javax.jcr.Node, javax.jcr.Node)
+     */
+    public void join(ItemSequence itemSequence, Node node, Node cause) throws RepositoryException {
+        SizedIterator<Node> nodes = getNodes(node);
+        long count = nodes.getSize();
+        if (count < 0) {
+            for (count = 0; nodes.hasNext(); count++, nodes.next());
+        }
+
+        if (count == 0) {
+            Node parent = node.getParent();
+            node.remove();
+            removeRec(parent);
+        }
+    }
+
+    /**
+     * This implementation does not actually join any nodes. It does however
+     * delete <code>node</code> if {@link #getProperties(Node)} returns an empty
+     * iterator. It does further recursively delete any parent of
+     * <code>node</code> which does not have any child node.
+     *
+     * @see org.apache.jackrabbit.flat.TreeManager#join(org.apache.jackrabbit.flat.ItemSequence,
+     *      javax.jcr.Node, javax.jcr.Property)
+     */
+    public void join(ItemSequence itemSequence, Node node, Property cause) throws RepositoryException {
+        SizedIterator<Property> properties = getProperties(node);
+        long count = properties.getSize();
+        if (count < 0) {
+            for (count = 0; properties.hasNext(); count++, properties.next());
+        }
+
+        if (count == 0) {
+            removeRec(node);
+        }
+    }
+
+    public Node getRoot() {
+        return root;
+    }
+
+    public boolean isRoot(Node node) throws RepositoryException {
+        return node.isSame(root);
+    }
+
+    /**
+     * Returns <code>!node.hasNodes()</code>
+     * @see org.apache.jackrabbit.flat.TreeManager#isLeaf(javax.jcr.Node)
+     */
+    public boolean isLeaf(Node node) throws RepositoryException {
+        return !node.hasNodes() && !isRoot(node);
+    }
+
+    public Comparator<String> getOrder() {
+        return order;
+    }
+
+    public boolean getAutoSave() {
+        return autoSave;
+    }
+
+    // -----------------------------------------------------< internal >---
+
+    /**
+     * Returns a {@link SizedIterator} of the child nodes of <code>node</code>.
+     */
+    @SuppressWarnings("unchecked")
+    protected SizedIterator<Node> getNodes(Node node) throws RepositoryException {
+        NodeIterator nodes = node.getNodes();
+        return getSizedIterator(nodes, nodes.getSize());
+    }
+
+    /**
+     * Returns a {@link SizedIterator} of the properties of <code>node</code> which
+     * excludes the <code>jcr.primaryType</code> property.
+     */
+    protected SizedIterator<Property> getProperties(final Node node) throws RepositoryException {
+        final PropertyIterator properties = node.getProperties();
+
+        @SuppressWarnings("unchecked")
+        final Iterator<Property> filtered = new FilterIterator(properties, new Predicate() {
+            public boolean evaluate(Object object) {
+                Property p = (Property) object;
+                try {
+                    return !JcrConstants.JCR_PRIMARYTYPE.equals(p.getName());
+                }
+                catch (RepositoryException ignore) {
+                    return true;
+                }
+
+            }
+        });
+
+        long size = properties.getSize();
+        return getSizedIterator(filtered, size > 0 ? size - 1 : size);
+    }
+
+    /**
+     * Creates and return an intermediate node for the given <code>name</code>
+     * as child node of <code>parent</code>.
+     */
+    protected Node createIntermediateNode(Node parent, String name) throws RepositoryException {
+        return parent.addNode(name);
+    }
+
+    /**
+     * Move <code>node</code> to the new <code>parent</code>.
+     */
+    protected void move(Node node, Node parent) throws RepositoryException {
+        String oldPath = node.getPath();
+        String newPath = parent.getPath() + "/" + node.getName();
+        node.getSession().move(oldPath, newPath);
+    }
+
+    /**
+     * Move <code>property</code> to the new <code>parent</code>.
+     */
+    protected void move(Property property, Node parent) throws RepositoryException {
+        parent.setProperty(property.getName(), property.getValue());
+        property.remove();
+    }
+
+    /**
+     * Wraps <code>iterator</code> into a {@link SizedIterator} given a
+     * <code>size</code>. The value of the <code>size</code> parameter must
+     * correctly reflect the number of items in <code>iterator</code>.Ê
+     */
+    protected final <T> SizedIterator<T> getSizedIterator(final Iterator<T> iterator, final long size) {
+        return new SizedIterator<T>() {
+            public boolean hasNext() {
+                return iterator.hasNext();
+            }
+
+            public T next() {
+                return iterator.next();
+            }
+
+            public void remove() {
+                iterator.remove();
+            }
+
+            public long getSize() {
+                return size;
+            }
+        };
+    }
+
+    // -----------------------------------------------------< internal >---
+
+    private <T extends Item> void split(Node node, Rank<T> ranking, ItemSequence itemSequence) throws RepositoryException {
+        if (ranking.size() <= maxChildren) {
+            return;
+        }
+
+        try {
+            Node grandParent;
+            if (isRoot(node)) {
+                grandParent = node;
+            }
+            else {
+                grandParent = node.getParent();
+
+                // leave first minChildren items where they are
+                ranking.take(minChildren);
+            }
+
+            // move remaining items to new parents
+            for (int k = ranking.size() / minChildren; k > 0; k--) {
+                T item = ranking.take(1).next();
+                String key = item.getName();
+
+                Node newParent;
+                if (grandParent.getPrimaryNodeType().hasOrderableChildNodes()) {
+                    Node dest = itemSequence.getSuccessor(grandParent, key);
+                    newParent = createIntermediateNode(grandParent, key);
+                    grandParent.orderBefore(key, dest == null ? null : dest.getName());
+                }
+                else {
+                    newParent = createIntermediateNode(grandParent, key);
+                }
+
+                move(item, newParent);
+
+                int c = k > 1 ? minChildren - 1 : ranking.size();
+                Iterator<T> remaining = ranking.take(c);
+
+                // If ordered, ranking returns an ordered iterator. So order will be correct here
+                while (remaining.hasNext()) {
+                    move(remaining.next(), newParent);
+                }
+            }
+
+            // If we did not reach root yet, recursively split the parent
+            if (!node.isSame(root)) {
+                split(itemSequence, grandParent, (Node) null);
+            }
+        }
+        catch (WrappedRepositoryException e) {
+            throw e.wrapped();
+        }
+    }
+
+    private <T extends Item> void move(T item, Node parent) throws RepositoryException {
+        if (item.isNode()) {
+            move((Node) item, parent);
+        }
+        else {
+            move((Property) item, parent);
+        }
+    }
+
+    private void removeRec(Node node) throws RepositoryException {
+        Node n = node;
+        while (!n.hasNodes() && !isRoot(n)) {
+            Node d = n;
+            n = n.getParent();
+            d.remove();
+        }
+    }
+
+    private static class WrappedRepositoryException extends RuntimeException {
+        private final RepositoryException wrapped;
+
+        public WrappedRepositoryException(RepositoryException e) {
+            super();
+            this.wrapped = e;
+        }
+
+        public RepositoryException wrapped() {
+            return wrapped;
+        }
+    }
+
+}
\ No newline at end of file

Added: jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/ItemSequence.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/ItemSequence.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/ItemSequence.java (added)
+++ jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/ItemSequence.java Mon Aug  2 16:56:10 2010
@@ -0,0 +1,508 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package org.apache.jackrabbit.flat;
+
+import org.apache.jackrabbit.flat.TreeTraverser.ErrorHandler;
+import org.apache.jackrabbit.flat.TreeTraverser.InclusionPolicy;
+
+import javax.jcr.ItemExistsException;
+import javax.jcr.Node;
+import javax.jcr.NodeIterator;
+import javax.jcr.PathNotFoundException;
+import javax.jcr.Property;
+import javax.jcr.RepositoryException;
+import javax.jcr.Session;
+import javax.jcr.Value;
+
+import java.util.Comparator;
+import java.util.Iterator;
+
+/**
+ * <p>
+ * This class serves as main entry point for obtaining sequences of {@link Node}
+ * s and {@link Property}s. It provides factory methods for creating
+ * {@link NodeSequence}s and {@link PropertySequence}s.
+ * </p>
+ *
+ * <p>
+ * NodeSequence and PropertySequence instances provide a flat representation of
+ * a JCR hierarchy rooted at a certain node. They allow iterating over all
+ * items, retrieving items by key, checking whether a given key is mapped,
+ * adding new items and removing existing items.
+ * </p>
+ *
+ * <p>
+ * The specifics of the mapping from the flat representation to the JCR
+ * hierarchy are delegated to a {@link TreeManager}. Particularly the
+ * TreeManager specifies the order of the items when retrieved as sequence and
+ * when and how to add and remove intermediate nodes when new items are inserted
+ * or removed.
+ * </p>
+ *
+ * <p>
+ * An {@link ErrorHandler} is used to handle exceptions which occur while
+ * traversing the hierarchy.
+ * </p>
+ *
+ * @see TreeTraverser
+ * @see NodeSequence
+ * @see PropertySequence
+ * @see TreeManager
+ */
+public abstract class ItemSequence {
+
+    /**
+     * The {@link TreeManager} instance managing the mapping between the
+     * sequence view and the JCR hierarchy.
+     */
+    protected final TreeManager treeManager;
+
+    /**
+     * The {@link ErrorHandler} instance used for handling exceptions occurring
+     * while traversing the hierarchy.
+     */
+    protected final ErrorHandler errorHandler;
+
+    /**
+     * @see TreeManager#getRoot()
+     */
+    protected final Node root;
+
+    /**
+     * @see TreeManager#getOrder()
+     */
+    protected final Comparator<String> order;
+
+    /**
+     * @see TreeManager#getAutoSave()
+     */
+    protected final boolean autoSave;
+
+    /**
+     * Create a new {@link ItemSequence} instance.
+     *
+     * @param treeManager The {@link TreeManager} for managing the mapping
+     *            between the sequence view and the JCR hierarchy.
+     * @param errorHandler The {@link ErrorHandler} for handling exceptions
+     *            occurring while traversing the hierarchy.
+     * @throws IllegalArgumentException If either <code>treeManager</code> is
+     *             <code>null</code> or {@link TreeManager#getRoot()} return
+     *             <code>null</code> or {@link TreeManager#getOrder()} return
+     *             <code>null</code>.
+     */
+    protected ItemSequence(TreeManager treeManager, ErrorHandler errorHandler) {
+        super();
+
+        if (treeManager == null) {
+            throw new IllegalArgumentException("tree manager must not be null");
+        }
+        if (treeManager.getRoot() == null) {
+            throw new IllegalArgumentException("root must not be null");
+        }
+        if (treeManager.getOrder() == null) {
+            throw new IllegalArgumentException("order must not be null");
+        }
+
+        this.treeManager = treeManager;
+        this.errorHandler = errorHandler;
+        this.root = treeManager.getRoot();
+        this.order = treeManager.getOrder();
+        this.autoSave = treeManager.getAutoSave();
+    }
+
+    /**
+     * Create a new {@link NodeSequence} instance.
+     *
+     * @param treeManager The {@link TreeManager} for managing the mapping
+     *            between the sequence view and the JCR hierarchy.
+     * @param errorHandler The {@link ErrorHandler} for handling exceptions
+     *            occurring while
+     * @return
+     */
+    public static NodeSequence createNodeSequence(TreeManager treeManager, ErrorHandler errorHandler) {
+        return new NodeSequenceImpl(treeManager, errorHandler);
+    }
+
+    /**
+     * Create a new {@link NodeSequence} instance.
+     *
+     * @param treeManager The {@link TreeManager} for managing the mapping
+     *            between the sequence view and the JCR hierarchy.
+     * @return
+     */
+    public static NodeSequence createNodeSequence(TreeManager treeManager) {
+        return new NodeSequenceImpl(treeManager, ErrorHandler.IGNORE);
+    }
+
+    /**
+     * Create a new {@link PropertySequence} instance.
+     *
+     * @param treeManager The {@link TreeManager} for managing the mapping
+     *            between the sequence view and the JCR hierarchy.
+     * @param errorHandler The {@link ErrorHandler} for handling exceptions
+     *            occurring while
+     * @return
+     */
+    public static PropertySequence createPropertySequence(TreeManager treeManager, ErrorHandler errorHandler) {
+        return new PropertySequenceImpl(treeManager, errorHandler);
+    }
+
+    /**
+     * Create a new {@link PropertySequence} instance.
+     *
+     * @param treeManager The {@link TreeManager} for managing the mapping
+     *            between the sequence view and the JCR hierarchy.
+     * @return
+     */
+    public static PropertySequence createPropertySequence(TreeManager treeManager) {
+        return new PropertySequenceImpl(treeManager, ErrorHandler.IGNORE);
+    }
+
+    /**
+     * Create a new {@link NodeSequence} instance with the same parametrization
+     * as this instance.
+     *
+     * @return
+     */
+    public NodeSequence getNodeSequence() {
+        return new NodeSequenceImpl(treeManager, errorHandler);
+    }
+
+    /**
+     * Create a new {@link PropertySequence} instance with the same
+     * parametrization as this instance.
+     *
+     * @return
+     */
+    public PropertySequence getPropertySequence() {
+        return new PropertySequenceImpl(treeManager, errorHandler);
+    }
+
+    // -----------------------------------------------------< internal >---
+
+    /**
+     * Returns the parent node for the given key. When the key is not present in
+     * this sequence already, the returned node is the node that would contain
+     * that key if it where present.
+     */
+    protected abstract Node getParent(String key) throws RepositoryException;
+
+    /**
+     * Returns the predecessor node for the given
+     * <code>key</key>. That is the node
+     * whose key directly precedes the passed <code>key</code> in the order
+     * determined by {@link TreeManager#getOrder()}. There are two cases:
+     * <ul>
+     * <li>A node with the given <code>key</code> is mapped: then that node is
+     * returned.</li>
+     * <li>A node with the given <code>key</code> is not mapped: the the node
+     * where that would contain that key if present is returned.</li>
+     * </ul>
+     */
+    protected final Node getPredecessor(String key) throws RepositoryException {
+        Node p = root;
+        Node n;
+        while ((n = getPredecessor(p, key)) != null) {
+            p = n;
+        }
+
+        return p;
+    }
+
+    /**
+     * Returns the direct predecessor of <code>key</code> amongst
+     * <code>node</code>'s child nodes wrt. to {@link TreeManager#getOrder()}.
+     * Returns <code>null</code> if either <code>node</code> has no child nodes
+     * or <code>node</code> is a leaf (see {@link TreeManager#isLeaf(Node)}) or
+     * <code>key</code> is smaller than all the keys of all child nodes of
+     * <code>node</code>.
+     */
+    protected final Node getPredecessor(Node node, String key) throws RepositoryException {
+        if (!node.hasNodes() || treeManager.isLeaf(node)) {
+            return null;
+        }
+
+        // Shortcut for exact match
+        try {
+            return node.getNode(key);
+        }
+        catch (PathNotFoundException ignore) { }
+
+        // Search for direct predecessor of key in the nodes children
+        // todo performance: for ordered nodes use binary search
+        NodeIterator childNodes = node.getNodes();
+        Node p = null;
+        while (childNodes.hasNext()) {
+            Node n = childNodes.nextNode();
+            String childKey = n.getName();
+            if (order.compare(key, childKey) > 0 && (p == null || order.compare(childKey, p.getName()) > 0)) {
+                p = n;
+            }
+        }
+
+        return p;
+    }
+
+    /**
+     * Returns the successor node for the given
+     * <code>key</key>. That is the node
+     * whose key directly succeeds the passed <code>key</code> in the order
+     * determined by {@link TreeManager#getOrder()}. There are two cases:
+     * <ul>
+     * <li>A node with the given <code>key</code> is mapped: then that node is
+     * returned.</li>
+     * <li>A node with the given <code>key</code> is not mapped: the the node
+     * where that would contain that key if present is returned.</li>
+     * </ul>
+     */
+    protected final Node getSuccessor(Node node, String key) throws RepositoryException {
+        if (!node.hasNodes() || treeManager.isLeaf(node)) {
+            return null;
+        }
+
+        // Shortcut for exact match
+        try {
+            return node.getNode(key);
+        }
+        catch (PathNotFoundException ignore) { }
+
+        // Search for direct succecessor of key in the nodes children
+        // todo performance: for ordered nodes use binary search
+        NodeIterator childNodes = node.getNodes();
+        Node s = null;
+        while (childNodes.hasNext()) {
+            Node n = childNodes.nextNode();
+            String childKey = n.getName();
+            if (order.compare(key, childKey) < 0 && (s == null || order.compare(childKey, s.getName()) < 0)) {
+                s = n;
+            }
+        }
+
+        return s;
+    }
+
+    /**
+     * Returns the node with the minimal key wrt. {@link TreeManager#getOrder()}.
+     * For the empty sequence this is {@link TreeManager#getRoot()}.
+     */
+    protected final Node getMinimal() throws RepositoryException {
+        Node p = null;
+        Node n = root;
+        while ((n = getMinimal(n)) != null) {
+            p = n;
+        }
+
+        return p;
+    }
+
+    /**
+     * Returns the node amongst the child nodes of <code>node</code> whose key
+     * is minimal wrt. {@link TreeManager#getOrder()}. Returns <code>null</code>
+     * id either <code>node</code> has no child nodes or <code>node</code> is a
+     * leaf (see {@link TreeManager#isLeaf(Node)}).
+     */
+    protected final Node getMinimal(Node node) throws RepositoryException {
+        if (!node.hasNodes() || treeManager.isLeaf(node)) {
+            return null;
+        }
+
+        // Search for minimal key in the nodes children
+        // todo performance: for ordered nodes use binary search
+        NodeIterator childNodes = node.getNodes();
+        Node p = childNodes.nextNode();
+        String minKey = p.getName();
+        while (childNodes.hasNext()) {
+            Node n = childNodes.nextNode();
+            if (order.compare(n.getName(), minKey) < 0) {
+                p = n;
+                minKey = p.getName();
+            }
+        }
+
+        return p;
+    }
+
+    /**
+     * Rename the path of the node with the minimal key. That is, assuming
+     * <code>node</code> is the node with the minimal key (see
+     * {@link #getMinimal()}), this method renames every segment of the path of
+     * <code>node</code> up to {@link TreeManager#getRoot()} to <code>key</code>
+     * . <em>Note: </em> If <code>node</code> is not the node with the minimal
+     * key, the behavior of this method is not specified.
+     */
+    protected final void renamePath(Node node, String key) throws RepositoryException {
+        if (!treeManager.isRoot(node)) {
+            Node p = node.getParent();
+            renamePath(p, key);
+            Session s = node.getSession();
+            s.move(node.getPath(), p.getPath() + "/" + key);
+
+            // If orderable, move to first child node
+            if (p.getPrimaryNodeType().hasOrderableChildNodes()) {
+                p.orderBefore(key, p.getNodes().nextNode().getName());
+            }
+        }
+    }
+
+    protected static class NodeSequenceImpl extends ItemSequence implements NodeSequence {
+
+        public NodeSequenceImpl(TreeManager treeManager, ErrorHandler errorHandler)  {
+            super(treeManager, errorHandler);
+        }
+
+        public Iterator<Node> iterator() {
+            return TreeTraverser.nodeIterator(root, errorHandler, new InclusionPolicy() {
+                public boolean include(Node node) throws RepositoryException {
+                    return treeManager.isLeaf(node);
+                }
+            });
+        }
+
+        public Node getItem(String key) throws RepositoryException {
+            return getParent(key).getNode(key);
+        }
+
+        public boolean hasItem(String key) throws RepositoryException {
+            return getParent(key).hasNode(key);
+        }
+
+        public Node addNode(String key, String primaryNodeTypeName) throws RepositoryException {
+            Node parent = getOrCreateParent(key);
+            if (parent.hasNode(key)) {
+                throw new ItemExistsException(key);
+            }
+
+            Node n;
+            if (parent.getPrimaryNodeType().hasOrderableChildNodes()) {
+                Node dest = getSuccessor(parent, key);
+                n = parent.addNode(key, primaryNodeTypeName);
+                parent.orderBefore(key, dest == null ? null : dest.getName());
+            }
+            else {
+                n = parent.addNode(key, primaryNodeTypeName);
+            }
+
+            treeManager.split(this, parent, n);
+
+            if (autoSave) {
+                parent.getSession().save();
+            }
+
+            return n;
+        }
+
+        public void removeNode(String key) throws RepositoryException {
+            Node parent = getParent(key);
+            Node n = parent.getNode(key);
+            n.remove();
+            treeManager.join(this, parent, n);
+
+            if (autoSave) {
+                parent.getSession().save();
+            }
+        }
+
+        @Override
+        public Node getParent(String key) throws RepositoryException {
+            Node p = getPredecessor(key);
+            if (treeManager.isLeaf(p) && !treeManager.isRoot(p)) {
+                return p.getParent();
+            }
+            else {
+                return p;
+            }
+        }
+
+        private Node getOrCreateParent(String key) throws RepositoryException {
+            Node p = getParent(key);
+            if (treeManager.isRoot(p)) {
+                Node min = getMinimal();
+                if (min != null) {
+                    p = min.getParent();
+                    renamePath(p, key);
+                }
+            }
+            return p;
+        }
+
+    }
+
+    protected static class PropertySequenceImpl extends ItemSequence implements PropertySequence {
+
+        public PropertySequenceImpl(TreeManager treeManager, ErrorHandler errorHandler) {
+            super(treeManager, errorHandler);
+        }
+
+        public Iterator<Property> iterator() {
+            return TreeTraverser.propertyIterator(getNodeSequence().iterator(), errorHandler);
+        }
+
+        public Property getItem(String key) throws RepositoryException {
+            return getParent(key).getProperty(key);
+        }
+
+        public boolean hasItem(String key) throws RepositoryException {
+            return getParent(key).hasProperty(key);
+        }
+
+        public Property addProperty(String key, Value value) throws RepositoryException {
+            Node parent = getOrCreateParent(key);
+            if (parent.hasProperty(key)) {
+                throw new ItemExistsException(key);
+            }
+
+            Property p = parent.setProperty(key, value);
+            treeManager.split(this, parent, p);
+
+            if (autoSave) {
+                p.getSession().save();
+            }
+
+            return p;
+        }
+
+        public void removeProperty(String key) throws RepositoryException {
+            Node parent = getParent(key);
+            Property p = parent.getProperty(key);
+            p.remove();
+            treeManager.join(this, parent, p);
+
+            if (autoSave) {
+                parent.getSession().save();
+            }
+        }
+
+        @Override
+        public Node getParent(String key) throws RepositoryException {
+            return getPredecessor(key);
+        }
+
+        private Node getOrCreateParent(String key) throws RepositoryException {
+            Node p = getParent(key);
+            if (treeManager.isRoot(p)) {
+                Node min = getMinimal();
+                if (min != null) {
+                    p = min;
+                    renamePath(p, key);
+                }
+            }
+            return p;
+        }
+
+    }
+
+}

Added: jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/NodeSequence.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/NodeSequence.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/NodeSequence.java (added)
+++ jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/NodeSequence.java Mon Aug  2 16:56:10 2010
@@ -0,0 +1,46 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package org.apache.jackrabbit.flat;
+
+import javax.jcr.Node;
+import javax.jcr.RepositoryException;
+
+/**
+ * Extension of {@link Sequence Sequence&lt;Node>} which provides methods for
+ * adding and removing nodes by key.
+ */
+public interface NodeSequence extends Sequence<Node> {
+
+    /**
+     * Add a with the given <code>key</code> and primary node type name.
+     *
+     * @param key key of the node to add
+     * @param primaryNodeTypeName primary node type of the node to add
+     * @return the newly added node
+     * @throws RepositoryException
+     */
+    Node addNode(String key, String primaryNodeTypeName) throws RepositoryException;
+
+    /**
+     * Remove the node with the given key.
+     *
+     * @param key The key of the node to remove
+     * @throws RepositoryException If there is no node with such a key or
+     *             another error occurs.
+     */
+    void removeNode(String key) throws RepositoryException;
+}
\ No newline at end of file

Added: jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/PropertySequence.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/PropertySequence.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/PropertySequence.java (added)
+++ jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/PropertySequence.java Mon Aug  2 16:56:10 2010
@@ -0,0 +1,47 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package org.apache.jackrabbit.flat;
+
+import javax.jcr.Property;
+import javax.jcr.RepositoryException;
+import javax.jcr.Value;
+
+/**
+ * Extension of {@link Sequence Sequence&lt;Property>} which provides methods
+ * for adding and removing properties by key.
+ */
+public interface PropertySequence extends Sequence<Property> {
+
+    /**
+     * Add a property with the given <code>key</code> and <code>value</code>.
+     *
+     * @param key key of the property to add
+     * @param value value of the property to add
+     * @return the newly added property
+     * @throws RepositoryException
+     */
+    Property addProperty(String key, Value value) throws RepositoryException;
+
+    /**
+     * Remove the property with the given key.
+     *
+     * @param key The key of the property to remove
+     * @throws RepositoryException If there is no property with such a key or
+     *             another error occurs.
+     */
+    void removeProperty(String key) throws RepositoryException;
+}
\ No newline at end of file

Added: jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/Rank.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/Rank.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/Rank.java (added)
+++ jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/Rank.java Mon Aug  2 16:56:10 2010
@@ -0,0 +1,280 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package org.apache.jackrabbit.flat;
+
+import org.apache.commons.collections.iterators.ArrayIterator;
+import org.apache.commons.collections.iterators.EmptyIterator;
+
+import java.lang.reflect.Array;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+/**
+ * <p>
+ * This class does efficient ranking of values of type <code>T</code> wrt. to a
+ * {@link Comparator} for <code>T</code>. After creating an instance of
+ * <code>Rank</code>, the {@link #take(int)} method returns the next
+ * <code>k</code> smallest values. That is, each of these values is smaller than
+ * every value not yet retrieved. The order of the values returned by
+ * <code>take</code> is not specified in general. However if the values are in
+ * increasing order, the values returned by <code>take</code> will also be in
+ * increasing order.
+ * </p>
+ * <p>
+ * <em>Note</em>: The values <em>may not contain duplicates</em> or the behavior
+ * of <code>take</code> is not defined.
+ * </p>
+ *
+ * @param <T> Type of values in this <code>Rank</code>.
+ */
+public class Rank<T> {
+    private final T[] values;
+    private final Comparator<? super T> order;
+    private int first;
+
+    /**
+     * Create a new instance of <code>Rank</code> for a given array of
+     * <code>values</code> and a given <code>order</code>. The
+     * <code>values</code> are manipulated in place, no copying is performed.
+     *
+     * @param values values for ranking. Duplicates are <em>not allowed</em>.
+     * @param order Ordering for ranking
+     */
+    public Rank(T[] values, Comparator<? super T> order) {
+        super();
+        this.values = values;
+        this.order = order;
+    }
+
+    /**
+     * Create a new instance of <code>Rank</code> for a given collection of
+     * <code>values</code> and a given <code>order</code>. The
+     * <code>values</code> are copied into an internal array before they are
+     * manipulated.
+     *
+     * @param values values for ranking. Duplicates are <em>not allowed</em>.
+     * @param componentType type evidence for the values
+     * @param order Ordering for ranking
+     */
+    @SuppressWarnings("unchecked")
+    public Rank(Collection<T> values, Class<T> componentType, Comparator<? super T> order) {
+        super();
+        Object array = Array.newInstance(componentType, values.size());
+        this.values = values.toArray((T[]) array);
+        this.order = order;
+    }
+
+    /**
+     * Create a new instance of <code>Rank</code> for the first
+     * <code>count</code> values in a a given iterator of <code>values</code>
+     * and a given <code>order</code>. The <code>values</code> are copied into
+     * an internal array before they are manipulated.
+     *
+     * @param values values for ranking. Duplicates are <em>not allowed</em>.
+     * @param componentType type evidence for the values
+     * @param count Number of items to include. -1 for all.
+     * @param order Ordering for ranking
+     */
+    @SuppressWarnings("unchecked")
+    public Rank(Iterator<T> values, Class<T> componentType, int count, Comparator<? super T> order) {
+        super();
+        this.order = order;
+
+        if (count >= 0) {
+            this.values = (T[]) Array.newInstance(componentType, count);
+            for (int k = 0; k < count; k++) {
+                this.values[k] = values.next();
+            }
+        }
+        else {
+            List<T> l = new LinkedList<T>();
+            while (values.hasNext()) {
+                l.add(values.next());
+            }
+            Object array = Array.newInstance(componentType, l.size());
+            this.values = l.toArray((T[]) array);
+        }
+    }
+
+    /**
+     * Create a new instance of <code>Rank</code> for a given array of
+     * <code>values</code>. The order is determined by the natural ordering of
+     * the values (i.e. through {@link Comparable}). The <code>values</code> are
+     * manipulated in place, no copying is performed.
+     *
+     * @param <S> extends Comparable&lt;S>
+     * @param values values for ranking. Duplicates are <em>not allowed</em>.
+     * @return A new instance of <code>Rank</code>.
+     */
+    public static <S extends Comparable<S>> Rank<S> rank(S[] values) {
+        return new Rank<S>(values, Rank.<S>comparableComparator());
+    }
+
+    /**
+     * Create a new instance of <code>Rank</code> for a given collection of
+     * <code>values</code>. The order is determined by the natural ordering of
+     * the values (i.e. through {@link Comparable}). The <code>values</code> are
+     * copied into an internal array before they are manipulated.
+     *
+     * @param <S> extends Comparable&lt;S>
+     * @param values values for ranking. Duplicates are <em>not allowed</em>.
+     * @param componentType type evidence for the values
+     * @return A new instance of <code>Rank</code>.
+     */
+    public static <S extends Comparable<S>> Rank<S> rank(Collection<S> values, Class<S> componentType) {
+        return new Rank<S>(values, componentType, Rank.<S>comparableComparator());
+    }
+
+    /**
+     * Create a new instance of <code>Rank</code> for the first
+     * <code>count</code> values in a a given iterator of <code>values</code>.
+     * The order is determined by the natural ordering of the values (i.e.
+     * through {@link Comparable}). The <code>values</code> are copied into an
+     * internal array before they are manipulated.
+     *
+     * @param <S> extends Comparable&lt;S>
+     * @param values values for ranking. Duplicates are <em>not allowed</em>.
+     * @param componentType type evidence for the values
+     * @param count Number of items to include. -1 for all.
+     * @return A new instance of <code>Rank</code>.
+     */
+    public static <S extends Comparable<S>> Rank<S> rank(Iterator<S> values, Class<S> componentType, int count) {
+        return new Rank<S>(values, componentType, count, Rank.<S>comparableComparator());
+    }
+
+    /**
+     * Utility method for creating a {@link Comparator} of <code>T</code> from a
+     * {@link Comparable} of type <code>T</code>.
+     *
+     * @param <T> extends Comparable&lt;T>
+     * @return Comparator whose order is defined by <code>T</code>.
+     */
+    public static <T extends Comparable<T>> Comparator<T> comparableComparator() {
+        return new Comparator<T>() {
+            public int compare(T c1, T c2) {
+                return c1.compareTo(c2);
+            }
+        };
+    }
+
+    public Comparator<? super T> getOrder() {
+        return order;
+    }
+
+    /**
+     * Returns the <code>n</code>-th smallest values remaining in this
+     * <code>Rank</code>.
+     *
+     * @param n Number of values to return
+     * @return An iterator containing the next <code>n</code> smallest values.
+     * @throws NoSuchElementException if this <code>Rank</code> has not enough
+     *             remaining elements or when <code>n</code> is negative.
+     */
+    public Iterator<T> take(int n) {
+        if (n < 0 || n + first > values.length) {
+            throw new NoSuchElementException();
+        }
+
+        if (n > 0) {
+            take(n, first, values.length - 1);
+            first += n;
+            return arrayIterator(values, first - n, first);
+        }
+        else {
+            return empty();
+        }
+    }
+
+    /**
+     * Returns the number of remaining items in the <code>Rank</code>.
+     *
+     * @return number of remaining items.
+     */
+    public int size() {
+        return values.length - first;
+    }
+
+    // -----------------------------------------------------< internal >---
+
+    /**
+     * Rearrange {@link #values} such that each of the <code>n</code> first
+     * values starting at <code>from</code> is smaller that all the remaining
+     * items up to <code>to</code>.
+     */
+    private void take(int n, int from, int to) {
+        // Shortcut for all values
+        if (n >= to - from + 1) {
+            return;
+        }
+
+        // Choosing the n-th value as pivot results in correct partitioning after one pass
+        // for already ordered values.
+        int pivot = from + n - 1;
+        int lo = from;
+        int hi = to;
+
+        // Partition values around pivot
+        while (lo < hi) {
+            // Find values to swap around the pivot
+            while (order.compare(values[lo], values[pivot]) < 0) lo++;
+            while (order.compare(values[hi], values[pivot]) > 0) hi--;
+            if (lo < hi) {
+                // Swap values and keep track of pivot position in case the pivot itself is swapped
+                if (lo == pivot) pivot = hi;
+                else if (hi == pivot) pivot = lo;
+                swap(lo, hi);
+                lo++;
+                hi--;
+            }
+        }
+
+        // Actual number of values taken
+        int nn = pivot + 1 - from;
+        if (nn > n) {      // Recurse: take first n elements from first partition
+            take(n, from, pivot);
+        }
+        else if (nn < n) { // Recurse: take first n - nn elements from second partition
+            take(n - nn, pivot + 1, to);
+        }
+        // else done
+    }
+
+    private void swap(int lo, int hi) {
+        T t1 = values[lo];
+        T t2 = values[hi];
+        if (order.compare(t1, t2) == 0) {
+            throw new IllegalStateException("Detected duplicates " + t1);
+        }
+        values[lo] = t2;
+        values[hi] = t1;
+    }
+
+    @SuppressWarnings("unchecked")
+    private static <T> Iterator<T> arrayIterator(T[] values, int from, int to) {
+        return new ArrayIterator(values, from, to);
+    }
+
+    @SuppressWarnings("unchecked")
+    private Iterator<T> empty() {
+        return EmptyIterator.INSTANCE;
+    }
+
+}

Added: jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/Sequence.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/Sequence.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/Sequence.java (added)
+++ jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/Sequence.java Mon Aug  2 16:56:10 2010
@@ -0,0 +1,66 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package org.apache.jackrabbit.flat;
+
+import javax.jcr.AccessDeniedException;
+import javax.jcr.Item;
+import javax.jcr.ItemNotFoundException;
+import javax.jcr.PathNotFoundException;
+import javax.jcr.RepositoryException;
+
+import java.util.Iterator;
+
+/**
+ * Interface for accessing JCR {@link Item}s sequentially through an
+ * {@link Iterator} or looking them up through a <code>key</code>.
+ *
+ * @param <T> extends &lt;Item>
+ */
+public interface Sequence<T extends Item> extends Iterable<T> {
+
+    /**
+     * Iterator for the {@link Item}s in this sequence. The order of the items
+     * is implementation specific.
+     *
+     * @see java.lang.Iterable#iterator()
+     */
+    Iterator<T> iterator();
+
+    /**
+     * Retrieve an {@link Item} from this sequence by its <code>key</code>. If
+     * the sequence does not contain the <code>key</code> this method throws an
+     * {@link ItemNotFoundException}.
+     *
+     * @param key The <code>key</code> of the item to retrieve. Must not be
+     *            <code>null</code>.
+     * @return The item belonging to <code>key</code>.
+     * @throws ItemNotFoundException
+     * @throws RepositoryException
+     */
+    T getItem(String key) throws AccessDeniedException, PathNotFoundException, ItemNotFoundException,
+            RepositoryException;
+
+    /**
+     * Determine whether this sequence contains a specific <code>key</code>.
+     *
+     * @param key The <code>key</code> to look up.
+     * @return <code>true</code> if this sequence contains <code>key</code>.
+     *         <code>False</code> otherwise.
+     * @throws RepositoryException
+     */
+    boolean hasItem(String key) throws RepositoryException;
+}
\ No newline at end of file

Added: jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/SizedIterator.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/SizedIterator.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/SizedIterator.java (added)
+++ jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/SizedIterator.java Mon Aug  2 16:56:10 2010
@@ -0,0 +1,35 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package org.apache.jackrabbit.flat;
+
+import java.util.Iterator;
+
+/**
+ * <code>SizedIterator</code> extends {@link Iterator} with a
+ * <code>getSize</code> method.
+ *
+ * @param <T> the type of elements of this iterator
+ */
+public interface SizedIterator<T> extends Iterator<T> {
+
+    /**
+     * The number of elements of this iterator or -1 if not known.
+     *
+     * @return number of elements.
+     */
+    long getSize();
+}



Mime
View raw message