On 4/29/07, William S Fulton <wsf@fultondesigns.co.uk> wrote:
You should tackle this like any other templated code you want to use
from SWIG. So giving the following to SWIG would be a start...

namespace std {
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                 RandomAccessIterator last);
}

then you need a %template for RandomAccessIterator. I don't know the
Python STL iterator mappings at all, so this might be covered already.
If not you need to get the RandomAccessIterator from the C++ world into
Python, by either using one of the Python STL wrappers (eg
vector::begin()) or write a method that will return it for you.


Eric Mahurin wrote:
Any reason why swig::PySwigIterator has no write access to the element it is iterating/pointing-to?  Write-access to C++ iterators is a major benefit compared to iterators of other languages (which are usually read-only - including python's).


Well, I finally got it working.  I had to hack into local versions of pyiterators.swg and std_map.i.  I added a set method to the PySwigIterator* classes to set the element that the iterator references (using the template function asval).  The map iterators were a problem since the const keys are part of the value, so the maps got there own iterator classes that errored on set.  Another thing that should be fixed is the problem that these PySwigIterator* classes give O(n) instead of O(1) performance for iterators that should be random access (incr and decr methods are O(n)).

After making these hacks, here is what I came up with that should give access to whatever STL algorithms you want in python.  I only checked with STL containers of python objects, but it should work with STL containers of C++ data also.

%{

#include <algorithm>
#include <iterator>

namespace swig {
    class PySwigIteratorRef {
        private:
            PySwigIterator* p;
        public:
            inline PySwigIteratorRef(PySwigIterator* p)
            : p(p) { }
            inline PySwigIteratorRef(const PySwigIteratorRef& other)
            : p(other.p->copy()) { }
            inline ~PySwigIteratorRef()
            { delete p; }
            inline operator PyObject_ptr() const
            { return PyObject_ptr(p->value()); }
            inline PyObject *operator->() const
            { return p->value(); }
            inline PySwigIteratorRef& operator=(const PyObject* v)
            { p->set(v); return *this; }
            inline PySwigIteratorRef& operator=(const PySwigIteratorRef& other)
            { p->set(other.p->value()); return *this; }
    };
    class PySwigIteratorProxy {
        private:
            PySwigIterator* p;
            bool owner;
        public:
            typedef PySwigIteratorProxy self_type;
            typedef PyObject_ptr        value_type;
            typedef PySwigIteratorRef   reference;
            typedef void*               pointer;
            typedef ptrdiff_t           difference_type;
            typedef std::random_access_iterator_tag iterator_category;

            inline PySwigIteratorProxy(PySwigIterator* p, bool owner=false)
            : p(p), owner(owner) {}
            inline PySwigIteratorProxy(const PySwigIteratorProxy& other)
            : p(other.p->copy()), owner(true) {}
            inline self_type& operator=(const self_type& other)
            { if (owner) delete p; p = other.p->copy(); owner = true; }
            inline ~PySwigIteratorProxy()
            { if (owner) delete p; }
            inline reference operator*() const
            { return reference(p->copy()); }
            inline self_type& operator++()
            { p->incr(); return *this; }
            inline self_type operator++(int)
            { self_type orig(*this);p->incr(); return orig; }
            inline self_type& operator--()
            { p->decr(); return *this; }
            inline self_type operator--(int)
            { self_type orig(*this); p->decr(); return orig; }
            inline reference operator[](const difference_type& i) const
            { return reference(p->copy()->advance(i)); }
            inline self_type& operator+=(const difference_type& i)
            { p->advance(i); return *this; }
            inline self_type operator+(const difference_type& i) const
            { self_type copy(*this); return copy+=i; }
            inline self_type& operator-=(const difference_type& i)
            { p->advance(-i); return *this; }
            inline self_type operator-(const difference_type& i) const
            { self_type copy(*this); return copy-=i; }
            inline bool operator==(self_type& other)
            { return *p==*(other.p); }
            inline bool operator!=(self_type& other)
            { return *p!=*(other.p); }
            inline difference_type operator-(self_type& other)
            { return *p-*(other.p); }
            inline bool operator<(self_type& other)
            { return (*p-*( other.p))<0; }
            inline bool operator>(self_type& other)
            { return (*p-*(other.p))>0; }
            inline bool operator<=(self_type& other)
            { return (*p-*( other.p))<=0; }
            inline bool operator>=(self_type& other)
            { return (*p-*(other.p))>=0; }
    };
}

%}

%inline %{
    namespace swig {
        void nth_element(PySwigIterator* first,
                         PySwigIterator* nth,
                         PySwigIterator* last)
        {
            std::nth_element(PySwigIteratorProxy(first),
                             PySwigIteratorProxy(nth),
                             PySwigIteratorProxy(last),
                             std::less<PyObject_ptr>());
        }
    }
%}


Here's an example usage to find the median element in O(n) time (assuming the O(n) random access doesn't dominate):

>>> import stl
>>> v = stl.vector([9,1,8,2,7,3,6,4,5])
>>> b = v.begin()
>>> e = v.end()
>>> m = b+(e-b)/2
>>> stl.nth_element(b,m,e)
>>> list(v)
[3, 1, 2, 4, 5, 6, 7, 8, 9]
>>> m.value()
5