You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jackrabbit.apache.org by md...@apache.org on 2010/08/02 18:56:11 UTC
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...
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<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);
+ }
+ }
+ }
+
+}