001 package org.expasy.jpl.commons.collection;
002
003
004 import java.util.AbstractList;
005 import java.util.List;
006
007
008 /**
009 * This object is a partition of a {@code List} that proposes a view of smaller
010 * split {@code List}s.
011 *
012 * <h4>Based on article:</h4>
013 * <p>
014 * http://www.vogella.de/articles/JavaAlgorithmsPartitionCollection/article.html
015 * </p>
016 *
017 * @author Lars Vogel
018 * @author Nikitin
019 *
020 * @param <T> the list element object.
021 *
022 * @version 1.0
023 *
024 */
025 @SuppressWarnings("unchecked")
026 public final class PartitionList<T> extends AbstractList<List<T>> {
027
028 /** default algorithm for index searching */
029 private static final IndexingAlgo INDEX_ALGO_DEFAULT;
030 private static final LastIndexingAlgo LAST_INDEX_ALGO_DEFAULT;
031
032 /** the list to partition */
033 private final List<T> list;
034
035 /** the max number of elements by partition */
036 private final int maxBucketCapacity;
037
038 /** number of remainders to spread over buckets */
039 private final int numOfRemainders;
040
041 /** the number of partitions */
042 @SuppressWarnings("unused")
043 private int numOfBucket;
044
045 private int[][] buckets;
046
047 /** the number of occupied buckets */
048 private int size;
049
050 static {
051 INDEX_ALGO_DEFAULT = new IndexingAlgo() {
052
053 public int indexOf(PartitionList parts, Object value) {
054
055 for (int i = 0; i < parts.size(); i++) {
056 List<Object> part = parts.get(i);
057
058 int index = part.indexOf(value);
059
060 if (index >= 0) {
061 return i;
062 }
063 }
064 return -1;
065 }
066 };
067
068 LAST_INDEX_ALGO_DEFAULT = new LastIndexingAlgo() {
069
070 public int lastIndexOf(PartitionList parts, Object value) {
071
072 for (int i = parts.size() - 1; i >= 0; i--) {
073 List<Object> part = parts.get(i);
074
075 int index = part.lastIndexOf(value);
076
077 if (index >= 0) {
078 return i;
079 }
080 }
081 return -1;
082 }
083 };
084 }
085
086 /**
087 * Default constructor.
088 *
089 * @param list the list to divide.
090 * @param maxBucketCapacity the maximum number of elements by bucket.
091 * @param numOfBucket the number of buckets.
092 * @param numberOfRemainders the number of remainders to distribute over
093 * buckets.
094 */
095 private PartitionList(List<T> list, int maxBucketCapacity, int numOfBucket,
096 int numOfRemainders) {
097 this.list = list;
098 this.maxBucketCapacity = maxBucketCapacity;
099 this.numOfBucket = numOfBucket;
100 this.size = Math.min(numOfBucket, list.size());
101
102 this.buckets = new int[numOfBucket][2];
103 this.numOfRemainders = numOfRemainders;
104
105 // if (numOfRemainders < numOfBucket) {
106 // this.numOfRemainders = numOfRemainders;
107 // } else {
108 // throw new IllegalArgumentException("bad remainder value: "
109 // + numOfRemainders);
110 // }
111 }
112
113 /**
114 * Make a partition from a given list and a partition capacity.
115 *
116 * @param list the list to partition.
117 * @param maxBucketCapacity the max partition capacity.
118 *
119 * @return a partition list.
120 */
121 public static <T> PartitionList<T> withBucketCapacity(List<T> list,
122 int maxBucketCapacity) {
123
124 if (list == null) {
125 throw new NullPointerException("the given list must be defined");
126 }
127 if (maxBucketCapacity < 0) {
128 throw new IllegalArgumentException(
129 "bucket size list must be greater than 0");
130 }
131
132 int bucketNumber = list.size() / maxBucketCapacity;
133 int remaindersInTheLastBucket = list.size() % maxBucketCapacity;
134 int remainders = 0;
135
136 if (remaindersInTheLastBucket > 0) {
137 bucketNumber++;
138
139 remainders =
140 list.size() - (bucketNumber * remaindersInTheLastBucket);
141 }
142
143 return new PartitionList<T>(list, maxBucketCapacity, bucketNumber,
144 remainders);
145 }
146
147 /**
148 * Make a partition from a given list and a bucket number.
149 *
150 * @param list the list to divide.
151 * @param bucketNumber the number of partitions.
152 *
153 * @return a partition list.
154 */
155 public static <T> PartitionList<T> withBucketNumber(List<T> list,
156 int bucketNumber) {
157
158 if (list == null) {
159 throw new NullPointerException("the given list must be defined");
160 }
161 if (bucketNumber <= 0) {
162 throw new IllegalArgumentException(
163 "number of partition must be greater than 0");
164 }
165
166 // the maximum number of elements that a bucket may store
167 int maxBucketCapacity = list.size() / bucketNumber;
168
169 // the number of element that possibly needs a bucket to be store in
170 int remainders = list.size() % bucketNumber;
171
172 // increase the capacity for the remainders
173 if (remainders > 0) {
174 maxBucketCapacity++;
175 }
176
177 return new PartitionList<T>(list, maxBucketCapacity, bucketNumber,
178 remainders);
179 }
180
181 @Override
182 public final List<T> get(int i) {
183
184 if (buckets[i][0] == 0 && buckets[i][1] == 0) {
185 buckets[i] = getInterval(i);
186 }
187 return list.subList(buckets[i][0], buckets[i][1]);
188 }
189
190 /**
191 * @return the whole list.
192 */
193 public final List<T> getList() {
194 return list;
195 }
196
197 /**
198 * Get the indices of {@code T}-objects of partition {@code i}.
199 *
200 * @param i the partition index.
201 * @return a list of indices.
202 */
203 public int[] getInterval(int i) {
204 int from = 0;
205 int to = 0;
206
207 checkBounds(i);
208
209 // Algorithm of homogeneous repartition:
210 /**
211 * <pre>
212 * This algorithm cuts a list of n elements in p partitions
213 * homogeneously such as in any partition (or bucket) the number of
214 * elements has reached its maximum capacity or has a free place.
215 *
216 * Input:
217 * List of elements [e1, e2, e3, e4, ... en-1, en]
218 * Output:
219 * List of list of elements [[e1, e2], [e3, e4], ... [en-1, en]]
220 *
221 * Example:
222 * Partition of 11 lists containing 1 to 11 elements distributed
223 * over 5 buckets.
224 * ___ ___ ___ ___ ___
225 * [1__] [___] [___] [___] [___] (list 1)
226 * ___ ___ ___ ___ ___
227 * [1__] [2__] [___] [___] [___] (list 2)
228 * ...
229 * ___ ___ ___ ___ ___
230 * [1__] [2__] [3__] [4__] [5__] (list 3)
231 * ...
232 * ___ ___ ___ ___ ___
233 * [12_] [34_] [56_] [78_] [9a_] (list 4)
234 * ___ ___ ___ ___ ___
235 * [123] [45_] [67_] [89_] [ab_] (list 5)
236 * 0 1 2 3 4
237 *
238 * The problem to solve is:
239 * What is the interval in the input list [from, to[ corresponding to
240 * the bucket i between [0, 5[ ?
241 *
242 * Observations:
243 * 1. if every buckets contain the same number of element, the operation is
244 * trivial: interval is [i*capacity, i+1*capacity[
245 * ex: in list 4, the interval of indices at bucket index 2 is [4, 6[
246 *
247 * 2. else the calculation is dependent of the number of remainder elements:
248 * if i < remainder then
249 * trivial step 1 (see bucket 0 of [list 5]) => solution is [0, 3[
250 * else
251 * the start index is 1-shifted from the last full bucket:
252 * the end index = start + capacity - 1
253 * </pre>
254 */
255
256 from = i * maxBucketCapacity;
257
258 if (numOfRemainders > 0 && i >= numOfRemainders) {
259 // each bucket distant from the last full bucket shift 1 place to
260 // the right
261 from -= i - numOfRemainders;
262 to = from + maxBucketCapacity - 1;
263 } else {
264 to = from + maxBucketCapacity;
265 }
266
267 to = Math.min(to, list.size());
268
269 return new int[] {from, to};
270 }
271
272 /**
273 * Get the indices of {@code T}-objects of partition {@code i}.
274 *
275 * @param i the partition index.
276 * @return a list of indices.
277 */
278 public IntegerSequence getIndices(int i) {
279 int[] interval = getInterval(i);
280 return new IntegerSequence.Builder(interval[0], interval[1]).build();
281 }
282
283 /**
284 * Get the indices of {@code T}-objects int the {@code i}th partition.
285 *
286 * @param i the partition index.
287 * @return a list of indices.
288 */
289 // private void computeIndices(int i) {
290 //
291 // checkBounds(i);
292 //
293 // from = i * maxBucketCapacity;
294 // if (numberOfRemainders > 0 && numberOfRemainders < i) {
295 // from -= i - numberOfRemainders;
296 // }
297 //
298 // to = from + maxBucketCapacity;
299 // if (numberOfRemainders > 0 && numberOfRemainders <= i) {
300 // to--;
301 // }
302 //
303 // to = Math.min(to, list.size());
304 // }
305
306 public void checkBounds(int i) {
307 if (i < 0) {
308 throw new IndexOutOfBoundsException("index " + i
309 + " must not be negative");
310 }
311
312 if (i >= list.size()) {
313 throw new IndexOutOfBoundsException("index " + i
314 + " must be less than size " + list.size());
315 }
316 }
317
318 @Override
319 public int size() {
320 return size;
321 }
322
323 /**
324 * @return the maxBucketSize
325 */
326 public int getMaxBucketCapacity() {
327 return maxBucketCapacity;
328 }
329
330 public int indexOf(Object value) {
331 return INDEX_ALGO_DEFAULT.indexOf(this, value);
332 }
333
334 public int indexOf(Object value, IndexingAlgo<T> algo) {
335 return algo.indexOf(this, value);
336 }
337
338 public int lastIndexOf(Object value) {
339 return LAST_INDEX_ALGO_DEFAULT.lastIndexOf(this, value);
340 }
341
342 public int lastIndexOf(Object value, LastIndexingAlgo<T> algo) {
343 return algo.lastIndexOf(this, value);
344 }
345
346 @Override
347 public boolean isEmpty() {
348 return list.isEmpty();
349 }
350
351 public interface IndexingAlgo<T> {
352
353 int indexOf(PartitionList<T> parts, Object value);
354 }
355
356 public interface LastIndexingAlgo<T> {
357
358 int lastIndexOf(PartitionList<T> parts, Object value);
359 }
360 }