jackrabbit-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mdue...@apache.org
Subject svn commit: r981597 [2/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
Added: jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/TreeManager.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/TreeManager.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/TreeManager.java
(added)
+++ jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/TreeManager.java
Mon Aug  2 16:56:10 2010
@@ -0,0 +1,150 @@
+/*
+ * 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.Property;
+import javax.jcr.RepositoryException;
+
+import java.util.Comparator;
+
+/**
+ * TreeManager instances are responsible for the mapping between sequence views
+ * of {@link Node}s and {@link Property}s and an hierarchical JCR
+ * representation. They are passed to the various factory methods in
+ * {@link ItemSequence} to parameterize the behavior of {@link NodeSequence}s
+ * and {@link PropertySequence}s.
+ *
+ * @see NodeSequence
+ * @see PropertySequence
+ */
+public interface TreeManager {
+
+    /**
+     * @return the root node of the JCR sub-tree where the items of the sequence
+     *         are be mapped to.
+     */
+    Node getRoot();
+
+    /**
+     * Determined whether the given <code>node</code> is the root node of the
+     * JCR sub-tree.
+     *
+     * @param node Node to test for root
+     * @return <code>getRoot().isSame(node)</code>.
+     * @throws RepositoryException
+     */
+    boolean isRoot(Node node) throws RepositoryException;
+
+    /**
+     * Determines whether the given <code>node</code> is a leaf. Leaf nodes are
+     * the nodes which are actually part of a {@link NodeSequence} or the
+     * parents of the properties of a {@link PropertySequence}.
+     *
+     * @param node Node to test for leaf
+     * @return <code>true</code> if <code>node</code> is a leaf node,
+     *         <code>false</code> otherwise.
+     * @throws RepositoryException
+     */
+    boolean isLeaf(Node node) throws RepositoryException;
+
+    /**
+     * {@link Comparator} used for establishing the order of the keys in the
+     * sequence.
+     *
+     * @return a <code>Comparator&lt;String></code> instance
+     */
+    Comparator<String> getOrder();
+
+    /**
+     * After the node <code>cause</code> has been inserted into the sequence
+     * <code>itemSequence</code>, the implementation of this method may decide
+     * to split the parent <code>node</code> of <code>cause</code>
into two or
+     * more new nodes. Splitting must be done such that the overall order of the
+     * keys in this sequence obeys the order given by {@link #getOrder()} as
+     * much as possible.
+     *
+     * @param itemSequence the {@link ItemSequence} where the new node
+     *            <code>cause</code> has been inserted.
+     * @param node the parent node of the newly inserted node
+     * @param cause the newly inserted node or <code>null</code> if not known.
+     * @throws RepositoryException
+     */
+    void split(ItemSequence itemSequence, Node node, Node cause) throws RepositoryException;
+
+    /**
+     * After the property <code>cause</code> has been inserted into the sequence
+     * <code>itemSequence</code>, the implementation of this method may decide
+     * to split the parent <code>node</code> of <code>cause</code>
into two or
+     * more new nodes. Splitting must be done such that the overall order of the
+     * keys in this sequence obeys the order given by {@link #getOrder()} as
+     * much as possible.
+     *
+     * @param itemSequence the {@link ItemSequence} where the new property
+     *            <code>cause</code> has been inserted.
+     * @param node the parent node of the newly inserted property
+     * @param cause the newly inserted property or <code>null</code> if not
+     *            known.
+     * @throws RepositoryException
+     */
+    void split(ItemSequence itemSequence, Node node, Property cause) throws RepositoryException;
+
+    /**
+     * After the node <code>cause</code> has been deleted from the sequence
+     * <code>itemSequence</code>, the implementation of this method may decide
+     * to join the parent <code>node</code> of <code>cause</code>
with some
+     * other nodes. Joining must be done such that the overall order of the keys
+     * in this sequence obeys the order given by {@link #getOrder()} as much as
+     * possible.
+     *
+     * @param itemSequence the {@link ItemSequence} where the node
+     *            <code>cause</code> has been deleted from.
+     * @param node the parent node from which <code>cause</code> has been
+     *            deleted.
+     * @param cause the deleted node or <code>null</code> if not known.
+     *            <em>Note:</em> <code>cause</code> might be stale.
+     * @throws RepositoryException
+     */
+    void join(ItemSequence itemSequence, Node node, Node cause) throws RepositoryException;
+
+    /**
+     * After the property <code>cause</code> has been deleted from the sequence
+     * <code>itemSequence</code>, the implementation of this method may decide
+     * to join the parent <code>node</code> of <code>cause</code>
with some
+     * other nodes. Joining must be done such that the overall order of the keys
+     * in this sequence obeys the order given by {@link #getOrder()} as much as
+     * possible.
+     *
+     * @param itemSequence the {@link ItemSequence} where the property
+     *            <code>cause</code> has been deleted from.
+     * @param node the parent node from which <code>cause</code> has been
+     *            deleted.
+     * @param cause the deleted property or <code>null</code> if not known.
+     *            <em>Note:</em> <code>cause</code> might be stale.
+     * @throws RepositoryException
+     */
+    void join(ItemSequence itemSequence, Node node, Property cause) throws RepositoryException;
+
+    /**
+     * Whether to automatically save changes of the current session occurring
+     * from adding/removing nodes and properties.
+     *
+     * @return <code>true</code> if changes should be automatically saved,
+     *         <code>false</code> otherwiese.
+     */
+    boolean getAutoSave();
+}

Added: jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/TreeTraverser.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/TreeTraverser.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/TreeTraverser.java
(added)
+++ jackrabbit/trunk/jackrabbit-jcr-commons/src/main/java/org/apache/jackrabbit/flat/TreeTraverser.java
Mon Aug  2 16:56:10 2010
@@ -0,0 +1,391 @@
+/*
+ * 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.EmptyIterator;
+import org.apache.commons.collections.iterators.IteratorChain;
+import org.apache.commons.collections.iterators.SingletonIterator;
+
+import javax.jcr.Item;
+import javax.jcr.Node;
+import javax.jcr.NodeIterator;
+import javax.jcr.Property;
+import javax.jcr.RepositoryException;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * <p>
+ * Utility class for traversing the {@link Item}s of a JCR hierarchy rooted at a
+ * specific {@link Node}.
+ * </p>
+ *
+ * <p>
+ * This class provides an {@link Iterator} of JCR items either through its
+ * implementation of {@link Iterable} or through various static factory methods.
+ * The iterators return its elements in pre-order. That is, each node occurs
+ * before its child nodes are traversed. The order in which child nodes are
+ * traversed is determined by the underlying JCR implementation. Generally the
+ * order is not specified unless a {@link Node} has orderable child nodes.
+ * </p>
+ *
+ * <p>
+ * Whether a specific node is included is determined by an
+ * {@link #InclusionPolicy}. Error occurring while traversing are delegated to
+ * an {@link #ErrorHandler}.
+ * </p>
+ */
+public final class TreeTraverser implements Iterable<Node> {
+    private final Node root;
+    private final ErrorHandler errorHandler;
+    private final InclusionPolicy inclusionPolicy;
+
+    /**
+     * Create a new instance of a TreeTraverser rooted at <code>node</code>.
+     *
+     * @param root The root node of the sub-tree to traverse
+     * @param errorHandler Handler for errors while traversing
+     * @param inclusionPolicy Inclusion policy to determine which nodes to
+     *            include
+     */
+    public TreeTraverser(Node root, ErrorHandler errorHandler, InclusionPolicy inclusionPolicy)
{
+        super();
+        this.root = root;
+        this.errorHandler = errorHandler == null? ErrorHandler.IGNORE : errorHandler;
+        this.inclusionPolicy = inclusionPolicy;
+    }
+
+    /**
+     * Create a new instance of a TreeTraverser rooted at <code>node</code>.
+     *
+     * @param root The root node of the sub-tree to traverse
+     */
+    public TreeTraverser(Node root) {
+        this(root, ErrorHandler.IGNORE, InclusionPolicy.ALL);
+    }
+
+    /**
+     * Error handler for handling {@link RepositoryException}s occurring on
+     * traversal. The predefined {@link #IGNORE} error handler can be used to
+     * ignore all exceptions.
+     */
+    public interface ErrorHandler {
+
+        /**
+         * Predefined error handler which ignores all exceptions.
+         */
+        public static ErrorHandler IGNORE = new ErrorHandler() {
+            public void call(Item item, RepositoryException exception) { /* ignore */ }
+        };
+
+        /**
+         * This call back method is called whenever an error occurs while
+         * traversing.
+         *
+         * @param item The item which was the target of an operation which
+         *            failed and caused the exception.
+         * @param exception The exception which occurred.
+         */
+        void call(Item item, RepositoryException exception);
+    }
+
+    /**
+     * Inclusion policy to determine which nodes to include when traversing.
+     * There a two predefined inclusion policies:
+     * <ul>
+     * <li>{@link #ALL} includes all nodes.</li>
+     * <li>{@link #LEAVES} includes only leave nodes. A leaf node is a node
+     * which does not have childe nodes.</li>
+     * </ul>
+     */
+    public interface InclusionPolicy {
+
+        /**
+         * This inclusions policy includes all nodes.
+         */
+        public static InclusionPolicy ALL = new InclusionPolicy() {
+            public boolean include(Node node) {
+                return true;
+            }
+        };
+
+        /**
+         * This inclusion policy only includes leave nodes. A leaf node is a
+         * node which does not have child nodes.
+         */
+        public static InclusionPolicy LEAVES = new InclusionPolicy() {
+            public boolean include(Node node) throws RepositoryException {
+                return !node.hasNodes();
+            }
+        };
+
+        /**
+         * Call back method to determine whether to include a given node.
+         *
+         * @param node The node under consideration
+         * @return <code>true</code> when <code>node</code> should
be included.
+         *         <code>false</code> otherwise.
+         *
+         * @throws RepositoryException
+         */
+        boolean include(Node node) throws RepositoryException;
+    }
+
+    /**
+     * Create an iterator for the nodes of the sub-tree rooted at
+     * <code>root</code>.
+     *
+     * @param root root node of the sub-tree to traverse
+     * @param errorHandler handler for exceptions occurring on traversal
+     * @param inclusionPolicy inclusion policy to determine which nodes to
+     *            include
+     * @return iterator of {@link Node}
+     */
+    public static Iterator<Node> nodeIterator(Node root, ErrorHandler errorHandler,
+            InclusionPolicy inclusionPolicy) {
+
+        return new TreeTraverser(root, errorHandler, inclusionPolicy).iterator();
+    }
+
+    /**
+     * Create an iterator for the nodes of the sub-tree rooted at
+     * <code>root</code>. Exceptions occurring on traversal are ignored.
+     *
+     * @param root root node of the sub-tree to traverse
+     * @return iterator of {@link Node}
+     */
+    public static Iterator<Node> nodeIterator(Node root) {
+        return nodeIterator(root, ErrorHandler.IGNORE, InclusionPolicy.ALL);
+    }
+
+    /**
+     * Create an iterator of the properties for a given iterator of nodes. The
+     * order of the returned properties is only specified so far that if node
+     * <code>n1</code> occurs before node <code>n2</code> in the
iterator of
+     * nodes, then any property of <code>n1</code> will occur before any
+     * property of <code>n2</code>.
+     *
+     * @param nodes nodes whose properties to chain
+     * @param errorHandler handler for exceptions occurring on traversal
+     * @return iterator of {@link Property}
+     */
+    public static Iterator<Property> propertyIterator(Iterator<Node> nodes, ErrorHandler
errorHandler) {
+        return chain(propertyIterators(nodes, errorHandler));
+    }
+
+    /**
+     * Create an iterator of the properties for a given iterator of nodes. The
+     * order of the returned properties is only specified so far that if node
+     * <code>n1</code> occurs before node <code>n2</code> in the
iterator of
+     * nodes, then any property of <code>n1</code> will occur before any
+     * property of <code>n2</code>. Exceptions occurring on traversal are
+     * ignored.
+     *
+     * @param nodes nodes whose properties to chain
+     * @return iterator of {@link Property}
+     */
+    public static Iterator<Property> propertyIterator(Iterator<Node> nodes) {
+        return propertyIterator(nodes, ErrorHandler.IGNORE);
+    }
+
+    /**
+     * Create an iterator of the properties of all nodes of the sub-tree rooted
+     * at <code>root</code>.
+     *
+     * @param root root node of the sub-tree to traverse
+     * @param errorHandler handler for exceptions occurring on traversal
+     * @param inclusionPolicy inclusion policy to determine which nodes to
+     *            include
+     * @return iterator of {@link Property}
+     */
+    public static Iterator<Property> propertyIterator(Node root, ErrorHandler errorHandler,
+            InclusionPolicy inclusionPolicy) {
+
+        return propertyIterator(nodeIterator(root, errorHandler, inclusionPolicy), errorHandler);
+    }
+
+    /**
+     * Create an iterator of the properties of all nodes of the sub-tree rooted
+     * at <code>root</code>. Exceptions occurring on traversal are ignored.
+     *
+     * @param root root node of the sub-tree to traverse
+     * @return iterator of {@link Property}
+     */
+    public static Iterator<Property> propertyIterator(Node root) {
+        return propertyIterator(root, ErrorHandler.IGNORE, InclusionPolicy.ALL);
+    }
+
+    /**
+     * Returns an iterator of {@link Node} for this instance.
+     *
+     * @see TreeTraverser#TreeTraverser(Node, ErrorHandler, InclusionPolicy)
+     * @see java.lang.Iterable#iterator()
+     */
+    public Iterator<Node> iterator() {
+        return iterator(root);
+    }
+
+    // -----------------------------------------------------< internal >---
+
+    /**
+     * Returns an iterator of the nodes of the sub-tree rooted at
+     * <code>node</code>.
+     */
+    private Iterator<Node> iterator(Node node) {
+        try {
+            if (inclusionPolicy.include(node)) {
+                return chain(singleton(node), childIterators(node));
+            }
+            else {
+                return chain(childIterators(node));
+            }
+        }
+        catch (RepositoryException e) {
+            errorHandler.call(node, e);
+            return empty();
+        }
+    }
+
+    /**
+     * Returns an iterator containing the single element <code>element</code>.
+     */
+    @SuppressWarnings("unchecked")
+    private static <T> Iterator<T> singleton(T element) {
+        return new SingletonIterator(element);
+    }
+
+    /**
+     * Returns an iterator of iterators of the child nodes of <code>node</code>.
+     */
+    private Iterator<Iterator<Node>> childIterators(final Node node) {
+        try {
+            return new Iterator<Iterator<Node>>() {
+                private final NodeIterator childNodes = node.getNodes();
+
+                public boolean hasNext() {
+                    return childNodes.hasNext();
+                }
+
+                public Iterator<Node> next() {
+                    return iterator(childNodes.nextNode());
+                }
+
+                public void remove() {
+                    throw new UnsupportedOperationException();
+                }
+            };
+        }
+        catch (RepositoryException e) {
+            errorHandler.call(node, e);
+            return empty();
+        }
+    }
+
+    /**
+     * Returns an iterator of all properties of all <code>nodes</code>. For node
+     * <code>n1</code> occurring before node <code>n2</code> in
+     * <code>nodes</code>, any property of <code>n1</code> will occur
before any
+     * property of <code>n2</code> in the iterator.
+     */
+    private static Iterator<Iterator<Property>> propertyIterators(final Iterator<Node>
nodes,
+            final ErrorHandler errorHandler) {
+
+        return new Iterator<Iterator<Property>>() {
+            public boolean hasNext() {
+                return nodes.hasNext();
+            }
+
+            @SuppressWarnings("unchecked")
+            public Iterator<Property> next() {
+                Node n = nodes.next();
+                try {
+                    return n.getProperties();
+                }
+                catch (RepositoryException e) {
+                    errorHandler.call(n, e);
+                    return empty();
+                }
+            }
+
+            public void remove() {
+                throw new UnsupportedOperationException();
+            }
+        };
+    }
+
+    /**
+     * Returns the concatenation of <code>iterator</code> with the concatenation
+     * of all iterators in <code>iterators</code>.
+     */
+    @SuppressWarnings("unchecked")
+    private static <T> Iterator<T> chain(Iterator<T> iterator, Iterator<Iterator<T>>
iterators) {
+        return new IteratorChain(iterator, new LazyIteratorChain<T>(iterators));
+    }
+
+    /**
+     * Returns the concatenation of all iterators in <code>iterators</code>.
+     */
+    private static <T> Iterator<T> chain(Iterator<Iterator<T>> iterators)
{
+        return new LazyIteratorChain<T>(iterators);
+    }
+
+    /**
+     * Returns an empty iterator.
+     */
+    @SuppressWarnings("unchecked")
+    private static <T> Iterator<T> empty() {
+        return EmptyIterator.INSTANCE;
+    }
+
+    /**
+     * The class implements the concatenation of iterators. The implementation
+     * is lazy in the sense that advancing off all iterators is deferred as much
+     * as possible. Specifically no iterator is fully unwrapped at one single
+     * point of time.
+     */
+    private static final class LazyIteratorChain<T> implements Iterator<T> {
+        private final Iterator<Iterator<T>> iterators;
+        private Iterator<T> currentIterator;
+
+        private LazyIteratorChain(Iterator<Iterator<T>> iterators) {
+            super();
+            this.iterators = iterators;
+        }
+
+        public boolean hasNext() {
+            while ((currentIterator == null || !currentIterator.hasNext()) && iterators.hasNext())
{
+                currentIterator = iterators.next();
+            }
+            return currentIterator != null && currentIterator.hasNext();
+        }
+
+        public T next() {
+            if (hasNext()) {
+                return currentIterator.next();
+            }
+            else {
+                throw new NoSuchElementException();
+            }
+        }
+
+        public void remove() {
+            throw new UnsupportedOperationException();
+        }
+    }
+
+}

Added: jackrabbit/trunk/jackrabbit-jcr-commons/src/test/java/flat/RankTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/trunk/jackrabbit-jcr-commons/src/test/java/flat/RankTest.java?rev=981597&view=auto
==============================================================================
--- jackrabbit/trunk/jackrabbit-jcr-commons/src/test/java/flat/RankTest.java (added)
+++ jackrabbit/trunk/jackrabbit-jcr-commons/src/test/java/flat/RankTest.java Mon Aug  2 16:56:10
2010
@@ -0,0 +1,185 @@
+/*
+ * 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 flat;
+
+import org.apache.jackrabbit.flat.Rank;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Random;
+import java.util.Set;
+
+import junit.framework.TestCase;
+
+public class RankTest extends TestCase {
+    private static final Random rnd = new Random();
+
+    public void testEmpty() {
+        Rank<Integer> r = Rank.rank(new Integer[0]);
+        assertFalse(r.take(0).hasNext());
+        assertEquals(0, r.size());
+        try {
+            r.take(1);
+            fail("Excpeted " + NoSuchElementException.class.getName());
+        }
+        catch (NoSuchElementException ignore) { }
+    }
+
+    public void testSingleton() {
+        Rank<Integer> r = Rank.rank(new Integer[] {42});
+        assertFalse(r.take(0).hasNext());
+        assertEquals(1, r.size());
+
+        Iterator<Integer> it = r.take(1);
+        assertTrue(it.hasNext());
+        assertEquals(0, r.size());
+        assertEquals(42, it.next().intValue());
+
+        assertFalse(r.take(0).hasNext());
+
+        try {
+            r.take(1);
+            fail("Excpeted " + NoSuchElementException.class.getName());
+        }
+        catch (NoSuchElementException ignore) { }
+    }
+
+    public void testRank() {
+        for (int n = 1; n <= 2000; n++) {
+            testRank(n);
+        }
+    }
+
+    public void testGetAll() {
+        int n = 100;
+        List<Integer> values = createValues(n);
+        Rank<Integer> r = Rank.rank(values, Integer.class);
+
+        try {
+            r.take(n + 1);
+            fail("Excpeted " + NoSuchElementException.class.getName());
+        }
+        catch (NoSuchElementException ignore) { }
+
+        assertEquals(n, r.size());
+
+        Iterator<Integer> it = r.take(n);
+        while (it.hasNext()) {
+            assertTrue(values.remove(it.next()));
+        }
+
+        assertTrue(values.isEmpty());
+        assertEquals(0, r.size());
+    }
+
+    public void testGetSingles() {
+        int n = 100;
+        List<Integer> values = createValues(n);
+        Rank<Integer> r = Rank.rank(values, Integer.class);
+
+        List<Integer> sorted = new ArrayList<Integer>();
+        Iterator<Integer> it;
+        while (r.size() > 0) {
+            it = r.take(1);
+            sorted.add(it.next());
+            assertFalse(it.hasNext());
+        }
+
+        assertTrue(sorted.containsAll(values));
+        assertTrue(values.containsAll(sorted));
+
+        Comparator<? super Integer> order = r.getOrder();
+        checkOrdered(sorted.iterator(), order);
+    }
+
+    public void testOrdered() {
+        int n = 1000000;
+        Integer[] values = new Integer[n];
+        for (int k = 0; k < n; k++) {
+            values[k] = k;
+        }
+
+        Rank<Integer> r = Rank.rank(values);
+        while (r.size() > 0) {
+            int k = Math.min(rnd.nextInt(n/10), r.size());
+            checkOrdered(r.take(k), r.getOrder());
+        }
+    }
+
+    // -----------------------------------------------------< internal >---
+
+    private static List<Integer> createValues(int count) {
+        Set<Integer> ints = new HashSet<Integer>();
+        for (int k = 0; k < count; k++) {
+            ints.add(rnd.nextInt());
+        }
+
+        List<Integer> intList = new LinkedList<Integer>(ints);
+        Collections.shuffle(intList);
+        return intList;
+    }
+
+    private <T> void checkOrdered(Iterator<T> it, Comparator<? super T>
order) {
+        T prev = it.next();
+        while (it.hasNext()) {
+            T next = it.next();
+            assertTrue(order.compare(prev, next) < 0);
+            prev = next;
+        }
+    }
+
+    private static void testRank(int count) {
+        List<Integer> ints = createValues(count);
+        Rank<Integer> r = Rank.rank(ints, Integer.class);
+        Set<Integer> all = new HashSet<Integer>(ints);
+        Set<Integer> previous = new HashSet<Integer>();
+        while (r.size() > 0) {
+            int n = Math.min(rnd.nextInt(count + 1), r.size());
+            Iterator<Integer> it = r.take(n);
+            Set<Integer> actual = new HashSet<Integer>();
+            while (it.hasNext()) {
+                Integer i = it.next();
+                assertTrue(actual.add(i));
+                assertTrue(all.remove(i));
+            }
+
+            checkOrdering(previous, actual, r.getOrder());
+            previous = actual;
+        }
+
+        assertTrue(all.isEmpty());
+    }
+
+    private static void checkOrdering(Set<Integer> previous, Set<Integer> actual,
+            Comparator<? super Integer> order) {
+
+        for (Iterator<Integer> pIt = previous.iterator(); pIt.hasNext(); ) {
+            Integer p = pIt.next();
+            for(Iterator<Integer> aIt = actual.iterator(); aIt.hasNext(); ) {
+                Integer a = aIt.next();
+                assertTrue(order.compare(p, a) < 0);
+            }
+        }
+    }
+
+}



Mime
View raw message