View Javadoc
1   package org.kuali.common.jute.collect;
2   
3   import static com.google.common.base.Preconditions.checkElementIndex;
4   import static com.google.common.base.Preconditions.checkNotNull;
5   import static com.google.common.collect.Lists.newArrayList;
6   import static com.google.common.collect.Ordering.natural;
7   import static java.lang.Math.min;
8   import static org.kuali.common.jute.base.Precondition.checkMin;
9   import static org.kuali.common.jute.base.Precondition.checkNotNull;
10  
11  import java.util.AbstractList;
12  import java.util.Collections;
13  import java.util.Comparator;
14  import java.util.List;
15  import java.util.RandomAccess;
16  
17  import com.google.common.base.Function;
18  import com.google.common.collect.ImmutableList;
19  import com.google.common.collect.Ordering;
20  import com.google.common.primitives.Doubles;
21  
22  public final class Lists {
23  
24      /**
25       * Alter the list passed in by randomly shuffling it's elements.
26       *
27       * @return the same list that was passed in.
28       */
29      public static <T> List<T> shuffle(List<T> list) {
30          Collections.shuffle(list);
31          return list;
32      }
33  
34      /**
35       * Create a mutable shuffled copy of the list passed in.
36       */
37      public static <T> List<T> shuffledCopy(List<T> list) {
38          return shuffle(newArrayList(list));
39      }
40  
41      /**
42       * Create an immutable shuffled copy of the list passed in.
43       */
44      public static <T> List<T> immutableShuffledCopy(List<T> list) {
45          return ImmutableList.copyOf(shuffledCopy(list));
46      }
47  
48      /**
49       * Returns consecutive {@linkplain List#subList(int, int) sublists} of a list, distributing the elements of the list as evenly as possible into the specified number of
50       * partitions. For example, distributing a list containing {@code [a, b, c, d, e]} into 3 partitions yields {@code [[a, b], [c, d], [e]]} -- an outer list containing three
51       * inner lists of one and two elements, all in the original order. The sizes of the returned lists will differ by at most one from each other.
52       *
53       * <p>
54       * The outer list is unmodifiable, but reflects the latest state of the source list. The inner lists are sublist views of the original list, produced on demand using
55       * {@link List#subList(int, int)}, and are subject to all the usual caveats about modification as explained in that API.
56       */
57      public static <T> List<List<T>> distribute(List<T> list, int partitions) {
58          checkNotNull(list);
59          checkMin(partitions, 1, "partitions");
60          return (list instanceof RandomAccess) ? new RandomAccessDistribution<T>(list, partitions) : new Distribution<T>(list, partitions);
61      }
62  
63      /**
64       * Creates a new, immutable, partitioned, list containing all of the elements from {@code list}. Elements are pseudo-evenly placed into sublists according to weight. The
65       * algorithm used to distribute the elements by weight is greedy and non-perfect, but fast, and good enough for many real-life situations.
66       *
67       * <p>
68       * Algorithm description:
69       * <li>Calculate the weight of each element using the supplied function</li>
70       * <li>Sort the elements in descending order by weight</li>
71       * <li>Create {@code partitions} empty sublists</li>
72       * <li>Add each element one at a time to the sublist with the smallest total weight</li>
73       *
74       * <p>
75       * The size of each partition can vary (and likely will vary in real world situations)
76       *
77       * <p>
78       * The ordering from the original {@code list} is not considered when producing the distribution.
79       *
80       * <p>
81       * The distribution is an immutable copy. Changes to the original {@code list} have no affect on the distribution.
82       */
83      public static <T> List<List<T>> scatter(Iterable<T> iterable, int partitions, Function<T, Double> weigher) {
84          checkNotNull(iterable, "iterable");
85          checkMin(partitions, 1, "partitions");
86          checkNotNull(weigher, "weigher");
87          List<Weighed<T>> weighed = natural().reverse().sortedCopy(weighElements(iterable, weigher));
88          List<List<T>> container = newContainer(min(weighed.size(), partitions));
89          if (!weighed.isEmpty()) {
90              fillContainer(container, weighed);
91          }
92          return immutableCopy(container);
93      }
94  
95      private static <T> List<List<T>> newContainer(int size) {
96          List<List<T>> container = newArrayList();
97          for (int i = 0; i < size; i++) {
98              List<T> list = newArrayList();
99              container.add(list);
100         }
101         return container;
102     }
103 
104     private static <T> void fillContainer(List<List<T>> container, List<Weighed<T>> sorted) {
105         List<WeightIndex> weightIndexes = newArrayList();
106         for (int i = 0; i < container.size(); i++) {
107             weightIndexes.add(new WeightIndex(i));
108         }
109         Ordering<WeightIndex> ordering = Ordering.from(WeightIndexComparator.INSTANCE);
110         WeightIndex min = ordering.min(weightIndexes);
111         for (Weighed<T> element : sorted) {
112             int index = min.getIndex();
113             List<T> list = container.get(index);
114             T value = element.getElement();
115             list.add(value);
116             double weight = min.getWeight() + element.getWeight();
117             min.setWeight(weight);
118             min = ordering.min(weightIndexes);
119         }
120     }
121 
122     private static <T> List<List<T>> immutableCopy(List<List<T>> container) {
123         List<List<T>> list = newArrayList();
124         for (List<T> element : container) {
125             list.add(ImmutableList.copyOf(element));
126         }
127         return ImmutableList.copyOf(list);
128     }
129 
130     private static <T> List<Weighed<T>> weighElements(Iterable<T> list, Function<T, Double> weigher) {
131         List<Weighed<T>> weighted = newArrayList();
132         for (T element : list) {
133             double weight = weigher.apply(element);
134             Weighed<T> weighed = newWeighed(element, weight);
135             weighted.add(weighed);
136         }
137         return weighted;
138     }
139 
140     private static <T> Weighed<T> newWeighed(T element, double weight) {
141         return new Weighed<T>(element, weight);
142     }
143 
144     private static class Weighed<T> implements Comparable<Weighed<T>> {
145 
146         public Weighed(T element, double weight) {
147             this.element = checkNotNull(element);
148             this.weight = weight;
149         }
150 
151         private final T element;
152         private final double weight;
153 
154         @Override
155         public int compareTo(Weighed<T> other) {
156             return Doubles.compare(this.weight, other.getWeight());
157         }
158 
159         public T getElement() {
160             return element;
161         }
162 
163         public double getWeight() {
164             return weight;
165         }
166 
167     }
168 
169     private enum WeightIndexComparator implements Comparator<WeightIndex> {
170         INSTANCE;
171 
172         @Override
173         public int compare(WeightIndex one, WeightIndex two) {
174             return Double.compare(one.getWeight(), two.getWeight());
175         }
176 
177     }
178 
179     private static class WeightIndex {
180 
181         public WeightIndex(int index) {
182             this.index = checkElementIndex(index, Integer.MAX_VALUE);
183         }
184 
185         private final int index;
186         private double weight;
187 
188         public int getIndex() {
189             return index;
190         }
191 
192         public double getWeight() {
193             return weight;
194         }
195 
196         public void setWeight(double weight) {
197             this.weight = weight;
198         }
199 
200     }
201 
202     private static class Distribution<T> extends AbstractList<List<T>> {
203         final List<T> list;
204         final int partitions;
205 
206         Distribution(List<T> list, int partitions) {
207             this.list = list;
208             this.partitions = partitions;
209         }
210 
211         @Override
212         public List<T> get(int index) {
213             checkElementIndex(index, size());
214             int listSize = list.size();
215             int normalPartitions = listSize % partitions;
216             int partialPartitionSize = listSize / partitions;
217             int normalPartitionSize = partialPartitionSize + 1;
218 
219             // Parts [0, normalPartitions) have size normalPartitionSize, the rest have size partialPartitionSize.
220             if (index < normalPartitions) {
221                 int chunkStart = normalPartitionSize * index;
222                 return list.subList(chunkStart, chunkStart + normalPartitionSize);
223             }
224 
225             int normalEnd = normalPartitions * normalPartitionSize;
226             int chunkStart = normalEnd + (index - normalPartitions) * partialPartitionSize;
227             return list.subList(chunkStart, chunkStart + partialPartitionSize);
228         }
229 
230         @Override
231         public int size() {
232             return partitions;
233         }
234     }
235 
236     private static class RandomAccessDistribution<T> extends Distribution<T> implements RandomAccess {
237         public RandomAccessDistribution(List<T> list, int parts) {
238             super(list, parts);
239         }
240     }
241 
242 }