/home/mhx/git/github/libmoost/include/moost/container/multi_map.hpp

Go to the documentation of this file.

/* vim:set ts=3 sw=3 sts=3 et: */
#ifndef MULTI_MAP_CONTAINER_H__
#define MULTI_MAP_CONTAINER_H__

#include <string>
#include <vector>
#include <algorithm>
#include <map>

#include "../which.hpp"
#include "policies/dense_hash_map.hpp"

#include "dense_hash_map.hpp"

namespace moost { namespace container {

typedef std::pair<int, int> multimap_value_type;

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

template < typename TKey,
           typename TVal,
           typename TLocMap = moost::container::dense_hash_map<TKey, multimap_value_type >
         >
class multi_map
{
private:

   typedef multi_map<TKey, TVal, TLocMap> self_type;

public:

   typedef TKey first_type;
   typedef TVal second_type;

   typedef typename
      policies::map_policy_selector
            < TKey, multimap_value_type, TLocMap>::policy_type loc_map_policy_type;

   typedef typename std::vector<TVal>::iterator        range_iterator;
   typedef typename std::vector<TVal>::const_iterator  const_range_iterator;

   class range
   {
   public:
      range() {}
      range( range_iterator f, range_iterator l ) : first(f), last(l) {}

      range_iterator begin() const { return first; }
      range_iterator end()   const { return last; }
      size_t size() const { return last - first; }
      bool empty() const { return (last - first) == 0; }

   private:
      range_iterator first;
      range_iterator last;
   };

   class const_range
   {
   public:

      const_range() {}
      const_range( const_range_iterator f, const_range_iterator l ) : first(f), last(l) {}
      const_range( const range& r ) : first(r.begin()), last(r.end()) {}

      void operator=( const range& r )
      { first = r.begin(); last = r.end(); }

      const_range_iterator begin() const { return first; }
      const_range_iterator end() const { return last; }

      size_t size() const { return last - first; }
      bool empty() const { return (last - first) == 0; }

   private:
      const_range_iterator first;
      const_range_iterator last;
   };


public:

   class const_iterator;

   class iterator /*: public const_iterator*/
   {
      friend class const_iterator;

   public:

      iterator() : m_pSelf(NULL) {}
      iterator( typename TLocMap::iterator it,
                typename TLocMap::iterator lastIt,
                self_type* pSelf )
         : m_loc_map_it(it), m_pSelf(pSelf)
      {
         if ( it == lastIt )
            std::make_pair( -1, range(m_pSelf->m_data.end(), m_pSelf->m_data.end()) );
         else
            update_iterator();
      }

      std::pair<int, range>& operator*()
      {
         update_iterator();
         return m_it;
      }
      std::pair<int, range>* operator->()
      {
         update_iterator();
         return &m_it;
      }

      iterator& operator++()
      {  // preincrement
         ++m_loc_map_it;
         return (*this);
      }

      iterator& operator--()
      {  // predecrement
         --m_loc_map_it;
         return (*this);
      }

      bool operator!=(const iterator& other) const
      {  // test for iterator inequality
         return other.m_loc_map_it != m_loc_map_it;
      }

   private:

      void update_iterator()
      {
         m_it.first = m_pSelf->m_locHandlerPolicy.template get_key<int>(m_pSelf->m_locations, m_loc_map_it);
         //m_it.first = TLocHandler::get_index(m_pSelf->m_locations, m_loc_map_it); // m_loc_map_it->first
         m_it.second = create_range();
      }

      range create_range()
      {
         multimap_value_type loc = m_pSelf->m_locHandlerPolicy.template get_value<multimap_value_type>(m_pSelf->m_locations, m_loc_map_it);

         //multimap_value_t loc = TLocHandler::get_location(m_loc_map_it);
         return range( m_pSelf->m_data.begin() +  loc.first, // start
                       m_pSelf->m_data.begin() + loc.first + loc.second ); //end
      }

      std::pair< int, range >    m_it;
      typename TLocMap::iterator m_loc_map_it;
      self_type*                 m_pSelf;
   };

   class const_iterator
   {
   public:

      const_iterator() : m_pSelf(NULL) {}
      const_iterator(const iterator& i)
         : m_it(i.m_it),
           m_loc_map_it(i.m_loc_map_it),
           m_pSelf(i.m_pSelf) {}

      const_iterator( typename TLocMap::const_iterator it,
                      typename TLocMap::const_iterator lastIt,
                      const self_type* pSelf )
         : m_loc_map_it(it), m_pSelf(pSelf)
      {
         if ( it == lastIt )
            std::make_pair( -1, const_range(m_pSelf->m_data.end(), m_pSelf->m_data.end()) );
         else
            update_iterator();
      }

      void operator=(const iterator& i)
      {  m_pSelf = i.m_pSelf; m_it = i.m_it; m_loc_map_it = i.m_loc_map_it; }

