|
1 #ifndef BOOST_PYTHON_SLICE_JDB20040105_HPP |
|
2 #define BOOST_PYTHON_SLICE_JDB20040105_HPP |
|
3 |
|
4 // Copyright (c) 2004 Jonathan Brandmeyer |
|
5 // Use, modification and distribution are subject to the |
|
6 // Boost Software License, Version 1.0. (See accompanying file |
|
7 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
|
8 |
|
9 #include <boost/python/detail/prefix.hpp> |
|
10 #include <boost/config.hpp> |
|
11 #include <boost/python/object.hpp> |
|
12 #include <boost/python/extract.hpp> |
|
13 #include <boost/python/converter/pytype_object_mgr_traits.hpp> |
|
14 |
|
15 #include <boost/iterator/iterator_traits.hpp> |
|
16 |
|
17 #include <iterator> |
|
18 #include <algorithm> |
|
19 |
|
20 namespace boost { namespace python { |
|
21 |
|
22 namespace detail |
|
23 { |
|
24 class BOOST_PYTHON_DECL slice_base : public object |
|
25 { |
|
26 public: |
|
27 // Get the Python objects associated with the slice. In principle, these |
|
28 // may be any arbitrary Python type, but in practice they are usually |
|
29 // integers. If one or more parameter is ommited in the Python expression |
|
30 // that created this slice, than that parameter is None here, and compares |
|
31 // equal to a default-constructed boost::python::object. |
|
32 // If a user-defined type wishes to support slicing, then support for the |
|
33 // special meaning associated with negative indicies is up to the user. |
|
34 object start() const; |
|
35 object stop() const; |
|
36 object step() const; |
|
37 |
|
38 protected: |
|
39 explicit slice_base(PyObject*, PyObject*, PyObject*); |
|
40 |
|
41 BOOST_PYTHON_FORWARD_OBJECT_CONSTRUCTORS(slice_base, object) |
|
42 }; |
|
43 } |
|
44 |
|
45 class slice : public detail::slice_base |
|
46 { |
|
47 typedef detail::slice_base base; |
|
48 public: |
|
49 // Equivalent to slice(::) |
|
50 slice() : base(0,0,0) {} |
|
51 |
|
52 // Each argument must be slice_nil, or implicitly convertable to object. |
|
53 // They should normally be integers. |
|
54 template<typename Integer1, typename Integer2> |
|
55 slice( Integer1 start, Integer2 stop) |
|
56 : base( object(start).ptr(), object(stop).ptr(), 0 ) |
|
57 {} |
|
58 |
|
59 template<typename Integer1, typename Integer2, typename Integer3> |
|
60 slice( Integer1 start, Integer2 stop, Integer3 stride) |
|
61 : base( object(start).ptr(), object(stop).ptr(), object(stride).ptr() ) |
|
62 {} |
|
63 |
|
64 // The following algorithm is intended to automate the process of |
|
65 // determining a slice range when you want to fully support negative |
|
66 // indicies and non-singular step sizes. Its functionallity is simmilar to |
|
67 // PySlice_GetIndicesEx() in the Python/C API, but tailored for C++ users. |
|
68 // This template returns a slice::range struct that, when used in the |
|
69 // following iterative loop, will traverse a slice of the function's |
|
70 // arguments. |
|
71 // while (start != end) { |
|
72 // do_foo(...); |
|
73 // std::advance( start, step); |
|
74 // } |
|
75 // do_foo(...); // repeat exactly once more. |
|
76 |
|
77 // Arguments: a [begin, end) pair of STL-conforming random-access iterators. |
|
78 |
|
79 // Return: slice::range, where start and stop define a _closed_ interval |
|
80 // that covers at most [begin, end-1] of the provided arguments, and a step |
|
81 // that is non-zero. |
|
82 |
|
83 // Throws: error_already_set() if any of the indices are neither None nor |
|
84 // integers, or the slice has a step value of zero. |
|
85 // std::invalid_argument if the resulting range would be empty. Normally, |
|
86 // you should catch this exception and return an empty sequence of the |
|
87 // appropriate type. |
|
88 |
|
89 // Performance: constant time for random-access iterators. |
|
90 |
|
91 // Rationale: |
|
92 // closed-interval: If an open interval were used, then for a non-singular |
|
93 // value for step, the required state for the end iterator could be |
|
94 // beyond the one-past-the-end postion of the specified range. While |
|
95 // probably harmless, the behavior of STL-conforming iterators is |
|
96 // undefined in this case. |
|
97 // exceptions on zero-length range: It is impossible to define a closed |
|
98 // interval over an empty range, so some other form of error checking |
|
99 // would have to be used by the user to prevent undefined behavior. In |
|
100 // the case where the user fails to catch the exception, it will simply |
|
101 // be translated to Python by the default exception handling mechanisms. |
|
102 |
|
103 template<typename RandomAccessIterator> |
|
104 struct range |
|
105 { |
|
106 RandomAccessIterator start; |
|
107 RandomAccessIterator stop; |
|
108 typename iterator_difference<RandomAccessIterator>::type step; |
|
109 }; |
|
110 |
|
111 template<typename RandomAccessIterator> |
|
112 slice::range<RandomAccessIterator> |
|
113 get_indicies( const RandomAccessIterator& begin, |
|
114 const RandomAccessIterator& end) const |
|
115 { |
|
116 // This is based loosely on PySlice_GetIndicesEx(), but it has been |
|
117 // carefully crafted to ensure that these iterators never fall out of |
|
118 // the range of the container. |
|
119 slice::range<RandomAccessIterator> ret; |
|
120 |
|
121 typedef typename iterator_difference<RandomAccessIterator>::type difference_type; |
|
122 difference_type max_dist = boost::detail::distance(begin, end); |
|
123 |
|
124 object slice_start = this->start(); |
|
125 object slice_stop = this->stop(); |
|
126 object slice_step = this->step(); |
|
127 |
|
128 // Extract the step. |
|
129 if (slice_step == object()) { |
|
130 ret.step = 1; |
|
131 } |
|
132 else { |
|
133 ret.step = extract<long>( slice_step); |
|
134 if (ret.step == 0) { |
|
135 PyErr_SetString( PyExc_IndexError, "step size cannot be zero."); |
|
136 throw_error_already_set(); |
|
137 } |
|
138 } |
|
139 |
|
140 // Setup the start iterator. |
|
141 if (slice_start == object()) { |
|
142 if (ret.step < 0) { |
|
143 ret.start = end; |
|
144 --ret.start; |
|
145 } |
|
146 else |
|
147 ret.start = begin; |
|
148 } |
|
149 else { |
|
150 difference_type i = extract<long>( slice_start); |
|
151 if (i >= max_dist && ret.step > 0) |
|
152 throw std::invalid_argument( "Zero-length slice"); |
|
153 if (i >= 0) { |
|
154 ret.start = begin; |
|
155 BOOST_USING_STD_MIN(); |
|
156 std::advance( ret.start, min BOOST_PREVENT_MACRO_SUBSTITUTION(i, max_dist-1)); |
|
157 } |
|
158 else { |
|
159 if (i < -max_dist && ret.step < 0) |
|
160 throw std::invalid_argument( "Zero-length slice"); |
|
161 ret.start = end; |
|
162 // Advance start (towards begin) not farther than begin. |
|
163 std::advance( ret.start, (-i < max_dist) ? i : -max_dist ); |
|
164 } |
|
165 } |
|
166 |
|
167 // Set up the stop iterator. This one is a little trickier since slices |
|
168 // define a [) range, and we are returning a [] range. |
|
169 if (slice_stop == object()) { |
|
170 if (ret.step < 0) { |
|
171 ret.stop = begin; |
|
172 } |
|
173 else { |
|
174 ret.stop = end; |
|
175 std::advance( ret.stop, -1); |
|
176 } |
|
177 } |
|
178 else { |
|
179 difference_type i = extract<long>(slice_stop); |
|
180 // First, branch on which direction we are going with this. |
|
181 if (ret.step < 0) { |
|
182 if (i+1 >= max_dist || i == -1) |
|
183 throw std::invalid_argument( "Zero-length slice"); |
|
184 |
|
185 if (i >= 0) { |
|
186 ret.stop = begin; |
|
187 std::advance( ret.stop, i+1); |
|
188 } |
|
189 else { // i is negative, but more negative than -1. |
|
190 ret.stop = end; |
|
191 std::advance( ret.stop, (-i < max_dist) ? i : -max_dist); |
|
192 } |
|
193 } |
|
194 else { // stepping forward |
|
195 if (i == 0 || -i >= max_dist) |
|
196 throw std::invalid_argument( "Zero-length slice"); |
|
197 |
|
198 if (i > 0) { |
|
199 ret.stop = begin; |
|
200 std::advance( ret.stop, (std::min)( i-1, max_dist-1)); |
|
201 } |
|
202 else { // i is negative, but not more negative than -max_dist |
|
203 ret.stop = end; |
|
204 std::advance( ret.stop, i-1); |
|
205 } |
|
206 } |
|
207 } |
|
208 |
|
209 // Now the fun part, handling the possibilites surrounding step. |
|
210 // At this point, step has been initialized, ret.stop, and ret.step |
|
211 // represent the widest possible range that could be traveled |
|
212 // (inclusive), and final_dist is the maximum distance covered by the |
|
213 // slice. |
|
214 typename iterator_difference<RandomAccessIterator>::type final_dist = |
|
215 boost::detail::distance( ret.start, ret.stop); |
|
216 |
|
217 // First case, if both ret.start and ret.stop are equal, then step |
|
218 // is irrelevant and we can return here. |
|
219 if (final_dist == 0) |
|
220 return ret; |
|
221 |
|
222 // Second, if there is a sign mismatch, than the resulting range and |
|
223 // step size conflict: std::advance( ret.start, ret.step) goes away from |
|
224 // ret.stop. |
|
225 if ((final_dist > 0) != (ret.step > 0)) |
|
226 throw std::invalid_argument( "Zero-length slice."); |
|
227 |
|
228 // Finally, if the last step puts us past the end, we move ret.stop |
|
229 // towards ret.start in the amount of the remainder. |
|
230 // I don't remember all of the oolies surrounding negative modulii, |
|
231 // so I am handling each of these cases separately. |
|
232 if (final_dist < 0) { |
|
233 difference_type remainder = -final_dist % -ret.step; |
|
234 std::advance( ret.stop, remainder); |
|
235 } |
|
236 else { |
|
237 difference_type remainder = final_dist % ret.step; |
|
238 std::advance( ret.stop, -remainder); |
|
239 } |
|
240 |
|
241 return ret; |
|
242 } |
|
243 |
|
244 public: |
|
245 // This declaration, in conjunction with the specialization of |
|
246 // object_manager_traits<> below, allows C++ functions accepting slice |
|
247 // arguments to be called from from Python. These constructors should never |
|
248 // be used in client code. |
|
249 BOOST_PYTHON_FORWARD_OBJECT_CONSTRUCTORS(slice, detail::slice_base) |
|
250 }; |
|
251 |
|
252 |
|
253 namespace converter { |
|
254 |
|
255 template<> |
|
256 struct object_manager_traits<slice> |
|
257 : pytype_object_manager_traits<&PySlice_Type, slice> |
|
258 { |
|
259 }; |
|
260 |
|
261 } // !namesapce converter |
|
262 |
|
263 } } // !namespace ::boost::python |
|
264 |
|
265 |
|
266 #endif // !defined BOOST_PYTHON_SLICE_JDB20040105_HPP |