activemq-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From chir...@apache.org
Subject svn commit: r778993 - in /activemq/sandbox/activemq-flow: ./ src/main/java/org/apache/activemq/broker/store/ src/main/java/org/apache/activemq/broker/store/kahadb/ src/main/java/org/apache/activemq/broker/store/memory/ src/main/java/org/apache/activemq...
Date Wed, 27 May 2009 04:38:38 GMT
Author: chirino
Date: Wed May 27 04:38:37 2009
New Revision: 778993

URL: http://svn.apache.org/viewvc?rev=778993&view=rev
Log:
Applying patch at https://issues.apache.org/activemq/browse/AMQ-2267
Thx Colin!


Added:
    activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/Comparators.java
    activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/TreeMap.java
    activemq/sandbox/activemq-flow/src/test/java/org/apache/activemq/util/
    activemq/sandbox/activemq-flow/src/test/java/org/apache/activemq/util/TreeMapTest.java
Modified:
    activemq/sandbox/activemq-flow/pom.xml
    activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/BrokerDatabase.java
    activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/kahadb/RootEntity.java
    activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/memory/MemoryStore.java
    activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/queue/CursoredQueue.java
    activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/SortedLinkedList.java
    activemq/sandbox/activemq-flow/src/test/java/org/apache/activemq/broker/SharedQueuePerfTest.java

Modified: activemq/sandbox/activemq-flow/pom.xml
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-flow/pom.xml?rev=778993&r1=778992&r2=778993&view=diff
==============================================================================
--- activemq/sandbox/activemq-flow/pom.xml (original)
+++ activemq/sandbox/activemq-flow/pom.xml Wed May 27 04:38:37 2009
@@ -107,8 +107,8 @@
         <groupId>org.apache.maven.plugins</groupId>
         <artifactId>maven-compiler-plugin</artifactId>
         <configuration>
-          <source>1.6</source>
-          <target>1.6</target>
+          <source>1.5</source>
+          <target>1.5</target>
         </configuration>
       </plugin>
 

Modified: activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/BrokerDatabase.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/BrokerDatabase.java?rev=778993&r1=778992&r2=778993&view=diff
==============================================================================
--- activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/BrokerDatabase.java (original)
+++ activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/BrokerDatabase.java Wed May 27 04:38:37 2009
@@ -384,12 +384,16 @@
                     for (Operation processed : processedQueue) {
                         processed.onRollback(e);
                     }
-                    onDatabaseException(new IOException(e));
+                    IOException ioe = new IOException(e.getMessage());
+                    ioe.initCause(e);
+                    onDatabaseException(ioe);
                 } catch (Exception e) {
                     for (Operation processed : processedQueue) {
                         processed.onRollback(e);
                     }
-                    onDatabaseException(new IOException(e));
+                    IOException ioe = new IOException(e.getMessage());
+                    ioe.initCause(e);
+                    onDatabaseException(ioe);
                 }
             }
         }
@@ -611,7 +615,7 @@
      * This is a convenience base class that can be used to implement
      * Operations. It handles operation cancellation for you.
      */
