source: NonGTP/Boost/boost/python/slice.hpp @ 857

Revision 857, 10.3 KB checked in by igarcia, 19 years ago (diff)
Line 
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
20namespace boost { namespace python {
21
22namespace 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
45class 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
253namespace converter {
254
255template<>
256struct 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
Note: See TracBrowser for help on using the repository browser.