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