1
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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));
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.