| #ifndef BOOST_PYTHON_SLICE_JDB20040105_HPP |
| #define BOOST_PYTHON_SLICE_JDB20040105_HPP |
| |
| // Copyright (c) 2004 Jonathan Brandmeyer |
| // Use, modification and distribution are subject to the |
| // Boost Software License, Version 1.0. (See accompanying file |
| // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| |
| #include <boost/python/detail/prefix.hpp> |
| #include <boost/config.hpp> |
| #include <boost/python/object.hpp> |
| #include <boost/python/extract.hpp> |
| #include <boost/python/converter/pytype_object_mgr_traits.hpp> |
| |
| #include <boost/iterator/iterator_traits.hpp> |
| |
| #include <iterator> |
| #include <algorithm> |
| |
| namespace boost { namespace python { |
| |
| namespace detail |
| { |
| class BOOST_PYTHON_DECL slice_base : public object |
| { |
| public: |
| // Get the Python objects associated with the slice. In principle, these |
| // may be any arbitrary Python type, but in practice they are usually |
| // integers. If one or more parameter is ommited in the Python expression |
| // that created this slice, than that parameter is None here, and compares |
| // equal to a default-constructed boost::python::object. |
| // If a user-defined type wishes to support slicing, then support for the |
| // special meaning associated with negative indicies is up to the user. |
| object start() const; |
| object stop() const; |
| object step() const; |
| |
| protected: |
| explicit slice_base(PyObject*, PyObject*, PyObject*); |
| |
| BOOST_PYTHON_FORWARD_OBJECT_CONSTRUCTORS(slice_base, object) |
| }; |
| } |
| |
| class slice : public detail::slice_base |
| { |
| typedef detail::slice_base base; |
| public: |
| // Equivalent to slice(::) |
| slice() : base(0,0,0) {} |
| |
| // Each argument must be slice_nil, or implicitly convertable to object. |
| // They should normally be integers. |
| template<typename Integer1, typename Integer2> |
| slice( Integer1 start, Integer2 stop) |
| : base( object(start).ptr(), object(stop).ptr(), 0 ) |
| {} |
| |
| template<typename Integer1, typename Integer2, typename Integer3> |
| slice( Integer1 start, Integer2 stop, Integer3 stride) |
| : base( object(start).ptr(), object(stop).ptr(), object(stride).ptr() ) |
| {} |
| |
| // The following algorithm is intended to automate the process of |
| // determining a slice range when you want to fully support negative |
| // indicies and non-singular step sizes. Its functionallity is simmilar to |
| // PySlice_GetIndicesEx() in the Python/C API, but tailored for C++ users. |
| // This template returns a slice::range struct that, when used in the |
| // following iterative loop, will traverse a slice of the function's |
| // arguments. |
| // while (start != end) { |
| // do_foo(...); |
| // std::advance( start, step); |
| // } |
| // do_foo(...); // repeat exactly once more. |
| |
| // Arguments: a [begin, end) pair of STL-conforming random-access iterators. |
| |
| // Return: slice::range, where start and stop define a _closed_ interval |
| // that covers at most [begin, end-1] of the provided arguments, and a step |
| // that is non-zero. |
| |
| // Throws: error_already_set() if any of the indices are neither None nor |
| // integers, or the slice has a step value of zero. |
| // std::invalid_argument if the resulting range would be empty. Normally, |
| // you should catch this exception and return an empty sequence of the |
| // appropriate type. |
| |
| // Performance: constant time for random-access iterators. |
| |
| // Rationale: |
| // closed-interval: If an open interval were used, then for a non-singular |
| // value for step, the required state for the end iterator could be |
| // beyond the one-past-the-end postion of the specified range. While |
| // probably harmless, the behavior of STL-conforming iterators is |
| // undefined in this case. |
| // exceptions on zero-length range: It is impossible to define a closed |
| // interval over an empty range, so some other form of error checking |
| // would have to be used by the user to prevent undefined behavior. In |
| // the case where the user fails to catch the exception, it will simply |
| // be translated to Python by the default exception handling mechanisms. |
| |
| template<typename RandomAccessIterator> |
| struct range |
| { |
| RandomAccessIterator start; |
| RandomAccessIterator stop; |
| typename iterator_difference<RandomAccessIterator>::type step; |
| }; |
| |
| template<typename RandomAccessIterator> |
| slice::range<RandomAccessIterator> |
| get_indicies( const RandomAccessIterator& begin, |
| const RandomAccessIterator& end) const |
| { |
| // This is based loosely on PySlice_GetIndicesEx(), but it has been |
| // carefully crafted to ensure that these iterators never fall out of |
| // the range of the container. |
| slice::range<RandomAccessIterator> ret; |
| |
| typedef typename iterator_difference<RandomAccessIterator>::type difference_type; |
| difference_type max_dist = boost::detail::distance(begin, end); |
| |
| object slice_start = this->start(); |
| object slice_stop = this->stop(); |
| object slice_step = this->step(); |
| |
| // Extract the step. |
| if (slice_step == object()) { |
| ret.step = 1; |
| } |
| else { |
| ret.step = extract<long>( slice_step); |
| if (ret.step == 0) { |
| PyErr_SetString( PyExc_IndexError, "step size cannot be zero."); |
| throw_error_already_set(); |
| } |
| } |
| |
| // Setup the start iterator. |
| if (slice_start == object()) { |
| if (ret.step < 0) { |
| ret.start = end; |
| --ret.start; |
| } |
| else |
| ret.start = begin; |
| } |
| else { |
| difference_type i = extract<long>( slice_start); |
| if (i >= max_dist && ret.step > 0) |
| throw std::invalid_argument( "Zero-length slice"); |
| if (i >= 0) { |
| ret.start = begin; |
| BOOST_USING_STD_MIN(); |
| std::advance( ret.start, min BOOST_PREVENT_MACRO_SUBSTITUTION(i, max_dist-1)); |
| } |
| else { |
| if (i < -max_dist && ret.step < 0) |
| throw std::invalid_argument( "Zero-length slice"); |
| ret.start = end; |
| // Advance start (towards begin) not farther than begin. |
| std::advance( ret.start, (-i < max_dist) ? i : -max_dist ); |
| } |
| } |
| |
| // Set up the stop iterator. This one is a little trickier since slices |
| // define a [) range, and we are returning a [] range. |
| if (slice_stop == object()) { |
| if (ret.step < 0) { |
| ret.stop = begin; |
| } |
| else { |
| ret.stop = end; |
| std::advance( ret.stop, -1); |
| } |
| } |
| else { |
| difference_type i = extract<long>(slice_stop); |
| // First, branch on which direction we are going with this. |
| if (ret.step < 0) { |
| if (i+1 >= max_dist || i == -1) |
| throw std::invalid_argument( "Zero-length slice"); |
| |
| if (i >= 0) { |
| ret.stop = begin; |
| std::advance( ret.stop, i+1); |
| } |
| else { // i is negative, but more negative than -1. |
| ret.stop = end; |
| std::advance( ret.stop, (-i < max_dist) ? i : -max_dist); |
| } |
| } |
| else { // stepping forward |
| if (i == 0 || -i >= max_dist) |
| throw std::invalid_argument( "Zero-length slice"); |
| |
| if (i > 0) { |
| ret.stop = begin; |
| std::advance( ret.stop, (std::min)( i-1, max_dist-1)); |
| } |
| else { // i is negative, but not more negative than -max_dist |
| ret.stop = end; |
| std::advance( ret.stop, i-1); |
| } |
| } |
| } |
| |
| // Now the fun part, handling the possibilites surrounding step. |
| // At this point, step has been initialized, ret.stop, and ret.step |
| // represent the widest possible range that could be traveled |
| // (inclusive), and final_dist is the maximum distance covered by the |
| // slice. |
| typename iterator_difference<RandomAccessIterator>::type final_dist = |
| boost::detail::distance( ret.start, ret.stop); |
| |
| // First case, if both ret.start and ret.stop are equal, then step |
| // is irrelevant and we can return here. |
| if (final_dist == 0) |
| return ret; |
| |
| // Second, if there is a sign mismatch, than the resulting range and |
| // step size conflict: std::advance( ret.start, ret.step) goes away from |
| // ret.stop. |
| if ((final_dist > 0) != (ret.step > 0)) |
| throw std::invalid_argument( "Zero-length slice."); |
| |
| // Finally, if the last step puts us past the end, we move ret.stop |
| // towards ret.start in the amount of the remainder. |
| // I don't remember all of the oolies surrounding negative modulii, |
| // so I am handling each of these cases separately. |
| if (final_dist < 0) { |
| difference_type remainder = -final_dist % -ret.step; |
| std::advance( ret.stop, remainder); |
| } |
| else { |
| difference_type remainder = final_dist % ret.step; |
| std::advance( ret.stop, -remainder); |
| } |
| |
| return ret; |
| } |
| |
| public: |
| // This declaration, in conjunction with the specialization of |
| // object_manager_traits<> below, allows C++ functions accepting slice |
| // arguments to be called from from Python. These constructors should never |
| // be used in client code. |
| BOOST_PYTHON_FORWARD_OBJECT_CONSTRUCTORS(slice, detail::slice_base) |
| }; |
| |
| |
| namespace converter { |
| |
| template<> |
| struct object_manager_traits<slice> |
| : pytype_object_manager_traits<&PySlice_Type, slice> |
| { |
| }; |
| |
| } // !namesapce converter |
| |
| } } // !namespace ::boost::python |
| |
| |
| #endif // !defined BOOST_PYTHON_SLICE_JDB20040105_HPP |