123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759 |
- // (C) Copyright Joel de Guzman 2003.
- // Distributed under 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)
- #ifndef INDEXING_SUITE_DETAIL_JDG20036_HPP
- # define INDEXING_SUITE_DETAIL_JDG20036_HPP
- # include <boost/python/extract.hpp>
- # include <boost/scoped_ptr.hpp>
- # include <boost/get_pointer.hpp>
- # include <boost/detail/binary_search.hpp>
- # include <boost/numeric/conversion/cast.hpp>
- # include <boost/python/detail/type_traits.hpp>
- # include <vector>
- # include <map>
- #include <iostream>
- namespace boost { namespace python { namespace detail {
- #if defined(NDEBUG)
- #define BOOST_PYTHON_INDEXING_CHECK_INVARIANT
- #else
- #define BOOST_PYTHON_INDEXING_CHECK_INVARIANT check_invariant()
- #endif
-
- template <class Proxy>
- struct compare_proxy_index
- {
- // This functor compares a proxy and an index.
- // This is used by proxy_group::first_proxy to
- // get first proxy with index i.
-
- template <class Index>
- bool operator()(PyObject* prox, Index i) const
- {
- typedef typename Proxy::policies_type policies_type;
- Proxy& proxy = extract<Proxy&>(prox)();
- return policies_type::
- compare_index(proxy.get_container(), proxy.get_index(), i);
- }
- };
-
- // The proxy_group class holds a vector of container element
- // proxies. First, what is a container element proxy? A container
- // element proxy acts like a smart pointer holding a reference to
- // a container and an index (see container_element, for details).
- //
- // The proxies are held in a vector always sorted by its index.
- // Various functions manage the addition, removal and searching
- // of proxies from the vector.
- //
- template <class Proxy>
- class proxy_group
- {
- public:
-
- typedef typename std::vector<PyObject*>::const_iterator const_iterator;
- typedef typename std::vector<PyObject*>::iterator iterator;
- typedef typename Proxy::index_type index_type;
- typedef typename Proxy::policies_type policies_type;
-
- iterator
- first_proxy(index_type i)
- {
- // Return the first proxy with index <= i
- return boost::detail::lower_bound(
- proxies.begin(), proxies.end(),
- i, compare_proxy_index<Proxy>());
- }
- void
- remove(Proxy& proxy)
- {
- // Remove a proxy
- for (iterator iter = first_proxy(proxy.get_index());
- iter != proxies.end(); ++iter)
- {
- if (&extract<Proxy&>(*iter)() == &proxy)
- {
- proxies.erase(iter);
- break;
- }
- }
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- }
- void
- add(PyObject* prox)
- {
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- // Add a proxy
- proxies.insert(
- first_proxy(extract<Proxy&>(prox)().get_index()), prox);
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- }
- void
- erase(index_type i, mpl::false_)
- {
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- // Erase the proxy with index i
- replace(i, i+1, 0);
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- }
- void
- erase(index_type i, mpl::true_)
- {
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- // Erase the proxy with index i
-
- iterator iter = first_proxy(i);
- extract<Proxy&> p(*iter);
-
- if (iter != proxies.end() && p().get_index() == i)
- {
- extract<Proxy&> p(*iter);
- p().detach();
- proxies.erase(iter);
- }
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- }
- void
- erase(index_type from, index_type to)
- {
- // note: this cannot be called when container is not sliceable
-
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- // Erase all proxies with indexes from..to
- replace(from, to, 0);
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- }
- void
- replace(
- index_type from,
- index_type to,
- typename std::vector<PyObject*>::size_type len)
- {
- // note: this cannot be called when container is not sliceable
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- // Erase all proxies with indexes from..to.
- // Adjust the displaced indexes such that the
- // final effect is that we have inserted *len*
- // number of proxies in the vacated region. This
- // procedure involves adjusting the indexes of
- // the proxies.
-
- iterator left = first_proxy(from);
- iterator right = proxies.end(); // we'll adjust this later
-
- for (iterator iter = left; iter != right; ++iter)
- {
- if (extract<Proxy&>(*iter)().get_index() > to)
- {
- right = iter; // adjust right
- break;
- }
- extract<Proxy&> p(*iter);
- p().detach();
- }
-
- typename std::vector<PyObject*>::size_type
- offset = left-proxies.begin();
- proxies.erase(left, right);
- right = proxies.begin()+offset;
- while (right != proxies.end())
- {
- typedef typename Proxy::container_type::difference_type difference_type;
- extract<Proxy&> p(*right);
- p().set_index(
- extract<Proxy&>(*right)().get_index()
- - (difference_type(to) - from - len)
- );
-
- ++right;
- }
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- }
-
- PyObject*
- find(index_type i)
- {
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- // Find the proxy with *exact* index i.
- // Return 0 (null) if no proxy with the
- // given index is found.
- iterator iter = first_proxy(i);
- if (iter != proxies.end()
- && extract<Proxy&>(*iter)().get_index() == i)
- {
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- return *iter;
- }
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- return 0;
- }
- typename std::vector<PyObject*>::size_type
- size() const
- {
- BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
- // How many proxies are there so far?
- return proxies.size();
- }
- private:
- #if !defined(NDEBUG)
- void
- check_invariant() const
- {
- for (const_iterator i = proxies.begin(); i != proxies.end(); ++i)
- {
- if ((*i)->ob_refcnt <= 0)
- {
- PyErr_SetString(PyExc_RuntimeError,
- "Invariant: Proxy vector in an inconsistent state");
- throw_error_already_set();
- }
-
- if (i+1 != proxies.end())
- {
- if (extract<Proxy&>(*(i+1))().get_index() ==
- extract<Proxy&>(*(i))().get_index())
- {
- PyErr_SetString(PyExc_RuntimeError,
- "Invariant: Proxy vector in an inconsistent state (duplicate proxy)");
- throw_error_already_set();
- }
- }
- }
- }
- #endif
-
- std::vector<PyObject*> proxies;
- };
-
- // proxy_links holds a map of Container pointers (keys)
- // with proxy_group(s) (data). Various functions manage
- // the addition, removal and searching of proxies from
- // the map.
- //
- template <class Proxy, class Container>
- class proxy_links
- {
- public:
-
- typedef std::map<Container*, proxy_group<Proxy> > links_t;
- typedef typename Proxy::index_type index_type;
- void
- remove(Proxy& proxy)
- {
- // Remove a proxy.
- typename links_t::iterator r = links.find(&proxy.get_container());
- if (r != links.end())
- {
- r->second.remove(proxy);
- if (r->second.size() == 0)
- links.erase(r);
- }
- }
-
- void
- add(PyObject* prox, Container& container)
- {
- // Add a proxy
- links[&container].add(prox);
- }
-
- template <class NoSlice>
- void erase(Container& container, index_type i, NoSlice no_slice)
- {
- // Erase the proxy with index i
- typename links_t::iterator r = links.find(&container);
- if (r != links.end())
- {
- r->second.erase(i, no_slice);
- if (r->second.size() == 0)
- links.erase(r);
- }
- }
-
- void
- erase(Container& container, index_type from, index_type to)
- {
- // Erase all proxies with indexes from..to
- typename links_t::iterator r = links.find(&container);
- if (r != links.end())
- {
- r->second.erase(from, to);
- if (r->second.size() == 0)
- links.erase(r);
- }
- }
- void
- replace(
- Container& container,
- index_type from, index_type to, index_type len)
- {
- // Erase all proxies with indexes from..to.
- // Adjust the displaced indexes such that the
- // final effect is that we have inserted *len*
- // number of proxies in the vacated region. This
- // procedure involves adjusting the indexes of
- // the proxies.
- typename links_t::iterator r = links.find(&container);
- if (r != links.end())
- {
- r->second.replace(from, to, len);
- if (r->second.size() == 0)
- links.erase(r);
- }
- }
-
- PyObject*
- find(Container& container, index_type i)
- {
- // Find the proxy with *exact* index i.
- // Return 0 (null) if no proxy with the given
- // index is found.
- typename links_t::iterator r = links.find(&container);
- if (r != links.end())
- return r->second.find(i);
- return 0;
- }
- private:
-
- links_t links;
- };
-
- // container_element is our container proxy class.
- // This class acts like a smart pointer to a container
- // element. The class holds an index and a reference to
- // a container. Dereferencing the smart pointer will
- // retrieve the nth (index) element from the container.
- //
- // A container_element can also be detached from the
- // container. In such a detached state, the container_element
- // holds a copy of the nth (index) element, which it
- // returns when dereferenced.
- //
- template <class Container, class Index, class Policies>
- class container_element
- {
- public:
-
- typedef Index index_type;
- typedef Container container_type;
- typedef typename Policies::data_type element_type;
- typedef Policies policies_type;
- typedef container_element<Container, Index, Policies> self_t;
- typedef proxy_group<self_t> links_type;
-
- container_element(object container, Index index)
- : ptr()
- , container(container)
- , index(index)
- {
- }
-
- container_element(container_element const& ce)
- : ptr(ce.ptr.get() == 0 ? 0 : new element_type(*ce.ptr.get()))
- , container(ce.container)
- , index(ce.index)
- {
- }
- ~container_element()
- {
- if (!is_detached())
- get_links().remove(*this);
- }
-
- element_type& operator*() const
- {
- if (is_detached())
- return *get_pointer(ptr);
- return Policies::get_item(get_container(), index);
- }
-
- element_type* get() const
- {
- if (is_detached())
- return get_pointer(ptr);
- return &Policies::get_item(get_container(), index);
- }
-
- void
- detach()
- {
- if (!is_detached())
- {
- ptr.reset(
- new element_type(
- Policies::get_item(get_container(), index)));
- container = object(); // free container. reset it to None
- }
- }
-
- bool
- is_detached() const
- {
- return get_pointer(ptr) != 0;
- }
- Container&
- get_container() const
- {
- return extract<Container&>(container)();
- }
-
- Index
- get_index() const
- {
- return index;
- }
- void
- set_index(Index i)
- {
- index = i;
- }
-
- static proxy_links<self_t, Container>&
- get_links()
- {
- // All container_element(s) maintain links to
- // its container in a global map (see proxy_links).
- // This global "links" map is a singleton.
-
- static proxy_links<self_t, Container> links;
- return links; // singleton
- }
- private:
-
- container_element& operator=(container_element const& ce);
- scoped_ptr<element_type> ptr;
- object container;
- Index index;
- };
- template <
- class Container
- , class DerivedPolicies
- , class ContainerElement
- , class Index
- >
- struct no_proxy_helper
- {
- static void
- register_container_element()
- {
- }
- template <class DataType>
- static object
- base_get_item_helper(DataType const& p, detail::true_)
- {
- return object(ptr(p));
- }
- template <class DataType>
- static object
- base_get_item_helper(DataType const& x, detail::false_)
- {
- return object(x);
- }
- static object
- base_get_item_(back_reference<Container&> const& container, PyObject* i)
- {
- return base_get_item_helper(
- DerivedPolicies::get_item(
- container.get(), DerivedPolicies::
- convert_index(container.get(), i))
- , is_pointer<BOOST_DEDUCED_TYPENAME Container::value_type>()
- );
- }
- static void
- base_replace_indexes(
- Container& /*container*/, Index /*from*/,
- Index /*to*/, Index /*n*/)
- {
- }
- template <class NoSlice>
- static void
- base_erase_index(
- Container& /*container*/, Index /*i*/, NoSlice /*no_slice*/)
- {
- }
-
- static void
- base_erase_indexes(Container& /*container*/, Index /*from*/, Index /*to*/)
- {
- }
- };
-
- template <
- class Container
- , class DerivedPolicies
- , class ContainerElement
- , class Index
- >
- struct proxy_helper
- {
- static void
- register_container_element()
- {
- register_ptr_to_python<ContainerElement>();
- }
- static object
- base_get_item_(back_reference<Container&> const& container, PyObject* i)
- {
- // Proxy
- Index idx = DerivedPolicies::convert_index(container.get(), i);
- if (PyObject* shared =
- ContainerElement::get_links().find(container.get(), idx))
- {
- handle<> h(python::borrowed(shared));
- return object(h);
- }
- else
- {
- object prox(ContainerElement(container.source(), idx));
- ContainerElement::
- get_links().add(prox.ptr(), container.get());
- return prox;
- }
- }
- static void
- base_replace_indexes(
- Container& container, Index from,
- Index to, Index n)
- {
- ContainerElement::get_links().replace(container, from, to, n);
- }
-
- template <class NoSlice>
- static void
- base_erase_index(
- Container& container, Index i, NoSlice no_slice)
- {
- ContainerElement::get_links().erase(container, i, no_slice);
- }
-
- static void
- base_erase_indexes(
- Container& container, Index from, Index to)
- {
- ContainerElement::get_links().erase(container, from, to);
- }
- };
-
- template <
- class Container
- , class DerivedPolicies
- , class ProxyHandler
- , class Data
- , class Index
- >
- struct slice_helper
- {
- static object
- base_get_slice(Container& container, PySliceObject* slice)
- {
- Index from, to;
- base_get_slice_data(container, slice, from, to);
- return DerivedPolicies::get_slice(container, from, to);
- }
- static void
- base_get_slice_data(
- Container& container, PySliceObject* slice, Index& from_, Index& to_)
- {
- if (Py_None != slice->step) {
- PyErr_SetString( PyExc_IndexError, "slice step size not supported.");
- throw_error_already_set();
- }
- Index min_index = DerivedPolicies::get_min_index(container);
- Index max_index = DerivedPolicies::get_max_index(container);
-
- if (Py_None == slice->start) {
- from_ = min_index;
- }
- else {
- long from = extract<long>( slice->start);
- if (from < 0) // Negative slice index
- from += max_index;
- if (from < 0) // Clip lower bounds to zero
- from = 0;
- from_ = boost::numeric_cast<Index>(from);
- if (from_ > max_index) // Clip upper bounds to max_index.
- from_ = max_index;
- }
- if (Py_None == slice->stop) {
- to_ = max_index;
- }
- else {
- long to = extract<long>( slice->stop);
- if (to < 0)
- to += max_index;
- if (to < 0)
- to = 0;
- to_ = boost::numeric_cast<Index>(to);
- if (to_ > max_index)
- to_ = max_index;
- }
- }
-
- static void
- base_set_slice(Container& container, PySliceObject* slice, PyObject* v)
- {
- Index from, to;
- base_get_slice_data(container, slice, from, to);
-
- extract<Data&> elem(v);
- // try if elem is an exact Data
- if (elem.check())
- {
- ProxyHandler::base_replace_indexes(container, from, to, 1);
- DerivedPolicies::set_slice(container, from, to, elem());
- }
- else
- {
- // try to convert elem to Data
- extract<Data> elem(v);
- if (elem.check())
- {
- ProxyHandler::base_replace_indexes(container, from, to, 1);
- DerivedPolicies::set_slice(container, from, to, elem());
- }
- else
- {
- // Otherwise, it must be a list or some container
- handle<> l_(python::borrowed(v));
- object l(l_);
-
- std::vector<Data> temp;
- for (int i = 0; i < l.attr("__len__")(); i++)
- {
- object elem(l[i]);
- extract<Data const&> x(elem);
- // try if elem is an exact Data type
- if (x.check())
- {
- temp.push_back(x());
- }
- else
- {
- // try to convert elem to Data type
- extract<Data> x(elem);
- if (x.check())
- {
- temp.push_back(x());
- }
- else
- {
- PyErr_SetString(PyExc_TypeError,
- "Invalid sequence element");
- throw_error_already_set();
- }
- }
- }
-
- ProxyHandler::base_replace_indexes(container, from, to,
- temp.end()-temp.begin());
- DerivedPolicies::set_slice(container, from, to,
- temp.begin(), temp.end());
- }
- }
- }
-
- static void
- base_delete_slice(Container& container, PySliceObject* slice)
- {
- Index from, to;
- base_get_slice_data(container, slice, from, to);
- ProxyHandler::base_erase_indexes(container, from, to);
- DerivedPolicies::delete_slice(container, from, to);
- }
- };
-
- template <
- class Container
- , class DerivedPolicies
- , class ProxyHandler
- , class Data
- , class Index
- >
- struct no_slice_helper
- {
- static void
- slicing_not_suported()
- {
- PyErr_SetString(PyExc_RuntimeError, "Slicing not supported");
- throw_error_already_set();
- }
-
- static object
- base_get_slice(Container& /*container*/, PySliceObject* /*slice*/)
- {
- slicing_not_suported();
- return object();
- }
-
- static void
- base_set_slice(Container& /*container*/, PySliceObject* /*slice*/, PyObject* /*v*/)
- {
- slicing_not_suported();
- }
-
- static void
- base_delete_slice(Container& /*container*/, PySliceObject* /*slice*/)
- {
- slicing_not_suported();
- }
- };
- #ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP
- }} // namespace python::detail
- #endif
- template <class Container, class Index, class Policies>
- inline typename Policies::data_type*
- get_pointer(
- python::detail::container_element<Container, Index, Policies> const& p)
- {
- // Get the pointer of a container_element smart pointer
- return p.get();
- }
- #ifndef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP
- // Don't hide these other get_pointer overloads
- using boost::python::get_pointer;
- using boost::get_pointer;
- }} // namespace python::detail
- #endif
- } // namespace boost
- #endif // INDEXING_SUITE_DETAIL_JDG20036_HPP
|