]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 indices 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 | // indices 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_indices( 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 = std::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 | std::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 | // Incorrect spelling. DO NOT USE. Only here for backward compatibility. | |
245 | // Corrected 2011-06-14. | |
246 | template<typename RandomAccessIterator> | |
247 | slice::range<RandomAccessIterator> | |
248 | get_indicies( const RandomAccessIterator& begin, | |
249 | const RandomAccessIterator& end) const | |
250 | { | |
251 | return get_indices(begin, end); | |
252 | } | |
253 | ||
254 | public: | |
255 | // This declaration, in conjunction with the specialization of | |
256 | // object_manager_traits<> below, allows C++ functions accepting slice | |
257 | // arguments to be called from from Python. These constructors should never | |
258 | // be used in client code. | |
259 | BOOST_PYTHON_FORWARD_OBJECT_CONSTRUCTORS(slice, detail::slice_base) | |
260 | }; | |
261 | ||
262 | ||
263 | namespace converter { | |
264 | ||
265 | template<> | |
266 | struct object_manager_traits<slice> | |
267 | : pytype_object_manager_traits<&PySlice_Type, slice> | |
268 | { | |
269 | }; | |
270 | ||
271 | } // !namesapce converter | |
272 | ||
273 | } } // !namespace ::boost::python | |
274 | ||
275 | ||
276 | #endif // !defined BOOST_PYTHON_SLICE_JDB20040105_HPP |