CountersMap.h

Go to the documentation of this file.

#ifndef COUNTERSMAP_H
#define COUNTERSMAP_H

// interface include
#include <cstddef> // std::ptrdiff_t
#include <map>
#include <array>
#include <functional> // std::less<>
#include <memory> // std::allocator<>
#include <utility> // std::pair<>
#include <iterator> // std::bidirectional_iterator_tag
#include <type_traits> // std::make_unsigned


namespace lar {
  
  constexpr bool IsPowerOf2(unsigned long long int v)
    { return v & 1? v == 1: IsPowerOf2(v >> 1); }
  
  constexpr int LowestSetBit(unsigned long long int v);
  
  
  namespace details {
    
    template <typename COUNTER, std::size_t NCounters>
    class CounterBlock: public std::array<COUNTER, NCounters> {
        public:
      using Counter_t = COUNTER;
      
      using Array_t = std::array<Counter_t, NCounters>; 
      using value_type = typename Array_t::value_type;
      
      CounterBlock(): Array_t() { Array_t::fill(0); }
      
      CounterBlock(size_t index, Counter_t value): CounterBlock()
        { Array_t::operator[](index) = value; }
      
      void fill(const value_type& value) { Array_t::fill(value); }
      void fill(size_t begin, size_t n, const value_type& value)
        {
          std::fill
            (Array_t::data() + begin, Array_t::data() + begin + n, value);
        }
      
    }; // CounterBlock
    
    template <
      typename KEY,
      typename COUNTER,
      size_t SIZE
      >
    struct CountersMapTraits {
      
      using Key_t = KEY; 
      using Counter_t = COUNTER; 
      
      static constexpr size_t NCounters = SIZE;
      
      using CounterBlock_t = CounterBlock<Counter_t, NCounters>;
      
      using PlainBaseMap_t = std::map<Key_t, CounterBlock_t, std::less<Key_t>>;
      
      using DefaultAllocator_t = typename PlainBaseMap_t::allocator_type;
      
      template <typename Alloc>
      using BaseMap_t
        = std::map<Key_t, CounterBlock_t, std::less<Key_t>, Alloc>;
      
      using MapValue_t = typename PlainBaseMap_t::value_type;
      
    }; // struct CountersMapTraits

  } // namespace details
  
  
  
  template <
    typename KEY,
    typename COUNTER,
    size_t SIZE,
    typename ALLOC
      = typename details::CountersMapTraits<KEY, COUNTER, SIZE>::DefaultAllocator_t,
    unsigned int SUBCOUNTERS=1
    >
  class CountersMap {
    static_assert(SUBCOUNTERS == 1, "subcounters not implemented yet");
    static_assert(IsPowerOf2(SIZE),
      "the size of the cluster of counters must be a power of 2");
    
    using Traits_t = details::CountersMapTraits<KEY, COUNTER, SIZE>;
    
      public:
    using Key_t = KEY; 
    using Counter_t = COUNTER; 
    using Allocator_t = ALLOC; 
    
    using CounterMap_t = CountersMap<KEY, COUNTER, SIZE, ALLOC, SUBCOUNTERS>;
    
    
    static constexpr size_t NCounters = Traits_t::NCounters;
    
    static constexpr size_t NSubcounters = NCounters * SUBCOUNTERS;
    
    using SubCounter_t = Counter_t;
    
    
    using CounterBlock_t = typename Traits_t::CounterBlock_t;
    
    using BaseMap_t = typename Traits_t::template BaseMap_t<
      typename std::allocator_traits<Allocator_t>::template rebind_alloc
        <typename Traits_t::MapValue_t>
      >;
    
    /*
    using const_iterator = double_fwd_const_iterator<
      typename BaseMap_t::const_iterator,
      PairSecond<typename BaseMap_t::value_type>
      >;
    */
    
    using mapped_type = SubCounter_t;
    using allocator_type = Allocator_t; 
    // TODO others are missing
    
    using value_type = std::pair<const Key_t, SubCounter_t>;
    
    class const_iterator;
    
    
    CountersMap() {}
    
