|
|
Boost : |
From: Andrew D Jewell (ajewell_at_[hidden])
Date: 2000-02-23 15:31:23
Sorry 'bout that. How's this?
At 9:23 PM +0100 2/23/00, Valentin Bonnard wrote:
>Andrew D Jewell wrote:
>
> > Name: runvector.h
> > Part 1.2 Type: Macintosh BinHex Archive
> > (application/mac-binhex40)
>
>fuste-/tmp $ binhex runvector.h
>File is not MacBinary: runvector.h
>
>Could you please send clear text, instead of encoded text ?
>
>--
>
>Valentin Bonnard
>
>------------------------------------------------------------------------
>Learn more with SmartPlanet. It's a new way of learning online.
>SmartPlanet offers hundreds of courses to take on your time,
>in your space. Join for FREE today!
>http://click.egroups.com/1/1704/1/_/9351/_/951337654/
>
>-- Talk to your group with your own voice!
>-- http://www.egroups.com/VoiceChatPage?listName=boost&m=1
#ifndef sfRunVector_H_
#define sfRunVector_H_
#define WD_DEBUG
inline void wd_assert(bool x)
{
if (x) {
}
else {
// assertion failed, take appropriate action
}
}
#include <vector>
/*
a RunVector is an implementation of vector that stores elements as a
list of ranges of identical values. The complexity of most things
becomes linear with the number of ranges.
for acting on ranges of values, see these methods
void Set(size_type n, size_type cnt, const_reference inValue)
sum_type Sum(size_type n) const
size_type InvSum(sum_type inValue) const
Serving Suggestions :
RunVector<int> x;
RunVector<unsigned short, unsigned long> y;
This was originally written as part of PITA (Platform
Independant Table Architecture) which
is a general set of classes for making tables (one the
screen, like in Excel or whatever)
abstracting the platform dependencies down to the tiniest
possible speck. Anyone interested in
my PITA library should send an email to ajewell_at_cinci.rr.com.
It's free, but not yet http accessible.
*/
namespace WebDexer {
template <class Value, class Sum = Value, class Allocator = std::allocator<T> >
class RunVector {
public:
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef Value
value_type;
typedef Sum
sum_type;
typedef typename Allocator::const_reference const_reference;
class helper_base {
friend class RunVector;
public:
helper_base() : mVec(*((RunVector*)0)), mPos(0) {}
helper_base(RunVector & inVec, size_type
inPos) : mVec(inVec), mPos(inPos) {}
helper_base(const helper_base & x) :
mVec(x.mVec), mPos(x.mPos) {}
bool operator==(const helper_base & x)
{return mPos == x.mPos;}
bool operator!=(const helper_base & x)
{return mPos != x.mPos;}
bool operator< (const helper_base & x)
{return mPos < x.mPos;}
bool operator<=(const helper_base & x)
{return mPos <= x.mPos;}
bool operator> (const helper_base & x)
{return mPos > x.mPos;}
bool operator>=(const helper_base & x)
{return mPos >= x.mPos;}
helper_base & operator++()
{
++mPos;
return *this;
}
helper_base operator++(int)
{
helper_base tmp = *this;
++mPos;
return tmp;
}
helper_base & operator--()
{
--mPos;
return *this;
}
helper_base operator--(int)
{
helper_base tmp = *this;
--mPos;
return tmp;
}
helper_base & operator+=(difference_type x)
{
mPos += x;
return *this;
}
helper_base & operator-=(difference_type x)
{
mPos -= x;
return *this;
}
friend difference_type operator-(const
helper_base & x, const helper_base & y)
{
return difference_type(x.mPos - y.mPos);
}
friend helper_base operator-(const
helper_base & x, difference_type n)
{
return helper_base(x.mVec, x.mPos - n);
}
friend helper_base operator+(const
helper_base & x, difference_type n)
{
return helper_base(x.mVec, x.mPos + n);
}
friend helper_base operator+(difference_type
n, const helper_base & x)
{
return helper_base(x.mVec, x.mPos + n);
}
operator T() const {return mVec.Get(mPos);}
protected:
RunVector & mVec;
size_type mPos;
};
class reference : public helper_base {
public:
reference() {}
reference(RunVector & inVec, size_type inPos)
: helper_base(inVec, inPos) {}
reference(const reference & x) : helper_base(x) {}
reference(const helper_base & x) : helper_base(x) {}
reference & operator=(const_reference x)
{mVec.Set(mPos, x); return *this;}
T * operator&() {return
&mVec.GetIt(mPos)->mValue;}
};
class iterator : public helper_base {
public:
iterator() {}
iterator(RunVector & inVec, size_type inPos)
: helper_base(inVec, inPos) {}
iterator(const iterator & x) : helper_base(x) {}
iterator(const helper_base & x) : helper_base(x) {}
iterator & operator=(const helper_base & x)
{mPos = x.mPos; return *this;}
reference operator[](difference_type x)
{return reference(mVec, mPos+x);}
reference operator* () {return reference(mVec, mPos);}
T * operator->() {return
&mVec.GetIt(mPos)->mValue;}
};
class const_iterator : public helper_base{
public:
const_iterator() {}
const_iterator(const RunVector & inVec,
size_type inPos)
: helper_base(const_cast<RunVector
&>(inVec), inPos) {}
const_iterator(const const_iterator & x) :
helper_base(x) {}
const_iterator(const helper_base & x) :
helper_base(x) {}
const_iterator & operator=(const helper_base
& x) {mPos = x.mPos; return *this;}
const T & operator[](difference_type x)
{return mVec.GetIt(mPos+x)->mValue;}
const T & operator* () {return
mVec.GetIt(mPos)->mValue;}
const T * operator->() {return
&mVec.GetIt(mPos)->mValue;}
};
typedef std::reverse_iterator<iterator>
reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
private:
struct VecElem {
VecElem() {}
VecElem(T inValue, size_type inSize = 1) :
mValue(inValue), mSize(inSize) {}
T mValue;
size_type mSize;
};
public:
RunVector() : mSize(0) {}
RunVector(const RunVector & r) : mElems(r.mElems), mSize(r.mSize) {}
RunVector(size_type n, T t) : mSize(n)
{mElems.push_back(VecElem(t, n));}
template <class InputIterator>
RunVector(InputIterator first, InputIterator last)
{while (first < last) push_back(*first++);}
iterator insert(iterator inPos, value_type x)
{
wd_assert(&inPos.mVec == this);
wd_assert(inPos.mPos <= size());
if (mElems.empty()) {
push_back(x);
return begin();
}
vec::iterator it = GetIt(inPos.mPos ? inPos.mPos-1 : 0);
it->mSize++;
mSize++;
Set(inPos.mPos, x);
return inPos;
}
void insert(iterator inPos, size_type n, value_type x)
{
wd_assert(&inPos.mVec == this);
wd_assert(inPos.mPos <= size());
insert(inPos, x);
vec::iterator it = GetIt(inPos.mPos);
it->mSize += n - 1;
mSize += n - 1;
}
template <bool b> struct chooser {};
template <class InputIterator>
void choose_insert(iterator position, InputIterator
first, InputIterator last, chooser<true>)
{
insert(position,
static_cast<size_type>(first), static_cast<value_type>(last));
}
template <class InputIterator>
void choose_insert(iterator position, InputIterator
first, InputIterator last, chooser<false>)
{
wd_assert(&it.mVec == this);
while (first < last) it = insert(it, *first++);
}
template <class InputIterator>
void insert(iterator position, InputIterator first,
InputIterator last)
{
choose_insert(position, first, last,
chooser<std::numeric_limits<InputIterator>::is_integer>());
}
iterator erase(iterator inPos)
{
wd_assert(&inPos.mVec == this);
vec::iterator it = GetIt(inPos);
if (it->mSize == 1) {
it = mElems.erase(it);
combine(it - mElems.begin());
}
else {
it->mSize--;
}
mSize--;
return inPos;
}
iterator erase(iterator first, iterator last)
{
wd_assert(&first.mVec == &last.mVec);
wd_assert(&first.mVec == this);
difference_type diff = last-first;
size_type within;
vec::iterator it = GetIt(first.mPos, within);
if (within > 0) {
size_type leftover = it->mSize - within;
if (diff < leftover) {
it->mSize -= diff;
mSize -= diff;
diff -= diff;
}
else {
it->mSize -= leftover;
mSize -= leftover;
diff -= leftover;
}
++it;
}
while (diff > 0) {
if (diff >= it->mSize) {
diff -= it->mSize;
mSize -= it->mSize;
it = mElems.erase(it);
}
else {
it->mSize -= diff;
mSize -= diff;
}
}
combine(it - mElems.begin());
return first;
}
iterator begin() {return iterator(*this, 0);}
const_iterator begin() const {return const_iterator(*this, 0);}
iterator end() {return iterator(*this, mSize);}
const_iterator end() const {return
const_iterator(*this, mSize);}
reverse_iterator rbegin() {return reverse_iterator(end());}
const_reverse_iterator rbegin() const {return reverse_iterator(end());}
reverse_iterator rend() {return reverse_iterator(begin());}
const_reverse_iterator rend() const {return reverse_iterator(begin());}
size_type size() const {return size_type(mSize);}
size_type max_size() const {return Allocator.max_size();}
bool empty() const {return mSize == 0;}
const_reference Get(size_type n) const {return GetIt(n)->mValue;}
reference operator[](size_type n)
{return reference(*this, n);}
const_reference operator[](size_type n) const {return
GetIt(n)->mValue;}
reference at(size_type n)
{if (n >= size()) throw out_of_range; return
reference(*this, n);}
const_reference at(size_type n) const {if
(n >= size()) throw out_of_range; return GetIt(n)->mValue;}
reference front() {return
reference(*this, 0);}
const_reference front() const {return mElems.front().mValue;}
reference back() {return
reference(*this, mSize-1);}
const_reference back() const {return mElems.back().mValue;}
void push_back(const_reference inValue)
{
if (mElems.empty()) {
mElems.push_back(inValue);
}
else {
if (mElems.back().mValue == inValue) {
mElems.back().mSize++;
}
else {
mElems.push_back(inValue);
}
}
mSize++;
}
void push_front(const_reference inValue)
{
if (mElems.empty()) {
mElems.push_front(inValue);
}
else {
if (mElems.front().mValue == inValue) {
mElems.front().mSize++;
}
else {
mElems.push_front(inValue);
}
}
mSize++;
}
void pop_back()
{
if (mElems.back().mSize == 1) {
mElems.pop_back();
}
else {
mElems.back().mSize--;
}
mSize--;
}
void pop_front()
{
if (mElems.front().mSize == 1) {
mElems.pop_front();
}
else {
mElems.front().mSize--;
}
mSize--;
}
void Set(size_type n, size_type cnt, const_reference inValue)
{
size_type count = cnt;
wd_assert(n < size());
wd_assert((n+count) <= size());
wd_assert(test());
#ifdef WD_DEBUG
size_type sum1 = Sum(n);
size_type sum2 = Sum(n+cnt);
size_type sum3 = Sum(size());
size_type newSum2 = sum1 + cnt * inValue;
size_type newSum3 = sum3 - sum2 + newSum2;
#endif
size_type within;
vec::iterator it = GetIt(n, within);
size_type remain = it->mSize - within;
if (within > 0) {
if (it->mValue == inValue) {
if (remain >= count) {
count = 0;
}
}
else {
VecElem t = *it;
it->mSize = within;
++it;
it = mElems.insert(it,
VecElem(inValue, count));
size_type leftover = t.mSize - within - count;
if (remain >= count) {
if (leftover) {
it =
mElems.insert(it+1, VecElem(t.mValue, leftover));
}
count = 0;
}
}
}
wd_assert(test());
while (1) {
wd_assert(n < size());
wd_assert((n+count) <= size());
if (it->mSize < count) {
size_type num = it->mSize;
it = mElems.erase(it);
it->mSize += num;
}
else if (it->mSize == count) {
it->mValue = inValue;
break;
}
else {
it->mSize -= count;
it = mElems.insert(it,
VecElem(inValue, count));
break;
}
}
combine(it - mElems.begin());
#ifdef WD_DEBUG
size_type Nsum1 = Sum(n);
size_type Nsum2 = Sum(n+cnt);
size_type Nsum3 = Sum(size());
wd_assert(sum1 == Nsum1);
wd_assert(newSum2 == Nsum2);
wd_assert(newSum3 == Nsum3);
#endif
}
void Set(size_type n, const_reference inValue)
{
Set (n, 1, inValue);
}
// return the summation of all elements from [0..n)
// presumes that binary + and binary * are defined on T
sum_type Sum(size_type n) const
{
wd_assert(n <= mSize);
sum_type sum = 0;
for (vec::const_iterator i=mElems.begin();
i<mElems.end(); ++i) {
if (n < i->mSize) {
sum += i->mValue * n;
break;
}
else {
sum += i->mValue * i->mSize;
n -= i->mSize;
}
}
return sum;
}
// return the index of the first entry at which the running
// total meets or exceeds inValue
// presumes that binary + and binary * are defined on T
// returns size() if inValue is never met
size_type InvSum(sum_type inValue) const
{
if (inValue <= 0) return 0;
sum_type sum = 0;
size_type tot = 0;
for (vec::const_iterator i=mElems.begin();
i<mElems.end(); ++i) {
sum_type subTot = i->mSize * i->mValue;
if ((sum + subTot) < inValue) {
sum += subTot;
tot += i->mSize;
}
else {
return tot + (inValue - sum) / i->mValue;
}
}
return size();
}
void clear()
{
mSize = 0;
mElems.clear();
}
// These last three public members iterate thru the
// RANGES rather than the actual elements
// they're indexed by the same types, so be careful
size_type NumRanges() {return mElems.size();}
// return the value and size for the giiven range
value_type GetRange(size_type n, size_type & outSize) const
{
wd_assert(n < mElems.size());
outSize = mElems[n].mSize;
return mElems[n].mValue;
}
// return the value, size and bounds for the given range
value_type GetRange(size_type n, size_type & outSize,
size_type & outBegin, size_type & outEnd) const
{
wd_assert(n < mElems.size());
outBegin = 0;
for (int i=0; i<n; ++i) {
outBegin += mElems[i].mSize;
}
outSize = mElems[n].mSize;
outEnd = outBegin + outSize;
return mElems[n].mValue;
}
#ifdef WD_DEBUG
// return the sum of the sizes of the elements
size_type CalcSize() const
{
size_type size = 0;
for (vec::const_iterator i=mElems.begin();
i<mElems.end(); ++i) {
size += i->mSize;
}
return size;
}
// test the runvector for consistancy
bool test() const
{
size_type s = CalcSize();
wd_assert(mSize == s);
for (vec::const_iterator i=mElems.begin();
i<mElems.end(); ++i) {
wd_assert(i->mSize > 0);
if (i > mElems.begin()) {
wd_assert((i-1)->mValue != i->mValue);
}
}
return true;
}
#endif
private:
typedef std::vector<VecElem> vec;
vec mElems;
size_type mSize; // redundant, must always equal the
sum of the sizes in mElems
// return the const_iterator for the range containing the given element
vec::const_iterator GetIt(size_type inPos) const {
wd_assert(inPos < size());
for (vec::const_iterator i=mElems.begin();
i<mElems.end(); ++i) {
if (inPos < i->mSize) return i;
inPos -= i->mSize;
}
return mElems.end() - 1;
}
// return the iterator for the range containing the given element
vec::iterator GetIt(size_type inPos) {
wd_assert(inPos < size());
for (vec::iterator i=mElems.begin(); i<mElems.end(); ++i) {
if (inPos < i->mSize) return i;
inPos -= i->mSize;
}
return mElems.end() - 1;
}
// return the const_iterator for the range containing the
given element, and its offset within the range
vec::iterator GetIt(size_type inPos, size_type & inWithin) {
wd_assert(inPos < size());
inWithin = inPos;
for (vec::iterator i=mElems.begin(); i<mElems.end(); ++i) {
if (inWithin < i->mSize) return i;
inWithin -= i->mSize;
}
return mElems.end() - 1;
}
// The nth range has changed. If its value now matches the adjacent
// values, combine the adjacent ranges
void combine(size_type n)
{
if (mElems.size() == 0) return;
if (n >= mElems.size()) n = mElems.size() - 1;
if (n > 0) {
if (mElems[n-1].mValue == mElems[n].mValue) {
mElems[n-1].mSize += mElems[n].mSize;
mElems.erase(mElems.begin() + n);
--n;
}
}
if (n < (mElems.size()-1)) {
if (mElems[n].mValue == mElems[n+1].mValue) {
mElems[n].mSize += mElems[n+1].mSize;
mElems.erase(mElems.begin() + n + 1);
}
}
wd_assert(test());
}
};
template <class T, class Allocator>
bool
operator==(const RunVector<T,Allocator>& x, const RunVector<T,Allocator>& y)
{return x.mElems == y.mElems;}
template <class T, class Allocator>
bool
operator!=(const RunVector<T,Allocator>& x, const RunVector<T,Allocator>& y)
{return x.mElems != y.mElems;}
template <class T, class Allocator>
bool
operator< (const RunVector<T,Allocator>& x, const RunVector<T,Allocator>& y)
{return x.mElems < y.mElems;}
template <class T, class Allocator>
bool
operator> (const RunVector<T,Allocator>& x, const RunVector<T,Allocator>& y)
{return x.mElems > y.mElems;}
template <class T, class Allocator>
bool
operator>=(const RunVector<T,Allocator>& x, const RunVector<T,Allocator>& y)
{return x.mElems >= y.mElems;}
template <class T, class Allocator>
bool
operator<=(const RunVector<T,Allocator>& x, const RunVector<T,Allocator>& y)
{return x.mElems <= y.mElems;}
// specialized algorithms:
template <class T, class Allocator>
void
swap(RunVector<T,Allocator>& x, RunVector<T,Allocator>& y)
{
swap(x.mElems, y.mElems);
swap(x.mSize, y.mSize);
}
}
#endif
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk