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      179534 :         group_key_less()
      34      179534 :         {}
      35      179534 :         group_key_less(const GroupCompare &group_compare): _group_compare(group_compare)
      36      179534 :         {}
      37       18343 :         bool operator ()(const typename group_key<Group>::type &key1, const typename group_key<Group>::type &key2) const
      38             :         {
      39       18343 :           if(key1.first != key2.first) return key1.first < key2.first;
      40       18343 :           if(key1.first != grouped_slots) return false;
      41           0 :           return _group_compare(key1.second.get(), key2.second.get());
      42       18343 :         }
      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      179534 :         grouped_list(const group_key_compare_type &group_key_compare):
      67       89767 :           _group_key_compare(group_key_compare)
      68      179534 :         {}
      69      179534 :         grouped_list(const grouped_list &other): _list(other._list),
      70       89767 :           _group_map(other._group_map), _group_key_compare(other._group_key_compare)
      71       89767 :         {
      72             :           // fix up _group_map
      73       89767 :           typename map_type::const_iterator other_map_it;
      74       89767 :           typename list_type::iterator this_list_it = _list.begin();
      75       89767 :           typename map_type::iterator this_map_it = _group_map.begin();
      76      179534 :           for(other_map_it = other._group_map.begin();
      77       89767 :             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      179534 :         }
      93     2095625 :         iterator begin()
      94             :         {
      95     2095625 :           return _list.begin();
      96             :         }
      97     5704306 :         iterator end()
      98             :         {
      99     5704306 :           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         343 :         iterator upper_bound(const group_key_type &key)
     107             :         {
     108         343 :           map_iterator map_it = _group_map.upper_bound(key);
     109         343 :           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       29777 :         void push_back(const group_key_type &key, const ValueType &value)
     124             :         {
     125       29777 :           map_iterator map_it;
     126       29777 :           if(key.first == back_ungrouped_slots)
     127             :           {// optimization
     128       29777 :             map_it = _group_map.end();
     129       29777 :           }else
     130             :           {
     131           0 :             map_it = _group_map.upper_bound(key);
     132             :           }
     133       29777 :           m_insert(map_it, key, value);
     134       29777 :         }
     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        1066 :         iterator erase(const group_key_type &key, const iterator &it)
     147             :         {
     148        1066 :           BOOST_ASSERT(it != _list.end());
     149        1066 :           map_iterator map_it = _group_map.lower_bound(key);
     150        1066 :           BOOST_ASSERT(map_it != _group_map.end());
     151        1066 :           BOOST_ASSERT(weakly_equivalent(map_it->first, key));
     152        1066 :           if(map_it->second == it)
     153             :           {
     154         343 :             iterator next = it;
     155         343 :             ++next;
     156             :             // if next is in same group
     157         343 :             if(next != upper_bound(key))
     158             :             {
     159           0 :               _group_map[key] = next;
     160           0 :             }else
     161             :             {
     162         343 :               _group_map.erase(map_it);
     163             :             }
     164         343 :           }
     165        1066 :           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        6000 :         bool weakly_equivalent(const group_key_type &arg1, const group_key_type &arg2)
     177             :         {
     178        6000 :           if(_group_key_compare(arg1, arg2)) return false;
     179        6000 :           if(_group_key_compare(arg2, arg1)) return false;
     180        6000 :           return true;
     181        6000 :         }
     182       29777 :         void m_insert(const map_iterator &map_it, const group_key_type &key, const ValueType &value)
     183             :         {
     184       29777 :           iterator list_it = get_list_iterator(map_it);
     185       29777 :           iterator new_it = _list.insert(list_it, value);
     186       29777 :           if(map_it != _group_map.end() && weakly_equivalent(key, map_it->first))
     187             :           {
     188           0 :             _group_map.erase(map_it);
     189           0 :           }
     190       29777 :           map_iterator lower_bound_it = _group_map.lower_bound(key);
     191       29777 :           if(lower_bound_it == _group_map.end() ||
     192        4934 :             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       24843 :             _group_map.insert(typename map_type::value_type(key, new_it));
     198       24843 :           }
     199       29777 :         }
     200       30120 :         iterator get_list_iterator(const const_map_iterator &map_it)
     201             :         {
     202       30120 :           iterator list_it;
     203       30120 :           if(map_it == _group_map.end())
     204             :           {
     205       30120 :             list_it = _list.end();
     206       30120 :           }else
     207             :           {
     208           0 :             list_it = map_it->second;
     209             :           }
     210       30120 :           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