Source/WTF/wtf/Spectrum.h

   1 /*
   2  * Copyright (C) 2011 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>
  36 class Spectrum {
  37 public:
  38     typedef typename HashMap<T, unsigned long>::iterator iterator;
  39     typedef typename HashMap<T, unsigned long>::const_iterator const_iterator;
  40
  41     Spectrum() { }
  42
  43     void add(const T& key, unsigned long count = 1)
  44     {
  45         typename HashMap<T, unsigned long>::AddResult result = m_map.add(key, count);
  46         if (!result.isNewEntry)
  47             result.iterator->second += count;
  48     }
  49
  50     unsigned long get(const T& key) const
  51     {
  52         const_iterator iter = m_map.find(key);
  53         if (iter == m_map.end())
  54             return 0;
  55         return iter->second;
  56     }
  57
  58     iterator begin() { return m_map.begin(); }
  59     iterator end() { return m_map.end(); }
  60     const_iterator begin() const { return m_map.begin(); }
  61     const_iterator end() const { return m_map.end(); }
  62
  63     struct KeyAndCount {
  64         KeyAndCount() { }
  65
  66         KeyAndCount(const T& key, unsigned long count)
  67             : key(key)
  68             , count(count)
  69         {
  70         }
  71
  72         bool operator<(const KeyAndCount& other) const
  73         {
  74             if (count != other.count)
  75                 return count < other.count;
  76             // This causes lower-ordered keys being returned first; this is really just
  77             // here to make sure that the order is somewhat deterministic rather than being
  78             // determined by hashing.
  79             return key > other.key;
  80         }
  81
  82         T key;
  83         unsigned long count;
  84     };
  85
  86     // Returns a list ordered from lowest-count to highest-count.
  87     Vector<KeyAndCount> buildList() const
  88     {
  89         Vector<KeyAndCount> list;
  90         for (const_iterator iter = begin(); iter != end(); ++iter)
  91             list.append(KeyAndCount(iter->first, iter->second));
  92
  93         std::sort(list.begin(), list.end());
  94         return list;
  95     }
  96
  97 private:
  98     HashMap<T, unsigned long> m_map;
  99 };
 100
 101 } // namespace WTF
 102
 103 using WTF::Spectrum;
 104
 105 #endif // Spectrum_h