sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject svn commit: r1790557 - in /sis/branches/JDK8/core/sis-utility/src: main/java/org/apache/sis/util/collection/FrequencySortedSet.java test/java/org/apache/sis/util/collection/FrequencySortedSetTest.java
Date Fri, 07 Apr 2017 14:08:15 GMT
Author: desruisseaux
Date: Fri Apr  7 14:08:15 2017
New Revision: 1790557

URL: http://svn.apache.org/viewvc?rev=1790557&view=rev
Log:
Complete FrequencySortedSet implementation.

Modified:
    sis/branches/JDK8/core/sis-utility/src/main/java/org/apache/sis/util/collection/FrequencySortedSet.java
    sis/branches/JDK8/core/sis-utility/src/test/java/org/apache/sis/util/collection/FrequencySortedSetTest.java

Modified: sis/branches/JDK8/core/sis-utility/src/main/java/org/apache/sis/util/collection/FrequencySortedSet.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK8/core/sis-utility/src/main/java/org/apache/sis/util/collection/FrequencySortedSet.java?rev=1790557&r1=1790556&r2=1790557&view=diff
==============================================================================
--- sis/branches/JDK8/core/sis-utility/src/main/java/org/apache/sis/util/collection/FrequencySortedSet.java
[UTF-8] (original)
+++ sis/branches/JDK8/core/sis-utility/src/main/java/org/apache/sis/util/collection/FrequencySortedSet.java
[UTF-8] Fri Apr  7 14:08:15 2017
@@ -31,9 +31,9 @@ import org.apache.sis.util.ArgumentCheck
 
 /**
  * A set with elements ordered by the amount of time they were {@linkplain #add added}.
- * Less frequently added elements are first, and most frequently added ones are last.
- * If some elements were added the same amount of time, then the iterator will traverse
- * them in their insertion order.
+ * By default, less frequently added elements are first and most frequently added elements
are last.
+ * If some elements were added the same amount of time, then the iterator will traverse them
in their
+ * insertion order.
  *
  * <p>An optional boolean argument in the constructor allows the construction of set
in reversed order
  * (most frequently added elements first, less frequently added last). This is similar but
not identical
@@ -46,7 +46,7 @@ import org.apache.sis.util.ArgumentCheck
  * @author  Martin Desruisseaux (Geomatys)
  * @version 0.8
  *
- * @param <E> the type of elements in the set.
+ * @param <E>  the type of elements in the set.
  *
  * @since 0.8
  * @module
@@ -64,8 +64,19 @@ public class FrequencySortedSet<E> exten
     private final Map<E,Integer> count;
 
     /**
-     * {@code +1} if the element should be sorted in the usual order, or {@code -1}
+     * {@code 0} if the element should be sorted in the usual order, or {@code -1}
      * if the elements should be sorted in reverse order (most frequent element first).
+     * This value is XORed with the number of times <var>n</var> that an element
is added: {@code n ^ order}.
+     * The intend is to store negative numbers in the {@link #count} map if this {@code FrequencySortedSet}
+     * has been created for reverse order.
+     *
+     * <div class="note"><b>Implementation note:</b>
+     * we could have used {@code +1} and {@code -1} for the usual and reverse order respectively,
and store the
+     * multiplication result {@code n * order} in the {@link #count} map. We rather use XOR
for two reasons:
+     * first, XOR is a simpler operation for the CPU than multiplication. Second, XOR guarantees
us that all
+     * negative numbers can be made positive in {@link #frequencies()}, by applying again
{@code n ^ order}.
+     * By contrast, the multiplication approach (or just the {@code -n} negation) would fail
to convert
+     * {@link Integer#MIN_VALUE}.</div>
      */
     private final int order;
 
