indexing_suite_detail.hpp

CGAL is a collaborative effort of several sites in Europe and Israel. The goal is to make the most i

//  (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/detail/workaround.hpp>
# include <boost/config.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()
        {