Libraryless. Click here for Pure Java version (10518L/58K).
1 | // not synchronized yet |
2 | persistable sclass OptimizedMultiSet<A> is IMultiSet<A> {
|
3 | new Map<A, Int> map; |
4 | // outer tree map for sorting |
5 | // inner linked hash set for reproducability (HashSet ordering sucks) |
6 | transient MultiSetMap<Int, A> byCount = multiSetMap_innerLinkedHashSet_outerRevTreeMap(); |
7 | int size; |
8 | |
9 | public int add(A a) { ret add(a, 1); }
|
10 | |
11 | int add(A a, int count) {
|
12 | if (count <= 0) ret 0; |
13 | size += count; |
14 | Int i = map.get(a); |
15 | if (i != null) |
16 | byCount.remove(i += count, a); |
17 | else |
18 | i = count; |
19 | map.put(a, i); |
20 | byCount.add(i, a); |
21 | ret i; |
22 | } |
23 | |
24 | // remove one occurrence of a (decrease its count) |
25 | void remove(A a) {
|
26 | Int i = map.get(a); |
27 | if (i != null) {
|
28 | --size; |
29 | byCount.remove(i, a); |
30 | if (--i > 0) {
|
31 | map.put(a, i); |
32 | byCount.add(i, a); |
33 | } else |
34 | map.remove(a); |
35 | } |
36 | } |
37 | |
38 | // remove all occurrences of a |
39 | void removeAll(A a) {
|
40 | Int i = map.get(a); |
41 | if (i == null) ret; |
42 | map.remove(a); |
43 | byCount.remove(i, a); |
44 | size -= i; |
45 | } |
46 | |
47 | public bool isEmpty() {
|
48 | ret map.isEmpty(); |
49 | } |
50 | |
51 | toString {
|
52 | ret str(map); |
53 | } |
54 | |
55 | A getMostPopularEntry() {
|
56 | ret firstValue(byCount); |
57 | } |
58 | |
59 | // returns first of least popular entries if there is a tie |
60 | A leastPopularEntry() {
|
61 | ret first(lastValue(castMultiSetMapToNavigableMap(byCount)); |
62 | } |
63 | |
64 | void _doneLoading {
|
65 | rebuildByCount(); |
66 | } |
67 | |
68 | // internal |
69 | void rebuildByCount {
|
70 | byCount.clear(); |
71 | for (A entry, int count : map) |
72 | byCount.put(count, entry); |
73 | } |
74 | |
75 | public int get(A a) {
|
76 | ret map.get(a); |
77 | } |
78 | |
79 | public int size() {
|
80 | ret size; |
81 | } |
82 | |
83 | int uniqueSize() {
|
84 | ret map.size(); |
85 | } |
86 | |
87 | L<A> highestFirst aka getSortedListDescending() {
|
88 | ret asList(multiSetMapValuesIterator(byCount)); |
89 | } |
90 | |
91 | // drop least popular items until at or below maxSize of (distinct) entries |
92 | void truncate(int maxSize) {
|
93 | assertTrue(maxSize >= 0); |
94 | while (uniqueSize() > maxSize) |
95 | removeAll(leastPopularEntry()); |
96 | } |
97 | |
98 | public synchronized Set<A> keySet() {
|
99 | return map.keySet(); |
100 | } |
101 | } |
download show line numbers debug dex old transpilations
Travelled to 9 computer(s): bhatertpkbcr, ekrmjmnbrukm, mowyntqkapby, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt, xrpafgyirdlv
No comments. add comment
| Snippet ID: | #1029108 |
| Snippet name: | OptimizedMultiSet - MultiSet that always also holds a list of all items sorted by popularity |
| Eternal ID of this version: | #1029108/37 |
| Text MD5: | daebedf1d3870425c3e85e71ce84da62 |
| Transpilation MD5: | 5b4d8c6cedaeff4646b5f8db832a8222 |
| Author: | stefan |
| Category: | javax |
| Type: | JavaX fragment (include) |
| Public (visible to everyone): | Yes |
| Archived (hidden from active list): | No |
| Created/modified: | 2023-03-20 20:56:46 |
| Source code size: | 2198 bytes / 101 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 285 / 697 |
| Version history: | 36 change(s) |
| Referenced in: | [show references] |