1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ossrv_pub/boost_apis/boost/python/slice.hpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,266 @@
1.4 +#ifndef BOOST_PYTHON_SLICE_JDB20040105_HPP
1.5 +#define BOOST_PYTHON_SLICE_JDB20040105_HPP
1.6 +
1.7 +// Copyright (c) 2004 Jonathan Brandmeyer
1.8 +// Use, modification and distribution are subject to the
1.9 +// Boost Software License, Version 1.0. (See accompanying file
1.10 +// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
1.11 +
1.12 +#include <boost/python/detail/prefix.hpp>
1.13 +#include <boost/config.hpp>
1.14 +#include <boost/python/object.hpp>
1.15 +#include <boost/python/extract.hpp>
1.16 +#include <boost/python/converter/pytype_object_mgr_traits.hpp>
1.17 +
1.18 +#include <boost/iterator/iterator_traits.hpp>
1.19 +
1.20 +#include <iterator>
1.21 +#include <algorithm>
1.22 +
1.23 +namespace boost { namespace python {
1.24 +
1.25 +namespace detail
1.26 +{
1.27 + class BOOST_PYTHON_DECL slice_base : public object
1.28 + {
1.29 + public:
1.30 + // Get the Python objects associated with the slice. In principle, these
1.31 + // may be any arbitrary Python type, but in practice they are usually
1.32 + // integers. If one or more parameter is ommited in the Python expression
1.33 + // that created this slice, than that parameter is None here, and compares
1.34 + // equal to a default-constructed boost::python::object.
1.35 + // If a user-defined type wishes to support slicing, then support for the
1.36 + // special meaning associated with negative indicies is up to the user.
1.37 + object start() const;
1.38 + object stop() const;
1.39 + object step() const;
1.40 +
1.41 + protected:
1.42 + explicit slice_base(PyObject*, PyObject*, PyObject*);
1.43 +
1.44 + BOOST_PYTHON_FORWARD_OBJECT_CONSTRUCTORS(slice_base, object)
1.45 + };
1.46 +}
1.47 +
1.48 +class slice : public detail::slice_base
1.49 +{
1.50 + typedef detail::slice_base base;
1.51 + public:
1.52 + // Equivalent to slice(::)
1.53 + slice() : base(0,0,0) {}
1.54 +
1.55 + // Each argument must be slice_nil, or implicitly convertable to object.
1.56 + // They should normally be integers.
1.57 + template<typename Integer1, typename Integer2>
1.58 + slice( Integer1 start, Integer2 stop)
1.59 + : base( object(start).ptr(), object(stop).ptr(), 0 )
1.60 + {}
1.61 +
1.62 + template<typename Integer1, typename Integer2, typename Integer3>
1.63 + slice( Integer1 start, Integer2 stop, Integer3 stride)
1.64 + : base( object(start).ptr(), object(stop).ptr(), object(stride).ptr() )
1.65 + {}
1.66 +
1.67 + // The following algorithm is intended to automate the process of
1.68 + // determining a slice range when you want to fully support negative
1.69 + // indicies and non-singular step sizes. Its functionallity is simmilar to
1.70 + // PySlice_GetIndicesEx() in the Python/C API, but tailored for C++ users.
1.71 + // This template returns a slice::range struct that, when used in the
1.72 + // following iterative loop, will traverse a slice of the function's
1.73 + // arguments.
1.74 + // while (start != end) {
1.75 + // do_foo(...);
1.76 + // std::advance( start, step);
1.77 + // }
1.78 + // do_foo(...); // repeat exactly once more.
1.79 +
1.80 + // Arguments: a [begin, end) pair of STL-conforming random-access iterators.
1.81 +
1.82 + // Return: slice::range, where start and stop define a _closed_ interval
1.83 + // that covers at most [begin, end-1] of the provided arguments, and a step
1.84 + // that is non-zero.
1.85 +
1.86 + // Throws: error_already_set() if any of the indices are neither None nor
1.87 + // integers, or the slice has a step value of zero.
1.88 + // std::invalid_argument if the resulting range would be empty. Normally,
1.89 + // you should catch this exception and return an empty sequence of the
1.90 + // appropriate type.
1.91 +
1.92 + // Performance: constant time for random-access iterators.
1.93 +
1.94 + // Rationale:
1.95 + // closed-interval: If an open interval were used, then for a non-singular
1.96 + // value for step, the required state for the end iterator could be
1.97 + // beyond the one-past-the-end postion of the specified range. While
1.98 + // probably harmless, the behavior of STL-conforming iterators is
1.99 + // undefined in this case.
1.100 + // exceptions on zero-length range: It is impossible to define a closed
1.101 + // interval over an empty range, so some other form of error checking
1.102 + // would have to be used by the user to prevent undefined behavior. In
1.103 + // the case where the user fails to catch the exception, it will simply
1.104 + // be translated to Python by the default exception handling mechanisms.
1.105 +
1.106 + template<typename RandomAccessIterator>
1.107 + struct range
1.108 + {
1.109 + RandomAccessIterator start;
1.110 + RandomAccessIterator stop;
1.111 + typename iterator_difference<RandomAccessIterator>::type step;
1.112 + };
1.113 +
1.114 + template<typename RandomAccessIterator>
1.115 + slice::range<RandomAccessIterator>
1.116 + get_indicies( const RandomAccessIterator& begin,
1.117 + const RandomAccessIterator& end) const
1.118 + {
1.119 + // This is based loosely on PySlice_GetIndicesEx(), but it has been
1.120 + // carefully crafted to ensure that these iterators never fall out of
1.121 + // the range of the container.
1.122 + slice::range<RandomAccessIterator> ret;
1.123 +
1.124 + typedef typename iterator_difference<RandomAccessIterator>::type difference_type;
1.125 + difference_type max_dist = boost::detail::distance(begin, end);
1.126 +
1.127 + object slice_start = this->start();
1.128 + object slice_stop = this->stop();
1.129 + object slice_step = this->step();
1.130 +
1.131 + // Extract the step.
1.132 + if (slice_step == object()) {
1.133 + ret.step = 1;
1.134 + }
1.135 + else {
1.136 + ret.step = extract<long>( slice_step);
1.137 + if (ret.step == 0) {
1.138 + PyErr_SetString( PyExc_IndexError, "step size cannot be zero.");
1.139 + throw_error_already_set();
1.140 + }
1.141 + }
1.142 +
1.143 + // Setup the start iterator.
1.144 + if (slice_start == object()) {
1.145 + if (ret.step < 0) {
1.146 + ret.start = end;
1.147 + --ret.start;
1.148 + }
1.149 + else
1.150 + ret.start = begin;
1.151 + }
1.152 + else {
1.153 + difference_type i = extract<long>( slice_start);
1.154 + if (i >= max_dist && ret.step > 0)
1.155 + throw std::invalid_argument( "Zero-length slice");
1.156 + if (i >= 0) {
1.157 + ret.start = begin;
1.158 + BOOST_USING_STD_MIN();
1.159 + std::advance( ret.start, min BOOST_PREVENT_MACRO_SUBSTITUTION(i, max_dist-1));
1.160 + }
1.161 + else {
1.162 + if (i < -max_dist && ret.step < 0)
1.163 + throw std::invalid_argument( "Zero-length slice");
1.164 + ret.start = end;
1.165 + // Advance start (towards begin) not farther than begin.
1.166 + std::advance( ret.start, (-i < max_dist) ? i : -max_dist );
1.167 + }
1.168 + }
1.169 +
1.170 + // Set up the stop iterator. This one is a little trickier since slices
1.171 + // define a [) range, and we are returning a [] range.
1.172 + if (slice_stop == object()) {
1.173 + if (ret.step < 0) {
1.174 + ret.stop = begin;
1.175 + }
1.176 + else {
1.177 + ret.stop = end;
1.178 + std::advance( ret.stop, -1);
1.179 + }
1.180 + }
1.181 + else {
1.182 + difference_type i = extract<long>(slice_stop);
1.183 + // First, branch on which direction we are going with this.
1.184 + if (ret.step < 0) {
1.185 + if (i+1 >= max_dist || i == -1)
1.186 + throw std::invalid_argument( "Zero-length slice");
1.187 +
1.188 + if (i >= 0) {
1.189 + ret.stop = begin;
1.190 + std::advance( ret.stop, i+1);
1.191 + }
1.192 + else { // i is negative, but more negative than -1.
1.193 + ret.stop = end;
1.194 + std::advance( ret.stop, (-i < max_dist) ? i : -max_dist);
1.195 + }
1.196 + }
1.197 + else { // stepping forward
1.198 + if (i == 0 || -i >= max_dist)
1.199 + throw std::invalid_argument( "Zero-length slice");
1.200 +
1.201 + if (i > 0) {
1.202 + ret.stop = begin;
1.203 + std::advance( ret.stop, (std::min)( i-1, max_dist-1));
1.204 + }
1.205 + else { // i is negative, but not more negative than -max_dist
1.206 + ret.stop = end;
1.207 + std::advance( ret.stop, i-1);
1.208 + }
1.209 + }
1.210 + }
1.211 +
1.212 + // Now the fun part, handling the possibilites surrounding step.
1.213 + // At this point, step has been initialized, ret.stop, and ret.step
1.214 + // represent the widest possible range that could be traveled
1.215 + // (inclusive), and final_dist is the maximum distance covered by the
1.216 + // slice.
1.217 + typename iterator_difference<RandomAccessIterator>::type final_dist =
1.218 + boost::detail::distance( ret.start, ret.stop);
1.219 +
1.220 + // First case, if both ret.start and ret.stop are equal, then step
1.221 + // is irrelevant and we can return here.
1.222 + if (final_dist == 0)
1.223 + return ret;
1.224 +
1.225 + // Second, if there is a sign mismatch, than the resulting range and
1.226 + // step size conflict: std::advance( ret.start, ret.step) goes away from
1.227 + // ret.stop.
1.228 + if ((final_dist > 0) != (ret.step > 0))
1.229 + throw std::invalid_argument( "Zero-length slice.");
1.230 +
1.231 + // Finally, if the last step puts us past the end, we move ret.stop
1.232 + // towards ret.start in the amount of the remainder.
1.233 + // I don't remember all of the oolies surrounding negative modulii,
1.234 + // so I am handling each of these cases separately.
1.235 + if (final_dist < 0) {
1.236 + difference_type remainder = -final_dist % -ret.step;
1.237 + std::advance( ret.stop, remainder);
1.238 + }
1.239 + else {
1.240 + difference_type remainder = final_dist % ret.step;
1.241 + std::advance( ret.stop, -remainder);
1.242 + }
1.243 +
1.244 + return ret;
1.245 + }
1.246 +
1.247 + public:
1.248 + // This declaration, in conjunction with the specialization of
1.249 + // object_manager_traits<> below, allows C++ functions accepting slice
1.250 + // arguments to be called from from Python. These constructors should never
1.251 + // be used in client code.
1.252 + BOOST_PYTHON_FORWARD_OBJECT_CONSTRUCTORS(slice, detail::slice_base)
1.253 +};
1.254 +
1.255 +
1.256 +namespace converter {
1.257 +
1.258 +template<>
1.259 +struct object_manager_traits<slice>
1.260 + : pytype_object_manager_traits<&PySlice_Type, slice>
1.261 +{
1.262 +};
1.263 +
1.264 +} // !namesapce converter
1.265 +
1.266 +} } // !namespace ::boost::python
1.267 +
1.268 +
1.269 +#endif // !defined BOOST_PYTHON_SLICE_JDB20040105_HPP