@@ -84,17 +95,19 @@ public class FrequencySortedSet<E> exten
      * Creates an initially empty set with less frequent elements first.
      */
     public FrequencySortedSet() {
-        this(false);
+        count = new LinkedHashMap<>();      // Default constructor in JDK implementation
applies lazy array allocation.
+        order = 0;
     }
 
     /**
      * Creates an initially empty set with the default initial capacity.
      *
      * @param  reversed  {@code true} if the elements should be sorted in reverse order
-     *                   (most frequent element first, less frequent last).
+     *                   (most frequent element first, less frequent element last).
      */
     public FrequencySortedSet(final boolean reversed) {
-        this(16, reversed);
+        count = new LinkedHashMap<>();
+        order = reversed ? -1 : 0;
     }
 
     /**
@@ -102,11 +115,11 @@ public class FrequencySortedSet<E> exten
      *
      * @param initialCapacity  the initial capacity.
      * @param reversed         {@code true} if the elements should be sorted in reverse order
-     *                         (most frequent element first, less frequent last).
+     *                         (most frequent element first, less frequent element last).
      */
     public FrequencySortedSet(final int initialCapacity, final boolean reversed) {
         count = new LinkedHashMap<>(initialCapacity);
-        order = reversed ? -1 : +1;
+        order = reversed ? -1 : 0;
     }
 
     /**
@@ -126,11 +139,11 @@ public class FrequencySortedSet<E> exten
     }
 
     /**
-     * Adds the specified element to this set. Returns {@code true} if this set changed as
a result
-     * of this operation. Changes in element order are not notified by the returned value.
+     * Repetitively adds the specified element to this set. Returns {@code true} if this
set changed
+     * as a result of this operation. Changes in element order are not notified by the returned
value.
      *
-     * @param  element     the element to add.
-     * @param  occurrence  the number of time to add the given elements. The default value
is 1.
+     * @param  element     the element to add (may be {@code null}).
+     * @param  occurrence  the number of time to add the given element. The default value
is 1.
      * @return {@code true} if this set changed as a result of this operation.
      * @throws IllegalArgumentException if {@code occurrence} is negative.
      */
@@ -138,12 +151,8 @@ public class FrequencySortedSet<E> exten
         if (occurrence != 0) {
             ArgumentChecks.ensurePositive("occurrence", occurrence);
             sorted = null;
-            occurrence *= order;
-            final Integer n = count.put(element, occurrence);
-            if (n == null) {
-                return true;
-            }
-            count.put(element, n + occurrence);
+            occurrence ^= order;
+            return count.merge(element, occurrence, (old, n) -> Math.addExact(old, n)
- order) == occurrence;
         }
         return false;
     }
@@ -152,7 +161,9 @@ public class FrequencySortedSet<E> exten
      * Adds the specified element to this set. Returns {@code true} if this set changed as
a result
      * of this operation. Changes in element order are not notified by the returned value.
      *
-     * @param  element  the element to add.
+     * <p>The default implementation delegates to <code>{@linkplain #add(Object,
int) add}(element, 1)</code>.</p>
+     *
+     * @param  element  the element to add (may be {@code null}).
      * @return {@code true} if this set changed as a result of this operation.
      */
     @Override
@@ -204,7 +215,7 @@ public class FrequencySortedSet<E> exten
     @Override
     public Iterator<E> iterator() {
         ensureSorted();
-        return new Iter();
+        return new Iter(sorted, 0, sorted.length);
     }
 
     /**
@@ -218,6 +229,12 @@ public class FrequencySortedSet<E> exten
         private final E[] elements;
 
         /**
+         * Index of the first element ({@code lower}) and index after the last element ({@code
upper})
+         * on which to iterate.
+         */
+        private final int lower, upper;
+
+        /**
          * Index of the next element to return.
          */
         private int index;
@@ -225,8 +242,11 @@ public class FrequencySortedSet<E> exten
         /**
          * Creates an new iterator.
          */
