Indexing support

Introduction

Indexing is a Boost Python facility for easy exportation of indexable C++ containers to Python. Indexable containers are containers that allow random access through the operator[] (e.g. std::vector).

While Boost Python has all the facilities needed to expose indexable C++ containers such as the ubiquitous std::vector to Python, the procedure is not as straightforward as we'd like it to be. Python containers do not map easily to C++ containers. Emulating Python containers in C++ (see Python Reference Manual, Emulating container types) using Boost.Python is non trivial. There are a lot of issues to consider before we can map a C++ container to Python. These involve implementing wrapper functions for the methods __len__, __getitem__, __setitem__, __delitem__, __iter__ and __contains__.

The goals:

Make indexable C++ containers behave exactly as one would expect a Python container to behave.
Provide default reference semantics for container element indexing (__getitem__) such that c[i] can be mutable. Require:
```
val = c[i]
c[i].m()
val == c[i]
```
where m is a non-const (mutating) member function (method).
Return safe references from __getitem__ such that subsequent adds and deletes to and from the container will not result in dangling references (will not crash Python).
Support slice indexes.
Accept Python container arguments (e.g. lists, tuples) wherever appropriate.
Allow for extensibility through re-definable policy classes.
Provide predefined support for the most common STL and STL-like indexable containers.

The Indexing Interface

The indexing_suite class is the base class for the management of C++ containers intended to be integrated to Python. The objective is make a C++ container look and feel and behave exactly as we'd expect a Python container. The class automatically wraps these special Python methods (taken from the Python reference: Emulating container types):

__len__(self)

Called to implement the built-in function len(). Should return the length of the object, an integer >= 0. Also, an object that doesn't define a __nonzero__() method and whose __len__() method returns zero is considered to be false in a Boolean context.

__getitem__(self, key)

Called to implement evaluation of self[key]. For sequence types, the accepted keys should be integers and slice objects. Note that the special interpretation of negative indexes (if the class wishes to emulate a sequence type) is up to the __getitem__() method. If key is of an inappropriate type, TypeError may be raised; if of a value outside the set of indexes for the sequence (after any special interpretation of negative values), IndexError should be raised. [Note: for loops expect that an IndexError will be raised for illegal indexes to allow proper detection of the end of the sequence.]

__setitem__(self, key, value)

Called to implement assignment to self[key]. Same note as for __getitem__(). This should only be implemented for mappings if the objects support changes to the values for keys, or if new keys can be added, or for sequences if elements can be replaced. The same exceptions should be raised for improper key values as for the __getitem__() method.

__delitem__(self, key)

Called to implement deletion of self[key]. Same note as for __getitem__(). This should only be implemented for mappings if the objects support removal of keys, or for sequences if elements can be removed from the sequence. The same exceptions should be raised for improper key values as for the __getitem__() method.

__iter__(self)

This method is called when an iterator is required for a container. This method should return a new iterator object that can iterate over all the objects in the container. For mappings, it should iterate over the keys of the container, and should also be made available as the method iterkeys().

Iterator objects also need to implement this method; they are required to return themselves. For more information on iterator objects, see Iterator Types in the Python Library Reference.

__contains__(self, item)

Called to implement membership test operators. Should return true if item is in self, false otherwise. For mapping objects, this should consider the keys of the mapping rather than the values or the key-item pairs.

index_suite sub-classes

vector_index_suite
map_index_suite

The indexing_suite is not meant to be used as is. A couple of policy functions must be supplied by subclasses of indexing_suite. However, a set of indexing_suite subclasses for the standard indexable STL containers will be provided, In most cases, we can simply use the available predefined suites. In some cases, we can refine the predefined suites to suit our needs.

vector_index_suite

The vector_indexing_suite class is a predefined indexing_suite derived class designed to wrap std::vector (and std::vector-like [i.e. a class with std::vector interface]) classes. It provides all the policies required by the indexing_suite.

Example usage:

class X {...};
...
class_<std::vector<X> >("XVec")
  .def(vector_indexing_suite<std::vector<X> >())
;

XVec is now a full-fledged Python container (see the example in full, along with its python test).

map_index_suite

The map_indexing_suite class is a predefined indexing_suite derived class designed to wrap std::map (and std::map-like [i.e. a class with std::map interface]) classes. It provides all the policies required by the indexing_suite.

Example usage:

class X {...};
...

class_<std::map<X> >("XMap")
    .def(map_indexing_suite<std::map<X> >())
;

By default indexed elements are returned by proxy. This can be disabled by supplying true in the NoProxy template parameter. XMap is now a full-fledged Python container (see the example in full, along with its python test).

`indexing_suite` class

DerivedPolicies

Template Parameter	Requirements	Semantics	Default
Container	A class type	The container type to be wrapped to Python.
DerivedPolicies	A subclass of indexing_suite	Derived classes provide the policy hooks. See DerivedPolicies below.
NoProxy	A boolean	By default indexed elements have Python reference semantics and are returned by proxy. This can be disabled by supplying true in the NoProxy template parameter.	false
NoSlice	A boolean	Do not allow slicing.	false
Data		The container's data type.	Container::value_type
Index		The container's index type.	Container::size_type
Key		The container's key type.	Container::value_type