    CountersMap(Allocator_t alloc): BaseMap_t(alloc) {}
    
    
    SubCounter_t operator[] (Key_t key) const { return GetSubCounter(key); }
    
    SubCounter_t set(Key_t key, SubCounter_t value);
    
    SubCounter_t increment(Key_t key);
    
    SubCounter_t decrement(Key_t key);
    
    
    // this stuff needs serious work to be completed
    
    const_iterator begin() const;
    
    const_iterator end() const;
    
    
    bool empty() const { return counter_map.empty(); }
    
    
    typename std::make_unsigned<Key_t>::type n_counters() const
      { return counter_map.size() * NSubcounters; }
    
    
    template <typename OALLOC>
    bool is_equal(
      const std::map<Key_t, SubCounter_t, std::less<Key_t>, OALLOC>& to,
      Key_t& first_difference
      ) const;
    
    
    template <typename OALLOC>
    bool is_equal
      (const std::map<Key_t, SubCounter_t, std::less<Key_t>, OALLOC>& to) const
      { Key_t dummy; return is_equal(to, dummy); }
    
    
      protected:
    
    using BlockKey_t = Key_t; 
    using CounterIndex_t = typename std::make_unsigned<Key_t>::type;
    
    
    struct CounterKey_t {
      BlockKey_t block; 
      CounterIndex_t counter; 
      // there should be a subcluster index here too
      
      CounterKey_t(): block(0), counter(0) {}
      
      CounterKey_t(BlockKey_t major, CounterIndex_t minor):
        block(major), counter(minor) {}
      
      CounterKey_t(Key_t key):
    //    CounterKey_t(key >> MinorKeyBits, key & MinorKeyMask) {}
        CounterKey_t(key & ~MinorKeyMask, key & MinorKeyMask) {}
      
    //  Key_t Key() const { return (block << MinorKeyBits) + counter; }
      Key_t Key() const { return block + counter; }
      
      operator Key_t() const { return Key(); }
      
      
      CounterKey_t& operator++()
        { if (++counter == MinorKeyRange) next_block(); return *this; }
      CounterKey_t& operator--()
        {
          if (counter-- == 0) { prev_block(); counter = MinorKeyRange - 1; }
          return *this;
        } // operator--()
      CounterKey_t& operator++(int)
        { CounterKey_t old(*this); this->operator++(); return old; }
      CounterKey_t& operator--(int)
        { CounterKey_t old(*this); this->operator--(); return old; }
      
      CounterKey_t& start_block() { counter = 0; return *this; }
      
      CounterKey_t& prev_block()
        { block -= MinorKeyRange; return start_block(); }
      
      CounterKey_t& next_block()
        { block += MinorKeyRange; return start_block(); }
      
      
      static constexpr Key_t MinorKeyRange = NSubcounters;
      
      static constexpr Key_t MinorKeyBits = LowestSetBit(MinorKeyRange);
      
      static constexpr Key_t MinorKeyMask = MinorKeyRange - 1;
      
      static_assert
        (MinorKeyBits > 0, "Wrong COUNTER value for lar::CountersMap");
      
    }; // struct CounterKey_t
    
    
    BaseMap_t counter_map; 
    
    
    Counter_t GetCounter(CounterKey_t key) const;
    
    // Since subcounters are not implemented yet, this is a no-op
    SubCounter_t GetSubCounter(CounterKey_t key) const
      { return GetCounter(key); }
    
    Counter_t& GetOrCreateCounter(CounterKey_t key);
    
    
    static CounterKey_t SplitKey(Key_t key) { return key; }
    
    static const_iterator make_const_iterator
      (typename BaseMap_t::const_iterator it, size_t ix)
      { return { it, ix }; }
    
      private:
    
    SubCounter_t unchecked_set(CounterKey_t key, SubCounter_t delta);
    
    SubCounter_t unchecked_add(CounterKey_t key, SubCounter_t delta);
    
  }; // class CountersMap
  
  
} // namespace lar


//------------------------------------------------------------------------------

namespace lar {
  
  namespace details {
    inline constexpr int LowestSetBitScaler(unsigned long long int v, int b)
      { return (v & 1)? b: LowestSetBitScaler(v >> 1, b + 1); }
    
