monotone

monotone Mtn Source Tree

Root/parallel_iter.hh

1#ifndef __PARALLEL_ITER_HH__
2#define __PARALLEL_ITER_HH__
3
4// Copyright (C) 2005 Nathaniel Smith <njs@pobox.com>
5//
6// This program is made available under the GNU GPL version 2.0 or
7// greater. See the accompanying file COPYING for details.
8//
9// This program is distributed WITHOUT ANY WARRANTY; without even the
10// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
11// PURPOSE.
12
13// An ugly, but handy, little helper class for doing parallel iteration
14// over maps.
15// Usage:
16// parallel::iter<std::map<foo, bar> > i(left_map, right_map);
17// while (i.next())
18// switch (i.state())
19// {
20// case parallel::invalid:
21// I(false);
22// case parallel::in_left:
23// // use left_value(), left_key(), left_data()
24// break;
25// case parallel::in_right:
26// // use right_value(), right_key(), right_data()
27// break;
28// case parallel::in_both:
29// // use left_value(), right_value(), left_key(), right_key(),
30// // left_data(), right_data()
31// break;
32// }
33//
34// This code would make Alexander Stepanov cry; not only is it only defined
35// for maps, but it will only work on maps that use the default (std::less)
36// sort order.
37
38#include <string>
39
40#include <boost/lexical_cast.hpp>
41
42#include "sanity.hh"
43
44namespace parallel
45{
46 typedef enum { in_left, in_right, in_both, invalid } state_t;
47
48 template <typename M>
49 class iter
50 {
51 public:
52 M const & left_map;
53 M const & right_map;
54
55 iter(M const & left_map, M const & right_map)
56 : left_map(left_map), right_map(right_map),
57 state_(invalid), started_(false), finished_(false)
58 {
59 }
60
61 bool next()
62 {
63 I(!finished_);
64 // update iterators past the last item returned
65 if (!started_)
66 {
67 left_ = left_map.begin();
68 right_ = right_map.begin();
69 started_ = true;
70 }
71 else
72 {
73 I(state_ != invalid);
74 if (state_ == in_left || state_ == in_both)
75 ++left_;
76 if (state_ == in_right || state_ == in_both)
77 ++right_;
78 }
79 // determine new state
80 I(started_);
81 if (left_ == left_map.end() && right_ == right_map.end())
82 {
83 finished_ = true;
84 state_ = invalid;
85 }
86 else if (left_ == left_map.end() && right_ != right_map.end())
87 state_ = in_right;
88 else if (left_ != left_map.end() && right_ == right_map.end())
89 state_ = in_left;
90 else
91 {
92 // Both iterators valid.
93 if (left_->first < right_->first)
94 state_ = in_left;
95 else if (right_->first < left_->first)
96 state_ = in_right;
97 else
98 {
99 I(left_->first == right_->first);
100 state_ = in_both;
101 }
102 }
103 return !finished_;
104 }
105
106 state_t state() const
107 {
108 return state_;
109 }
110
111 typename M::value_type const &
112 left_value()
113 {
114 I(state_ == in_left || state_ == in_both);
115 return *left_;
116 }
117
118 typename M::key_type const &
119 left_key()
120 {
121 return left_value().first;
122 }
123
124 typename M::value_type::second_type const &
125 left_data()
126 {
127 return left_value().second;
128 }
129
130 typename M::value_type const &
131 right_value()
132 {
133 I(state_ == in_right || state_ == in_both);
134 return *right_;
135 }
136
137 typename M::key_type const &
138 right_key()
139 {
140 return right_value().first;
141 }
142
143 typename M::value_type::second_type const &
144 right_data()
145 {
146 return right_value().second;
147 }
148
149 private:
150 state_t state_;
151 bool started_, finished_;
152 typename M::const_iterator left_;
153 typename M::const_iterator right_;
154
155 };
156
157 template <typename M> void
158 dump(iter<M> const & i, std::string & out)
159 {
160 out = boost::lexical_cast<std::string>(i.state());
161 switch (i.state())
162 {
163 case in_left: out += " in_left"; break;
164 case in_right: out += " in_right"; break;
165 case in_both: out += " in_both"; break;
166 case invalid: out += " invalid"; break;
167 }
168 out += "\n";
169 }
170
171}
172
173// Local Variables:
174// mode: C++
175// fill-column: 76
176// c-file-style: "gnu"
177// indent-tabs-mode: nil
178// End:
179// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:
180
181#endif

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status