source: trunk/yat/utility/MergeIterator.h @ 3065

Last change on this file since 3065 was 3065, checked in by Peter, 8 years ago

improve docs

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 5.0 KB
Line 
1#ifndef theplu_yat_utility_merge_iterator
2#define theplu_yat_utility_merge_iterator
3
4// $Id: MergeIterator.h 3065 2013-07-14 22:44:19Z peter $
5
6/*
7  Copyright (C) 2013 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/iterator/iterator_facade.hpp>
29
30#include <iterator>
31#include <set>
32#include <vector>
33
34namespace theplu {
35namespace yat {
36namespace utility {
37
38  /**
39     \brief Iterate over several ranges as if ranges have been merged
40
41     MergeIterator is an \input_iterator that is created from several
42     ranges and will iterate over the elements is the ranges as if
43     ranges have been merged. Ranges have to be sorted (as defined by
44     the \c Compare object) or behaviour is undefined. When
45     incremented, the iterator looks at next element in each range,
46     identifies the smallest element, and points at that.
47
48     \since New in yat 0.11
49   */
50  template<
51    typename Base,
52    class Compare=std::less<typename std::iterator_traits<Base>::value_type>
53    >
54  class MergeIterator
55    : public boost::iterator_facade<
56    MergeIterator<Base, Compare>,
57    const typename std::iterator_traits<Base>::value_type,
58    std::input_iterator_tag
59    >
60  {
61  public:
62    /**
63       Creates an end-of-range iterator
64     */
65    MergeIterator(void) {};
66
67    /**
68       \brief Create MergeIterator
69
70       Create a MergeIterator that will iterate over ranges
71       [vec[0].first, vec[0].second), [vec[1].first, vec[1].second), ...
72
73       \see make_merge_iterator(const std::vector<std::pair<Base, Base> >&)
74     */
75    MergeIterator(const std::vector<std::pair<Base, Base> >& vec)
76    { init(vec); };
77
78    /**
79       \brief Creates MergeIterator using \a comp as compare object.
80
81       Same as MergeIterator(2) but using \a comp rather than using a
82       default constructed Compare object.
83
84       \see
85       make_merge_iterator(const std::vector<std::pair<Base, Base> >&, const Compare&)
86     */
87    MergeIterator(const std::vector<std::pair<Base, Base> >& vec,
88                  const Compare& comp)
89    : data_(PairCompare(comp))
90    { init(vec); }
91
92  private:
93    friend class boost::iterator_core_access;
94
95    typename MergeIterator<Base, Compare>::reference dereference(void) const;
96    bool equal(const MergeIterator& other) const;
97    void init(const std::vector<std::pair<Base,Base> >& v);
98    void increment(void);
99
100    class PairCompare
101    {
102    public:
103      PairCompare(void) {}
104      PairCompare(const Compare& c) : comp_(c) {}
105      bool operator()(const std::pair<Base, Base>& x,
106                      const std::pair<Base, Base>& y) const
107      { return comp_(*x.first, *y.first); }
108    private:
109      Compare comp_;
110    };
111
112    std::multiset<std::pair<Base, Base>, PairCompare> data_;
113  };
114
115  /**
116     Creates a MergeIterator that iterates over ranges defined in \a vec.
117
118     \relates MergeIterator
119   */
120  template<typename Base>
121  MergeIterator<Base>
122  make_merge_iterator(const std::vector<std::pair<Base, Base> >& vec)
123  {
124    return MergeIterator<Base>(vec);
125  }
126
127
128  /**
129     Creates a MergeIterator that iterates over ranges defined in \a
130     vec, using \a comp to compare elements.
131
132     \relates MergeIterator
133  */
134  template<typename Base, class Compare>
135  MergeIterator<Base, Compare>
136  make_merge_iterator(const std::vector<std::pair<Base, Base> >& vec,
137                      const Compare& comp)
138  {
139    return MergeIterator<Base, Compare>(vec, comp);
140  }
141
142
143
144  // template implementations
145
146  template<typename Base, class Compare>
147  typename MergeIterator<Base, Compare>::reference
148  MergeIterator<Base, Compare>::dereference(void) const
149  {
150    YAT_ASSERT(data_.size());
151    YAT_ASSERT(data_.begin()->first != data_.begin()->second);
152    return *data_.begin()->first;
153  }
154
155
156  template<typename Base, class Compare>
157  bool MergeIterator<Base, Compare>::equal(const MergeIterator& other) const
158  {
159    if (data_.empty() || other.data_.empty())
160      return data_.empty() == other.data_.empty();
161    return data_.begin()->first == other.data_.begin()->first;
162  }
163
164
165  template<typename Base, class Compare>
166  void
167  MergeIterator<Base,Compare>::init(const std::vector<std::pair<Base,Base> >& v)
168  {
169    for (size_t i=0; i<v.size(); ++i)
170      if (v[i].first != v[i].second)
171        data_.insert(v[i]);
172  }
173
174
175  template<typename Base, class Compare>
176  void MergeIterator<Base, Compare>::increment(void)
177  {
178    if (data_.empty())
179      return;
180    // store first range
181    std::pair<Base, Base> tmp = *data_.begin();
182    // remove first range from set of ranges
183    data_.erase(data_.begin());
184    // iterate the first range and if not end-of-range, insert the
185    // range back into set of ranges
186    if (++(tmp.first) != tmp.second)
187      data_.insert(tmp);
188  }
189
190}}}
191#endif
Note: See TracBrowser for help on using the repository browser.