    namespace counters_map {
      static constexpr bool bDebug = true;

      
    } // namespace counters_map
  } // namespace details
  
  
  inline constexpr int LowestSetBit(unsigned long long int v)
    { return (v == 0)? -1: details::LowestSetBitScaler(v, 0); }
  
  // providing "definitions" of the static constants;
  // these are required if the code is going to take the address of these
  // constants, which is most often due to the use of "const size_t&" in some
  // function, where "size_t" is a template argument type
  // (or else the reference would not be needed).
  // I am not providing the same for the protected and private members
  // (just because of laziness).
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  constexpr size_t CountersMap<K, C, S, A, SUB>::NCounters;
  
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  constexpr size_t CountersMap<K, C, S, A, SUB>::NSubcounters;
  
  
  // CountersMap<>::const_iterator does not fully implement the STL iterator
  // interface, since it does not implement operator-> () (for technical reason:
  // the value does not actually exist and it does not have an address),
  // in addition to std::swap().
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  class CountersMap<K, C, S, A, SUB>::const_iterator:
    public std::bidirectional_iterator_tag
  {
    friend CountersMap<K, C, S, A, SUB>;
    
      public:
    using value_type = typename CounterMap_t::value_type; 
    using difference_type = std::ptrdiff_t;
    using pointer = const value_type*;
    using reference = const value_type&;
    using iterator_category = std::bidirectional_iterator_tag;
    
    using iterator_type = CounterMap_t::const_iterator; 
    
    const_iterator() = default;
    
    value_type operator*() const { return { key(), iter->second[index] }; }
    
    iterator_type& operator++()
      {
        if (++index >= NSubcounters) { ++iter; index = 0; }
        return *this;
      } // operator++
    iterator_type operator++(int)
      { iterator_type old(*this); this->operator++(); return old; }
    
    iterator_type& operator--()
      {
        if (index == 0) { --iter; index = NSubcounters - 1; }
        else --index;
        return *this;
      } // operator--()
    iterator_type operator--(int)
      { iterator_type old(*this); this->operator--(); return old; }
    
    bool operator== (const iterator_type& as) const
      { return (iter == as.iter) && (index == as.index); }
    bool operator!= (const iterator_type& as) const
      { return (iter != as.iter) || (index != as.index); }
    
    
    CounterKey_t key() const { return { iter->first, index }; }
    
      protected:
    typename BaseMap_t::const_iterator iter;
    CounterIndex_t index; 
    
    const_iterator(typename BaseMap_t::const_iterator it, size_t ix):
      iter(it), index(ix) {}
    
  }; // CountersMap<>::const_iterator
  
  
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::SubCounter_t
    CountersMap<K, C, S, A, SUB>::set(Key_t key, SubCounter_t value)
    { return unchecked_set(CounterKey_t(key), value); }
  
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::SubCounter_t
    CountersMap<K, C, S, A, SUB>::increment(Key_t key)
    { return unchecked_add(CounterKey_t(key), +1); }
  
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::SubCounter_t
    CountersMap<K, C, S, A, SUB>::decrement(Key_t key)
    { return unchecked_add(CounterKey_t(key), -1); }
  
  
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::const_iterator
    CountersMap<K, C, S, A, SUB>::begin() const
    { return const_iterator{ counter_map.begin(), 0 }; }
  
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::const_iterator
    CountersMap<K, C, S, A, SUB>::end() const
    { return const_iterator{ counter_map.end(), 0 }; }
  
  
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  template <typename OALLOC>
  bool CountersMap<K, C, S, A, SUB>::is_equal(
    const std::map<Key_t, SubCounter_t, std::less<Key_t>, OALLOC>& to,
    Key_t& first_difference
  ) const {
    // this function is not optimised
    using CompMap_t
      = const std::map<Key_t, SubCounter_t, std::less<Key_t>, OALLOC>;
    typename CompMap_t::const_iterator to_iter = to.begin(), to_end = to.end();
    for (const typename const_iterator::value_type& p: *this) {
      
      if (to_iter != to_end) { // we have still counters to find
        // if counter is already beyond the next non-empty one froml STL map,
        // then we are missing some
        if (p.first > to_iter->first) {
          first_difference = to_iter->first;
          return false;
        }
    //    while (p.first > to_iter->first) {
    //      ++nMissingKeys;
    //      std::cout << "ERROR missing key " << to_iter->first << std::endl;
    //      if (++to_iter == to_end) break;
    //    } // while
    //  } // if
    //  
    //  if (to_iter != to_end) { // we have still counters to find
        if (p.first == to_iter->first) {
          // if the counter is in SLT map, the two counts must match
        //  std::cout << "  " << p.first << " " << p.second << std::endl;
          if (to_iter->second != p.second) {
          //  std::cout << "ERROR wrong counter value " << p.second
          //    << ", expected " << to_iter->second << std::endl;
          //  ++nMismatchValue;
            first_difference = to_iter->first;
            return false;
          }
          ++to_iter; // done with it
        }
        else if (p.first < to_iter->first) {
          // if the counter is not in STL map, then it must be 0
          if (p.second != 0) {
          //  ++nExtraKeys;
          //  std::cout << "ERROR extra key " << p.first << " (" << p.second << ")"
          //    << std::endl;
            first_difference = p.first;
            return false;
          }
        //  else {
        //    std::cout << "  " << p.first << " " << p.second << " (not in STL)"
        //      << std::endl;
        //  }
        }
      }
      else { // if we are at the end of compared map
        // no more keys in STL map
        if (p.second != 0) {
        //  ++nExtraKeys;
        //  std::cout << "ERROR extra key " << p.first << " (" << p.second << ")"
        //    << std::endl;
          first_difference = p.first;
          return false;
        }
      }
    } // for element in map
    
    return true;
  } // CountersMap<>::is_equal()
  
  
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::Counter_t
    CountersMap<K, C, S, A, SUB>::GetCounter(CounterKey_t key) const
  {
    typename BaseMap_t::const_iterator iBlock = counter_map.find(key.block);
    return (iBlock == counter_map.end())? 0: iBlock->second[key.counter];
  } // CountersMap<>::GetCounter() const
  
  
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  inline typename CountersMap<K, C, S, A, SUB>::Counter_t&
    CountersMap<K, C, S, A, SUB>::GetOrCreateCounter(CounterKey_t key)
    { return counter_map[key.block][key.counter]; }
  
  
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  typename CountersMap<K, C, S, A, SUB>::SubCounter_t
    CountersMap<K, C, S, A, SUB>::unchecked_set
    (CounterKey_t key, SubCounter_t value)
  {
    // take it low level here
    // first get the iterator to the block
    typename BaseMap_t::iterator iBlock = counter_map.lower_bound(key.block);
    if (iBlock != counter_map.end()) {
      if (iBlock->first == key.block) { // sweet, we have that counter already
        return iBlock->second[key.counter] = value;
      }
    }
    // no counter there yet: create one;
    // hint to insert before the block in the position we jave already found
    // (this is optimal in STL map for C++11);
    // create a block using the special constructor;
    // the temporary value created here is moved to the map
    counter_map.insert(iBlock, { key.block, { key.counter, value } } );
    return value;
  } // CountersMap<>::unchecked_add() const
  
  
  template <typename K, typename C, size_t S, typename A, unsigned int SUB>
  typename CountersMap<K, C, S, A, SUB>::SubCounter_t
    CountersMap<K, C, S, A, SUB>::unchecked_add
    (CounterKey_t key, SubCounter_t delta)
  {
    // take it low level here
    // first get the iterator to the block
    typename BaseMap_t::iterator iBlock = counter_map.lower_bound(key.block);
    if (iBlock != counter_map.end()) {
      if (iBlock->first == key.block) { // sweet, we have that counter already
        return iBlock->second[key.counter] += delta;
      }
    }
    // no counter there yet: create one;
    // hint to insert before the block in the position we jave already found
    // (this is optimal in STL map for C++11);
    // create a block using the special constructor;
    // the temporary value created here is moved to the map
    counter_map.insert(iBlock, { key.block, { key.counter, delta } } );
    return delta;
  } // CountersMap<>::unchecked_add() const
  
  
} // namespace lar


#endif // BULKALLOCATOR_H