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(::)
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>
slice(Integer1 start,Integer2 stop)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>
slice(Integer1 start,Integer2 stop,Integer3 stride)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>
get_indices(const RandomAccessIterator & begin,const RandomAccessIterator & end) const113     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>
get_indicies(const RandomAccessIterator & begin,const RandomAccessIterator & end) const248     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
277