-    private abstract class OperationBase extends LinkedNode<OperationBase> implements Operation {
+    abstract class OperationBase extends LinkedNode<OperationBase> implements Operation {
         public boolean flushRequested = false;
         public long opSequenceNumber = -1;
 

Modified: activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/kahadb/RootEntity.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/kahadb/RootEntity.java?rev=778993&r1=778992&r2=778993&view=diff
==============================================================================
--- activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/kahadb/RootEntity.java (original)
+++ activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/kahadb/RootEntity.java Wed May 27 04:38:37 2009
@@ -159,7 +159,9 @@
         try {
             constructQueueHierarchy();
         } catch (KeyNotFoundException e) {
-            throw new IOException("Inconsistent store", e);
+            IOException ioe = new IOException("Inconsistent store");
+            ioe.initCause(e);
+            throw ioe;
         }
     }
 

Modified: activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/memory/MemoryStore.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/memory/MemoryStore.java?rev=778993&r1=778992&r2=778993&view=diff
==============================================================================
--- activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/memory/MemoryStore.java (original)
+++ activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/broker/store/memory/MemoryStore.java Wed May 27 04:38:37 2009
@@ -18,6 +18,7 @@
 
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
@@ -33,6 +34,7 @@
 import org.apache.activemq.queue.QueueStore;
 import org.apache.activemq.util.ByteArrayOutputStream;
 import org.apache.activemq.util.ByteSequence;
+import org.apache.activemq.util.Comparators;
 
 /**
  * An in memory implementation of the {@link QueueStore} interface. It does not
@@ -89,7 +91,7 @@
     static private class StoredQueue {
         QueueStore.QueueDescriptor descriptor;
 
-        TreeMap<Long, QueueRecord> records = new TreeMap<Long, QueueRecord>();
+        TreeMap<Long, QueueRecord> records = new TreeMap<Long, QueueRecord>(Comparators.LONG_COMPARATOR);
         // Maps tracking to sequence number:
         HashMap<Long, Long> trackingMap = new HashMap<Long, Long>();
         int count = 0;
@@ -197,8 +199,8 @@
             QueueQueryResultImpl result = new QueueQueryResultImpl();
             result.count = count;
             result.size = size;
-            result.firstSequence = records.isEmpty() ? 0 : records.firstEntry().getValue().getQueueKey();
-            result.lastSequence = records.isEmpty() ? 0 : records.lastEntry().getValue().getQueueKey();
+            result.firstSequence = records.isEmpty() ? 0 : records.get(records.firstKey()).getQueueKey();
+            result.lastSequence = records.isEmpty() ? 0 :  records.get(records.lastKey()).getQueueKey();
             result.desc = descriptor.copy();
             if (this.partitions != null) {
                 ArrayList<QueueQueryResult> childResults = new ArrayList<QueueQueryResult>(partitions.size());
@@ -300,7 +302,7 @@
         private HashMap<Long, MessageRecordHolder> messages = new HashMap<Long, MessageRecordHolder>();
 
         private TreeMap<AsciiBuffer, TreeMap<AsciiBuffer, Buffer>> maps = new TreeMap<AsciiBuffer, TreeMap<AsciiBuffer, Buffer>>();
-        private TreeMap<Long, Stream> streams = new TreeMap<Long, Stream>();
+        private TreeMap<Long, Stream> streams = new TreeMap<Long, Stream>(Comparators.LONG_COMPARATOR);
         private TreeMap<AsciiBuffer, StoredQueue> queues = new TreeMap<AsciiBuffer, StoredQueue>();
         private TreeMap<Buffer, Transaction> transactions = new TreeMap<Buffer, Transaction>();
 

Modified: activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/queue/CursoredQueue.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/queue/CursoredQueue.java?rev=778993&r1=778992&r2=778993&view=diff
==============================================================================
--- activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/queue/CursoredQueue.java (original)
+++ activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/queue/CursoredQueue.java Wed May 27 04:38:37 2009
@@ -17,11 +17,11 @@
 package org.apache.activemq.queue;
 
 import java.util.Collection;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedList;
-import java.util.TreeMap;
 import java.util.Map.Entry;
 
 import org.apache.activemq.flow.Flow;
@@ -33,9 +33,11 @@
 import org.apache.activemq.queue.QueueStore.RestoredElement;
 import org.apache.activemq.queue.QueueStore.SaveableQueueElement;
 import org.apache.activemq.queue.Subscription.SubscriptionDeliveryCallback;
+import org.apache.activemq.util.Comparators;
 import org.apache.activemq.util.Mapper;
 import org.apache.activemq.util.SortedLinkedList;
 import org.apache.activemq.util.SortedLinkedListNode;
+import org.apache.activemq.util.TreeMap;
 
 /**
  * @author cmacnaug
@@ -61,7 +63,7 @@
     private final ElementLoader loader;
     public final QueueDescriptor queueDescriptor;
     private final Object mutex;
-
+    
     public CursoredQueue(PersistencePolicy<V> persistencePolicy, Mapper<Long, V> expirationMapper, Flow flow, QueueDescriptor queueDescriptor, QueueStore<?, V> store, Object mutex) {
         this.persistencePolicy = persistencePolicy;
         this.mutex = mutex;
@@ -1114,7 +1116,7 @@
 
         private static final int MAX_CACHE_SIZE = 500;
         private long uncachedMin = Long.MAX_VALUE;
-        TreeMap<Long, HashSet<QueueElement<V>>> expirationCache = new TreeMap<Long, HashSet<QueueElement<V>>>();
+        TreeMap<Long, HashSet<QueueElement<V>>> expirationCache = new TreeMap<Long, HashSet<QueueElement<V>>>(Comparators.LONG_COMPARATOR);
         private int cacheSize = 0;
 
         public final boolean needsDispatch() {

Added: activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/Comparators.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/Comparators.java?rev=778993&view=auto
==============================================================================
--- activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/Comparators.java (added)
+++ activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/Comparators.java Wed May 27 04:38:37 2009
@@ -0,0 +1,37 @@
+/**
+ * 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.activemq.util;
+
+import java.util.Comparator;
+
+/**
+ * @author cmacnaug
+ * 
+ */
+public class Comparators {
+
+    public static final Comparator<Long> LONG_COMPARATOR = new Comparator<Long>() {
+        /*
+         * (non-Javadoc)
+         * 
+         * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
+         */
+        public int compare(Long o1, Long o2) {
+            return o1.compareTo(o2);
+        }
+    };
+}

Modified: activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/SortedLinkedList.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/SortedLinkedList.java?rev=778993&r1=778992&r2=778993&view=diff
==============================================================================
--- activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/SortedLinkedList.java (original)
+++ activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/SortedLinkedList.java Wed May 27 04:38:37 2009
@@ -17,7 +17,6 @@
 package org.apache.activemq.util;
 
 import java.util.ArrayList;
-import java.util.TreeMap;
 import java.util.Map.Entry;
 
 public class SortedLinkedList<T extends SortedLinkedListNode<T>> {
@@ -25,9 +24,9 @@
     protected final TreeMap<Long, T> index;
     T head;
     int size;
-
+   
     public SortedLinkedList() {
-        index = new TreeMap<Long, T>();
+        index = new TreeMap<Long, T>(Comparators.LONG_COMPARATOR);
     }
 
     public boolean isEmpty() {
@@ -152,5 +151,4 @@
         }
         return rc;
     }
-
 }

