yat/utility/MergeIterator.h

Code
Comments
Other
Rev Date Author Line
2995 13 Mar 13 peter 1 #ifndef theplu_yat_utility_merge_iterator
2995 13 Mar 13 peter 2 #define theplu_yat_utility_merge_iterator
2995 13 Mar 13 peter 3
2995 13 Mar 13 peter 4 // $Id$
2995 13 Mar 13 peter 5
2995 13 Mar 13 peter 6 /*
3792 12 Apr 19 peter 7   Copyright (C) 2013, 2015, 2016, 2018 Peter Johansson
2995 13 Mar 13 peter 8
2995 13 Mar 13 peter 9   This file is part of the yat library, http://dev.thep.lu.se/yat
2995 13 Mar 13 peter 10
2995 13 Mar 13 peter 11   The yat library is free software; you can redistribute it and/or
2995 13 Mar 13 peter 12   modify it under the terms of the GNU General Public License as
2995 13 Mar 13 peter 13   published by the Free Software Foundation; either version 3 of the
2995 13 Mar 13 peter 14   License, or (at your option) any later version.
2995 13 Mar 13 peter 15
2995 13 Mar 13 peter 16   The yat library is distributed in the hope that it will be useful,
2995 13 Mar 13 peter 17   but WITHOUT ANY WARRANTY; without even the implied warranty of
2995 13 Mar 13 peter 18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
2995 13 Mar 13 peter 19   General Public License for more details.
2995 13 Mar 13 peter 20
2995 13 Mar 13 peter 21   You should have received a copy of the GNU General Public License
2995 13 Mar 13 peter 22   along with yat. If not, see <http://www.gnu.org/licenses/>.
2995 13 Mar 13 peter 23 */
2995 13 Mar 13 peter 24
2995 13 Mar 13 peter 25 #include "stl_utility.h"
2995 13 Mar 13 peter 26 #include "yat/utility/yat_assert.h"
2995 13 Mar 13 peter 27
3509 21 Jul 16 peter 28 #include <boost/concept_check.hpp>
3509 21 Jul 16 peter 29 #include <boost/iterator/iterator_concepts.hpp>
2995 13 Mar 13 peter 30 #include <boost/iterator/iterator_facade.hpp>
3387 16 Mar 15 peter 31 #include <boost/iterator/iterator_traits.hpp>
2995 13 Mar 13 peter 32
2995 13 Mar 13 peter 33 #include <iterator>
2995 13 Mar 13 peter 34 #include <set>
2995 13 Mar 13 peter 35 #include <vector>
2995 13 Mar 13 peter 36
2995 13 Mar 13 peter 37 namespace theplu {
2995 13 Mar 13 peter 38 namespace yat {
2995 13 Mar 13 peter 39 namespace utility {
2995 13 Mar 13 peter 40
2995 13 Mar 13 peter 41   /**
2995 13 Mar 13 peter 42      \brief Iterate over several ranges as if ranges have been merged
2995 13 Mar 13 peter 43
2995 13 Mar 13 peter 44      MergeIterator is an \input_iterator that is created from several
3139 02 Dec 13 peter 45      ranges and will iterate over the elements in the ranges as if
3139 02 Dec 13 peter 46      ranges have been merged. Input ranges have to be sorted (as defined by
2995 13 Mar 13 peter 47      the \c Compare object) or behaviour is undefined. When
2995 13 Mar 13 peter 48      incremented, the iterator looks at next element in each range,
2995 13 Mar 13 peter 49      identifies the smallest element, and points at that.
3065 14 Jul 13 peter 50
3388 16 Mar 15 peter 51      Type Requirements:
3389 16 Mar 15 peter 52      - \c Base is a \readable_iterator
3389 16 Mar 15 peter 53      - \c Base is a \single_pass_iterator
3389 16 Mar 15 peter 54      - \c Compare models
3388 16 Mar 15 peter 55      <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
3388 16 Mar 15 peter 56      StrictWeakOrdering</a>
3388 16 Mar 15 peter 57
3065 14 Jul 13 peter 58      \since New in yat 0.11
2995 13 Mar 13 peter 59    */
2995 13 Mar 13 peter 60   template<
2995 13 Mar 13 peter 61     typename Base,
2995 13 Mar 13 peter 62     class Compare=std::less<typename std::iterator_traits<Base>::value_type>
2995 13 Mar 13 peter 63     >
2995 13 Mar 13 peter 64   class MergeIterator
2995 13 Mar 13 peter 65     : public boost::iterator_facade<
2995 13 Mar 13 peter 66     MergeIterator<Base, Compare>,
3387 16 Mar 15 peter 67     typename boost::iterator_value<Base>::type,
3387 16 Mar 15 peter 68     boost::single_pass_traversal_tag,
3387 16 Mar 15 peter 69     typename boost::iterator_reference<Base>::type
2995 13 Mar 13 peter 70     >
2995 13 Mar 13 peter 71   {
2995 13 Mar 13 peter 72   public:
2995 13 Mar 13 peter 73     /**
2995 13 Mar 13 peter 74        Creates an end-of-range iterator
2995 13 Mar 13 peter 75      */
2995 13 Mar 13 peter 76     MergeIterator(void) {};
2995 13 Mar 13 peter 77
2995 13 Mar 13 peter 78     /**
2995 13 Mar 13 peter 79        \brief Create MergeIterator
2995 13 Mar 13 peter 80
2995 13 Mar 13 peter 81        Create a MergeIterator that will iterate over ranges
2995 13 Mar 13 peter 82        [vec[0].first, vec[0].second), [vec[1].first, vec[1].second), ...
2995 13 Mar 13 peter 83
2995 13 Mar 13 peter 84        \see make_merge_iterator(const std::vector<std::pair<Base, Base> >&)
2995 13 Mar 13 peter 85      */
2995 13 Mar 13 peter 86     MergeIterator(const std::vector<std::pair<Base, Base> >& vec)
2995 13 Mar 13 peter 87     {  init(vec); };
2995 13 Mar 13 peter 88
2995 13 Mar 13 peter 89     /**
2995 13 Mar 13 peter 90        \brief Creates MergeIterator using \a comp as compare object.
2995 13 Mar 13 peter 91
2995 13 Mar 13 peter 92        Same as MergeIterator(2) but using \a comp rather than using a
2995 13 Mar 13 peter 93        default constructed Compare object.
2995 13 Mar 13 peter 94
2995 13 Mar 13 peter 95        \see
3065 14 Jul 13 peter 96        make_merge_iterator(const std::vector<std::pair<Base, Base> >&, const Compare&)
2995 13 Mar 13 peter 97      */
2995 13 Mar 13 peter 98     MergeIterator(const std::vector<std::pair<Base, Base> >& vec,
2995 13 Mar 13 peter 99                   const Compare& comp)
2995 13 Mar 13 peter 100     : data_(PairCompare(comp))
2995 13 Mar 13 peter 101     {  init(vec); }
2995 13 Mar 13 peter 102
2995 13 Mar 13 peter 103   private:
2995 13 Mar 13 peter 104     friend class boost::iterator_core_access;
2995 13 Mar 13 peter 105
2995 13 Mar 13 peter 106     typename MergeIterator<Base, Compare>::reference dereference(void) const;
2995 13 Mar 13 peter 107     bool equal(const MergeIterator& other) const;
2995 13 Mar 13 peter 108     void init(const std::vector<std::pair<Base,Base> >& v);
2995 13 Mar 13 peter 109     void increment(void);
2995 13 Mar 13 peter 110
2995 13 Mar 13 peter 111     class PairCompare
2995 13 Mar 13 peter 112     {
2995 13 Mar 13 peter 113     public:
2995 13 Mar 13 peter 114       PairCompare(void) {}
2995 13 Mar 13 peter 115       PairCompare(const Compare& c) : comp_(c) {}
2995 13 Mar 13 peter 116       bool operator()(const std::pair<Base, Base>& x,
2995 13 Mar 13 peter 117                       const std::pair<Base, Base>& y) const
2995 13 Mar 13 peter 118       {  return comp_(*x.first, *y.first);  }
2995 13 Mar 13 peter 119     private:
2995 13 Mar 13 peter 120       Compare comp_;
2995 13 Mar 13 peter 121     };
2995 13 Mar 13 peter 122
2995 13 Mar 13 peter 123     std::multiset<std::pair<Base, Base>, PairCompare> data_;
2995 13 Mar 13 peter 124   };
2995 13 Mar 13 peter 125
2995 13 Mar 13 peter 126   /**
2995 13 Mar 13 peter 127      Creates a MergeIterator that iterates over ranges defined in \a vec.
3065 14 Jul 13 peter 128
3065 14 Jul 13 peter 129      \relates MergeIterator
2995 13 Mar 13 peter 130    */
2995 13 Mar 13 peter 131   template<typename Base>
2995 13 Mar 13 peter 132   MergeIterator<Base>
2995 13 Mar 13 peter 133   make_merge_iterator(const std::vector<std::pair<Base, Base> >& vec)
2995 13 Mar 13 peter 134   {
2995 13 Mar 13 peter 135     return MergeIterator<Base>(vec);
2995 13 Mar 13 peter 136   }
2995 13 Mar 13 peter 137
2995 13 Mar 13 peter 138
2995 13 Mar 13 peter 139   /**
2995 13 Mar 13 peter 140      Creates a MergeIterator that iterates over ranges defined in \a
2995 13 Mar 13 peter 141      vec, using \a comp to compare elements.
3065 14 Jul 13 peter 142
3065 14 Jul 13 peter 143      \relates MergeIterator
2995 13 Mar 13 peter 144   */
2995 13 Mar 13 peter 145   template<typename Base, class Compare>
2995 13 Mar 13 peter 146   MergeIterator<Base, Compare>
2995 13 Mar 13 peter 147   make_merge_iterator(const std::vector<std::pair<Base, Base> >& vec,
2995 13 Mar 13 peter 148                       const Compare& comp)
2995 13 Mar 13 peter 149   {
2995 13 Mar 13 peter 150     return MergeIterator<Base, Compare>(vec, comp);
2995 13 Mar 13 peter 151   }
2995 13 Mar 13 peter 152
2995 13 Mar 13 peter 153
2995 13 Mar 13 peter 154
2995 13 Mar 13 peter 155   // template implementations
2995 13 Mar 13 peter 156
2995 13 Mar 13 peter 157   template<typename Base, class Compare>
2995 13 Mar 13 peter 158   typename MergeIterator<Base, Compare>::reference
2995 13 Mar 13 peter 159   MergeIterator<Base, Compare>::dereference(void) const
2995 13 Mar 13 peter 160   {
2995 13 Mar 13 peter 161     YAT_ASSERT(data_.size());
2995 13 Mar 13 peter 162     YAT_ASSERT(data_.begin()->first != data_.begin()->second);
2995 13 Mar 13 peter 163     return *data_.begin()->first;
2995 13 Mar 13 peter 164   }
2995 13 Mar 13 peter 165
2995 13 Mar 13 peter 166
2995 13 Mar 13 peter 167   template<typename Base, class Compare>
2995 13 Mar 13 peter 168   bool MergeIterator<Base, Compare>::equal(const MergeIterator& other) const
2995 13 Mar 13 peter 169   {
2995 13 Mar 13 peter 170     if (data_.empty() || other.data_.empty())
2995 13 Mar 13 peter 171       return data_.empty() == other.data_.empty();
2995 13 Mar 13 peter 172     return data_.begin()->first == other.data_.begin()->first;
2995 13 Mar 13 peter 173   }
2995 13 Mar 13 peter 174
2995 13 Mar 13 peter 175
2995 13 Mar 13 peter 176   template<typename Base, class Compare>
2995 13 Mar 13 peter 177   void
2995 13 Mar 13 peter 178   MergeIterator<Base,Compare>::init(const std::vector<std::pair<Base,Base> >& v)
2995 13 Mar 13 peter 179   {
3509 21 Jul 16 peter 180     BOOST_CONCEPT_ASSERT((boost_concepts::ReadableIterator<Base>));
3509 21 Jul 16 peter 181     BOOST_CONCEPT_ASSERT((boost_concepts::SinglePassIterator<Base>));
2995 13 Mar 13 peter 182     for (size_t i=0; i<v.size(); ++i)
2995 13 Mar 13 peter 183       if (v[i].first != v[i].second)
2995 13 Mar 13 peter 184         data_.insert(v[i]);
2995 13 Mar 13 peter 185   }
2995 13 Mar 13 peter 186
2995 13 Mar 13 peter 187
2995 13 Mar 13 peter 188   template<typename Base, class Compare>
2995 13 Mar 13 peter 189   void MergeIterator<Base, Compare>::increment(void)
2995 13 Mar 13 peter 190   {
2995 13 Mar 13 peter 191     if (data_.empty())
2995 13 Mar 13 peter 192       return;
2995 13 Mar 13 peter 193     // store first range
2995 13 Mar 13 peter 194     std::pair<Base, Base> tmp = *data_.begin();
2995 13 Mar 13 peter 195     // remove first range from set of ranges
2995 13 Mar 13 peter 196     data_.erase(data_.begin());
2995 13 Mar 13 peter 197     // iterate the first range and if not end-of-range, insert the
2995 13 Mar 13 peter 198     // range back into set of ranges
2995 13 Mar 13 peter 199     if (++(tmp.first) != tmp.second)
3729 10 Apr 18 peter 200       // tmp was first in data_ prior incrementation, so it's a good
3729 10 Apr 18 peter 201       // guess that tmp is first also after the incrementation
3729 10 Apr 18 peter 202       data_.insert(data_.begin(), tmp);
2995 13 Mar 13 peter 203   }
2995 13 Mar 13 peter 204
2995 13 Mar 13 peter 205 }}}
2995 13 Mar 13 peter 206 #endif

Generated on Sat Oct 14 02:24:53 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)