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

Last change on this file since 3389 was 3389, checked in by Peter, 4 years ago

docs

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