From 2de569d23468c94fdcf1adc336a580b053423fd7 Mon Sep 17 00:00:00 2001 From: Alex Clayton Date: Fri, 19 Feb 2016 15:10:29 +0000 Subject: 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 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 { - 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> onResult = new Signal1>(); + + public static void sortResults(List 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 subList = queries.subList(i, nextI); + List weights = transform(subList, new UnaryOperation() { + + @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 cumulativeWeights = + partialSum(weights.subList(j, weights.size()), Integer.valueOf(0), + new BinaryOperation() { + + @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 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 int upperBound(List range,T value,Comparator 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 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 > int upperBound(List range,T value) { + Comparator comparator = new Comparator() { + + @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 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 int lowerBound(List range,T value,Comparator 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 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 > int lowerBound(List range,T value) { + Comparator comparator = new Comparator() { + + @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 Type of input to the operation + * @param Type of output of the operation + */ + public interface UnaryOperation { + + /** + * 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 Type of the first input to the operation. + * @param Type of the second input to the operation. + * @param Type of the output of the operation. + */ + public interface BinaryOperation { + + /** + * 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 Type of the input objects + * @param 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 List transform(Collection input, + UnaryOperation operation) { + List output = new ArrayList(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 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 List partialSum(Collection input, + T initialValue,BinaryOperation sumOp) { + List partialSums = new ArrayList(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 results = new ArrayList(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 results = new ArrayList(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); + } + +} -- cgit v0.10.2-6-g49f6