Chris@16: // Boost.Signals2 library
Chris@16: 
Chris@16: // Copyright Frank Mori Hess 2007-2008.
Chris@16: // Use, modification and
Chris@16: // distribution is subject to the Boost Software License, Version
Chris@16: // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: // For more information, see http://www.boost.org
Chris@16: 
Chris@16: #ifndef BOOST_SIGNALS2_SLOT_GROUPS_HPP
Chris@16: #define BOOST_SIGNALS2_SLOT_GROUPS_HPP
Chris@16: 
Chris@16: #include <boost/signals2/connection.hpp>
Chris@16: #include <boost/optional.hpp>
Chris@16: #include <list>
Chris@16: #include <map>
Chris@16: #include <utility>
Chris@16: 
Chris@16: namespace boost {
Chris@16:   namespace signals2 {
Chris@16:     namespace detail {
Chris@16:       enum slot_meta_group {front_ungrouped_slots, grouped_slots, back_ungrouped_slots};
Chris@16:       template<typename Group>
Chris@16:       struct group_key
Chris@16:       {
Chris@16:         typedef std::pair<enum slot_meta_group, boost::optional<Group> > type;
Chris@16:       };
Chris@16:       template<typename Group, typename GroupCompare>
Chris@16:       class group_key_less
Chris@16:       {
Chris@16:       public:
Chris@16:         group_key_less()
Chris@16:         {}
Chris@16:         group_key_less(const GroupCompare &group_compare): _group_compare(group_compare)
Chris@16:         {}
Chris@16:         bool operator ()(const typename group_key<Group>::type &key1, const typename group_key<Group>::type &key2) const
Chris@16:         {
Chris@16:           if(key1.first != key2.first) return key1.first < key2.first;
Chris@16:           if(key1.first != grouped_slots) return false;
Chris@16:           return _group_compare(key1.second.get(), key2.second.get());
Chris@16:         }
Chris@16:       private:
Chris@16:         GroupCompare _group_compare;
Chris@16:       };
Chris@16:       template<typename Group, typename GroupCompare, typename ValueType>
Chris@16:       class grouped_list
Chris@16:       {
Chris@16:       public:
Chris@16:         typedef group_key_less<Group, GroupCompare> group_key_compare_type;
Chris@16:       private:
Chris@16:         typedef std::list<ValueType> list_type;
Chris@16:         typedef std::map
Chris@16:           <
Chris@16:             typename group_key<Group>::type,
Chris@16:             typename list_type::iterator,
Chris@16:             group_key_compare_type
Chris@16:           > map_type;
Chris@16:         typedef typename map_type::iterator map_iterator;
Chris@16:         typedef typename map_type::const_iterator const_map_iterator;
Chris@16:       public:
Chris@16:         typedef typename list_type::iterator iterator;
Chris@16:         typedef typename list_type::const_iterator const_iterator;
Chris@16:         typedef typename group_key<Group>::type group_key_type;
Chris@16: 
Chris@16:         grouped_list(const group_key_compare_type &group_key_compare):
Chris@16:           _group_key_compare(group_key_compare)
Chris@16:         {}
Chris@16:         grouped_list(const grouped_list &other): _list(other._list),
Chris@16:           _group_map(other._group_map), _group_key_compare(other._group_key_compare)
Chris@16:         {
Chris@16:           // fix up _group_map
Chris@16:           typename map_type::const_iterator other_map_it;
Chris@16:           typename list_type::iterator this_list_it = _list.begin();
Chris@16:           typename map_type::iterator this_map_it = _group_map.begin();
Chris@16:           for(other_map_it = other._group_map.begin();
Chris@16:             other_map_it != other._group_map.end();
Chris@16:             ++other_map_it, ++this_map_it)
Chris@16:           {
Chris@16:             BOOST_ASSERT(this_map_it != _group_map.end());
Chris@16:             this_map_it->second = this_list_it;
Chris@16:             typename list_type::const_iterator other_list_it = other.get_list_iterator(other_map_it);
Chris@16:             typename map_type::const_iterator other_next_map_it = other_map_it;
Chris@16:             ++other_next_map_it;
Chris@16:             typename list_type::const_iterator other_next_list_it = other.get_list_iterator(other_next_map_it);
Chris@16:             while(other_list_it != other_next_list_it)
Chris@16:             {
Chris@16:               ++other_list_it;
Chris@16:               ++this_list_it;
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16:         iterator begin()
Chris@16:         {
Chris@16:           return _list.begin();
Chris@16:         }
Chris@16:         iterator end()
Chris@16:         {
Chris@16:           return _list.end();
Chris@16:         }
Chris@16:         iterator lower_bound(const group_key_type &key)
Chris@16:         {
Chris@16:           map_iterator map_it = _group_map.lower_bound(key);
Chris@16:           return get_list_iterator(map_it);
Chris@16:         }
Chris@16:         iterator upper_bound(const group_key_type &key)
Chris@16:         {
Chris@16:           map_iterator map_it = _group_map.upper_bound(key);
Chris@16:           return get_list_iterator(map_it);
Chris@16:         }
Chris@16:         void push_front(const group_key_type &key, const ValueType &value)
Chris@16:         {
Chris@16:           map_iterator map_it;
Chris@16:           if(key.first == front_ungrouped_slots)
Chris@16:           {// optimization
Chris@16:             map_it = _group_map.begin();
Chris@16:           }else
Chris@16:           {
Chris@16:             map_it = _group_map.lower_bound(key);
Chris@16:           }
Chris@16:           m_insert(map_it, key, value);
Chris@16:         }
Chris@16:         void push_back(const group_key_type &key, const ValueType &value)
Chris@16:         {
Chris@16:           map_iterator map_it;
Chris@16:           if(key.first == back_ungrouped_slots)
Chris@16:           {// optimization
Chris@16:             map_it = _group_map.end();
Chris@16:           }else
Chris@16:           {
Chris@16:             map_it = _group_map.upper_bound(key);
Chris@16:           }
Chris@16:           m_insert(map_it, key, value);
Chris@16:         }
Chris@16:         void erase(const group_key_type &key)
Chris@16:         {
Chris@16:           map_iterator map_it = _group_map.lower_bound(key);
Chris@16:           iterator begin_list_it = get_list_iterator(map_it);
Chris@16:           iterator end_list_it = upper_bound(key);
Chris@16:           if(begin_list_it != end_list_it)
Chris@16:           {
Chris@16:             _list.erase(begin_list_it, end_list_it);
Chris@16:             _group_map.erase(map_it);
Chris@16:           }
Chris@16:         }
Chris@16:         iterator erase(const group_key_type &key, const iterator &it)
Chris@16:         {
Chris@16:           BOOST_ASSERT(it != _list.end());
Chris@16:           map_iterator map_it = _group_map.lower_bound(key);
Chris@16:           BOOST_ASSERT(map_it != _group_map.end());
Chris@16:           BOOST_ASSERT(weakly_equivalent(map_it->first, key));
Chris@16:           if(map_it->second == it)
Chris@16:           {
Chris@16:             iterator next = it;
Chris@16:             ++next;
Chris@16:             // if next is in same group
Chris@16:             if(next != upper_bound(key))
Chris@16:             {
Chris@16:               _group_map[key] = next;
Chris@16:             }else
Chris@16:             {
Chris@16:               _group_map.erase(map_it);
Chris@16:             }
Chris@16:           }
Chris@16:           return _list.erase(it);
Chris@16:         }
Chris@16:         void clear()
Chris@16:         {
Chris@16:           _list.clear();
Chris@16:           _group_map.clear();
Chris@16:         }
Chris@16:       private:
Chris@16:         /* Suppress default assignment operator, since it has the wrong semantics. */
Chris@16:         grouped_list& operator=(const grouped_list &other);
Chris@16: 
Chris@16:         bool weakly_equivalent(const group_key_type &arg1, const group_key_type &arg2)
Chris@16:         {
Chris@16:           if(_group_key_compare(arg1, arg2)) return false;
Chris@16:           if(_group_key_compare(arg2, arg1)) return false;
Chris@16:           return true;
Chris@16:         }
Chris@16:         void m_insert(const map_iterator &map_it, const group_key_type &key, const ValueType &value)
Chris@16:         {
Chris@16:           iterator list_it = get_list_iterator(map_it);
Chris@16:           iterator new_it = _list.insert(list_it, value);
Chris@16:           if(map_it != _group_map.end() && weakly_equivalent(key, map_it->first))
Chris@16:           {
Chris@16:             _group_map.erase(map_it);
Chris@16:           }
Chris@16:           map_iterator lower_bound_it = _group_map.lower_bound(key);
Chris@16:           if(lower_bound_it == _group_map.end() ||
Chris@16:             weakly_equivalent(lower_bound_it->first, key) == false)
Chris@16:           {
Chris@16:             /* doing the following instead of just
Chris@16:               _group_map[key] = new_it;
Chris@16:               to avoid bogus error when enabling checked iterators with g++ */
Chris@16:             _group_map.insert(typename map_type::value_type(key, new_it));
Chris@16:           }
Chris@16:         }
Chris@16:         iterator get_list_iterator(const const_map_iterator &map_it)
Chris@16:         {
Chris@16:           iterator list_it;
Chris@16:           if(map_it == _group_map.end())
Chris@16:           {
Chris@16:             list_it = _list.end();
Chris@16:           }else
Chris@16:           {
Chris@16:             list_it = map_it->second;
Chris@16:           }
Chris@16:           return list_it;
Chris@16:         }
Chris@16:         const_iterator get_list_iterator(const const_map_iterator &map_it) const
Chris@16:         {
Chris@16:           const_iterator list_it;
Chris@16:           if(map_it == _group_map.end())
Chris@16:           {
Chris@16:             list_it = _list.end();
Chris@16:           }else
Chris@16:           {
Chris@16:             list_it = map_it->second;
Chris@16:           }
Chris@16:           return list_it;
Chris@16:         }
Chris@16: 
Chris@16:         list_type _list;
Chris@16:         // holds iterators to first list item in each group
Chris@16:         map_type _group_map;
Chris@16:         group_key_compare_type _group_key_compare;
Chris@16:       };
Chris@16:     } // end namespace detail
Chris@16:     enum connect_position { at_back, at_front };
Chris@16:   } // end namespace signals2
Chris@16: } // end namespace boost
Chris@16: 
Chris@16: #endif // BOOST_SIGNALS2_SLOT_GROUPS_HPP