template <class Container,
	  class DerivedPolicies,
	   bool NoProxy = false,
	   bool NoSlice = false,
	   class Data = typename Container::value_type,
	   class Index = typename Container::size_type,
	   class Key = typename Container::value_type>
class indexing_suite : unspecified
{
public:
  indexing_suite(); // default constructor
}

DerivedPolicies

Derived classes provide the hooks needed by the indexing_suite:

data_type&
get_item(Container& container, index_type i);

static object
get_slice(Container& container, index_type from, index_type to);

static void
set_item(Container& container, index_type i, data_type const& v);

static void
set_slice(
    Container& container, index_type from,
    index_type to, data_type const& v
);

template <class Iter>
static void
set_slice(Container& container, index_type from,
    index_type to, Iter first, Iter last
);

static void
delete_item(Container& container, index_type i);

static void
delete_slice(Container& container, index_type from, index_type to);

static size_t
size(Container& container);

template <class T>
static bool
contains(Container& container, T const& val);

static index_type
convert_index(Container& container, PyObject* i);

static index_type
adjust_index(index_type current, index_type from,
    index_type to, size_type len);

Most of these policies are self explanatory. However, convert_index and adjust_index deserve some explanation.

convert_index converts a Python index into a C++ index that the container can handle. For instance, negative indexes in Python, by convention, start counting from the right(e.g. C1 indexes the rightmost element in C). convert_index should handle the necessary conversion for the C++ container (e.g. convert -1 to C.size()-1). convert_index should also be able to convert the type of the index (A dynamic Python type) to the actual type that the C++ container expects.

When a container expands or contracts, held indexes to its elements must be adjusted to follow the movement of data. For instance, if we erase 3 elements, starting from index 0 from a 5 element vector, what used to be at index 4 will now be at index 1:

[a][b][c][d][e] ---> [d][e]
              ^           ^
              4           1

adjust_index takes care of the adjustment. Given a current index, the function should return the adjusted index when data in the container at index from..to is replaced by len elements.

class `vector_indexing_suite`

Template Parameter	Requirements	Semantics	Default
Container	A class type	The container type to be wrapped to Python.
NoProxy	A boolean	By default indexed elements have Python reference semantics and are returned by proxy. This can be disabled by supplying true in the NoProxy template parameter.	false
DerivedPolicies	A subclass of indexing_suite	The vector_indexing_suite may still be derived to further tweak any of the predefined policies. Static polymorphism through CRTP (James Coplien. "Curiously Recurring Template Pattern". C++ Report, Feb. 1995) enables the base indexing_suite class to call policy function of the most derived class

template <class Container,
	  bool NoProxy = false,
          class DerivedPolicies = unspecified_default>
class vector_indexing_suite : unspecified_base
{
public:

    typedef typename Container::value_type data_type;
    typedef typename Container::value_type key_type;
    typedef typename Container::size_type index_type;
    typedef typename Container::size_type size_type;
    typedef typename Container::difference_type difference_type;

    data_type&
    get_item(Container& container, index_type i);

    static object
    get_slice(Container& container, index_type from, index_type to);

    static void
    set_item(Container& container, index_type i, data_type const& v);

    static void
    set_slice(Container& container, index_type from,
        index_type to, data_type const& v);

    template <class Iter>
    static void
    set_slice(Container& container, index_type from,
        index_type to, Iter first, Iter last);

    static void
    delete_item(Container& container, index_type i);

    static void
    delete_slice(Container& container, index_type from, index_type to);

    static size_t
    size(Container& container);

    static bool
    contains(Container& container, key_type const& key);

    static index_type
    convert_index(Container& container, PyObject* i);

    static index_type
    adjust_index(index_type current, index_type from,
        index_type to, size_type len);
};

class `map_indexing_suite`

Template Parameter	Requirements	Semantics	Default
Container	A class type	The container type to be wrapped to Python.
NoProxy	A boolean	By default indexed elements have Python reference semantics and are returned by proxy. This can be disabled by supplying true in the NoProxy template parameter.	false
DerivedPolicies	A subclass of indexing_suite	The vector_indexing_suite may still be derived to further tweak any of the predefined policies. Static polymorphism through CRTP (James Coplien. "Curiously Recurring Template Pattern". C++ Report, Feb. 1995) enables the base indexing_suite class to call policy function of the most derived class

template <class Container,
          bool NoProxy = false,
          class DerivedPolicies = unspecified_default>
class map_indexing_suite : unspecified_base
{
public:

    typedef typename Container::value_type value_type;
    typedef typename Container::value_type::second_type data_type;
    typedef typename Container::key_type key_type;
    typedef typename Container::key_type index_type;
    typedef typename Container::size_type size_type;
    typedef typename Container::difference_type difference_type;

    static data_type&
    get_item(Container& container, index_type i);

    static void
    set_item(Container& container, index_type i, data_type const& v);

    static void
    delete_item(Container& container, index_type i);

    static size_t
    size(Container& container);

    static bool
    contains(Container& container, key_type const& key);

    static bool
    compare_index(Container& container, index_type a, index_type b);

    static index_type
    convert_index(Container& container, PyObject* i);
};