      std::pair<int, const_range>& operator*()
      {
         update_iterator();
         return m_it;
      }
      std::pair<int, const_range>* operator->()
      {
         update_iterator();
         return &m_it;
      }

      const_iterator& operator++()
      {  // preincrement
         ++m_loc_map_it;
         return (*this);
      }

      const_iterator& operator--()
      {  // predecrement
         --m_loc_map_it;
         return (*this);
      }

      bool operator!=(const const_iterator& other) const
      {  // test for iterator inequality
         return other.m_loc_map_it != m_loc_map_it;
      }

   protected:

      void update_iterator()
      {
         m_it.first = m_pSelf->m_locHandlerPolicy.template get_key<int>(m_pSelf->m_locations, m_loc_map_it); // m_loc_map_it->first
         //m_it.first = TLocHandler::get_index(m_pSelf->m_locations, m_loc_map_it); // m_loc_map_it->first
         m_it.second = create_range();
      }

      const_range create_range()
      {
         multimap_value_type loc = m_pSelf->m_locHandlerPolicy.template get_value<multimap_value_type>(m_pSelf->m_locations, m_loc_map_it);
         //multimap_value_t loc = TLocHandler::get_location(m_loc_map_it);
         return const_range( m_pSelf->m_data.begin() + loc.first, // start
                             m_pSelf->m_data.begin() + loc.first + loc.second ); //end
      }

      std::pair< int, const_range >    m_it;
      typename TLocMap::const_iterator m_loc_map_it;
      const self_type*                 m_pSelf;
      //std::vector<TVal>*         m_pData;
   };



   iterator       begin()       { return iterator(m_locations.begin(), m_locations.end(), this); }
   const_iterator begin() const { return const_iterator(m_locations.begin(), m_locations.end(), this); }

   iterator       end()       { return iterator(m_locations.end(), m_locations.end(), this); }
   const_iterator end() const { return const_iterator(m_locations.end(), m_locations.end(), this); }

public:

   multi_map(const loc_map_policy_type& locHandlerPolicy = loc_map_policy_type() )
   : m_locHandlerPolicy(locHandlerPolicy)
   { m_locHandlerPolicy.init(m_locations); }

   template <int WhichKey, typename Iterator>
   void create_map(Iterator first, Iterator last, size_t suggestedSize = 128);

   template < typename Iterator,
              typename GetKeyPolicy, // int operator()( typename const Entry& e )
              typename GetValuesPolicy > // void operator()( typename const Entry& e, vector<TVal>& vals)
   void create_map( Iterator first, Iterator last,
                    const GetKeyPolicy& getKey,
                    const GetValuesPolicy& getValues,
                    size_t suggestedSize = 128 );

   template <int WhichKey, typename TFirst, typename TSecond>
   void create_map( std::vector<TFirst, TSecond>& i2i, bool doSort = true);

   template <int WhichKey, typename TFirst, typename TSecond>
   void create_map_compressed(std::vector<TFirst, TSecond>& i2i, bool doSort = true);

   template <int WhichKey, typename Iterator>
   void create_map_compressed(Iterator first, Iterator last, size_t suggestedSize = 128);


   range operator[](const TKey& key);
   const_range operator[](const TKey& key) const;

   void clear();

   size_t size() const
   { return m_locations.size(); }

   bool empty() const
   { return m_locations.empty(); }

protected:

