summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAlex Clayton <alex.clayton@isode.com>2016-02-19 15:10:29 (GMT)
committerAlex Clayton <alex.clayton@isode.com>2016-02-29 11:09:07 (GMT)
commit2de569d23468c94fdcf1adc336a580b053423fd7 (patch)
treef34fff273c65be6006c9de34c6903ad8db553118
parent3bfe54c141dd3fa20e391312a0a84c75731e2b2a (diff)
downloadstroke-2de569d23468c94fdcf1adc336a580b053423fd7.zip
stroke-2de569d23468c94fdcf1adc336a580b053423fd7.tar.bz2
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
-rw-r--r--PortingProgress.txt4
-rw-r--r--src/com/isode/stroke/base/JavaRandomGenerator.java31
-rw-r--r--src/com/isode/stroke/base/RandomGenerator.java23
-rw-r--r--src/com/isode/stroke/network/DomainNameServiceQuery.java250
-rw-r--r--test/com/isode/stroke/network/DomainNameServiceQueryTest.java89
5 files changed, 390 insertions, 7 deletions
diff --git a/PortingProgress.txt b/PortingProgress.txt
index 4eb2e15..0f798e5 100644
--- a/PortingProgress.txt
+++ b/PortingProgress.txt
@@ -19,7 +19,7 @@ All files ported to 6ca201d0b48f4273e24dd7bff17c4a46eeaddf39 except for:
Algorithm, API, Atomic, boost_bsignals, BoostFilesystemVersion,
BoostRandomGenerator, Concat, Debug, Error, foreach, format,
- Log, Override, Path, Paths, PathTest, Platform, RandomGenerator,
+ Log, Override, Path, Paths, PathTest, Platform,
Regex, sleep, StartStopper, String, StringTest, WindowsRegistry -- Doesn't Need Porting.
SafeAllocator -- Not Yet Ported!
@@ -133,8 +133,6 @@ Network:
All files ported to 6ca201d0b48f4273e24dd7bff17c4a46eeaddf39 except for:
-DomainNameServiceQuery -- sortResults not Implemented.
-DomainNameServiceQueryTest -- Not Yet Ported!
GConfProxyProvider, UnixProxyProvider, WindowsProxyProvider, MacOSXProxyProvider -- Not Yet Ported!
NetworkEnvironment, SolarisNetworkEnvironment, UnixNetworkEnvironment, WindowsNetworkEnvironment -- Not Yet Ported!
HTTPConnectProxiedConnectionTest -- Not Yet Ported!
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;
+ }
+
}
diff --git a/test/com/isode/stroke/network/DomainNameServiceQueryTest.java b/test/com/isode/stroke/network/DomainNameServiceQueryTest.java
new file mode 100644
index 0000000..3ad212a
--- /dev/null
+++ b/test/com/isode/stroke/network/DomainNameServiceQueryTest.java
@@ -0,0 +1,89 @@
+/* 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.network;
+
+import static org.junit.Assert.assertEquals;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.junit.Test;
+
+import com.isode.stroke.base.RandomGenerator;
+import com.isode.stroke.network.DomainNameServiceQuery.Result;
+
+/**
+ * Test for {@link DomainNameServiceQuery}
+ */
+public class DomainNameServiceQueryTest {
+
+ private static class RandomGenerator1 implements RandomGenerator {
+
+ @Override
+ public int generateRandomInteger(int max) {
+ return 0;
+ }
+
+ }
+
+ public static class RandomGenerator2 implements RandomGenerator {
+
+ @Override
+ public int generateRandomInteger(int max) {
+ return max;
+ }
+
+ }
+
+ @Test
+ public void testSortResults_Random1() {
+ List<Result> results = new ArrayList<Result>(6);
+ results.add(new Result("server1.com", 5222, 5, 1));
+ results.add(new Result("server2.com", 5222, 3, 10));
+ results.add(new Result("server3.com", 5222, 6, 1));
+ results.add(new Result("server4.com", 5222, 3, 20));
+ results.add(new Result("server5.com", 5222, 2, 1));
+ results.add(new Result("server6.com", 5222, 3, 10));
+
+ RandomGenerator generator = new RandomGenerator1();
+ DomainNameServiceQuery.sortResults(results, generator);
+
+ assertEquals("server5.com",results.get(0).hostname);
+ assertEquals("server2.com",results.get(1).hostname);
+ assertEquals("server4.com",results.get(2).hostname);
+ assertEquals("server6.com",results.get(3).hostname);
+ assertEquals("server1.com",results.get(4).hostname);
+ assertEquals("server3.com",results.get(5).hostname);
+ }
+
+ @Test
+ public void testSortResults_Random2() {
+ List<Result> results = new ArrayList<Result>(7);
+ results.add(new Result("server1.com", 5222, 5, 1));
+ results.add(new Result("server2.com", 5222, 3, 10));
+ results.add(new Result("server3.com", 5222, 6, 1));
+ results.add(new Result("server4.com", 5222, 3, 20));
+ results.add(new Result("server5.com", 5222, 2, 1));
+ results.add(new Result("server6.com", 5222, 3, 10));
+ results.add(new Result("server7.com", 5222, 3, 40));
+
+ RandomGenerator generator = new RandomGenerator2();
+ DomainNameServiceQuery.sortResults(results, generator);
+
+ assertEquals("server5.com",results.get(0).hostname);
+ assertEquals("server7.com",results.get(1).hostname);
+ assertEquals("server2.com",results.get(2).hostname);
+ assertEquals("server4.com",results.get(3).hostname);
+ assertEquals("server6.com",results.get(4).hostname);
+ assertEquals("server1.com",results.get(5).hostname);
+ assertEquals("server3.com",results.get(6).hostname);
+ }
+
+}