Add sort method for ServiceQuery and add Tests

Add the sortResult static method to the DomainNameServiceQuery class. This required adding a few equivalances for C++ std library methods to the class. And add a test for the new method too. Test-information: All unit tests pass ok. Change-Id: Idee0888f7ea140d35a971414fc2fd3cbcdfc337f
author: Alex Clayton <alex.clayton@isode.com> 2016-02-19 15:10:29 (GMT)
committer: Alex Clayton <alex.clayton@isode.com> 2016-02-29 11:09:07 (GMT)
commit: 2de569d23468c94fdcf1adc336a580b053423fd7 (patch)
tree: f34fff273c65be6006c9de34c6903ad8db553118 /src
parent: 3bfe54c141dd3fa20e391312a0a84c75731e2b2a (diff)
download: stroke-2de569d23468c94fdcf1adc336a580b053423fd7.zip
stroke-2de569d23468c94fdcf1adc336a580b053423fd7.tar.bz2
3 files changed, 300 insertions, 4 deletions
diff --git a/src/com/isode/stroke/base/JavaRandomGenerator.java b/src/com/isode/stroke/base/JavaRandomGenerator.java
new file mode 100644
index 0000000..09d389d
--- /dev/null
+++ b/src/com/isode/stroke/base/JavaRandomGenerator.java
@@ -0,0 +1,31 @@
+/*  Copyright (c) 2016, Isode Limited, London, England.
+ *  All rights reserved.
+ *
+ *  Acquisition and use of this software and related materials for any
+ *  purpose requires a written license agreement from Isode Limited,
+ *  or a written license from an organisation licensed by Isode Limited
+ *  to grant such a license.
+ *
+ */
+package com.isode.stroke.base;
+
+import java.util.Random;
+
+/**
+ * A {@link RandomGenerator} that generates integers with a uniform 
+ * distribution (using the java {@link Random} class).
+ */
+public final class JavaRandomGenerator implements RandomGenerator {
+
+    /**
+     * {@link Random} to use to generate the numbers
+     */
+    private final Random rng = new Random();
+
+    @Override
+    public int generateRandomInteger(int max) {
+        // Random.nextInt(bound) is exclusive of bound
+        return rng.nextInt(max+1);
+    }
+
+}
diff --git a/src/com/isode/stroke/base/RandomGenerator.java b/src/com/isode/stroke/base/RandomGenerator.java
new file mode 100644
index 0000000..970bb98
--- /dev/null
+++ b/src/com/isode/stroke/base/RandomGenerator.java
@@ -0,0 +1,23 @@
+/*  Copyright (c) 2016, Isode Limited, London, England.
+ *  All rights reserved.
+ *
+ *  Acquisition and use of this software and related materials for any
+ *  purpose requires a written license agreement from Isode Limited,
+ *  or a written license from an organisation licensed by Isode Limited
+ *  to grant such a license.
+ *
+ */
+package com.isode.stroke.base;
+
+public interface RandomGenerator {
+
+    /**
+     * Generates a random integer between 0 and 'max',
+     * 'max' inclusive.
+     * @param max The maximum possible value 
+     * to generate (inclusive)
+     * @return A random integer between 0 and 'max' 
+     */
+    public int generateRandomInteger(int max);
+    
+}
diff --git a/src/com/isode/stroke/network/DomainNameServiceQuery.java b/src/com/isode/stroke/network/DomainNameServiceQuery.java
index 05e4d32..6fb73cb 100644
--- a/src/com/isode/stroke/network/DomainNameServiceQuery.java
+++ b/src/com/isode/stroke/network/DomainNameServiceQuery.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2010, Isode Limited, London, England.
+ * Copyright (c) 2010-2016, Isode Limited, London, England.
  * All rights reserved.
  */
 /*
@@ -8,8 +8,15 @@
  */
 package com.isode.stroke.network;
 
+import com.ibm.icu.util.BytesTrie.Iterator;
+import com.isode.stroke.base.RandomGenerator;
 import com.isode.stroke.signals.Signal1;
