Line data    Source code

       1             : // Boost.Signals2 library
       2             : 
       3             : // Copyright Frank Mori Hess 2007-2008.
       4             : // Use, modification and
       5             : // distribution is subject to the Boost Software License, Version
       6             : // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : 
       9             : // For more information, see http://www.boost.org
      10             : 
      11             : #ifndef BOOST_SIGNALS2_SLOT_GROUPS_HPP
      12             : #define BOOST_SIGNALS2_SLOT_GROUPS_HPP
      13             : 
      14             : #include <boost/signals2/connection.hpp>
      15             : #include <boost/optional.hpp>
      16             : #include <list>
      17             : #include <map>
      18             : #include <utility>
      19             : 
      20             : namespace boost {
      21             :   namespace signals2 {
      22             :     namespace detail {
      23             :       enum slot_meta_group {front_ungrouped_slots, grouped_slots, back_ungrouped_slots};
      24             :       template<typename Group>
      25             :       struct group_key
      26             :       {
      27             :         typedef std::pair<enum slot_meta_group, boost::optional<Group> > type;
      28             :       };
      29             :       template<typename Group, typename GroupCompare>
      30             :       class group_key_less
      31             :       {
      32             :       public:
      33        6916 :         group_key_less()
      34        6916 :         {}
      35        6916 :         group_key_less(const GroupCompare &group_compare): _group_compare(group_compare)
      36        6916 :         {}
      37        1344 :         bool operator ()(const typename group_key<Group>::type &key1, const typename group_key<Group>::type &key2) const
      38             :         {
      39        1344 :           if(key1.first != key2.first) return key1.first < key2.first;
      40        1344 :           if(key1.first != grouped_slots) return false;
      41           0 :           return _group_compare(key1.second.get(), key2.second.get());
      42        1344 :         }
      43             :       private:
      44             :         GroupCompare _group_compare;
      45             :       };
      46             :       template<typename Group, typename GroupCompare, typename ValueType>
      47             :       class grouped_list
      48             :       {
      49             :       public:
      50             :         typedef group_key_less<Group, GroupCompare> group_key_compare_type;
      51             :       private:
      52             :         typedef std::list<ValueType> list_type;
      53             :         typedef std::map
      54             :           <
      55             :             typename group_key<Group>::type,
      56             :             typename list_type::iterator,
      57             :             group_key_compare_type
      58             :           > map_type;
      59             :         typedef typename map_type::iterator map_iterator;
      60             :         typedef typename map_type::const_iterator const_map_iterator;
      61             :       public:
      62             :         typedef typename list_type::iterator iterator;
      63             :         typedef typename list_type::const_iterator const_iterator;
      64             :         typedef typename group_key<Group>::type group_key_type;
      65             : 
      66        6916 :         grouped_list(const group_key_compare_type &group_key_compare):
      67        3458 :           _group_key_compare(group_key_compare)
      68        6916 :         {}
      69        6916 :         grouped_list(const grouped_list &other): _list(other._list),
      70        3458 :           _group_map(other._group_map), _group_key_compare(other._group_key_compare)
      71        3458 :         {
      72             :           // fix up _group_map
      73        3458 :           typename map_type::const_iterator other_map_it;
      74        3458 :           typename list_type::iterator this_list_it = _list.begin();
      75        3458 :           typename map_type::iterator this_map_it = _group_map.begin();
      76        6916 :           for(other_map_it = other._group_map.begin();
      77        3458 :             other_map_it != other._group_map.end();
      78           0 :             ++other_map_it, ++this_map_it)
      79             :           {
      80           0 :             BOOST_ASSERT(this_map_it != _group_map.end());
      81           0 :             this_map_it->second = this_list_it;
      82           0 :             typename list_type::const_iterator other_list_it = other.get_list_iterator(other_map_it);
      83           0 :             typename map_type::const_iterator other_next_map_it = other_map_it;
      84           0 :             ++other_next_map_it;
      85           0 :             typename list_type::const_iterator other_next_list_it = other.get_list_iterator(other_next_map_it);
      86           0 :             while(other_list_it != other_next_list_it)
      87             :             {
      88           0 :               ++other_list_it;
      89           0 :               ++this_list_it;
      90             :             }
      91           0 :           }
      92        6916 :         }
      93      165444 :         iterator begin()
      94             :         {
      95      165444 :           return _list.begin();
      96             :         }
      97      417181 :         iterator end()
      98             :         {
      99      417181 :           return _list.end();
     100             :         }
     101             :         iterator lower_bound(const group_key_type &key)
     102             :         {
     103             :           map_iterator map_it = _group_map.lower_bound(key);
     104             :           return get_list_iterator(map_it);
     105             :         }
     106         336 :         iterator upper_bound(const group_key_type &key)
     107             :         {
     108         336 :           map_iterator map_it = _group_map.upper_bound(key);
     109         336 :           return get_list_iterator(map_it);
     110             :         }
     111           0 :         void push_front(const group_key_type &key, const ValueType &value)
     112             :         {
     113           0 :           map_iterator map_it;
     114           0 :           if(key.first == front_ungrouped_slots)
     115             :           {// optimization
     116           0 :             map_it = _group_map.begin();
     117           0 :           }else
     118             :           {
     119           0 :             map_it = _group_map.lower_bound(key);
     120             :           }
     121           0 :           m_insert(map_it, key, value);
     122           0 :         }
     123         712 :         void push_back(const group_key_type &key, const ValueType &value)
     124             :         {
     125         712 :           map_iterator map_it;
     126         712 :           if(key.first == back_ungrouped_slots)
     127             :           {// optimization
     128         712 :             map_it = _group_map.end();
     129         712 :           }else
     130             :           {
     131           0 :             map_it = _group_map.upper_bound(key);
     132             :           }
     133         712 :           m_insert(map_it, key, value);
     134         712 :         }
     135             :         void erase(const group_key_type &key)
     136             :         {
     137             :           map_iterator map_it = _group_map.lower_bound(key);
     138             :           iterator begin_list_it = get_list_iterator(map_it);
     139             :           iterator end_list_it = upper_bound(key);
     140             :           if(begin_list_it != end_list_it)
     141             :           {
     142             :             _list.erase(begin_list_it, end_list_it);
     143             :             _group_map.erase(map_it);
     144             :           }
     145             :         }
     146         336 :         iterator erase(const group_key_type &key, const iterator &it)
     147             :         {
     148         336 :           BOOST_ASSERT(it != _list.end());
     149         336 :           map_iterator map_it = _group_map.lower_bound(key);
     150         336 :           BOOST_ASSERT(map_it != _group_map.end());
     151         336 :           BOOST_ASSERT(weakly_equivalent(map_it->first, key));
     152         336 :           if(map_it->second == it)
     153             :           {
     154         336 :             iterator next = it;
     155         336 :             ++next;
     156             :             // if next is in same group
     157         336 :             if(next != upper_bound(key))
     158             :             {
     159           0 :               _group_map[key] = next;
     160           0 :             }else
     161             :             {
     162         336 :               _group_map.erase(map_it);
     163             :             }
     164         336 :           }
     165         336 :           return _list.erase(it);
     166             :         }
     167             :         void clear()
     168             :         {
     169             :           _list.clear();
     170             :           _group_map.clear();
     171             :         }
     172             :       private:
     173             :         /* Suppress default assignment operator, since it has the wrong semantics. */
     174             :         grouped_list& operator=(const grouped_list &other);
     175             : 
     176         336 :         bool weakly_equivalent(const group_key_type &arg1, const group_key_type &arg2)
     177             :         {
     178         336 :           if(_group_key_compare(arg1, arg2)) return false;
     179         336 :           if(_group_key_compare(arg2, arg1)) return false;
     180         336 :           return true;
     181         336 :         }
     182         712 :         void m_insert(const map_iterator &map_it, const group_key_type &key, const ValueType &value)
     183             :         {
     184         712 :           iterator list_it = get_list_iterator(map_it);
     185         712 :           iterator new_it = _list.insert(list_it, value);
     186         712 :           if(map_it != _group_map.end() && weakly_equivalent(key, map_it->first))
     187             :           {
     188           0 :             _group_map.erase(map_it);
     189           0 :           }
     190         712 :           map_iterator lower_bound_it = _group_map.lower_bound(key);
     191         712 :           if(lower_bound_it == _group_map.end() ||
     192           0 :             weakly_equivalent(lower_bound_it->first, key) == false)
     193             :           {
     194             :             /* doing the following instead of just
     195             :               _group_map[key] = new_it;
     196             :               to avoid bogus error when enabling checked iterators with g++ */
     197         712 :             _group_map.insert(typename map_type::value_type(key, new_it));
     198         712 :           }
     199         712 :         }
     200        1048 :         iterator get_list_iterator(const const_map_iterator &map_it)
     201             :         {
     202        1048 :           iterator list_it;
     203        1048 :           if(map_it == _group_map.end())
     204             :           {
     205        1048 :             list_it = _list.end();
     206        1048 :           }else
     207             :           {
     208           0 :             list_it = map_it->second;
     209             :           }
     210        1048 :           return list_it;
     211             :         }
     212           0 :         const_iterator get_list_iterator(const const_map_iterator &map_it) const
     213             :         {
     214           0 :           const_iterator list_it;
     215           0 :           if(map_it == _group_map.end())
     216             :           {
     217           0 :             list_it = _list.end();
     218           0 :           }else
     219             :           {
     220           0 :             list_it = map_it->second;
     221             :           }
     222           0 :           return list_it;
     223             :         }
     224             : 
     225             :         list_type _list;
     226             :         // holds iterators to first list item in each group
     227             :         map_type _group_map;
     228             :         group_key_compare_type _group_key_compare;
     229             :       };
     230             :     } // end namespace detail
     231             :     enum connect_position { at_back, at_front };
     232             :   } // end namespace signals2
     233             : } // end namespace boost
     234             : 
     235             : #endif // BOOST_SIGNALS2_SLOT_GROUPS_HPP