public static List<WeightedHostAddress> prioritize(WeightedHostAddress[] records) {
        final List<WeightedHostAddress> result = new LinkedList<>();

        // sort by priority (ascending)
        SortedMap<Integer, Set<WeightedHostAddress>> byPriority = new TreeMap<>();
        for(final WeightedHostAddress record : records) {
            if (byPriority.containsKey(record.getPriority())) {
                byPriority.get(record.getPriority()).add(record);
            } else {
                final Set<WeightedHostAddress> set = new HashSet<>();
                set.add(record);
                byPriority.put(record.getPriority(), set);
            }
        }

        // now, randomize each priority set by weight.
        for(Map.Entry<Integer, Set<WeightedHostAddress>> weights : byPriority.entrySet()) {

            List<WeightedHostAddress> zeroWeights = new LinkedList<>();

            int totalWeight = 0;
            final Iterator<WeightedHostAddress> i = weights.getValue().iterator();
            while (i.hasNext()) {
                final WeightedHostAddress next = i.next();
                if (next.weight == 0) {
                    // set aside, as these should be considered last according to the RFC.
                    zeroWeights.add(next);
                    i.remove();
                    continue;
                }

                totalWeight += next.getWeight();
            }

            int iterationWeight = totalWeight;
            Iterator<WeightedHostAddress> iter = weights.getValue().iterator();
            while (iter.hasNext()) {
                int needle = new Random().nextInt(iterationWeight);

                while (true) {
                    final WeightedHostAddress record = iter.next();
                    needle -= record.getWeight();
                    if (needle <= 0) {
                        result.add(record);
                        iter.remove();
                        iterationWeight -= record.getWeight();
                        break;
                    }
                }
                iter = weights.getValue().iterator();
            }

            // finally, append the hosts with zero priority (shuffled)
            Collections.shuffle(zeroWeights);
            result.addAll(zeroWeights);
        }

        return result;
    }
@Test
    public void testSameWeights() throws Exception {
        // setup
        final DNSUtil.WeightedHostAddress hostA = new DNSUtil.WeightedHostAddress("hostA", 5222, false, 1, 10);
        final DNSUtil.WeightedHostAddress hostB = new DNSUtil.WeightedHostAddress("hostB", 5222, false, 1, 10);
        final DNSUtil.WeightedHostAddress[] hosts = new DNSUtil.WeightedHostAddress[] { hostA, hostB };

        // do magic
        boolean hostAWasFirst = false;
        boolean hostBWasFirst = false;
        final int maxTries = Integer.MAX_VALUE;
        for (int i=0; i<maxTries; i++) {
            final List<DNSUtil.WeightedHostAddress> result = DNSUtil.prioritize(hosts);
            if (hostA.equals(result.get(0))) {
                hostAWasFirst = true;
            }

            if (hostB.equals(result.get(0))) {
                hostBWasFirst = true;
            }

            if (hostAWasFirst && hostBWasFirst) {
                break;
            }

            if (i%1000000==0 && i>0) {
                System.err.println("The last " + i + " iterations of this test all had the same result, which is very unlikely to occur (there should be an even distribution between two possible outcomes). We'll iterate up to "+ maxTries +" times, but you might want to abort the unit test at this point...");
            }
        }

        // verify
        assertTrue( hostAWasFirst );
        assertTrue( hostBWasFirst );
    }