Imported WebKit commit 7e538425aa020340619e927792f3d895061fb54b (http://svn.webkit.org/repository/webkit/trunk@116286)

1 files changed, 105 insertions, 0 deletions

diff --git a/Source/WTF/wtf/Spectrum.h b/Source/WTF/wtf/Spectrum.h
new file mode 100644
index 000000000..5e7a484cd
--- /dev/null
+++ b/Source/WTF/wtf/Spectrum.h
@@ -0,0 +1,105 @@
+/*
+ * Copyright (C) 2011 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Spectrum_h
+#define Spectrum_h
+
+#include <wtf/HashMap.h>
+#include <wtf/Vector.h>
+#include <algorithm>
+
+namespace WTF {
+
+template<typename T>
+class Spectrum {
+public:
+    typedef typename HashMap<T, unsigned long>::iterator iterator;
+    typedef typename HashMap<T, unsigned long>::const_iterator const_iterator;
+    
+    Spectrum() { }
+    
+    void add(const T& key, unsigned long count = 1)
+    {
+        typename HashMap<T, unsigned long>::AddResult result = m_map.add(key, count);
+        if (!result.isNewEntry)
+            result.iterator->second += count;
+    }
+    
+    unsigned long get(const T& key) const
+    {
+        const_iterator iter = m_map.find(key);
+        if (iter == m_map.end())
+            return 0;
+        return iter->second;
+    }
+    
+    iterator begin() { return m_map.begin(); }
+    iterator end() { return m_map.end(); }
+    const_iterator begin() const { return m_map.begin(); }
+    const_iterator end() const { return m_map.end(); }
+    
+    struct KeyAndCount {
+        KeyAndCount() { }
+        
+        KeyAndCount(const T& key, unsigned long count)
+            : key(key)
+            , count(count)
+        {
+        }
+        
+        bool operator<(const KeyAndCount& other) const
+        {
+            if (count != other.count)
+                return count < other.count;
+            // This causes lower-ordered keys being returned first; this is really just
+            // here to make sure that the order is somewhat deterministic rather than being
+            // determined by hashing.
+            return key > other.key;
+        }
+
+        T key;
+        unsigned long count;
+    };
+    
+    // Returns a list ordered from lowest-count to highest-count.
+    Vector<KeyAndCount> buildList() const
+    {
+        Vector<KeyAndCount> list;
+        for (const_iterator iter = begin(); iter != end(); ++iter)
+            list.append(KeyAndCount(iter->first, iter->second));
+        
+        std::sort(list.begin(), list.end());
+        return list;
+    }
+    
+private:
+    HashMap<T, unsigned long> m_map;
+};
+
+} // namespace WTF
+
+using WTF::Spectrum;
+
+#endif // Spectrum_h