Added: activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/TreeMap.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/TreeMap.java?rev=778993&view=auto
==============================================================================
--- activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/TreeMap.java (added)
+++ activemq/sandbox/activemq-flow/src/main/java/org/apache/activemq/util/TreeMap.java Wed May 27 04:38:37 2009
@@ -0,0 +1,1048 @@
+/**
+ * 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.activemq.util;
+
+import java.util.AbstractCollection;
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+import java.util.Map.Entry;
+
+/**
+ * A TreeMap that is lighter weight than the Sun implementation with
+ * implementations for upper/lower/floor/ceiling accessors.
+ */
+public class TreeMap<K, V> {
+    private static final boolean RED = false;
+    private static final boolean BLACK = true;
+
+    private int count;
+    private TreeMapNode<K, V> root;
+    private final Comparator<? super K> comparator;
+
+    public TreeMap() {
+        this.comparator = null;
+    }
+
+    @SuppressWarnings("unchecked")
+    private int compare(K k1, K k2) {
+        if (comparator != null) {
+            return comparator.compare(k1, k2);
+        } else {
+            return ((Comparable<K>) k1).compareTo(k2);
+        }
+    }
+
+    public TreeMap(Comparator<? super K> comparator) {
+        this.comparator = comparator;
+    }
+
+    public Comparator<? super K> comparator() {
+        return comparator;
+    }
+
+    /**
+     * 
+     * @return The first key in the map.
+     */
+    public K firstKey() {
+        TreeMapNode<K, V> first = firstNode();
+        if (first != null) {
+            return first.key;
+        }
+        return null;
+    }
+
+    private TreeMapNode<K, V> firstNode() {
+        if (root == null) {
+            return null;
+        }
+        TreeMapNode<K, V> leftMost = root;
+        while (leftMost.left != null) {
+            leftMost = leftMost.left;
+        }
+
+        return leftMost;
+    }
+
+    /**
+     * @return The last key in the map.
+     */
+    public K lastKey() {
+        TreeMapNode<K, V> last = lastNode();
+        if (last != null) {
+            return last.key;
+        }
+        return null;
+    }
+
+    private TreeMapNode<K, V> lastNode() {
+        if (root == null) {
+            return null;
+        }
+        TreeMapNode<K, V> rightMost = root;
+        while (rightMost.right != null) {
+            rightMost = rightMost.left;
+        }
+
+        return rightMost;
+    }
+
+    /**
+     * Clears all elements in this map.
+     */
+    public void clear() {
+        //TODO possible assist gc here by scanning and removing refs?
+        //Will almost certain want to do this if we switch this over
+        //to allowing additions to be the entries themselves.
+        root = null;
+        count = 0;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see java.util.Map#containsKey(java.lang.Object)
+     */
+    public boolean containsKey(K key) {
+        return findInternal(key, root) != null;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see java.util.Map#containsValue(java.lang.Object)
+     */
+    public boolean containsValue(Object value) {
+        for (Map.Entry<K, V> entry : entrySet()) {
+            if (entry.getValue() == value) {
+                return true;
+            } else if (value != null && value.equals(entry)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see java.util.Map#entrySet()
+     */
+    public Set<Map.Entry<K, V>> entrySet() {
+        return new AbstractSet<Map.Entry<K, V>>() {
+
+            @Override
+            public Iterator<Entry<K, V>> iterator() {
+                return new EntryIterator();
+            }
+
+            @SuppressWarnings("unchecked")
+            @Override
+            public boolean contains(Object o) {
+                try {
+                    Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
+                    TreeMapNode<K, V> ours = findInternal(entry.getKey(), root);
+                    if (ours != null) {
+                        return ours.val == null ? entry.getValue() == null : ours.val.equals(entry.getValue());
+                    } else {
+                        return false;
+                    }
+                } catch (ClassCastException cce) {
+                    return false;
+                }
+            }
+
+            @SuppressWarnings("unchecked")
+            @Override
+            public boolean remove(Object o) {
+                return TreeMap.this.removeNode((TreeMapNode<K, V>) o) != null;
+            }
+
+            @Override
+            public int size() {
+                return count;
+            }
+
+            @Override
+            public void clear() {
+                TreeMap.this.clear();
+            }
+        };
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see java.util.Map#get(java.lang.Object)
+     */
+    public V get(K key) {
+        TreeMapNode<K, V> node = findInternal(key, root);
+        if (node != null) {
+            return node.val;
+        }
+        return null;
+    }
+
+    private final TreeMapNode<K, V> findInternal(K key, TreeMapNode<K, V> r) {
+        while (r != null) {
+            int c = compare(key, r.key);
+            if (c == 0) {
+                return r;
+            } else if (c > 0) {
+                r = r.right;
+            } else {
+                r = r.left;
+            }
+        }
+        return null;
+    }
+
+    /**
+     * Returns a key-value mapping associated with the least key in this map, or
+     * null if the map is empty.
+     * 
+     * @return The lowest key in the map
+     */
+    public Entry<K, V> firstEntry() {
+        TreeMapNode<K, V> r = root;
+        while (r != null) {
+            if (r.left == null) {
+                break;
+            }
+            r = r.left;
+        }
+
+        return r;
+    }
+
+    /**
+     * Returns a key-value mapping associated with the greatest key in this map,
+     * or null if the map is empty.
+     * 
+     * @return The entry associated with the greates key in the map.
+     */
+    public Entry<K, V> lastEntry() {
+        TreeMapNode<K, V> r = root;
+        while (r != null) {
+            if (r.right == null) {
+                break;
+            }
+            r = r.right;
+        }
+
+        return r;
+    }
+
+    /**
+     * Returns a key-value mapping associated with the greatest key strictly
+     * less than the given key, or null if there is no such key
+     * 
+     * @param key
+     *            the key.
+     * @return
+     */
+    public Entry<K, V> lowerEntry(K key) {
+        TreeMapNode<K, V> n = root;
+        TreeMapNode<K, V> l = null;
+        while (n != null) {
+            int c = compare(key, n.key);
+            if (c <= 0) {
+                n = n.left;
+            } else {
+                //Update the low node:
+                if (l == null || compare(n.key, l.key) > 0) {
+                    l = n;
+                }
+                //Now need to scan the right tree to see if there is
+                //a higher low value to consider:
+                if (n.right == null) {
+                    break;
+                }
+                n = n.right;
+            }
+        }
+        return l;
+    }
+
+    /**
+     * Returns a key-value mapping associated with the greatest key less than or
+     * equal to the given key, or null if there is no such key.
+     * 
+     * @param key
+     *            The key for which to search.
+     * @return a key-value mapping associated with the greatest key less than or
+     *         equal to the given key, or null if there is no such key.
+     */
+    public Entry<K, V> floorEntry(K key) {
+        TreeMapNode<K, V> n = root;
+        TreeMapNode<K, V> l = null;
+        while (n != null) {
+            int c = compare(key, n.key);
+            if (c == 0) {
+                return n;
+            }
+
+            if (c < 0) {
+                n = n.left;
+            } else {
+                //Update the low node:
+                if (l == null || compare(n.key, l.key) > 0) {
+                    l = n;
+                }
+                //Now need to scan the right tree to see if there is
+                //a higher low value to consider:
+                if (n.right == null) {
+                    break;
+                }
+                n = n.right;
+            }
+        }
+        return l;
+    }
+
+    /**
+     * Returns a key-value mapping associated with the lowest key strictly
+     * greater than the given key, or null if there is no such key
+     * 
+     * @param key
+     *            The key
+     * @return a key-value mapping associated with the lowest key strictly
+     *         greater than the given key
+     */
+    public Entry<K, V> upperEntry(K key) {
+        TreeMapNode<K, V> n = root;
+        TreeMapNode<K, V> h = null;
+        while (n != null) {
+            int c = compare(key, n.key);
+            if (c >= 0) {
+                n = n.right;
+            } else {
+                //Update the high node:
+                if (h == null || compare(n.key, h.key) < 0) {
+                    h = n;
+                }
+                //Now need to scan the left tree to see if there is
+                //a lower high value to consider:
+                if (n.left == null) {
+                    break;
+                }
+                n = n.left;
+            }
+        }
+        return h;
+    }
+
+    /**
+     * Returns a key-value mapping associated with the least key greater than or
+     * equal to the given key, or null if there is no such key.
+     * 
+     * @param key
+     * @return
+     */
+    public Entry<K, V> ceilingEntry(K key) {
+        TreeMapNode<K, V> n = root;
+        TreeMapNode<K, V> h = null;
+        while (n != null) {
+            int c = compare(key, n.key);
+            if (c == 0) {
+                return n;
+            }
+
+            if (c > 0) {
+                n = n.right;
+            } else {
+                //Update the high node:
+                if (h == null || compare(n.key, h.key) < 0) {
+                    h = n;
+                }
+                //Now need to scan the left tree to see if there is
+                //a lower high value to consider:
+                if (n.left == null) {
+                    break;
+                }
+                n = n.left;
+            }
+        }
+        return h;
+    }
+
+    protected final TreeMapNode<K, V> findNext(TreeMapNode<K, V> n) {
+        if (n == null)
+            return null;
+        else if (n.right != null) {
+            TreeMapNode<K, V> p = n.right;
+            while (p.left != null) {
+                p = p.left;
+            }
+            return p;
+        } else {
+            TreeMapNode<K, V> p = n.parent;
+            TreeMapNode<K, V> ch = n;
+            while (p != null && ch == p.right) {
+                ch = p;
+                p = p.parent;
+            }
+            return p;
+        }
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see java.util.Map#isEmpty()
+     */
+    public boolean isEmpty() {
+        return count == 0;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see java.util.Map#keySet()
+     */
+    public Set<K> keySet() {
+        return new AbstractSet<K>() {
+
+            @Override
+            public void clear() {
+                TreeMap.this.clear();
+            }
+
+            @SuppressWarnings("unchecked")
+            @Override
+            public boolean remove(Object o) {
+                return TreeMap.this.remove((K) o) != null;
+            }
+
+            @Override
+            public Iterator<K> iterator() {
+                return new KeyIterator();
+            }
+
+            @Override
+            public int size() {
+                return count;
+            }
+        };
+
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see java.util.Map#putAll(java.util.Map)
+     */
+    public void putAll(Map<? extends K, ? extends V> t) {
+        for (Map.Entry<? extends K, ? extends V> entry : t.entrySet()) {
+            put(entry.getKey(), entry.getValue());
+        }
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see java.util.Map#remove(java.lang.Object)
+     */
+    public V remove(K key) {
+        return removeNode(findInternal(key, root));
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see java.util.Map#put(java.lang.Object, java.lang.Object)
+     */
+    public V put(final K key, final V value) {
+
+        if (root == null) {
+            // map is empty
+            root = new TreeMapNode<K, V>(key, value, null, this);
+            count++;
+            return null;
+        }
+        TreeMapNode<K, V> n = root;
+
+        // add new mapping
+        while (true) {
+            int c = compare(key, n.key);
+
+            if (c == 0) {
+                V old = n.val;
+                n.val = value;
+                return old;
+            } else if (c < 0) {
+                if (n.left != null) {
+                    n = n.left;
+                } else {
+                    n.left = new TreeMapNode<K, V>(key, value, n, this);
+                    count++;
+                    doRedBlackInsert(n.left);
+                    return null;
+                }
+            } else { // c > 0
+                if (n.right != null) {
+                    n = n.right;
+                } else {
+                    n.right = new TreeMapNode<K, V>(key, value, n, this);
+                    count++;
+                    doRedBlackInsert(n.right);
+                    return null;
+                }
+            }
+        }
+    }
+
+    /**
+     * complicated red-black insert stuff. Based on apache commons BidiMap
+     * method:
+     * 
+     * @param n
+     *            the newly inserted node
+     */
+    private void doRedBlackInsert(final TreeMapNode<K, V> n) {
+        TreeMapNode<K, V> currentNode = n;
+        color(currentNode, RED);
+
+        while (currentNode != null && currentNode != root && isRed(currentNode.parent)) {
+            if (isLeftChild(parent(currentNode))) {
+                TreeMapNode<K, V> y = getRight(getGrandParent(currentNode));
+
+                if (isRed(y)) {
+                    color(parent(currentNode), BLACK);
+                    color(y, BLACK);
+                    color(getGrandParent(currentNode), RED);
+
+                    currentNode = getGrandParent(currentNode);
+                } else {
+                    if (isRightChild(currentNode)) {
+                        currentNode = parent(currentNode);
+
+                        rotateLeft(currentNode);
+                    }
+
+                    color(parent(currentNode), BLACK);
+                    color(getGrandParent(currentNode), RED);
+
+                    if (getGrandParent(currentNode) != null) {
+                        rotateRight(getGrandParent(currentNode));
+                    }
+                }
+            } else {
+
+                // just like clause above, except swap left for right
+                TreeMapNode<K, V> y = getLeft(getGrandParent(currentNode));
+
+                if (isRed(y)) {
+                    color(parent(currentNode), BLACK);
+                    color(y, BLACK);
+                    color(getGrandParent(currentNode), RED);
+
+                    currentNode = getGrandParent(currentNode);
+                } else {
+                    if (isLeftChild(currentNode)) {
+                        currentNode = parent(currentNode);
+
+                        rotateRight(currentNode);
+                    }
+
+                    color(parent(currentNode), BLACK);
+                    color(getGrandParent(currentNode), RED);
+
+                    if (getGrandParent(currentNode) != null) {
+                        rotateLeft(getGrandParent(currentNode));
+                    }
+                }
+            }
+        }
+
+        color(root, BLACK);
+    }
+
+    //Based on Apache common's TreeBidiMap
+    private void rotateLeft(TreeMapNode<K, V> n) {
+        TreeMapNode<K, V> r = n.right;
+        n.right = r.left;
+        if (r.left != null) {
+            r.left.parent = n;
+        }
+        r.parent = n.parent;
+        if (n.parent == null) {
+            root = r;
+        } else if (n.parent.left == n) {
+            n.parent.left = r;
+        } else {
+            n.parent.right = r;
+        }
+
+        r.left = n;
+        n.parent = r;
+    }
+
+    //Based on Apache common's TreeBidiMap    
+    private void rotateRight(TreeMapNode<K, V> n) {
+        TreeMapNode<K, V> l = n.left;
+        n.left = l.right;
+        if (l.right != null) {
+            l.right.parent = n;
+        }
+        l.parent = n.parent;
+        if (n.parent == null) {
+            root = l;
+        } else if (n.parent.right == n) {
+            n.parent.right = l;
+        } else {
+            n.parent.left = l;
+        }
+        l.right = n;
+        n.parent = l;
+    }
+
+    /**
+     * complicated red-black delete stuff. Based on Apache Common's TreeBidiMap
+     * 
+     * @param n
+     *            the node to be deleted
+     */
+    private final V removeNode(TreeMapNode<K, V> n) {
+        if (n == null) {
+            return null;
+        }
+
+        if (n.map != this) {
+            throw new IllegalStateException("Node not in list");
+        }
+
+        V old = n.val;
+
+        count--;
+
+        //if deleted node has both left and children, swap with
+        // the next greater node
+        if (n.left != null && n.right != null) {
+            TreeMapNode<K, V> next = findNext(n);
+            n.key = next.key;
+            n.val = next.val;
+            n = next;
+        }
+
+        TreeMapNode<K, V> replacement = n.left != null ? n.left : n.right;
+
+        if (replacement != null) {
+            replacement.parent = n.parent;
+
+            if (n.parent == null) {
+                root = replacement;
+            } else if (n == n.parent.left) {
+                n.parent.left = replacement;
+            } else {
+                n.parent.right = replacement;
+            }
+
+            n.left = null;
+            n.right = null;
+            n.parent = null;
+
+            if (isBlack(n)) {
+                doRedBlackDeleteFixup(replacement);
+            }
+        } else {
+
+            // replacement is null
+            if (n.parent == null) {
+                // empty tree
+                root = null;
+            } else {
+
+                // deleted node had no children
+                if (isBlack(n)) {
+                    doRedBlackDeleteFixup(n);
+                }
+
+                if (n.parent != null) {
+                    if (n == n.parent.left) {
+                        n.parent.left = null;
+                    } else {
+                        n.parent.right = null;
+                    }
+
+                    n.parent = null;
+                }
+            }
+        }
+        return old;
+    }
+
+    /**
+     * complicated red-black delete stuff. Based on Apache Commons TreeBidiMap.
+     * 
+     * @param replacementNode
+     *            the node being replaced
+     */
+    private void doRedBlackDeleteFixup(final TreeMapNode<K, V> replacementNode) {
+        TreeMapNode<K, V> currentNode = replacementNode;
+
+        while (currentNode != root && isBlack(currentNode)) {
+            if (isLeftChild(currentNode)) {
+                TreeMapNode<K, V> siblingNode = getRight(currentNode.parent);
+
+                if (isRed(siblingNode)) {
+                    color(siblingNode, BLACK);
+                    color(parent(currentNode), RED);
+                    rotateLeft(parent(currentNode));
+
+                    siblingNode = getRight(parent(currentNode));
+                }
+
+                if (isBlack(getLeft(siblingNode)) && isBlack(getRight(siblingNode))) {
+                    color(siblingNode, RED);
+
+                    currentNode = currentNode.parent;
+                } else {
+                    if (isBlack(getRight(siblingNode))) {
+                        color(getLeft(siblingNode), BLACK);
+                        color(siblingNode, RED);
+                        rotateRight(siblingNode);
+
+                        siblingNode = getRight(parent(currentNode));
+                    }
+
+                    color(siblingNode, getColor(parent(currentNode)));
+                    color(parent(currentNode), BLACK);
+                    color(getRight(siblingNode), BLACK);
+                    rotateLeft(parent(currentNode));
+
+                    currentNode = root;
+                }
+            } else {
+                TreeMapNode<K, V> siblingNode = getRight(currentNode);
+
+                if (isRed(siblingNode)) {
+                    color(siblingNode, BLACK);
+                    color(parent(currentNode), RED);
+                    rotateRight(parent(currentNode));
+
+                    siblingNode = getLeft(parent(currentNode));
+                }
+
+                if (isBlack(getRight(siblingNode)) && isBlack(getLeft(siblingNode))) {
+                    color(siblingNode, RED);
+
+                    currentNode = parent(currentNode);
+                } else {
+                    if (isBlack(getLeft(siblingNode))) {
+                        color(getRight(siblingNode), BLACK);
+                        color(siblingNode, RED);
+                        rotateLeft(siblingNode);
+
+                        siblingNode = getLeft(parent(currentNode));
+                    }
+
+                    color(siblingNode, getColor(parent(currentNode)));
+                    color(parent(currentNode), BLACK);
+                    color(getLeft(siblingNode), BLACK);
+                    rotateRight(parent(currentNode));
+
+                    currentNode = root;
+                }
+            }
+        }
+
+        color(currentNode, BLACK);
+    }
+
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see java.util.Map#size()
+     */
+    public int size() {
+        return count;
+    }
+
+    /*
+     * (non-Javadoc)
+     * 
+     * @see java.util.Map#values()
+     */
+    public Collection<V> values() {
+        return new AbstractCollection<V>() {
+
+            @Override
+            public Iterator<V> iterator() {
+                return new ValueIterator();
+            }
+
+            @Override
+            public int size() {
+                return count;
+            }
+        };
+    }
+
+    private static <K, V> TreeMapNode<K, V> parent(TreeMapNode<K, V> n) {
+        return (n == null ? null : n.parent);
+    }
+
+    private static <K, V> void color(TreeMapNode<K, V> n, boolean c) {
+        if (n != null)
+            n.color = c;
+    }
+
+    private static <K, V> boolean getColor(TreeMapNode<K, V> n) {
+        return (n == null ? BLACK : n.color);
+    }
+
+    /**
+     * get a node's left child. mind you, the node may not exist. no problem
+     * 
+     * @param node
+     *            the node (may be null) in question
+     */
+    private static <K, V> TreeMapNode<K, V> getLeft(TreeMapNode<K, V> n) {
+        return (n == null) ? null : n.left;
+    }
+
+    /**
+     * get a node's right child. mind you, the node may not exist. no problem
+     * 
+     * @param node
+     *            the node (may be null) in question
+     */
+    private static <K, V> TreeMapNode<K, V> getRight(TreeMapNode<K, V> n) {
+        return (n == null) ? null : n.right;
+    }
+
+    /**
+     * is the specified node red? if the node does not exist, no, it's black,
+     * thank you
+     * 
+     * @param node
+     *            the node (may be null) in question
+     */
+    private static <K, V> boolean isRed(TreeMapNode<K, V> n) {
+        return n == null ? false : n.color == RED;
+    }
+
+    /**
+     * is the specified black red? if the node does not exist, sure, it's black,
+     * thank you
+     * 
+     * @param node
+     *            the node (may be null) in question
+     */
+    private static <K, V> boolean isBlack(final TreeMapNode<K, V> n) {
+        return n == null ? true : n.color == BLACK;
+    }
+
+    /**
+     * is this node its parent's left child? mind you, the node, or its parent,
+     * may not exist. no problem. if the node doesn't exist ... it's its
+     * non-existent parent's left child. If the node does exist but has no
+     * parent ... no, we're not the non-existent parent's left child. Otherwise
+     * (both the specified node AND its parent exist), check.
+     * 
+     * @param node
+     *            the node (may be null) in question
+     */
+    private static <K, V> boolean isLeftChild(final TreeMapNode<K, V> node) {
+
+        return node == null ? true : (node.parent == null ? false : (node == node.parent.left));
+    }
+
+    /**
+     * is this node its parent's right child? mind you, the node, or its parent,
+     * may not exist. no problem. if the node doesn't exist ... it's its
+     * non-existent parent's right child. If the node does exist but has no
+     * parent ... no, we're not the non-existent parent's right child. Otherwise
+     * (both the specified node AND its parent exist), check.
+     * 
+     * @param node
+     *            the node (may be null) in question
+     * @param index
+     *            the KEY or VALUE int
+     */
+    private static <K, V> boolean isRightChild(final TreeMapNode<K, V> node) {
+        return node == null ? true : (node.parent == null ? false : (node == node.parent.right));
+
+    }
+
+    /**
+     * get a node's grandparent. mind you, the node, its parent, or its
+     * grandparent may not exist. no problem
+     * 
+     * @param node
+     *            the node (may be null) in question
+     */
+    private static <K, V> TreeMapNode<K, V> getGrandParent(final TreeMapNode<K, V> node) {
+        return parent(parent(node));
+    }
+
+    public static class TreeMapNode<K, V> implements Map.Entry<K, V> {
+        TreeMap<K, V> map;
+        V val;
+        K key;
+        boolean color = BLACK;
+
+        TreeMapNode<K, V> parent;
+        TreeMapNode<K, V> left;
+        TreeMapNode<K, V> right;
+
+        TreeMapNode(K key, V val, TreeMapNode<K, V> parent, TreeMap<K, V> map) {
+            this.key = key;
+            this.parent = parent;
+            this.val = val;
+            this.map = map;
+        }
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see java.util.Map.Entry#getKey()
+         */
+        public K getKey() {
+            return key;
+        }
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see java.util.Map.Entry#getValue()
+         */
+        public V getValue() {
+            return val;
+        }
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see java.util.Map.Entry#setValue(java.lang.Object)
+         */
+        public V setValue(V val) {
+            V old = this.val;
+            this.val = val;
+            return old;
+        }
+
+        @SuppressWarnings("unchecked")
+        public boolean equals(Object o) {
+            if (!(o instanceof Map.Entry))
+                return false;
+            Map.Entry e = (Map.Entry) o;
+
+            return (key == null ? e.getKey() == null : key.equals(e.getKey())) && (val == null ? e.getValue() == null : val.equals(e.getValue()));
+        }
+
+        public int hashCode() {
+            int keyHash = (key == null ? 0 : key.hashCode());
+            int valueHash = (val == null ? 0 : val.hashCode());
+            return keyHash ^ valueHash;
+        }
+    }
+
+    private class ValueIterator extends AbstractEntryIterator<V> {
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see java.util.Iterator#next()
+         */
+        public V next() {
+            getNext();
+            if (last == null) {
+                return null;
+            } else {
+                return last.val;
+            }
+        }
+    }
+
+    private class KeyIterator extends AbstractEntryIterator<K> {
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see java.util.Iterator#next()
+         */
+        public K next() {
+            getNext();
+            if (last == null) {
+                return null;
+            } else {
+                return last.key;
+            }
+        }
+    }
+
+    private class EntryIterator extends AbstractEntryIterator<Map.Entry<K, V>> {
+        /*
+         * (non-Javadoc)
+         * 
+         * @see java.util.Iterator#next()
+         */
+        public Entry<K, V> next() {
+            getNext();
+            if (last == null) {
+                return null;
+            } else {
+                return last;
+            }
+        }
+
+    }
+
+    private abstract class AbstractEntryIterator<T> implements Iterator<T> {
+
+        TreeMapNode<K, V> last = null;
+        TreeMapNode<K, V> next = firstNode();
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see java.util.Iterator#hasNext()
+         */
+        public boolean hasNext() {
+            return next != null;
+        }
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see java.util.Iterator#next()
+         */
+        protected TreeMapNode<K, V> getNext() {
+            last = next;
+            next = findNext(next);
+            return last;
+        }
+
+        /*
+         * (non-Javadoc)
+         * 
+         * @see java.util.Iterator#remove()
+         */
+        public void remove() {
+            TreeMap.this.removeNode(last);
+            last = null;
+        }
+
+    }
+}
\ No newline at end of file

Modified: activemq/sandbox/activemq-flow/src/test/java/org/apache/activemq/broker/SharedQueuePerfTest.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-flow/src/test/java/org/apache/activemq/broker/SharedQueuePerfTest.java?rev=778993&r1=778992&r2=778993&view=diff
==============================================================================
--- activemq/sandbox/activemq-flow/src/test/java/org/apache/activemq/broker/SharedQueuePerfTest.java (original)
+++ activemq/sandbox/activemq-flow/src/test/java/org/apache/activemq/broker/SharedQueuePerfTest.java Wed May 27 04:38:37 2009
@@ -66,7 +66,7 @@
     BrokerDatabase database;
     BrokerQueueStore queueStore;
     private static final boolean USE_KAHA_DB = true;
-    private static final boolean PERSISTENT = true;
+    private static final boolean PERSISTENT = false;
     private static final boolean PURGE_STORE = true;
 
     protected MetricAggregator totalProducerRate = new MetricAggregator().name("Aggregate Producer Rate").unit("items");

Added: activemq/sandbox/activemq-flow/src/test/java/org/apache/activemq/util/TreeMapTest.java
URL: http://svn.apache.org/viewvc/activemq/sandbox/activemq-flow/src/test/java/org/apache/activemq/util/TreeMapTest.java?rev=778993&view=auto
==============================================================================
--- activemq/sandbox/activemq-flow/src/test/java/org/apache/activemq/util/TreeMapTest.java (added)
+++ activemq/sandbox/activemq-flow/src/test/java/org/apache/activemq/util/TreeMapTest.java Wed May 27 04:38:37 2009
@@ -0,0 +1,137 @@
+/**
+ * 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.activemq.util;
+
+import java.util.Comparator;
+import java.util.Iterator;
+
+import junit.framework.TestCase;
+
+/**
+ * @author cmacnaug
+ * 
+ */
+public class TreeMapTest extends TestCase {
+
+    public void testOrdering() {
+        Integer[] keys = new Integer[101];
+        TreeMap<Integer, Integer> testMap = new TreeMap<Integer, Integer>(new Comparator<Integer>() {
+
+            public int compare(Integer o1, Integer o2) {
+                return o1.compareTo(o2);
+            }
+        });
+        
+        java.util.TreeMap<Integer, Integer> refMap = new java.util.TreeMap<Integer, Integer>(new Comparator<Integer>() {
+
+            public int compare(Integer o1, Integer o2) {
+                return o1.compareTo(o2);
+            }
+        });
+        
+        for (int i = 0; i < keys.length; i++) {
+            keys[i] = i * 2;
+            testMap.put(keys[i], keys[i]);
+            refMap.put(keys[i], keys[i]);
+        }
+        
+        assertEquals(testMap.get(4), refMap.get(4));
+        assertEquals(testMap.get(3), refMap.get(3));
+        assertEquals(testMap.size(), refMap.size());
+        
+        //Test lookup:
+        assertEquals(null, testMap.lowerEntry(-2));
+        assertEquals(null, testMap.lowerEntry(-1));
+        assertEquals(null, testMap.lowerEntry(0));
+        assertEquals(new Integer(0), testMap.lowerEntry(1).getValue());
+        assertEquals(new Integer(0), testMap.lowerEntry(2).getValue());
+        assertEquals(new Integer(48), testMap.floorEntry(49).getValue());
+        assertEquals(new Integer(50), testMap.floorEntry(50).getValue());
+        assertEquals(new Integer(50), testMap.floorEntry(51).getValue());
+        assertEquals(new Integer(196), testMap.lowerEntry(198).getValue());
+        assertEquals(new Integer(198), testMap.lowerEntry(199).getValue());
+        assertEquals(new Integer(198), testMap.lowerEntry(200).getValue());
+        assertEquals(new Integer(200), testMap.lowerEntry(201).getValue());
+        assertEquals(new Integer(200), testMap.lowerEntry(202).getValue());
+        
+        assertEquals(null, testMap.floorEntry(-2));
+        assertEquals(null, testMap.floorEntry(-1));
+        assertEquals(new Integer(0), testMap.floorEntry(0).getValue());
+        assertEquals(new Integer(0), testMap.floorEntry(1).getValue());
+        assertEquals(new Integer(2), testMap.floorEntry(2).getValue());
+        assertEquals(new Integer(48), testMap.floorEntry(49).getValue());
+        assertEquals(new Integer(50), testMap.floorEntry(50).getValue());
+        assertEquals(new Integer(50), testMap.floorEntry(51).getValue());
+        assertEquals(new Integer(198), testMap.floorEntry(198).getValue());
+        assertEquals(new Integer(198), testMap.floorEntry(199).getValue());
+        assertEquals(new Integer(200), testMap.floorEntry(200).getValue());
+        assertEquals(new Integer(200), testMap.floorEntry(201).getValue());
+        assertEquals(new Integer(200), testMap.floorEntry(202).getValue());
+        
+        assertEquals(new Integer(0), testMap.upperEntry(-2).getValue());
+        assertEquals(new Integer(0), testMap.upperEntry(-1).getValue());
+        assertEquals(new Integer(2), testMap.upperEntry(0).getValue());
+        assertEquals(new Integer(2), testMap.upperEntry(1).getValue());
+        assertEquals(new Integer(4), testMap.upperEntry(2).getValue());
+        assertEquals(new Integer(50), testMap.upperEntry(49).getValue());
+        assertEquals(new Integer(52), testMap.upperEntry(50).getValue());
+        assertEquals(new Integer(52), testMap.upperEntry(51).getValue());
+        assertEquals(new Integer(200), testMap.upperEntry(198).getValue());
+        assertEquals(new Integer(200), testMap.upperEntry(199).getValue());
+        assertEquals(null, testMap.upperEntry(200));
+        assertEquals(null, testMap.upperEntry(201));
+        assertEquals(null, testMap.upperEntry(202));
+        
+        assertEquals(new Integer(0), testMap.ceilingEntry(-2).getValue());
+        assertEquals(new Integer(0), testMap.ceilingEntry(-1).getValue());
+        assertEquals(new Integer(0), testMap.ceilingEntry(0).getValue());
+        assertEquals(new Integer(2), testMap.ceilingEntry(1).getValue());
+        assertEquals(new Integer(2), testMap.ceilingEntry(2).getValue());
+        assertEquals(new Integer(50), testMap.ceilingEntry(49).getValue());
+        assertEquals(new Integer(50), testMap.ceilingEntry(50).getValue());
+        assertEquals(new Integer(52), testMap.ceilingEntry(51).getValue());
+        assertEquals(new Integer(198), testMap.ceilingEntry(198).getValue());
+        assertEquals(new Integer(200), testMap.ceilingEntry(199).getValue());
+        assertEquals(new Integer(200), testMap.ceilingEntry(200).getValue());
+        assertEquals(null, testMap.ceilingEntry(201));
+        assertEquals(null, testMap.ceilingEntry(202));
+        
+        //Test iterators:
+        assertEquals(refMap.keySet().iterator(), testMap.keySet().iterator());
+        assertEquals(refMap.values().iterator(), testMap.values().iterator());
+        assertEquals(refMap.entrySet().iterator(), testMap.entrySet().iterator());
+        
+        //Test removal:
+        assertEquals(refMap.remove(refMap.firstKey()), testMap.remove(testMap.firstKey()));
+        Iterator<Integer> refIt = refMap.values().iterator();
+        Iterator<Integer> testIt = testMap.values().iterator();
+        refIt.next();
+        testIt.next();
+        refIt.remove();
+        testIt.remove();
+        assertEquals(testIt, refIt);
+    }
+    
+    private static <T> void assertEquals(Iterator<T> i1, Iterator<T> i2)
+    {
+        assertEquals(i1.hasNext(), i2.hasNext());
+        if(i1.hasNext())
+        {
+            assertEquals(i1.next(), i2.next());
+        }
+    }
+}



Mime
View raw message