1 // (C) Copyright Joel de Guzman 2003.
2 // Distributed under the Boost Software License, Version 1.0. (See
3 // accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
6 #ifndef INDEXING_SUITE_DETAIL_JDG20036_HPP
7 # define INDEXING_SUITE_DETAIL_JDG20036_HPP
9 # include <boost/python/extract.hpp>
10 # include <boost/scoped_ptr.hpp>
11 # include <boost/get_pointer.hpp>
12 # include <boost/detail/binary_search.hpp>
13 # include <boost/numeric/conversion/cast.hpp>
14 # include <boost/type_traits/is_pointer.hpp>
19 namespace boost { namespace python { namespace detail {
22 #define BOOST_PYTHON_INDEXING_CHECK_INVARIANT
24 #define BOOST_PYTHON_INDEXING_CHECK_INVARIANT check_invariant()
27 template <class Proxy>
28 struct compare_proxy_index
30 // This functor compares a proxy and an index.
31 // This is used by proxy_group::first_proxy to
32 // get first proxy with index i.
34 template <class Index>
35 bool operator()(PyObject* prox, Index i) const
37 typedef typename Proxy::policies_type policies_type;
38 Proxy& proxy = extract<Proxy&>(prox)();
39 return policies_type::
40 compare_index(proxy.get_container(), proxy.get_index(), i);
44 // The proxy_group class holds a vector of container element
45 // proxies. First, what is a container element proxy? A container
46 // element proxy acts like a smart pointer holding a reference to
47 // a container and an index (see container_element, for details).
49 // The proxies are held in a vector always sorted by its index.
50 // Various functions manage the addition, removal and searching
51 // of proxies from the vector.
53 template <class Proxy>
58 typedef typename std::vector<PyObject*>::const_iterator const_iterator;
59 typedef typename std::vector<PyObject*>::iterator iterator;
60 typedef typename Proxy::index_type index_type;
61 typedef typename Proxy::policies_type policies_type;
64 first_proxy(index_type i)
66 // Return the first proxy with index <= i
67 return boost::detail::lower_bound(
68 proxies.begin(), proxies.end(),
69 i, compare_proxy_index<Proxy>());
76 for (iterator iter = first_proxy(proxy.get_index());
77 iter != proxies.end(); ++iter)
79 if (&extract<Proxy&>(*iter)() == &proxy)
85 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
91 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
94 first_proxy(extract<Proxy&>(prox)().get_index()), prox);
95 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
99 erase(index_type i, mpl::false_)
101 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
102 // Erase the proxy with index i
104 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
108 erase(index_type i, mpl::true_)
110 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
111 // Erase the proxy with index i
113 iterator iter = first_proxy(i);
114 extract<Proxy&> p(*iter);
116 if (iter != proxies.end() && p().get_index() == i)
118 extract<Proxy&> p(*iter);
122 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
126 erase(index_type from, index_type to)
128 // note: this cannot be called when container is not sliceable
130 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
131 // Erase all proxies with indexes from..to
132 replace(from, to, 0);
133 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
140 typename std::vector<PyObject*>::size_type len)
142 // note: this cannot be called when container is not sliceable
144 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
145 // Erase all proxies with indexes from..to.
146 // Adjust the displaced indexes such that the
147 // final effect is that we have inserted *len*
148 // number of proxies in the vacated region. This
149 // procedure involves adjusting the indexes of
152 iterator left = first_proxy(from);
153 iterator right = proxies.end(); // we'll adjust this later
155 for (iterator iter = left; iter != right; ++iter)
157 if (extract<Proxy&>(*iter)().get_index() > to)
159 right = iter; // adjust right
162 extract<Proxy&> p(*iter);
166 typename std::vector<PyObject*>::size_type
167 offset = left-proxies.begin();
168 proxies.erase(left, right);
169 right = proxies.begin()+offset;
171 while (right != proxies.end())
173 typedef typename Proxy::container_type::difference_type difference_type;
174 extract<Proxy&> p(*right);
176 extract<Proxy&>(*right)().get_index()
177 - (difference_type(to) - from - len)
182 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
188 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
189 // Find the proxy with *exact* index i.
190 // Return 0 (null) if no proxy with the
191 // given index is found.
192 iterator iter = first_proxy(i);
193 if (iter != proxies.end()
194 && extract<Proxy&>(*iter)().get_index() == i)
196 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
199 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
203 typename std::vector<PyObject*>::size_type
206 BOOST_PYTHON_INDEXING_CHECK_INVARIANT;
207 // How many proxies are there so far?
208 return proxies.size();
215 check_invariant() const
217 for (const_iterator i = proxies.begin(); i != proxies.end(); ++i)
219 if ((*i)->ob_refcnt <= 0)
221 PyErr_SetString(PyExc_RuntimeError,
222 "Invariant: Proxy vector in an inconsistent state");
223 throw_error_already_set();
226 if (i+1 != proxies.end())
228 if (extract<Proxy&>(*(i+1))().get_index() ==
229 extract<Proxy&>(*(i))().get_index())
231 PyErr_SetString(PyExc_RuntimeError,
232 "Invariant: Proxy vector in an inconsistent state (duplicate proxy)");
233 throw_error_already_set();
240 std::vector<PyObject*> proxies;
243 // proxy_links holds a map of Container pointers (keys)
244 // with proxy_group(s) (data). Various functions manage
245 // the addition, removal and searching of proxies from
248 template <class Proxy, class Container>
253 typedef std::map<Container*, proxy_group<Proxy> > links_t;
254 typedef typename Proxy::index_type index_type;
260 typename links_t::iterator r = links.find(&proxy.get_container());
261 if (r != links.end())
263 r->second.remove(proxy);
264 if (r->second.size() == 0)
270 add(PyObject* prox, Container& container)
273 links[&container].add(prox);
276 template <class NoSlice>
277 void erase(Container& container, index_type i, NoSlice no_slice)
279 // Erase the proxy with index i
280 typename links_t::iterator r = links.find(&container);
281 if (r != links.end())
283 r->second.erase(i, no_slice);
284 if (r->second.size() == 0)
290 erase(Container& container, index_type from, index_type to)
292 // Erase all proxies with indexes from..to
293 typename links_t::iterator r = links.find(&container);
294 if (r != links.end())
296 r->second.erase(from, to);
297 if (r->second.size() == 0)
304 Container& container,
305 index_type from, index_type to, index_type len)
307 // Erase all proxies with indexes from..to.
308 // Adjust the displaced indexes such that the
309 // final effect is that we have inserted *len*
310 // number of proxies in the vacated region. This
311 // procedure involves adjusting the indexes of
314 typename links_t::iterator r = links.find(&container);
315 if (r != links.end())
317 r->second.replace(from, to, len);
318 if (r->second.size() == 0)
324 find(Container& container, index_type i)
326 // Find the proxy with *exact* index i.
327 // Return 0 (null) if no proxy with the given
329 typename links_t::iterator r = links.find(&container);
330 if (r != links.end())
331 return r->second.find(i);
340 // container_element is our container proxy class.
341 // This class acts like a smart pointer to a container
342 // element. The class holds an index and a reference to
343 // a container. Dereferencing the smart pointer will
344 // retrieve the nth (index) element from the container.
346 // A container_element can also be detached from the
347 // container. In such a detached state, the container_element
348 // holds a copy of the nth (index) element, which it
349 // returns when dereferenced.
351 template <class Container, class Index, class Policies>
352 class container_element
356 typedef Index index_type;
357 typedef Container container_type;
358 typedef typename Policies::data_type element_type;
359 typedef Policies policies_type;
360 typedef container_element<Container, Index, Policies> self_t;
361 typedef proxy_group<self_t> links_type;
363 container_element(object container, Index index)
365 , container(container)
370 container_element(container_element const& ce)
371 : ptr(ce.ptr.get() == 0 ? 0 : new element_type(*ce.ptr.get()))
372 , container(ce.container)
380 get_links().remove(*this);
383 element_type& operator*() const
386 return *get_pointer(ptr);
387 return Policies::get_item(get_container(), index);
390 element_type* get() const
393 return get_pointer(ptr);
394 return &Policies::get_item(get_container(), index);
404 Policies::get_item(get_container(), index)));
405 container = object(); // free container. reset it to None
412 return get_pointer(ptr) != 0;
416 get_container() const
418 return extract<Container&>(container)();
433 static proxy_links<self_t, Container>&
436 // All container_element(s) maintain links to
437 // its container in a global map (see proxy_links).
438 // This global "links" map is a singleton.
440 static proxy_links<self_t, Container> links;
441 return links; // singleton
446 container_element& operator=(container_element const& ce);
448 scoped_ptr<element_type> ptr;
455 , class DerivedPolicies
456 , class ContainerElement
459 struct no_proxy_helper
462 register_container_element()
466 template <class DataType>
468 base_get_item_helper(DataType const& p, mpl::true_)
470 return object(ptr(p));
473 template <class DataType>
475 base_get_item_helper(DataType const& x, mpl::false_)
481 base_get_item_(back_reference<Container&> const& container, PyObject* i)
483 return base_get_item_helper(
484 DerivedPolicies::get_item(
485 container.get(), DerivedPolicies::
486 convert_index(container.get(), i))
487 , is_pointer<BOOST_DEDUCED_TYPENAME Container::value_type>()
492 base_replace_indexes(
493 Container& /*container*/, Index /*from*/,
494 Index /*to*/, Index /*n*/)
498 template <class NoSlice>
501 Container& /*container*/, Index /*i*/, NoSlice /*no_slice*/)
506 base_erase_indexes(Container& /*container*/, Index /*from*/, Index /*to*/)
513 , class DerivedPolicies
514 , class ContainerElement
520 register_container_element()
522 register_ptr_to_python<ContainerElement>();
526 base_get_item_(back_reference<Container&> const& container, PyObject* i)
529 Index idx = DerivedPolicies::convert_index(container.get(), i);
531 if (PyObject* shared =
532 ContainerElement::get_links().find(container.get(), idx))
534 handle<> h(python::borrowed(shared));
539 object prox(ContainerElement(container.source(), idx));
541 get_links().add(prox.ptr(), container.get());
547 base_replace_indexes(
548 Container& container, Index from,
551 ContainerElement::get_links().replace(container, from, to, n);
554 template <class NoSlice>
557 Container& container, Index i, NoSlice no_slice)
559 ContainerElement::get_links().erase(container, i, no_slice);
564 Container& container, Index from, Index to)
566 ContainerElement::get_links().erase(container, from, to);
572 , class DerivedPolicies
580 base_get_slice(Container& container, PySliceObject* slice)
583 base_get_slice_data(container, slice, from, to);
584 return DerivedPolicies::get_slice(container, from, to);
589 Container& container, PySliceObject* slice, Index& from_, Index& to_)
591 if (Py_None != slice->step) {
592 PyErr_SetString( PyExc_IndexError, "slice step size not supported.");
593 throw_error_already_set();
596 Index min_index = DerivedPolicies::get_min_index(container);
597 Index max_index = DerivedPolicies::get_max_index(container);
599 if (Py_None == slice->start) {
603 long from = extract<long>( slice->start);
604 if (from < 0) // Negative slice index
606 if (from < 0) // Clip lower bounds to zero
608 from_ = boost::numeric_cast<Index>(from);
609 if (from_ > max_index) // Clip upper bounds to max_index.
613 if (Py_None == slice->stop) {
617 long to = extract<long>( slice->stop);
622 to_ = boost::numeric_cast<Index>(to);
629 base_set_slice(Container& container, PySliceObject* slice, PyObject* v)
632 base_get_slice_data(container, slice, from, to);
634 extract<Data&> elem(v);
635 // try if elem is an exact Data
638 ProxyHandler::base_replace_indexes(container, from, to, 1);
639 DerivedPolicies::set_slice(container, from, to, elem());
643 // try to convert elem to Data
644 extract<Data> elem(v);
647 ProxyHandler::base_replace_indexes(container, from, to, 1);
648 DerivedPolicies::set_slice(container, from, to, elem());
652 // Otherwise, it must be a list or some container
653 handle<> l_(python::borrowed(v));
656 std::vector<Data> temp;
657 for (int i = 0; i < l.attr("__len__")(); i++)
660 extract<Data const&> x(elem);
661 // try if elem is an exact Data type
668 // try to convert elem to Data type
669 extract<Data> x(elem);
676 PyErr_SetString(PyExc_TypeError,
677 "Invalid sequence element");
678 throw_error_already_set();
683 ProxyHandler::base_replace_indexes(container, from, to,
684 temp.end()-temp.begin());
685 DerivedPolicies::set_slice(container, from, to,
686 temp.begin(), temp.end());
692 base_delete_slice(Container& container, PySliceObject* slice)
695 base_get_slice_data(container, slice, from, to);
696 ProxyHandler::base_erase_indexes(container, from, to);
697 DerivedPolicies::delete_slice(container, from, to);
703 , class DerivedPolicies
708 struct no_slice_helper
711 slicing_not_suported()
713 PyErr_SetString(PyExc_RuntimeError, "Slicing not supported");
714 throw_error_already_set();
718 base_get_slice(Container& /*container*/, PySliceObject* /*slice*/)
720 slicing_not_suported();
725 base_set_slice(Container& /*container*/, PySliceObject* /*slice*/, PyObject* /*v*/)
727 slicing_not_suported();
731 base_delete_slice(Container& /*container*/, PySliceObject* /*slice*/)
733 slicing_not_suported();
737 #ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP
738 }} // namespace python::detail
741 template <class Container, class Index, class Policies>
742 inline typename Policies::data_type*
744 python::detail::container_element<Container, Index, Policies> const& p)
746 // Get the pointer of a container_element smart pointer
750 #ifndef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP
751 // Don't hide these other get_pointer overloads
752 using boost::python::get_pointer;
753 using boost::get_pointer;
754 }} // namespace python::detail
759 #endif // INDEXING_SUITE_DETAIL_JDG20036_HPP