Unreviewed, rolling out r234489.
[WebKit-https.git] / Source / WTF / wtf / Spectrum.h
1 /*
2  * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef Spectrum_h
27 #define Spectrum_h
28
29 #include <wtf/HashMap.h>
30 #include <wtf/Vector.h>
31 #include <algorithm>
32
33 namespace WTF {
34
35 template<typename T, typename CounterType = unsigned>
36 class Spectrum {
37 public:
38     typedef typename HashMap<T, CounterType>::iterator iterator;
39     typedef typename HashMap<T, CounterType>::const_iterator const_iterator;
40     
41     Spectrum() { }
42     
43     void add(const T& key, CounterType count = 1)
44     {
45         if (!count)
46             return;
47         typename HashMap<T, CounterType>::AddResult result = m_map.add(key, count);
48         if (!result.isNewEntry)
49             result.iterator->value += count;
50     }
51     
52     template<typename U>
53     void addAll(const Spectrum<T, U>& otherSpectrum)
54     {
55         for (auto& entry : otherSpectrum)
56             add(entry.key, entry.count);
57     }
58     
59     CounterType get(const T& key) const
60     {
61         const_iterator iter = m_map.find(key);
62         if (iter == m_map.end())
63             return 0;
64         return iter->value;
65     }
66     
67     size_t size() const { return m_map.size(); }
68     
69     iterator begin() { return m_map.begin(); }
70     iterator end() { return m_map.end(); }
71     const_iterator begin() const { return m_map.begin(); }
72     const_iterator end() const { return m_map.end(); }
73     
74     struct KeyAndCount {
75         KeyAndCount() { }
76         
77         KeyAndCount(const T& key, CounterType count)
78             : key(key)
79             , count(count)
80         {
81         }
82         
83         bool operator<(const KeyAndCount& other) const
84         {
85             if (count != other.count)
86                 return count < other.count;
87             // This causes lower-ordered keys being returned first; this is really just
88             // here to make sure that the order is somewhat deterministic rather than being
89             // determined by hashing.
90             return key > other.key;
91         }
92
93         T key;
94         CounterType count;
95     };
96     
97     // Returns a list ordered from lowest-count to highest-count.
98     Vector<KeyAndCount> buildList() const
99     {
100         Vector<KeyAndCount> list;
101         for (const_iterator iter = begin(); iter != end(); ++iter)
102             list.append(KeyAndCount(iter->key, iter->value));
103         
104         std::sort(list.begin(), list.end());
105         return list;
106     }
107     
108     void clear() { m_map.clear(); }
109     
110     template<typename Functor>
111     void removeIf(const Functor& functor)
112     {
113         m_map.removeIf([&functor] (typename HashMap<T, CounterType>::KeyValuePairType& pair) {
114                 return functor(KeyAndCount(pair.key, pair.value));
115             });
116     }
117     
118 private:
119     HashMap<T, CounterType> m_map;
120 };
121
122 } // namespace WTF
123
124 using WTF::Spectrum;
125
126 #endif // Spectrum_h