+
+import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
 
 public abstract class DomainNameServiceQuery {
 
@@ -34,13 +41,248 @@ public abstract class DomainNameServiceQuery {
         public final int weight;
     };
 
-    public class ResultPriorityComparator {
+    /**
+     * Compares {@link DomainNameServiceQuery.Result} based on their 
+     * priority only.
+     *
+     */
+    public final static class ResultPriorityComparator implements Comparator<Result> {
 
-        public boolean compare(DomainNameServiceQuery.Result a, DomainNameServiceQuery.Result b) {
-            return a.priority < b.priority;
+        public int compare(DomainNameServiceQuery.Result a, DomainNameServiceQuery.Result b) {
+            if (a.priority < b.priority) {
+                return -1;
+            }
+            if (a.priority > b.priority) {
+                return 1;
+            }
+            return 0;
         }
     };
 
     public abstract void run();
     public final Signal1<Collection<Result>> onResult = new Signal1<Collection<Result>>();
+    
+    public static void sortResults(List<Result> queries,RandomGenerator generator) {
+        ResultPriorityComparator comparator = new ResultPriorityComparator();
+        Collections.sort(queries,comparator);
+        int i = 0;
+        while (i < queries.size()) {
+            Result current = queries.get(i);
+            int nextI = upperBound(queries, current, comparator);
+            if ((nextI - i) > 1) {
+                List<Result> subList = queries.subList(i, nextI);
+                List<Integer> weights = transform(subList, new UnaryOperation<Result, Integer>() {
+
+                    @Override
+                    public Integer perform(Result item) {
+                        // easy hack to account for '0' weights getting at least some weight
+                        return Integer.valueOf(item.weight+1);
+                    }
+
+                });
+                for (int j = 0; j < (weights.size()-1); j++) {
+                    List<Integer> cumulativeWeights =
+                            partialSum(weights.subList(j, weights.size()), Integer.valueOf(0), 
+                                    new BinaryOperation<Integer, Integer, Integer>() {
+
+                                @Override
+                                public Integer perform(Integer int1,
+                                        Integer int2) {
+                                    int results = int1.intValue() + int2.intValue();
+                                    return Integer.valueOf(results);
+                                }
+                                
+                            });
+                    int lastWeight = cumulativeWeights.get(cumulativeWeights.size() - 1).intValue();
+                    int randomNumber = generator.generateRandomInteger(lastWeight);
+                    int selectedIndex = lowerBound(cumulativeWeights, Integer.valueOf(randomNumber));
+                    Collections.swap(subList, j, j+selectedIndex);
+                    Collections.swap(weights, j, j+selectedIndex);
+                }
+                
+            }
+            i = nextI;
+        }
+    }
+    
+    /**
+     * Behaves similarly to the c++ function std::upper_bound.
+     * Given a range that is sorted with respect to the given
+     * {@link Comparator}, returns the index of the first element in the range greater
+     * (under the {@link Comparator}) then the given value.
+     * @param <T> The type of the value.
+     * @param range A sorted (with respect to {@code comp}) list of
+     * T.  Should not be {@code null}.
+     * @param value A value to search the list for.  Should not be {@code null}.
+     * @param comp The comparator to use for the search, the {@code range} should be
+     * sorted with respect to this.  Should not be {@code null}.
+     * @return The index of the first element in {@code range} that is greater (under
+     * {@code comp}) then {@code value}, or {@code range.size()} if there is no such value.
+     */
+    public static <T> int upperBound(List<? extends T> range,T value,Comparator<? super T> comp) {
+        for (int i = 0; i < range.size(); i++) {
+            T current = range.get(i);
+            if (comp.compare(current, value) > 0) {
+                return i;
+            }
+        }
+        return range.size();
+    }
+    
+    /**
+     * Behaves similarly to the c++ function std::upper_bound.
+     * Given a range that is sorted with respect to the natural order of its elements
+     * , returns the index of the first element in the range greater then the given value.
+     * @param <T> The type of the value.
+     * @param range A sorted list of
+     * T.  Should not be {@code null}.
+     * @param value A value to search the list for.  Should not be {@code null}.
+     * @return The index of the first element in {@code range} that is greate then {@code value},
+     * or {@code range.size()} if there is no such value.
+     */
+    public static <T extends Comparable<T>> int upperBound(List<? extends T> range,T value) {
+        Comparator<T> comparator = new Comparator<T>() {
+
+            @Override
+            public int compare(T a, T b) {
+                return a.compareTo(b);
+            }
+        };
+        return upperBound(range, value, comparator);
+    }
+    
+    /**
+     * Behaves similarly to the c++ function std::lower_bound.
+     * Given a range that is sorted with respect to the given
+     * {@link Comparator}, returns the index of the first element in the range that is not
+     * less then (i.e it is greater then or equal to) a given value.
+     * @param <T> The type of the value.
+     * @param range A sorted (with respect to {@code comp}) list of
+     * T.  Should not be {@code null}.
+     * @param value A value to search the list for.  Should not be {@code null}.
+     * @param comp The comparator to use for the search, the {@code range} should be
+     * sorted with respect to this.  Should not be {@code null}.
+     * @return The index of the first element in {@code range} that is not less then 
+     * (i.e it is greater then or equal to) then {@code value}, or {@code range.size()} 
+     * if there is no such value.
+     */
+    public static <T> int lowerBound(List<? extends T> range,T value,Comparator<? super T> comp) {
+        for (int i = 0; i < range.size(); i++) {
+            T current = range.get(i);
+            if (comp.compare(current, value) < 0) {
+                continue;
+            }
+            return i;
+        }
+        return range.size();
+    }
+    
+    /**
+     * Behaves similarly to the c++ function std::lower_bound.
+     * Given a range that is sorted with respect to the natural order of its elements
+     * , returns the index of the first element in the range that is not less then
+     * (i.e it is greater then or equal to) a given value.
+     * @param <T> The type of the value.
+     * @param range A sorted list of
+     * T.  Should not be {@code null}.
+     * @param value A value to search the list for.  Should not be {@code null}.
+     * @return The index of the first element in {@code range} that is not less then
+     * (i.e it is greater then or equal to) {@code value},
+     * or {@code range.size()} if there is no such value.
+     */
+    public static <T extends Comparable<T>> int lowerBound(List<? extends T> range,T value) {
+        Comparator<T> comparator = new Comparator<T>() {
+
+            @Override
+            public int compare(T a, T b) {
+                return a.compareTo(b);
+            }
+        };
+        return lowerBound(range, value, comparator);
+    }
+    
+    /**
+     * Operation that produces an item of type T from
+     * an item of type S
+     * @param <S> Type of input to the operation
+     * @param <T> Type of output of the operation
+     */
+    public interface UnaryOperation<S,T> {
+        
+        /**
+         * Produces an item of type T from an item of type S
+         * @param item An item of type S.
+         * @return An item of type T
+         */
+        public T perform(S item);
+        
+    }
+    
+    /**
+     * Operation that produces an item of type T from
+     * an items of type R and an item of type S.
+     *
+     * @param <R> Type of the first input to the operation.
+     * @param <S> Type of the second input to the operation.
+     * @param <T> Type of the output of the operation.
+     */
+    public interface BinaryOperation<R,S,T> {
+        
+        /**
+         * Produces an item of type from an Item of type R
+         * and an Item of type S
+         * @param input1 An item of type R
+         * @param input2 An item of type S
+         * @return An item of type T
+         */
+        public T perform(R input1,S input2);
+        
+    }
+    
+    /**
+     * Behaves similar to the C++ function std::transform
+     * Transform a list of items of type T into a list of item of
+     * type S using the given {@link UnaryOperation}
+     * @param <S> Type of the input objects
+     * @param <T> Type of the output objects.
+     * @param input The input objects to apply the {@link UnaryOperation}
+     * to.
+     * @param operation The {@link UnaryOperation} to apply to the input
+     * to get the output.
+     * @return The results of applying the {@link UnaryOperation} to
+     * the input in the order they are returned by the input's {@link Iterator}.
+     */
+    public static <S,T> List<T> transform(Collection<? extends S> input,
+            UnaryOperation<? super S,? extends T> operation) {
+        List<T> output = new ArrayList<T>(input.size());
+        for (S item : input) {
+            T product = operation.perform(item);
+            output.add(product);
+        }
+        return output;
+    }
+    
+    /**
+     * Produces the partial sum of the elements in a {@link Collections} using the
+     * given {@link BinaryOperation}.
+     * @param <T> The type of objects to calculate the sum for
+     * @param input The items to produce the partial sums for.  Should not be {@code null}.
+     * @param initialValue The initial value for the sum to add the first element.
+     * @param sumOp The {@link BinaryOperation} to produce the sum must take two items
+     * of type T to produce another item of type T.  Should not be {@code null}.
+     * @return A {@link List} of T consisting of the partial sums of the input. 
+     * Will not be {@code null}
+     */
+    public static <T> List<T> partialSum(Collection<? extends T> input,
+            T initialValue,BinaryOperation<? super T,? super T,? extends T> sumOp) {
+        List<T> partialSums = new ArrayList<T>(input.size());
+        T previousSum = initialValue;
+        for (T currentInput : input) {
+            T newSum = sumOp.perform(previousSum, currentInput);
+            partialSums.add(newSum);
+            previousSum = newSum;
+        }
+        return partialSums;
+    }
+    
 }
author	Alex Clayton <alex.clayton@isode.com>	2016-02-19 15:10:29 (GMT)
committer	Alex Clayton <alex.clayton@isode.com>	2016-02-29 11:09:07 (GMT)
commit	2de569d23468c94fdcf1adc336a580b053423fd7 (patch)
tree	f34fff273c65be6006c9de34c6903ad8db553118 /src
parent	3bfe54c141dd3fa20e391312a0a84c75731e2b2a (diff)
download	stroke-2de569d23468c94fdcf1adc336a580b053423fd7.zip stroke-2de569d23468c94fdcf1adc336a580b053423fd7.tar.bz2