signals2/detail/slot_groups.hpp

0001 // Boost.Signals2 library
0002
0003 // Copyright Frank Mori Hess 2007-2008.
0004 // Use, modification and
0005 // distribution is subject to the Boost Software License, Version
0006 // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 // For more information, see http://www.boost.org
0010
0011 #ifndef BOOST_SIGNALS2_SLOT_GROUPS_HPP
0012 #define BOOST_SIGNALS2_SLOT_GROUPS_HPP
0013
0014 #include <boost/signals2/connection.hpp>
0015 #include <boost/optional.hpp>
0016 #include <list>
0017 #include <map>
0018 #include <utility>
0019
0020 namespace boost {
0021   namespace signals2 {
0022     namespace detail {
0023       enum slot_meta_group {front_ungrouped_slots, grouped_slots, back_ungrouped_slots};
0024       template<typename Group>
0025       struct group_key
0026       {
0027         typedef std::pair<enum slot_meta_group, boost::optional<Group> > type;
0028       };
0029       template<typename Group, typename GroupCompare>
0030       class group_key_less
0031       {
0032       public:
0033         group_key_less()
0034         {}
0035         group_key_less(const GroupCompare &group_compare): _group_compare(group_compare)
0036         {}
0037         bool operator ()(const typename group_key<Group>::type &key1, const typename group_key<Group>::type &key2) const
0038         {
0039           if(key1.first != key2.first) return key1.first < key2.first;
0040           if(key1.first != grouped_slots) return false;
0041           return _group_compare(key1.second.get(), key2.second.get());
0042         }
0043       private:
0044         GroupCompare _group_compare;
0045       };
0046       template<typename Group, typename GroupCompare, typename ValueType>
0047       class grouped_list
0048       {
0049       public:
0050         typedef group_key_less<Group, GroupCompare> group_key_compare_type;
0051       private:
0052         typedef std::list<ValueType> list_type;
0053         typedef std::map
0054           <
0055             typename group_key<Group>::type,
0056             typename list_type::iterator,
0057             group_key_compare_type
0058           > map_type;
0059         typedef typename map_type::iterator map_iterator;
0060         typedef typename map_type::const_iterator const_map_iterator;
0061       public:
0062         typedef typename list_type::iterator iterator;
0063         typedef typename list_type::const_iterator const_iterator;
0064         typedef typename group_key<Group>::type group_key_type;
0065
0066         grouped_list(const group_key_compare_type &group_key_compare):
0067           _group_key_compare(group_key_compare)
0068         {}
0069         grouped_list(const grouped_list &other): _list(other._list),
0070           _group_map(other._group_map), _group_key_compare(other._group_key_compare)
0071         {
0072           // fix up _group_map
0073           typename map_type::const_iterator other_map_it;
0074           typename list_type::iterator this_list_it = _list.begin();
0075           typename map_type::iterator this_map_it = _group_map.begin();
0076           for(other_map_it = other._group_map.begin();
0077             other_map_it != other._group_map.end();
0078             ++other_map_it, ++this_map_it)
0079           {
0080             BOOST_ASSERT(this_map_it != _group_map.end());
0081             this_map_it->second = this_list_it;
0082             typename list_type::const_iterator other_list_it = other.get_list_iterator(other_map_it);
0083             typename map_type::const_iterator other_next_map_it = other_map_it;
0084             ++other_next_map_it;
0085             typename list_type::const_iterator other_next_list_it = other.get_list_iterator(other_next_map_it);
0086             while(other_list_it != other_next_list_it)
0087             {
0088               ++other_list_it;
0089               ++this_list_it;
0090             }
0091           }
0092         }
0093         iterator begin()
0094         {
0095           return _list.begin();
0096         }
0097         iterator end()
0098         {
0099           return _list.end();
0100         }
0101         iterator lower_bound(const group_key_type &key)
0102         {
0103           map_iterator map_it = _group_map.lower_bound(key);
0104           return get_list_iterator(map_it);
0105         }
0106         iterator upper_bound(const group_key_type &key)
0107         {
0108           map_iterator map_it = _group_map.upper_bound(key);
0109           return get_list_iterator(map_it);
0110         }
0111         void push_front(const group_key_type &key, const ValueType &value)
0112         {
0113           map_iterator map_it;
0114           if(key.first == front_ungrouped_slots)
0115           {// optimization
0116             map_it = _group_map.begin();
0117           }else
0118           {
0119             map_it = _group_map.lower_bound(key);
0120           }
0121           m_insert(map_it, key, value);
0122         }
0123         void push_back(const group_key_type &key, const ValueType &value)
0124         {
0125           map_iterator map_it;
0126           if(key.first == back_ungrouped_slots)
0127           {// optimization
0128             map_it = _group_map.end();
0129           }else
0130           {
0131             map_it = _group_map.upper_bound(key);
0132           }
0133           m_insert(map_it, key, value);
0134         }
0135         void erase(const group_key_type &key)
0136         {
0137           map_iterator map_it = _group_map.lower_bound(key);
0138           iterator begin_list_it = get_list_iterator(map_it);
0139           iterator end_list_it = upper_bound(key);
0140           if(begin_list_it != end_list_it)
0141           {
0142             _list.erase(begin_list_it, end_list_it);
0143             _group_map.erase(map_it);
0144           }
0145         }
0146         iterator erase(const group_key_type &key, const iterator &it)
0147         {
0148           BOOST_ASSERT(it != _list.end());
0149           map_iterator map_it = _group_map.lower_bound(key);
0150           BOOST_ASSERT(map_it != _group_map.end());
0151           BOOST_ASSERT(weakly_equivalent(map_it->first, key));
0152           if(map_it->second == it)
0153           {
0154             iterator next = it;
0155             ++next;
0156             // if next is in same group
0157             if(next != upper_bound(key))
0158             {
0159               _group_map[key] = next;
0160             }else
0161             {
0162               _group_map.erase(map_it);
0163             }
0164           }
0165           return _list.erase(it);
0166         }
0167         void clear()
0168         {
0169           _list.clear();
0170           _group_map.clear();
0171         }
0172       private:
0173         /* Suppress default assignment operator, since it has the wrong semantics. */
0174         grouped_list& operator=(const grouped_list &other);
0175
0176         bool weakly_equivalent(const group_key_type &arg1, const group_key_type &arg2)
0177         {
0178           if(_group_key_compare(arg1, arg2)) return false;
0179           if(_group_key_compare(arg2, arg1)) return false;
0180           return true;
0181         }
0182         void m_insert(const map_iterator &map_it, const group_key_type &key, const ValueType &value)
0183         {
0184           iterator list_it = get_list_iterator(map_it);
0185           iterator new_it = _list.insert(list_it, value);
0186           if(map_it != _group_map.end() && weakly_equivalent(key, map_it->first))
0187           {
0188             _group_map.erase(map_it);
0189           }
0190           map_iterator lower_bound_it = _group_map.lower_bound(key);
0191           if(lower_bound_it == _group_map.end() ||
0192             weakly_equivalent(lower_bound_it->first, key) == false)
0193           {
0194             /* doing the following instead of just
0195               _group_map[key] = new_it;
0196               to avoid bogus error when enabling checked iterators with g++ */
0197             _group_map.insert(typename map_type::value_type(key, new_it));
0198           }
0199         }
0200         iterator get_list_iterator(const const_map_iterator &map_it)
0201         {
0202           iterator list_it;
0203           if(map_it == _group_map.end())
0204           {
0205             list_it = _list.end();
0206           }else
0207           {
0208             list_it = map_it->second;
0209           }
0210           return list_it;
0211         }
0212         const_iterator get_list_iterator(const const_map_iterator &map_it) const
0213         {
0214           const_iterator list_it;
0215           if(map_it == _group_map.end())
0216           {
0217             list_it = _list.end();
0218           }else
0219           {
0220             list_it = map_it->second;
0221           }
0222           return list_it;
0223         }
0224
0225         list_type _list;
0226         // holds iterators to first list item in each group
0227         map_type _group_map;
0228         group_key_compare_type _group_key_compare;
0229       };
0230     } // end namespace detail
0231     enum connect_position { at_back, at_front };
0232   } // end namespace signals2
0233 } // end namespace boost
0234
0235 #endif // BOOST_SIGNALS2_SLOT_GROUPS_HPP