   TLocMap m_locations;
   loc_map_policy_type m_locHandlerPolicy;
   //TLocHandler m_locHandler;
   std::vector<TVal> m_data;

};

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

template <typename TKey, typename TVal, typename TLocMap>
template <int WhichKey, typename TFirst, typename TSecond>
void multi_map<TKey, TVal, TLocMap>::create_map( std::vector<TFirst, TSecond>& i2i,
                                                 bool doSort )
{
   if ( i2i.empty() )
      return;
   if ( doSort )
   {
      using namespace moost;
      typename which<WhichKey>::template comparer<std::less> comparer;
      std::stable_sort(i2i.begin(), i2i.end(), comparer );
   }

   create_map<WhichKey>( i2i.begin(), i2i.end(), i2i.size() );
}

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

template <typename TKey, typename TVal, typename TLocMap>
template <int WhichKey, typename Iterator>
void multi_map<TKey, TVal, TLocMap>::create_map( Iterator first, Iterator last,
                                                 size_t suggestedSize )
{
   if ( first == last )
      return;

   int currPos = 0;
   int currSize = 0;

   typename moost::which<WhichKey> getKey;
   typename moost::which<WhichKey>::other_type getValue;

   TKey currKey = getKey(*first);

   if ( suggestedSize > 0 )
      m_data.reserve(suggestedSize);

   Iterator it;
   for ( it = first; it != last; ++it )
   {
      if ( currKey != getKey(*it) )
      {
         m_locHandlerPolicy.put(m_locations, currKey, std::make_pair(currPos, currSize));
         currKey = getKey(*it);
         currPos = static_cast<int>(m_data.size());
         currSize = 0;
      }

      m_data.push_back( getValue(*it) );
      ++currSize;
   }

   // last one
   m_locHandlerPolicy.put(m_locations, currKey, std::make_pair(currPos, currSize));
}

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

template <typename TKey, typename TVal, typename TLocMap>
template < typename Iterator, typename GetKeyPolicy, typename GetValuesPolicy >
void multi_map<TKey, TVal, TLocMap>::create_map( Iterator first,
                                                 Iterator last,
                                                 const GetKeyPolicy& getKey,
                                                 const GetValuesPolicy& getValues,
                                                 size_t suggestedSize /*= 128 */)
{
   if ( suggestedSize > 0 )
      m_data.reserve(suggestedSize);

   int currKey;
   std::vector<TVal> values;

   int entryPos = 0;
   int valuesSize;

   for ( Iterator it = first; it != last; ++it )
   {
      currKey = getKey(*it);
      getValues(*it, values);
      if ( values.empty() )
         continue;

      valuesSize = static_cast<int>(values.size());

      std::copy( values.begin(), values.end(), back_inserter(m_data) );
      m_locHandlerPolicy.put(m_locations, currKey, std::make_pair(entryPos, valuesSize));
      entryPos += valuesSize;
   }
}

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

template <typename TKey, typename TVal, typename TLocMap>
template <int WhichKey, typename TFirst, typename TSecond>
void multi_map<TKey, TVal, TLocMap>::create_map_compressed( std::vector<TFirst, TSecond>& i2i,
                                                          bool doSort )
{
   if ( i2i.empty() )
      return;
   if ( doSort )
   {
      using namespace moost;
      typename which<WhichKey>::template comparer<std::less> comparer;
      std::stable_sort(i2i.begin(), i2i.end(), comparer );
   }

   create_map_compressed<WhichKey>( i2i.begin(), i2i.end(), i2i.size() );
}

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

template <typename TKey, typename TVal, typename TLocMap>
template <int WhichKey, typename Iterator>
void multi_map<TKey, TVal, TLocMap>::create_map_compressed( Iterator first, Iterator last,
                                                          size_t suggestedSize )
{
   if ( first == last )
      return;

   int currPos = 0;
   int currSize = 0;

   typename moost::which<WhichKey> getKey;
   typename moost::which<WhichKey>::other_type getValue;

   TKey currKey = getKey(*first);

   if ( suggestedSize > 0 )
      m_data.reserve(suggestedSize);

   std::map<TVal, int> compressedLocsMap;
   typename std::map<TVal, int>::iterator clIt;

   Iterator it;
   for ( it = first; it != last; ++it )
   {
      if ( currKey != getKey(*it) )
      {
         if ( currSize == 1 )
         {
            // does it have the given value?
            clIt = compressedLocsMap.find( m_data.back() );
            if ( clIt == compressedLocsMap.end() )
            {
               // not found! Add it!
               compressedLocsMap[m_data.back()] = currPos;
            }
            else
            {
               m_data.pop_back();
               currPos = clIt->second;
            }
         }

         m_locHandlerPolicy.put(m_locations, currKey, std::make_pair(currPos, currSize));
         currKey = getKey(*it);
         currPos = static_cast<int>(m_data.size());
         currSize = 0;
      }

      m_data.push_back( getValue(*it) );
      ++currSize;
   }

   // last one
   m_locHandlerPolicy.put(m_locations, currKey, std::make_pair(currPos, currSize));
}

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

template <typename TKey, typename TVal, typename TLocMap>
typename multi_map<TKey, TVal, TLocMap>::range
multi_map<TKey, TVal, TLocMap>::operator[]( const TKey& key )
{
   multimap_value_type loc;
   if ( m_locHandlerPolicy(m_locations, key, loc) )
   {
      return range( m_data.begin() + loc.first, // start
                    m_data.begin() + loc.first + loc.second  // end
                  );
   }
   else
   {
      return range(m_data.end(), m_data.end());
   }
}

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

template <typename TKey, typename TVal, typename TLocMap>
typename multi_map<TKey, TVal, TLocMap>::const_range
multi_map<TKey, TVal, TLocMap>::operator[]( const TKey& key ) const
{
   multimap_value_type loc;
   if ( m_locHandlerPolicy(m_locations, key, loc) )
   {
      return const_range( m_data.begin() + loc.first, // start
                          m_data.begin() + loc.first + loc.second  // end
                         );
   }
   else
   {
      return const_range(m_data.end(), m_data.end());
   }
}

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

template <typename TKey, typename TVal, typename TLocMap>
void multi_map<TKey, TVal, TLocMap>::clear()
{
   m_data.clear();
   m_locations.clear();
}

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

}}

#endif // MULTI_MAP_CONTAINER_H__

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