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

Last change on this file since 2995 was 2995, checked in by Peter, 9 years ago

closes #741. New class MergeIterator?

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 4.9 KB
Line 
1#ifndef theplu_yat_utility_merge_iterator
2#define theplu_yat_utility_merge_iterator
3
4// $Id: MergeIterator.h 2995 2013-03-13 11:30:49Z 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  template<
49    typename Base,
50    class Compare=std::less<typename std::iterator_traits<Base>::value_type>
51    >
52  class MergeIterator
53    : public boost::iterator_facade<
54    MergeIterator<Base, Compare>,
55    const typename std::iterator_traits<Base>::value_type,
56    std::input_iterator_tag
57    >
58  {
59  public:
60    /**
61       Creates an end-of-range iterator
62     */
63    MergeIterator(void) {};
64
65    /**
66       \brief Create MergeIterator
67
68       Create a MergeIterator that will iterate over ranges
69       [vec[0].first, vec[0].second), [vec[1].first, vec[1].second), ...
70
71       \see make_merge_iterator(const std::vector<std::pair<Base, Base> >&)
72     */
73    MergeIterator(const std::vector<std::pair<Base, Base> >& vec)
74    { init(vec); };
75
76    /**
77       \brief Creates MergeIterator using \a comp as compare object.
78
79       Same as MergeIterator(2) but using \a comp rather than using a
80       default constructed Compare object.
81
82       \see
83       make_merge_iterator(const vector<pair<Base, Base> >&, const Compare&)
84     */
85    MergeIterator(const std::vector<std::pair<Base, Base> >& vec,
86                  const Compare& comp)
87    : data_(PairCompare(comp))
88    { init(vec); }
89
90  private:
91    friend class boost::iterator_core_access;
92
93    typename MergeIterator<Base, Compare>::reference dereference(void) const;
94    bool equal(const MergeIterator& other) const;
95    void init(const std::vector<std::pair<Base,Base> >& v);
96    void increment(void);
97
98    class PairCompare
99    {
100    public:
101      PairCompare(void) {}
102      PairCompare(const Compare& c) : comp_(c) {}
103      bool operator()(const std::pair<Base, Base>& x,
104                      const std::pair<Base, Base>& y) const
105      { return comp_(*x.first, *y.first); }
106    private:
107      Compare comp_;
108    };
109
110    std::multiset<std::pair<Base, Base>, PairCompare> data_;
111  };
112
113  /**
114     Creates a MergeIterator that iterates over ranges defined in \a vec.
115   */
116  template<typename Base>
117  MergeIterator<Base>
118  make_merge_iterator(const std::vector<std::pair<Base, Base> >& vec)
119  {
120    return MergeIterator<Base>(vec);
121  }
122
123
124  /**
125     Creates a MergeIterator that iterates over ranges defined in \a
126     vec, using \a comp to compare elements.
127  */
128  template<typename Base, class Compare>
129  MergeIterator<Base, Compare>
130  make_merge_iterator(const std::vector<std::pair<Base, Base> >& vec,
131                      const Compare& comp)
132  {
133    return MergeIterator<Base, Compare>(vec, comp);
134  }
135
136
137
138  // template implementations
139
140  template<typename Base, class Compare>
141  typename MergeIterator<Base, Compare>::reference
142  MergeIterator<Base, Compare>::dereference(void) const
143  {
144    YAT_ASSERT(data_.size());
145    YAT_ASSERT(data_.begin()->first != data_.begin()->second);
146    return *data_.begin()->first;
147  }
148
149
150  template<typename Base, class Compare>
151  bool MergeIterator<Base, Compare>::equal(const MergeIterator& other) const
152  {
153    if (data_.empty() || other.data_.empty())
154      return data_.empty() == other.data_.empty();
155    return data_.begin()->first == other.data_.begin()->first;
156  }
157
158
159  template<typename Base, class Compare>
160  void
161  MergeIterator<Base,Compare>::init(const std::vector<std::pair<Base,Base> >& v)
162  {
163    for (size_t i=0; i<v.size(); ++i)
164      if (v[i].first != v[i].second)
165        data_.insert(v[i]);
166  }
167
168
169  template<typename Base, class Compare>
170  void MergeIterator<Base, Compare>::increment(void)
171  {
172    if (data_.empty())
173      return;
174    // store first range
175    std::pair<Base, Base> tmp = *data_.begin();
176    // remove first range from set of ranges
177    data_.erase(data_.begin());
178    // iterate the first range and if not end-of-range, insert the
179    // range back into set of ranges
180    if (++(tmp.first) != tmp.second)
181      data_.insert(tmp);
182  }
183
184}}}
185#endif
Note: See TracBrowser for help on using the repository browser.