[boost] [multi_index] Multi-Index as fast running median solver

Subject: [boost] [multi_index] Multi-Index as fast running median solver
From: Ryan Fogarty (ryan.fogarty.msece_at_[hidden])
Date: 2010-08-16 12:38:45

I'm hoping to use multi-index' ordered_index (non-unique) to do a fast
running median. Given a set of M numbers and a window size of N compute the
medians (for each of M - N + 1 solutions). Here is my solution:

template<typename T>
class FastMedianSolver {
private:
    // boost::multi_index does most of the heavy lifting for this
FastMedianSolver.
    // This index is given both "sequence" and "tree" semantics.
    typedef typename boost::multi_index_container<
T,indexed_by<sequenced<>,ordered_non_unique<identity<T> > > > SortedList;
    typedef typename SortedList::template nth_index<0> SeqIndex;
    typedef typename SeqIndex::type SIndex;
    typedef typename SortedList::template nth_index<1> TreeIndex;
    typedef typename TreeIndex::type TIndex;

    SortedList mQueue;
    const size_t mSize;
    const size_t mHalfSize;

public:
    typedef typename SIndex::iterator iterator;

    /**
     * Create a FastMedianSolver with queue size as argument
     *
     * @param size - size of the queue.
     */
    // Note: fast divide by 2 is: X >> 1
    FastMedianSolver(size_t size) : mSize(size), mHalfSize(size >> 1) {}

     /**
     * insert a value into the median queue
     */
    void insert(const T& value) {
        mQueue.push_front(value);
        if(mQueue.size() > mSize) mQueue.pop_back();
    }

     /**
     * Get the median for the elements within the queue. Note:
     * the algorithm requires a full queue, o.w. may throw an exception.
     */
    const T& getMedian() {
        // Ensure queue is filled up before we ask for median!
        assert((mQueue.size() >> 1) == mHalfSize);
         typename TIndex::iterator tNdx(mQueue.get<1>().begin());
        // Now grab the median element
        // Note that unfortunately the root() node is not exposed so the
only way to get the central node
        // is to iterate to it :( (this will incur a O(N) operation on this
function which is a little unfortunate
        for(int i = 0; i < mHalfSize; ++i,++tNdx);

        // This would be better if it were available and accurate!
//          typename TIndex::iterator tNdx(mQueue.get<1>().beginAtRoot());

        // TODO: Check if we need to average the output of 2 positions if
mSize is even
        return *tNdx;
    }
};

Note, that to get to the central node I just iterate the ordered list half
way through set:

for(int i = 0; i < mHalfSize; ++i,++tNdx);

However, what I was hoping was that I could get the root node directly.
ordered_index doesn't expose an iterator to root() so I put it in
ordered_index.hpp as:

  iterator               beginAtRoot(){return make_iterator(root());}

However, this isn't working out because the tree isn't always balanced. My
question is 2-fold is there any way to force the internal red-black tree to
stay balanced; and secondly, would that have an appreciable performance
penalty.

Thank you,
Ryan