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
26
27
28
29 public static <T> List<T> shuffle(List<T> list) {
30 Collections.shuffle(list);
31 return list;
32 }
33
34
35
36
37 public static <T> List<T> shuffledCopy(List<T> list) {
38 return shuffle(newArrayList(list));
39 }
40
41
42
43
44 public static <T> List<T> immutableShuffledCopy(List<T> list) {
45 return ImmutableList.copyOf(shuffledCopy(list));
46 }
47
48
49
50
51
52
53
54
55
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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
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 }