1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 package org.dishevelled.weighted;
25
26 import java.util.Map;
27 import java.util.Set;
28 import java.util.List;
29 import java.util.Random;
30 import java.util.HashMap;
31 import java.util.Iterator;
32 import java.util.ArrayList;
33 import java.util.Collection;
34 import java.util.Collections;
35 import java.util.Comparator;
36 import java.util.AbstractSet;
37 import java.util.AbstractCollection;
38
39
40
41
42
43
44
45
46 public final class HashWeightedMap<E>
47 implements WeightedMap<E>
48 {
49
50 private final Map<E, Double> map;
51
52
53 private Double totalWeight = 0.0d;
54
55
56 private Random random = new Random();
57
58
59 private transient Map<E, Integer> rank;
60
61
62 private transient boolean dirty;
63
64
65 private transient EntrySet entrySet;
66
67
68 private transient KeySet keySet;
69
70
71 private transient Values values;
72
73
74 private static final int DEFAULT_INITIAL_CAPACITY = 16;
75
76
77 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
78
79
80
81
82
83
84 public HashWeightedMap()
85 {
86 map = new HashMap<E, Double>();
87 dirty = true;
88 }
89
90
91
92
93
94
95
96 public HashWeightedMap(final int initialCapacity)
97 {
98 map = new HashMap<E, Double>(initialCapacity, DEFAULT_LOAD_FACTOR);
99 dirty = true;
100 }
101
102
103
104
105
106
107
108
109 public HashWeightedMap(final int initialCapacity, final float loadFactor)
110 {
111 map = new HashMap<E, Double>(initialCapacity, loadFactor);
112 dirty = true;
113 }
114
115
116
117
118
119
120
121 public HashWeightedMap(final WeightedMap<? extends E> weightedMap)
122 {
123 map = new HashMap<E, Double>(Math.max(2 * weightedMap.size(), DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
124 putAll(weightedMap);
125 }
126
127
128
129
130
131
132
133
134 public void setRandom(final Random random)
135 {
136 if (random == null)
137 {
138 throw new IllegalArgumentException("random must not be null");
139 }
140 this.random = random;
141 }
142
143
144 public void clear()
145 {
146 map.clear();
147 dirty = true;
148 totalWeight = 0.0d;
149 }
150
151
152 public int size()
153 {
154 return map.size();
155 }
156
157
158 public boolean isEmpty()
159 {
160 return map.isEmpty();
161 }
162
163
164 public boolean containsKey(final Object o)
165 {
166 return map.containsKey(o);
167 }
168
169
170 public boolean containsValue(final Object o)
171 {
172 return map.containsValue(o);
173 }
174
175
176 public Double get(final Object o)
177 {
178 return map.get(o);
179 }
180
181
182 public Double put(final E e, final Double w)
183 {
184
185 if (w < 0.0d)
186 {
187 throw new IllegalArgumentException("w must be >= 0.0d");
188 }
189
190 Double oldWeight = map.put(e, w);
191 if (oldWeight != null)
192 {
193 totalWeight -= oldWeight;
194 }
195 dirty = true;
196 totalWeight += w;
197 return oldWeight;
198 }
199
200
201 public void putAll(final Map<? extends E, ? extends Double> t)
202 {
203 for (Map.Entry<? extends E, ? extends Double> e : t.entrySet())
204 {
205 put(e.getKey(), e.getValue());
206 }
207 }
208
209
210 public Double remove(final Object o)
211 {
212 Double w = map.remove(o);
213 if (w != null)
214 {
215 dirty = true;
216 totalWeight -= w;
217 }
218 return w;
219 }
220
221
222 public E sample()
223 {
224 Double r = random.nextDouble();
225
226 for (E e : keySet())
227 {
228 r -= normalizedWeight(e);
229
230 if (r <= 0.0d)
231 {
232 return e;
233 }
234 }
235 return null;
236 }
237
238
239 public Double weight(final E e)
240 {
241 return map.get(e);
242 }
243
244
245 public Double normalizedWeight(final E e)
246 {
247 if (isEmpty())
248 {
249 return null;
250 }
251 if (totalWeight == 0.0d)
252 {
253 return 0.0d;
254 }
255
256 Double w = weight(e);
257
258 if (w == null)
259 {
260 return null;
261 }
262
263 return (w / totalWeight);
264 }
265
266
267 public Double totalWeight()
268 {
269 return totalWeight;
270 }
271
272
273 public int rank(final E e)
274 {
275 if (dirty)
276 {
277 calculateRank();
278 dirty = false;
279 }
280 return rank.containsKey(e) ? rank.get(e) : -1;
281 }
282
283
284 public int maximumRank()
285 {
286 if (isEmpty())
287 {
288 return -1;
289 }
290
291 int maximumRank = 0;
292 for (E e : keySet())
293 {
294 int currentRank = rank(e);
295
296 if (currentRank > maximumRank)
297 {
298 maximumRank = currentRank;
299 }
300 }
301
302 return maximumRank;
303 }
304
305
306
307
308
309 private void calculateRank()
310 {
311 rank = new HashMap<E, Integer>(size());
312
313 int r = 0;
314 List<E> l = new ArrayList<E>(keySet());
315 Collections.sort(l, byRankDescending);
316
317 Double lastWeight = Double.NaN;
318 for (E e : l)
319 {
320 Double w = normalizedWeight(e);
321 if (!lastWeight.equals(w))
322 {
323 r++;
324 }
325 rank.put(e, r);
326 lastWeight = w;
327 }
328 l = null;
329 }
330
331
332 public Set<E> keySet()
333 {
334 if (keySet == null)
335 {
336 keySet = new KeySet();
337 }
338 return keySet;
339 }
340
341
342 public Collection<Double> values()
343 {
344 if (values == null)
345 {
346 values = new Values();
347 }
348 return values;
349 }
350
351
352 public Set<Map.Entry<E, Double>> entrySet()
353 {
354 if (entrySet == null)
355 {
356 entrySet = new EntrySet();
357 }
358 return entrySet;
359 }
360
361
362
363
364
365 private transient final Comparator<E> byRankDescending = new Comparator<E>()
366 {
367
368 public int compare(final E e1, final E e2)
369 {
370 Double w1 = normalizedWeight(e1);
371 Double w2 = normalizedWeight(e2);
372
373 return (w2.compareTo(w1));
374 }
375 };
376
377
378
379
380 private class KeySet
381 extends AbstractSet<E>
382 {
383
384
385 public int size()
386 {
387 return map.keySet().size();
388 }
389
390
391 public void clear()
392 {
393 HashWeightedMap.this.clear();
394 }
395
396
397 public Iterator<E> iterator()
398 {
399 return new KeySetIterator();
400 }
401 }
402
403
404
405
406 private class KeySetIterator
407 implements Iterator<E>
408 {
409
410 private Iterator<E> iterator;
411
412
413 private E e;
414
415
416
417
418
419 public KeySetIterator()
420 {
421 iterator = map.keySet().iterator();
422 }
423
424
425
426 public boolean hasNext()
427 {
428 return iterator.hasNext();
429 }
430
431
432 public E next()
433 {
434 e = iterator.next();
435 return e;
436 }
437
438
439 public void remove()
440 {
441 Double w = weight(e);
442 iterator.remove();
443 dirty = true;
444 totalWeight -= w;
445 }
446 }
447
448
449
450
451 private class Values
452 extends AbstractCollection<Double>
453 {
454
455
456 public int size()
457 {
458 return map.values().size();
459 }
460
461
462 public void clear()
463 {
464 HashWeightedMap.this.clear();
465 }
466
467
468 public Iterator<Double> iterator()
469 {
470 return new ValuesIterator();
471 }
472 }
473
474
475
476
477 private class ValuesIterator
478 implements Iterator<Double>
479 {
480
481 private Iterator<Double> iterator;
482
483
484 private Double w;
485
486
487
488
489
490 public ValuesIterator()
491 {
492 iterator = map.values().iterator();
493 }
494
495
496
497 public boolean hasNext()
498 {
499 return iterator.hasNext();
500 }
501
502
503 public Double next()
504 {
505 w = iterator.next();
506 return w;
507 }
508
509
510 public void remove()
511 {
512 iterator.remove();
513 dirty = true;
514 totalWeight -= w;
515 }
516 }
517
518
519
520
521 private class EntrySet
522 extends AbstractSet<Map.Entry<E, Double>>
523 {
524
525
526 public int size()
527 {
528 return map.entrySet().size();
529 }
530
531
532 public void clear()
533 {
534 HashWeightedMap.this.clear();
535 }
536
537
538 public Iterator<Map.Entry<E, Double>> iterator()
539 {
540 return new EntrySetIterator();
541 }
542 }
543
544
545
546
547 private class EntrySetIterator
548 implements Iterator<Map.Entry<E, Double>>
549 {
550
551 private Iterator<Map.Entry<E, Double>> iterator;
552
553
554 private Map.Entry<E, Double> e;
555
556
557
558
559
560 public EntrySetIterator()
561 {
562 iterator = map.entrySet().iterator();
563 }
564
565
566
567 public boolean hasNext()
568 {
569 return iterator.hasNext();
570 }
571
572
573 public Map.Entry<E, Double> next()
574 {
575 e = iterator.next();
576 return new MapEntry(e);
577 }
578
579
580 public void remove()
581 {
582 iterator.remove();
583 dirty = true;
584 totalWeight -= e.getValue();
585 }
586 }
587
588
589
590
591 private class MapEntry
592 implements Map.Entry<E, Double>
593 {
594
595 private Map.Entry<E, Double> e;
596
597
598
599
600
601
602
603 public MapEntry(final Map.Entry<E, Double> e)
604 {
605 this.e = e;
606 }
607
608
609
610 public boolean equals(final Object o)
611 {
612 return e.equals(o);
613 }
614
615
616 public int hashCode()
617 {
618 return e.hashCode();
619 }
620
621
622 public E getKey()
623 {
624 return e.getKey();
625 }
626
627
628 public Double getValue()
629 {
630 return e.getValue();
631 }
632
633
634 public Double setValue(final Double w)
635 {
636
637 if (w < 0.0d)
638 {
639 throw new IllegalArgumentException("w must be >= 0.0d");
640 }
641
642 Double oldWeight = e.setValue(w);
643 if (oldWeight != null)
644 {
645 totalWeight -= oldWeight;
646 }
647 dirty = true;
648 totalWeight += w;
649 return oldWeight;
650 }
651 }
652 }