-        Iter() {
+        Iter(final E[] sorted, final int lower, final int upper) {
             elements = sorted;
+            this.index = lower;
+            this.lower = lower;
+            this.upper = upper;
         }
 
         /**
@@ -234,7 +254,7 @@ public class FrequencySortedSet<E> exten
          */
         @Override
         public boolean hasNext() {
-            return index < elements.length;
+            return index < upper;
         }
 
         /**
@@ -242,10 +262,10 @@ public class FrequencySortedSet<E> exten
          */
         @Override
         public E next() {
-            if (index >= elements.length) {
-                throw new NoSuchElementException();
+            if (index < upper) {
+                return elements[index++];
             }
-            return elements[index++];
+            throw new NoSuchElementException();
         }
 
         /**
@@ -253,10 +273,7 @@ public class FrequencySortedSet<E> exten
          */
         @Override
         public void remove() {
-            if (index == 0) {
-                throw new IllegalStateException();
-            }
-            if (!FrequencySortedSet.this.remove(elements[index - 1])) {
+            if (index == lower || !FrequencySortedSet.this.remove(elements[index - 1])) {
                 // Could also be ConcurrentModificationException - we do not differentiate.
                 throw new IllegalStateException();
             }
@@ -264,27 +281,213 @@ public class FrequencySortedSet<E> exten
     }
 
     /**
-     * Not yet implemented.
+     * A view over a subset of {@link FrequencySortedSet}.
+     */
+    private final class SubSet extends AbstractSet<E> implements SortedSet<E>,
Serializable {
+        /**
+         * For cross-version compatibility.
+         */
+        private static final long serialVersionUID = 6843072153603161179L;
+
+        /**
+         * Reference to the {@link FrequencySortedSet#sorted} array, used for detecting changes.
+         */
+        private transient E[] elements;
+
+        /**
+         * Low endpoint (inclusive) of the subset. May be {@code null}.
+         */
+        private final E fromElement;
+
+        /**
+         * High endpoint (exclusive) of the subset. May be {@code null}.
+         */
+        private final E toElement;
+
+        /**
+         * Whether the set should take in account {@link #fromElement} or {@link #toElement}.
+         * We have to use those booleans (we can not use {@code null} sentinel value instead)
+         * because {@code null} is a legal value for {@code from/toElement}.
+         */
+        private final boolean hasFrom, hasTo;
+
+        /**
+         * Lower and upper index computed from {@link #fromElement} and {@link #toElement}.
+         */
+        private transient int lower, upper;
+
+        /**
+         * Creates a new subset from the lower element (inclusive) to the upper element (exclusive).
+         * Each endpoint can be null.
+         */
+        SubSet(final boolean hasFrom, final E fromElement, final boolean hasTo, final E toElement)
{
+            this.fromElement = fromElement;
+            this.toElement   = toElement;
+            this.hasFrom     = hasFrom;
+            this.hasTo       = hasTo;
+        }
+
+        /**
+         * Returns the comparator, which is the same than {@link FrequencySortedSet#comparator()}.
+         */
+        @Override
+        public Comparator<E> comparator() {
+            return FrequencySortedSet.this;
+        }
+
+        /**
+         * Ensures that {@link #lower} and {@link #upper} indices are valid.
+         */
+        private void ensureValidRange() {
+            if (elements == null || elements != sorted) {
+                ensureSorted();
+                elements = sorted;
+                if (hasFrom) {
+                    lower = Arrays.binarySearch(elements, fromElement, FrequencySortedSet.this);
+                    if (lower < 0) lower = ~lower;
+                }
+                if (hasTo) {
+                    upper = Arrays.binarySearch(elements, toElement, FrequencySortedSet.this);
+                    if (upper < 0)     upper = ~upper;
+                    if (upper < lower) upper =  lower;
+                } else {
+                    upper = elements.length;
+                }
+            }
+        }
+
+        /**
+         * Returns an iterator over the elements in this subset.
+         */
+        @Override
+        public Iterator<E> iterator() {
+            ensureValidRange();
+            return new Iter(elements, lower, upper);
+        }
+
+        /**
+         * Returns the number of elements in this subset.
+         */
+        @Override
+        public int size() {
+            ensureValidRange();
+            return upper - lower;
+        }
+
+        /**
+         * Returns the first element in this subset.
+         *
+         * @see FrequencySortedSet#first()
+         */
+        @Override
+        public E first() {
+            ensureValidRange();
+            if (lower != upper) {
+                return elements[lower];
+            } else {
+                throw new NoSuchElementException();
+            }
+        }
+
+        /**
+         * Returns the last element in this subset.
+         *
+         * @see FrequencySortedSet#last()
+         */
+        @Override
+        public E last() {
+            ensureValidRange();
+            if (lower != upper) {
+                return elements[upper - 1];
+            } else {
+                throw new NoSuchElementException();
+            }
+        }
+
+        /**
+         * Returns a view of the portion of this subset whose elements occur
+         * with a frequency strictly less than {@code toElement} frequency.
+         *
+         * @see FrequencySortedSet#headSet(Object)
+         */
+        @Override
+        public SortedSet<E> headSet(final E to) {
+            return subSet(fromElement, to, hasFrom ? 0 : 2);
+        }
+
+        /**
+         * Returns a view of the portion of this subset whose elements occur with
+         * a frequency equal or greater than {@code fromElement} frequency.
+         *
+         * @see FrequencySortedSet#tailSet(Object)
+         */
+        @Override
+        public SortedSet<E> tailSet(final E from) {
+            return subSet(from, toElement, hasTo ? 0 : 1);
+        }
+
+        /**
+         * Returns a view of the portion of this subset whose elements occur with a frequency
in the
+         * range of {@code fromElement} frequency inclusive to {@code toElement} frequency
exclusive.
+         *
+         * @see FrequencySortedSet#subSet(Object, Object)
+         */
+        @Override
+        public SortedSet<E> subSet(final E from, final E to) {
+            return subSet(from, to, 0);
+        }
+
+        /**
+         * Implementation of {@link #headSet(Object)}, {@link #tailSet(Object)} and {@link
#subSet(Object, Object)}.
+         * The {@code bounds} argument tell which {@link FrequencySortedSet} method to delegate
to.
+         */
+        private SortedSet<E> subSet(E from, E to, final int bounded) {
+            if (hasFrom && compare(from, fromElement) < 0) from = fromElement;
+            if (hasTo   && compare(to,     toElement) > 0) to   = toElement;
+            switch (bounded) {
+                default: throw new AssertionError(bounded);
+                case 0:  return FrequencySortedSet.this.subSet(from, to);
+                case 1:  return FrequencySortedSet.this.tailSet(from);
+                case 2:  return FrequencySortedSet.this.headSet(to);
+            }
+        }
+    }
+
+    /**
+     * Returns a view of the portion of this set whose elements occur with a frequency strictly
less than
+     * {@code toElement} frequency.
+     *
+     * @param  toElement  high endpoint (exclusive) of the returned set. May be {@code null}.
+     * @return a view of the portion of this set delimited by the given endpoint.
      */
     @Override
-    public SortedSet<E> headSet(E toElement) {
-        throw new UnsupportedOperationException("Not supported yet.");
+    public SortedSet<E> headSet(final E toElement) {
+        return new SubSet(false, null, true, toElement);
     }
 
     /**
-     * Not yet implemented.
+     * Returns a view of the portion of this set whose elements occur with a frequency equal
or greater than
+     * {@code fromElement} frequency.
+     *
+     * @param  fromElement  low endpoint (inclusive) of the returned set. May be {@code null}.
+     * @return a view of the portion of this set delimited by the given endpoint.
      */
     @Override
-    public SortedSet<E> tailSet(E fromElement) {
-        throw new UnsupportedOperationException("Not supported yet.");
+    public SortedSet<E> tailSet(final E fromElement) {
+        return new SubSet(true, fromElement, false, null);
     }
 
     /**
-     * Not yet implemented.
+     * Returns a view of the portion of this set whose elements occur with a frequency in
the range of
+     * {@code fromElement} frequency inclusive to {@code toElement} frequency exclusive.
+     *
+     * @param  fromElement  low endpoint (inclusive) of the returned set. May be {@code null}.
+     * @param  toElement    high endpoint (exclusive) of the returned set. May be {@code
null}.
+     * @return a view of the portion of this set delimited by the given endpoints.
      */
     @Override
-    public SortedSet<E> subSet(E fromElement, E toElement) {
-        throw new UnsupportedOperationException("Not supported yet.");
+    public SortedSet<E> subSet(final E fromElement, final E toElement) {
+        return new SubSet(true, fromElement, true, toElement);
     }
 
     /**
@@ -337,28 +540,27 @@ public class FrequencySortedSet<E> exten
     }
 
     /**
-     * Sorts the elements in frequency order, if not already done. The sorted array will
contains
+     * Sorts the elements in frequency order, if not already done. The sorted array will
contain
      * all elements without duplicated values, with the less frequent element first and the
most
-     * frequent last (or the converse if this set has been created for reverse order).
+     * frequent element last (or the converse if this set has been created for reverse order).
      * If some elements appear at the same frequency, then their ordering will be preserved.
      */
     @SuppressWarnings("unchecked")
     private void ensureSorted() {
-        if (sorted != null) {
-            return;
-        }
-        @SuppressWarnings("rawtypes")                                   // Generic array
creation.
-        final Map.Entry<E,Integer>[] entries = count.entrySet().toArray(new Map.Entry[count.size()]);
-        Arrays.sort(entries, COMPARATOR);
-        final int length = entries.length;
-        sorted = (E[]) new Object[length];
-        if (frequencies == null || frequencies.length != length) {
-            frequencies = new int[length];
-        }
-        for (int i=0; i<length; i++) {
-            final Map.Entry<E,Integer> entry = entries[i];
-            sorted[i] = entry.getKey();
-            frequencies[i] = Math.abs(entry.getValue());
+        if (sorted == null) {
+            @SuppressWarnings("rawtypes")                                   // Generic array
creation.
+            final Map.Entry<E,Integer>[] entries = count.entrySet().toArray(new Map.Entry[count.size()]);
+            Arrays.sort(entries, COMPARATOR);
+            final int length = entries.length;
+            sorted = (E[]) new Object[length];
+            if (frequencies == null || frequencies.length != length) {
+                frequencies = new int[length];
+            }
+            for (int i=0; i<length; i++) {
+                final Map.Entry<E,Integer> entry = entries[i];
+                sorted[i] = entry.getKey();
+                frequencies[i] = entry.getValue() ^ order;
+            }
         }
     }
 
@@ -409,16 +611,16 @@ public class FrequencySortedSet<E> exten
      * Returns the frequency of the specified element in this set.
      *
      * @param  element  the element whose frequency is to be obtained.
-     * @return the frequency of the given element, or {@code 0} if it doesn't occur in this
set.
+     * @return the frequency of the given element, or {@code 0} if it does not occur in this
set.
      */
     public int frequency(final E element) {
-        return Math.abs(signedFrequency(element));
+        return signedFrequency(element) ^ order;
     }
 
     /**
-     * Returns the frequency of each element in this set, in iteration order.
+     * Returns the frequency of all elements in this set, in iteration order.
      *
-     * @return the frequency of each element in this set.
+     * @return the frequency of all elements in this set.
      */
     public int[] frequencies() {
         ensureSorted();

Modified: sis/branches/JDK8/core/sis-utility/src/test/java/org/apache/sis/util/collection/FrequencySortedSetTest.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK8/core/sis-utility/src/test/java/org/apache/sis/util/collection/FrequencySortedSetTest.java?rev=1790557&r1=1790556&r2=1790557&view=diff
==============================================================================
--- sis/branches/JDK8/core/sis-utility/src/test/java/org/apache/sis/util/collection/FrequencySortedSetTest.java
[UTF-8] (original)
+++ sis/branches/JDK8/core/sis-utility/src/test/java/org/apache/sis/util/collection/FrequencySortedSetTest.java
[UTF-8] Fri Apr  7 14:08:15 2017
@@ -16,7 +16,9 @@
  */
 package org.apache.sis.util.collection;
 
+import java.util.Arrays;
 import java.util.Collections;
+import org.apache.sis.test.DependsOnMethod;
 import org.apache.sis.test.TestCase;
 import org.junit.Test;
 
@@ -51,6 +53,7 @@ public final strictfp class FrequencySor
      * Simple test with 2 elements.
      */
     @Test
+    @DependsOnMethod("testSimple")
     public void testTwoElements() {
         final FrequencySortedSet<Integer> set = new FrequencySortedSet<>(true);
         for (int i=0; i<10; i++) {
@@ -64,4 +67,30 @@ public final strictfp class FrequencySor
         assertEquals(Integer.valueOf(11), set.last());
         assertArrayEquals(new int[] {10, 4}, set.frequencies());
     }
+
+    /**
+     * Tests creation of various subsets.
+     */
+    @Test
+    @DependsOnMethod("testTwoElements")
+    public void testSubSet() {
+        final FrequencySortedSet<Integer> set = new FrequencySortedSet<>();
+        set.addAll(Arrays.asList(2, 5, 3, 2, 4, 2, 3, 6, 2));
+        assertArrayEquals(new Integer[] {5, 4, 6, 3, 2}, set.toArray());
+        assertArrayEquals(new int[] {1, 1, 1, 2, 4}, set.frequencies());
+
+        assertArrayEquals("Expected all elements occurring less often than 2.",
+                          new Integer[] {5, 4, 6, 3}, set.headSet(2).toArray());
+
+        assertArrayEquals("Expected all elements occurring less often than 3.",
+                          new Integer[] {5, 4, 6}, set.headSet(3).toArray());
+
+        assertArrayEquals("Expected all elements occurring at least as often than 3.",
+                          new Integer[] {3, 2}, set.tailSet(3).toArray());
+
+        assertArrayEquals("Expected all elements occurring at least as often than 3 but less
than 2.",
+                          new Integer[] {3}, set.subSet(3, 2).toArray());
+
+        assertTrue(set.subSet(2, 3).isEmpty());
+    }
 }



Mime
View raw message