Circular buffer offsets and sorted set of offsets sorted on their index

Question

Consider the following C++03 code:

#include <algorithm>
#include <deque>
#include <boost/iterator/counting_iterator.hpp>

const unsigned int _count = 0x10000;

struct recentFunctor {
  recentFunctor(const int base, const int firstOffset)
    : _base(base),
      _firstOffset(firstOffset) {
  }

  int getIndex(const int offset) const {
    return _base + _normalize(offset - _firstOffset);
  }

  bool operator()(const int offsetA, const int offsetB) const {
    return getIndex(offsetA) < getIndex(offsetB);
  }

private:
  int _normalize(const int offset) const {
    // Make negative offsets positive like math modulo.
    // Assumes _count is 0x10000.
    return int(static_cast<uint16_t>(offset));
  }

  const int _base;
  const int _firstOffset;

};

// Insert the inclusive range [beginOffset, lastOffset] into the recentItems
// ordered deque of offsets.  The offsets are into a circular array of 65,536
// items, so the range may wrap around.  The ordering of the offsets is based
// upon the index that corresponds to each offset.  For example, a beginOffset
// of 65,000 and a lastOffset of 100 means to insert the range of offsets
// [65000, 65535] into the deque at insertionPoint followed by the range of
// offsets [0, 100] and the beginOffset of 65,000 may correspond to an index of
// 65,000 but the lastOffset of 100 could correspond to an index of 65636 for
// the first time the circual buffer to which these offsets refer wraps around.

void
insertRecentRange(const int beginOffset,
                  const int lastOffset,
                  const int currentBase,
                  const int currentFirstOffset,
                  std::deque<int>::iterator insertionPoint,
                  std::deque<int> &recentItems)
{
  // The recentItems is an ordered set of offsets that have been noted.

  if (beginOffset <= lastOffset) {
    recentItems.insert(insertionPoint,
                       boost::counting_iterator<int>(beginOffset),
                       boost::counting_iterator<int>(lastOffset + 1));
  } else {
    // Fix this in C++11, for now insert() does not return what we want so we
    // must call lower_bound() to compute it:
    recentItems.insert(insertionPoint,
                       boost::counting_iterator<int>(beginOffset),
                       boost::counting_iterator<int>(int(_count)));

    std::deque<int>::iterator firstInsert
      = std::lower_bound(recentItems.begin(), recentItems.end(), beginOffset,
                         recentFunctor(currentBase, currentFirstOffset));

    recentItems.insert(firstInsert + (int(_count) - beginOffset),
                       boost::counting_iterator<int>(0),
                       boost::counting_iterator<int>(lastOffset + 1));
  }
}

While working in C++03, is there any way to perform the insert() and not have to call lower_bound() to compute a follow on insertion point for the remaining offsets? Can this code be made easier to understand without changing the underlying data structures? Any other suggestions to improve this?

Answer 1

One way is to supply uint16_t as the third template argument to boost::counting_iterator so that it allows wrapping around, allowing the code to be greatly simplified:

#include <algorithm>
#include <deque>
#include <boost/iterator/counting_iterator.hpp>

// Assumes _count == 65536 (0x10000)
typedef boost::counting_iterator<uint16_t,
                                 boost::use_default,
                                 uint16_t> uint16_wrapping_counting_iterator;


// Insert the inclusive range [beginOffset, lastOffset] into the recentItems
// ordered deque of offsets.  The offsets are into a circular array of 65,536
// items, so the range may wrap around.  The ordering of the offsets is based
// upon the index that corresponds to each offset.  For example, a beginOffset
// of 65,000 and a lastOffset of 100 means to insert the range of offsets
// [65000, 65535] into the deque at insertionPoint followed by the range of
// offsets [0, 100] and the beginOffset of 65,000 may correspond to an index of
// 65,000 but the lastOffset of 100 could correspond to an index of 65636 for
// the first time the circual buffer to which these offsets refer wraps around.

void
insertRecentRange(const int beginOffset,
                  const int lastOffset,
                  std::deque<int>::iterator insertionPoint,
                  std::deque<int> &recentItems)
{
  const uint16_t startOffset = uint16_t(beginOffset);
  const uint16_t endOffset   = uint16_t(lastOffset + 1);

  // The recentItems is an ordered set of offsets that have been noted.
  recentItems.insert(insertionPoint,
                     uint16_wrapping_counting_iterator(startOffset),
                     uint16_wrapping_counting_iterator(endOffset));
}