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
39#include "lexical_cast.hh"
40
41#include "sanity.hh"
42
43namespace parallel
44{
45 typedef enum { in_left, in_right, in_both, invalid } state_t;
46
47 template <typename M>
48 class iter
49 {
50 public:
51 M const & left_map;
52 M const & right_map;
53
54 iter(M const & left_map, M const & right_map)
55 : left_map(left_map), right_map(right_map),
56 state_(invalid), started_(false), finished_(false)
57 {
58 }
59
60 bool next()
61 {
62 I(!finished_);
63 // update iterators past the last item returned
64 if (!started_)
65 {
66 left_ = left_map.begin();
67 right_ = right_map.begin();
68 started_ = true;
69 }
70 else
71 {
72 I(state_ != invalid);
73 if (state_ == in_left || state_ == in_both)
74 ++left_;
75 if (state_ == in_right || state_ == in_both)
76 ++right_;
77 }
78 // determine new state
79 I(started_);
80 if (left_ == left_map.end() && right_ == right_map.end())
81 {
82 finished_ = true;
83 state_ = invalid;
84 }
85 else if (left_ == left_map.end() && right_ != right_map.end())
86 state_ = in_right;
87 else if (left_ != left_map.end() && right_ == right_map.end())
88 state_ = in_left;
89 else
90 {
91 // Both iterators valid.
92 if (left_->first < right_->first)
93 state_ = in_left;
94 else if (right_->first < left_->first)
95 state_ = in_right;
96 else
97 {
98 I(left_->first == right_->first);
99 state_ = in_both;
100 }
101 }
102 return !finished_;
103 }
104
105 state_t state() const
106 {
107 return state_;
108 }
109
110 typename M::value_type const &
111 left_value()
112 {
113 I(state_ == in_left || state_ == in_both);
114 return *left_;
115 }
116
117 typename M::key_type const &
118 left_key()
119 {
120 return left_value().first;
121 }
122
123 typename M::value_type::second_type const &
124 left_data()
125 {
126 return left_value().second;
127 }
128
129 typename M::value_type const &
130 right_value()
131 {
132 I(state_ == in_right || state_ == in_both);
133 return *right_;
134 }
135
136 typename M::key_type const &
137 right_key()
138 {
139 return right_value().first;
140 }
141
142 typename M::value_type::second_type const &
143 right_data()
144 {
145 return right_value().second;
146 }
147
148 private:
149 state_t state_;
150 bool started_, finished_;
151 typename M::const_iterator left_;
152 typename M::const_iterator right_;
153
154 };
155
156 template <typename M> void
157 dump(iter<M> const & i, std::string & out)
158 {
159 out = boost::lexical_cast<std::string>(i.state());
160 switch (i.state())
161 {
162 case in_left: out += " in_left"; break;
163 case in_right: out += " in_right"; break;
164 case in_both: out += " in_both"; break;
165 case invalid: out += " invalid"; break;
166 }
167 out += "\n";
168 }
169
170}
171
172// Local Variables:
173// mode: C++
174// fill-column: 76
175// c-file-style: "gnu"
176// indent-tabs-mode: nil
177// End:
178// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:
179
180#endif

Archive Download this file

Branches

Tags

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