yat  0.21pre
MergeIterator.h
1 #ifndef theplu_yat_utility_merge_iterator
2 #define theplu_yat_utility_merge_iterator
3 
4 // $Id: MergeIterator.h 3792 2019-04-12 07:15:09Z peter $
5 
6 /*
7  Copyright (C) 2013, 2015, 2016, 2018 Peter Johansson
8 
9  This file is part of the yat library, http://dev.thep.lu.se/yat
10 
11  The yat library is free software; you can redistribute it and/or
12  modify it under the terms of the GNU General Public License as
13  published by the Free Software Foundation; either version 3 of the
14  License, or (at your option) any later version.
15 
16  The yat library is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  General Public License for more details.
20 
21  You should have received a copy of the GNU General Public License
22  along with yat. If not, see <http://www.gnu.org/licenses/>.
23 */
24 
25 #include "stl_utility.h"
26 #include "yat/utility/yat_assert.h"
27 
28 #include <boost/concept_check.hpp>
29 #include <boost/iterator/iterator_concepts.hpp>
30 #include <boost/iterator/iterator_facade.hpp>
31 #include <boost/iterator/iterator_traits.hpp>
32 
33 #include <iterator>
34 #include <set>
35 #include <vector>
36 
37 namespace theplu {
38 namespace yat {
39 namespace utility {
40 
60  template<
61  typename Base,
62  class Compare=std::less<typename std::iterator_traits<Base>::value_type>
63  >
65  : public boost::iterator_facade<
66  MergeIterator<Base, Compare>,
67  typename boost::iterator_value<Base>::type,
68  boost::single_pass_traversal_tag,
69  typename boost::iterator_reference<Base>::type
70  >
71  {
72  public:
76  MergeIterator(void) {};
77 
86  MergeIterator(const std::vector<std::pair<Base, Base> >& vec)
87  { init(vec); };
88 
98  MergeIterator(const std::vector<std::pair<Base, Base> >& vec,
99  const Compare& comp)
100  : data_(PairCompare(comp))
101  { init(vec); }
102 
103  private:
104  friend class boost::iterator_core_access;
105 
106  typename MergeIterator<Base, Compare>::reference dereference(void) const;
107  bool equal(const MergeIterator& other) const;
108  void init(const std::vector<std::pair<Base,Base> >& v);
109  void increment(void);
110 
111  class PairCompare
112  {
113  public:
114  PairCompare(void) {}
115  PairCompare(const Compare& c) : comp_(c) {}
116  bool operator()(const std::pair<Base, Base>& x,
117  const std::pair<Base, Base>& y) const
118  { return comp_(*x.first, *y.first); }
119  private:
120  Compare comp_;
121  };
122 
123  std::multiset<std::pair<Base, Base>, PairCompare> data_;
124  };
125 
131  template<typename Base>
132  MergeIterator<Base>
133  make_merge_iterator(const std::vector<std::pair<Base, Base> >& vec)
134  {
135  return MergeIterator<Base>(vec);
136  }
137 
138 
145  template<typename Base, class Compare>
147  make_merge_iterator(const std::vector<std::pair<Base, Base> >& vec,
148  const Compare& comp)
149  {
150  return MergeIterator<Base, Compare>(vec, comp);
151  }
152 
153 
154 
155  // template implementations
156 
157  template<typename Base, class Compare>
160  {
161  YAT_ASSERT(data_.size());
162  YAT_ASSERT(data_.begin()->first != data_.begin()->second);
163  return *data_.begin()->first;
164  }
165 
166 
167  template<typename Base, class Compare>
168  bool MergeIterator<Base, Compare>::equal(const MergeIterator& other) const
169  {
170  if (data_.empty() || other.data_.empty())
171  return data_.empty() == other.data_.empty();
172  return data_.begin()->first == other.data_.begin()->first;
173  }
174 
175 
176  template<typename Base, class Compare>
177  void
178  MergeIterator<Base,Compare>::init(const std::vector<std::pair<Base,Base> >& v)
179  {
180  BOOST_CONCEPT_ASSERT((boost_concepts::ReadableIterator<Base>));
181  BOOST_CONCEPT_ASSERT((boost_concepts::SinglePassIterator<Base>));
182  for (size_t i=0; i<v.size(); ++i)
183  if (v[i].first != v[i].second)
184  data_.insert(v[i]);
185  }
186 
187 
188  template<typename Base, class Compare>
189  void MergeIterator<Base, Compare>::increment(void)
190  {
191  if (data_.empty())
192  return;
193  // store first range
194  std::pair<Base, Base> tmp = *data_.begin();
195  // remove first range from set of ranges
196  data_.erase(data_.begin());
197  // iterate the first range and if not end-of-range, insert the
198  // range back into set of ranges
199  if (++(tmp.first) != tmp.second)
200  // tmp was first in data_ prior incrementation, so it's a good
201  // guess that tmp is first also after the incrementation
202  data_.insert(data_.begin(), tmp);
203  }
204 
205 }}}
206 #endif
MergeIterator< Base, Compare > make_merge_iterator(const std::vector< std::pair< Base, Base > > &vec, const Compare &comp)
Definition: MergeIterator.h:147
The Department of Theoretical Physics namespace as we define it.
Iterate over several ranges as if ranges have been merged.
Definition: MergeIterator.h:64
MergeIterator(const std::vector< std::pair< Base, Base > > &vec)
Create MergeIterator.
Definition: MergeIterator.h:86
MergeIterator< Base > make_merge_iterator(const std::vector< std::pair< Base, Base > > &vec)
Definition: MergeIterator.h:133
MergeIterator(const std::vector< std::pair< Base, Base > > &vec, const Compare &comp)
Creates MergeIterator using comp as compare object.
Definition: MergeIterator.h:98
MergeIterator(void)
Definition: MergeIterator.h:76

Generated on Wed Jan 25 2023 03:34:29 for yat by  doxygen 1.8.14