Source code

001/*-------------------------------------------------------------------------+
002|                                                                          |
003| Copyright 2005-2011 The ConQAT Project                                   |
004|                                                                          |
005| Licensed under the Apache License, Version 2.0 (the "License");          |
006| you may not use this file except in compliance with the License.         |
007| You may obtain a copy of the License at                                  |
008|                                                                          |
009|    http://www.apache.org/licenses/LICENSE-2.0                            |
010|                                                                          |
011| Unless required by applicable law or agreed to in writing, software      |
012| distributed under the License is distributed on an "AS IS" BASIS,        |
013| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
014| See the License for the specific language governing permissions and      |
015| limitations under the License.                                           |
016+-------------------------------------------------------------------------*/
017package org.conqat.lib.commons.collections;
018
019import java.io.PrintWriter;
020import java.io.Serializable;
021import java.util.Collection;
022import java.util.Comparator;
023import java.util.Iterator;
024import java.util.LinkedHashMap;
025import java.util.List;
026import java.util.Map;
027import java.util.Map.Entry;
028import java.util.function.BiFunction;
029
030import org.conqat.lib.commons.js_export.ExportAsType;
031import org.conqat.lib.commons.js_export.ExportToJavaScript;
032
033import com.fasterxml.jackson.annotation.JsonProperty;
034
035/**
036 * This class manages a set of counters (i.e. is a mapping from some key objects
037 * to integers). As the implementation is based on hash maps, key objects must
038 * provide suitable hash keys.
039 */
040@ExportToJavaScript
041public class CounterSet<E> implements Serializable, Iterable<Pair<E, Integer>> {
042
043        /** Version used for serialization. */
044        private static final long serialVersionUID = 1;
045
046        /** The underlying map. */
047        @JsonProperty("map")
048        @ExportAsType("!Object<string, number>")
049        protected final Map<E, Integer> map = new LinkedHashMap<>();
050
051        /** Stores total value. */
052        @JsonProperty("total")
053        protected int total = 0;
054
055        /** Constructs an empty {@link CounterSet}. */
056        public CounterSet() {
057                // nothing to do
058        }
059
060        /**
061         * Constructs a new {@link CounterSet} from the given keys. Initializes all keys
062         * with 1.
063         */
064        public CounterSet(Collection<E> keys) {
065                incAll(keys);
066        }
067
068        /** Constructs a CounterSet with one value. */
069        public CounterSet(E key, int value) {
070                inc(key, value);
071        }
072
073        /**
074         * Add the given increment to an element. If the element was not present before,
075         * it is interpreted as if it was present with value 0. Returns the new value.
076         *
077         * @param key
078         *            the key of the counter to increment.
079         * @param increment
080         *            the increment.
081         */
082        public int inc(E key, int increment) {
083                Integer value = map.get(key);
084                int newValue;
085                if (value == null) {
086                        newValue = increment;
087                } else {
088                        newValue = value + increment;
089                }
090                map.put(key, newValue);
091
092                // update total sum
093                total += increment;
094                return getValue(key);
095        }
096
097        /**
098         * Same as <code>inc(key, 1)</code>.
099         *
100         * @see #inc(Object, int)
101         */
102        public int inc(E key) {
103                return inc(key, 1);
104        }
105
106        /**
107         * Add the given increment to the given keys. If a key was not present before,
108         * it is interpreted as if it was present with value 0.
109         *
110         * @param keys
111         *            the keys of the counter to increment.
112         * @param increment
113         *            the increment.
114         */
115        public void incAll(Collection<E> keys, int increment) {
116                for (E key : keys) {
117                        inc(key, increment);
118                }
119        }
120
121        /** Increments the given elements by 1 */
122        public void incAll(Collection<E> keys) {
123                for (E key : keys) {
124                        inc(key);
125                }
126        }
127
128        /**
129         * Adds the given {@link CounterSet} to this {@link CounterSet} by incrementing
130         * all keys contained from other.
131         */
132        public void add(CounterSet<E> other) {
133                for (E key : other.getKeys()) {
134                        inc(key, other.getValue(key));
135                }
136        }
137
138        /**
139         * Removes the second CounterSet from the first one and returns a new
140         * CounterSet.
141         */
142        public static <E> CounterSet<E> removeSecondFromFirst(CounterSet<E> first, CounterSet<E> second) {
143                CounterSet<E> merged = new CounterSet<>();
144                for (E key : CollectionUtils.unionSet(first.getKeys(), second.getKeys())) {
145                        merged.inc(key, first.getValue(key));
146                        merged.inc(key, -second.getValue(key));
147                        if (merged.getValue(key) == 0) {
148                                merged.remove(key);
149                        }
150                }
151                return merged;
152        }
153
154        /**
155         * Removes all keys that the given filter matches.
156         */
157        public void removeIf(BiFunction<E, Integer, Boolean> filter) {
158                map.entrySet().removeIf(next -> filter.apply(next.getKey(), next.getValue()));
159        }
160
161        /**
162         * Remove the entry with the given key, i.e. sets its value to 0. In case the
163         * entry does not exist, nothing happens.
164         */
165        public void remove(E key) {
166                total -= getValue(key);
167                map.remove(key);
168        }
169
170        /** Removes all entries with the given keys. */
171        public void removeAll(Collection<E> keys) {
172                for (E key : keys) {
173                        remove(key);
174                }
175        }
176
177        /** Clears the counter set. */
178        public void clear() {
179                map.clear();
180                total = 0;
181        }
182
183        /**
184         * Checks if an element is stored in the array.
185         */
186        public boolean contains(E key) {
187                return map.containsKey(key);
188        }
189
190        /**
191         * Get the value for an element. If the the element is not stored in the counter
192         * <code>0</code> is returned.
193         */
194        public int getValue(E key) {
195                Integer value = map.get(key);
196                if (value == null) {
197                        return 0;
198                }
199                return value;
200        }
201
202        /**
203         * Returns the set of all elements used a keys for counters.
204         */
205        public UnmodifiableSet<E> getKeys() {
206                return CollectionUtils.asUnmodifiable(map.keySet());
207        }
208
209        /** Returns a list of all keys ordered by their value ascending */
210        public List<E> getKeysByValueAscending() {
211                return CollectionUtils.sort(getKeys(), new Comparator<E>() {
212                        @Override
213                        public int compare(E key1, E key2) {
214                                return map.get(key1).compareTo(map.get(key2));
215                        }
216                });
217        }
218
219        /** Returns a list of all keys ordered by their value descending */
220        public List<E> getKeysByValueDescending() {
221                return CollectionUtils.reverse(getKeysByValueAscending());
222        }
223
224        /** Get total sum of all elements. */
225        public int getTotal() {
226                return total;
227        }
228
229        /** Returns a collection of all values */
230        public Collection<Integer> values() {
231                return map.values();
232        }
233
234        /** {@inheritDoc} */
235        @Override
236        public String toString() {
237                return map.toString();
238        }
239
240        /**
241         * Prints the distribution of values (ascending or descending) to System.out,
242         * where each value is printed on a separate line in the form &lt;key&gt; :
243         * &lt;value&gt;.
244         *
245         * <p>
246         * <i>Example:</i><br>
247         *
248         * foo : 4 <br>
249         * bar : 2
250         * </p>
251         */
252        public void printValueDistribution(boolean ascending) {
253                printValueDistribution(new PrintWriter(System.out), ascending);
254        }
255
256        /**
257         * Prints the distribution of values (ascending or descending) to the given
258         * stream, where each value is printed on a separate line in the form
259         * &lt;key&gt; : &lt;value&gt;.
260         *
261         * <p>
262         * <i>Example:</i><br>
263         *
264         * foo : 4 <br>
265         * bar : 2
266         * </p>
267         */
268        public void printValueDistribution(PrintWriter writer, boolean ascending) {
269                List<E> keys = null;
270                if (ascending) {
271                        keys = getKeysByValueAscending();
272                } else {
273                        keys = getKeysByValueDescending();
274                }
275                for (E key : keys) {
276                        writer.print(String.valueOf(key));
277                        writer.print(" : ");
278                        writer.print(getValue(key));
279                        writer.println();
280                }
281                writer.flush();
282        }
283
284        /** {@inheritDoc} */
285        @Override
286        public boolean equals(Object obj) {
287                if (obj instanceof CounterSet) {
288                        @SuppressWarnings("rawtypes")
289                        CounterSet other = (CounterSet) obj;
290                        return map.equals(other.map);
291                }
292                return false;
293        }
294
295        /** {@inheritDoc} */
296        @Override
297        public int hashCode() {
298                return map.hashCode();
299        }
300
301        /** Returns the values as {@link Map}. */
302        public Map<E, Integer> toMap() {
303                return new LinkedHashMap<>(map);
304        }
305
306        /** Returns the values as a {@link Map}, but omits keys where the value is 0. */
307        public Map<E, Integer> toMapWithoutZeroEntries() {
308                Map<E, Integer> map = toMap();
309                map.keySet().removeIf(key -> map.get(key) == 0);
310                return map;
311        }
312
313        /** {@inheritDoc} */
314        @Override
315        public Iterator<Pair<E, Integer>> iterator() {
316                return new Iterator<Pair<E, Integer>>() {
317                        private Iterator<Map.Entry<E, Integer>> delegate = map.entrySet().iterator();
318
319                        /** {@inheritDoc} */
320                        @Override
321                        public boolean hasNext() {
322                                return delegate.hasNext();
323                        }
324
325                        /** {@inheritDoc} */
326                        @Override
327                        public Pair<E, Integer> next() {
328                                Entry<E, Integer> next = delegate.next();
329                                if (next == null) {
330                                        return null;
331                                }
332                                return new Pair<>(next.getKey(), next.getValue());
333                        }
334                };
335        }
336}