// templated Vector class for dynamic arrays of elements of arbitrary type
// Copyright (C) 1998,1999 Colin McCormack,
// see LICENSE (MD5 f5220f8f599e5e926f37cf32efe3ab68) for terms
// $Id: Vector_hh.html,v 1.1.1.1 2000/04/09 01:07:51 skeptopotamus Exp $
#ifndef VECTOR_HH
#define VECTOR_HH
#include <typeinfo>
#include <stdlib.h>
#include <assert.h>
class ostream;
/** Templated Vector class
A Vector is a pair of Segments, one (Vector's parent) delineates
the active subrange of the second, (called allocation)
allocation is a TupleBase array allocated by QVMM, it encloses the active subrange
*/
template <class T>
class Vector
: public Segment<T> // the active region of a Vector
{
public:
// static vars controlling memory allocation internal overhead
/** a extra proportion of allocation (3 == 133%)
*/
static unsigned int extra_allocation;
/** minimum proportional occupancy before shrinking
*/
static unsigned int minimum_occupancy;
/** the minimum size of an allocation in bytes
*/
static unsigned int minimum_size;
/** calculate an allocation based on the above parameters
*/
static int actual_allocation(int newlen) {
return (newlen + (newlen / extra_allocation)) >? minimum_size; // >? is max op
}
protected:
/** dump Vector to file
*/
friend ostream& operator<< <T> (ostream& out, const Vector<T> & vec);
/** Vector's allocation is managed with rlloc, resize and shrink
*/
/** the allocated space for this Vector
*/
TupleBase<T> *allocation;
/** accessor for @see allocation
*/
TupleBase<T> *Allocation() const {
return allocation;
}
/** reallocate Tuple
create a new allocation of actual_allocation(len) size
@param newlen new length Vector allocation
*/
void rlloc(int newlen);
/** realloc Tuple to accomodate new growth
ensure Vector has at least len elements, reallocating as needed
@param newlen new length Vector allocation
*/
void resize(int newlen);
/** reallocate Tuple if shrunk below minimum utilization
reduce an allocation if it's fallen below the low-water-mark
defined for this Vector type
*/
void shrink();
/** set the Segment of this Vector
*/
Segment<T>::set;
public:
/////////////////////////////
// Simple constructors
/** Null Vector constructor
*/
Vector();
/** construct with pre-allocation
*/
Vector(int size);
/** destructor - does nothing
*/
virtual ~Vector();
/** destroy contents
*/
void destroy(int len = 1);
/** consistency check
*/
void check(int i = 1) const;
/////////////////////////////////////
// accessors
/** Segment array accessor
*/
T &operator[](int offset);
/** hoist @see Segment element accessor
*/
Segment<T>::element;
/** hoist @see Segment empty predicate
*/
Segment<T>::empty;
/** hoist @see Segment boolean cast
*/
Segment<T>::operator bool;
/////////////////////////////////////
// copy constructors of sundry kinds
/** Copy T* array of a given size
*/
Vector(const T *contentT, int size);
/** Copy Segment
*/
Vector(const Segment<T> &contentT);
/** Make singleton T& Vector
*/
Vector(const T &contentT);
/** Repeat T& as array
*/
Vector(const T &contentT, int repetition);
/** Reference Tuple
*/
Vector(TupleBase<T> *t);
/** Reference Tuple
*/
Vector(TupleBase<T> &t);
/** Reference SubTuple
@param _start start of subrange
@param _len length of subrange
*/
Vector(TupleBase<T> *t, int _start, int _len=-1);
/** Reference SubTuple
@param _start start of subrange
@param _len length of subrange
*/
Vector(TupleBase<T> &t, int _start, int _len=-1);
/** Reference Vector<T>*
*/
Vector(const Vector<T> *v);
/** Reference Vector<T>&
*/
Vector(const Vector<T> &v);
/** Reference subrange Vector<T>*
@param _start start of subrange
@param _len length of subrange
*/
Vector(const Vector<T> *v, int _start, int _len=-1);
/** Reference subrange Vector<T>&
@param _start start of subrange
@param _len length of subrange
*/
Vector(const Vector<T> &v, int _start, int _len=-1);
/** union: v1 + v2
*/
Vector(const Vector<T> *v1, const Vector<T> *v2);
/** union: v1 + v2
*/
Vector(const Vector<T> &v1, const Vector<T> &v2);
private:
/** doDel - delete but don't shrink (used by replace)
*/
Vector<T> *doDel(int where, int what);
public:
/** mutator - remove range from Vector
*/
Vector<T> *del(int where = 0, int what=-1);
/** mutator - append values to right
*/
Vector<T> *vconcat(const T *addT, int additional);
/** mutator - append values to right
*/
Vector<T> *vconcat(const T *addT) {
return vconcat(addT, T::findNull(addT));
}
/** mutator - append values to right
*/
Vector<T> *vconcat(const T &addT) {
return vconcat(&addT, 1);
}
/** mutator - append values to right
*/
Vector<T> *vconcat(const Segment<T> *addT) {
return vconcat(addT->content(), addT->Length());
}
/** mutator - append values to right
*/
Vector<T> *vconcat(const Segment<T> &addT) {
return vconcat(addT.content(), addT.Length());
}
/** mutator - append values to right
*/
Vector<T> *vconcat(int count, ...);
/** mutator - insert values before point
*/
Vector<T> *vinsert(int where, const T *addT, int what);
/** mutator - insert values before point
*/
Vector<T> *vinsert(int where, const T *addT) {
return vinsert(where, addT, T::findNull(addT));
}
/** mutator - insert values before point
*/
Vector<T> *vinsert(int where, const Segment<T> *addT) {
return vinsert(where, addT->content(), addT->Length());
}
/** mutator - insert values before point
*/
Vector<T> *vinsert(int where, const Segment<T> &addT) {
return vinsert(where, addT.content(), addT.Length());
}
/** mutator - replace range with array
*/
Vector<T> *Replace(int where, int what, const T *addT, int additional);
/** mutator - replace range with array
*/
Vector<T> *Replace(int where, int what, const T *addT) {
return Replace(where, what, addT, T::findNull(addT));
}
/** mutator - replace range with array
*/
Vector<T> *Replace(int where, int what, const Segment<T> *addT) {
return Replace(where, what, addT->content(), addT->Length());
}
/** mutator - replace range with array
*/
Vector<T> *Replace(int where, int what, const Vector<T> &addT) {
return Replace(where, what, addT.content(), addT.Length());
}
////////////////////////////////////
// mutator - set operations on Vector
/** add an element to the set, true if added
*/
bool set_add(const T &d);
/** delete an element from the set, true if deleted
*/
bool set_remove(const T &d);
/** convert Vector to set
*/
void toset();
};
// reallocate Segment
template <class T>
void Vector<T>::rlloc(int newlen)
{
assert(newlen > 0);
check(); // validate the current state
const int asize = actual_allocation(newlen);
TupleBase<T> *newalloc = new (asize) TupleBase<T>(this, asize);
if (allocation)
allocation->dncount(); // destroy contents of old Tuple
allocation = newalloc; // make new allocation the current one
allocation->upcount(); // bump refcount
start = allocation->content(); // point Vector to correct Tuple
T::init(start + len, asize - len); // initialize new space in new Tuple
len = newlen; // set the new length
check(); // test the result
}
// realloc Vector's Segment to accomodate new growth
// realloc uses extra_allocation to give each allocation more space for growth
template <class T>
void Vector<T>::resize(int newlen)
{
assert(newlen > 0);
if (!allocation) {
rlloc(newlen);
} else if (allocation->Length() < newlen) {
// insufficient space, realloc
if (newlen) {
if (!start) {
// this was a NULL Vector - allocate it some space
const int asize = actual_allocation(newlen);
check();
allocation = new (asize) TupleBase<T>(asize);
allocation->upcount();
set(allocation->content(), newlen);// point Vector at Tuple
T::init(start, newlen); // initialize contents of new Segment
check();
} else {
rlloc(newlen);
}
} else {
// Segment's shrunk to nothing, delete it and make a NULL Vector
allocation->dncount();
allocation = (TupleBase<T>*)0;
(Segment<T>)*this = Segment<T>((T*)0,0);
}
} else {
len = newlen;
}
}
// reallocate Vector's Segment if it's shrunk below minimum utilization
template <class T>
void Vector<T>::shrink()
{
if (start) {
// it's not a NULL Vector
if (!len) {
// Segment's shrunk to nothing, delete it and make a NULL Vector
allocation->dncount();
allocation = (TupleBase<T>*)0;
set(0, 0);
} else if ((allocation->Length() / (int)minimum_occupancy) > len) {
// the allocation Segment is under-occupied,
// make a new tighter-fitting one
rlloc(len);
}
}
check();
}
// return an element of Vector, extending as required
template <class T>
T & Vector<T>::operator[] (int index) //const
{
if (index >= len) {
resize(index+1); // extend the Vector
len = index+1;
check();
}
return start[index];
}
// consistency check
template <class T>
void Vector<T>::check(int i) const
{
if (allocation) {
#ifdef BTREE_INTEGRITY
Memory::Assert();
#endif
assert(allocation->encloses(*this) || !"active doesn't enclose allocation");
T::check(start, len);
} else if (len) {
assert(!"Null start pointer, non-zero length");
}
DEBLOG(cerr << "check: " << *this << '\n');
while (--i) {
// recursive - lets Vector<Vector<>> work
(this+1)->check(i);
}
}
// Null Vector constructor
template <class T>
Vector<T>::Vector()
: Segment<T>(0),
allocation((TupleBase<T>*)0)
{}
// construct a Vector with pre-allocation
template <class T>
Vector<T>::Vector(int size)
: allocation(new (actual_allocation(size))
TupleBase<T>(actual_allocation(size)))
{
set(allocation->content(), 0);
allocation->upcount();
}
// Copy T* array of a given size
template <class T>
Vector<T>::Vector(const T *contentT, int size)
: allocation(new (actual_allocation(size))
TupleBase<T>(actual_allocation(size)))
{
set(allocation->content(), size);
T::check(contentT, size);
T::dup(start, contentT, size);
allocation->upcount();
}
// Copy Segment
template <class T>
Vector<T>::Vector(const Segment<T> &contentT)
: allocation(new (actual_allocation(len))
TupleBase<T>(actual_allocation(len)))
{
set(allocation->content(), contentT.Length());
T::check(contentT.content(), len);
T::dup(start, contentT, len);
allocation->upcount();
}
// Singleton T& Vector
template <class T>
Vector<T>::Vector(const T &contentT)
: allocation(new (actual_allocation(1)) TupleBase<T>(actual_allocation(1)))
{
set(allocation->content(), 1);
*start = contentT;
allocation->upcount();
}
// Repeat T& as array
template <class T>
Vector<T>::Vector(const T &contentT, int repetition)
: allocation(new (actual_allocation(repetition))
TupleBase<T>(actual_allocation(repetition)))
{
set(allocation->content(), repetition);
T::segFill(start, contentT, repetition);
allocation->upcount();
}
// Reference Tuple
template <class T>
Vector<T>::Vector(TupleBase<T> *t)
: allocation(t)
{
if (allocation) {
set(allocation->content(), allocation->Length());
check();
allocation->upcount();
}
}
// Reference Tuple
template <class T>
Vector<T>::Vector(TupleBase<T> &t)
: allocation(&t)
{
if (allocation) {
set(allocation->content(), allocation->Length());
check();
allocation->upcount();
}
}
// Reference Sub-Tuple
template <class T>
Vector<T>::Vector(TupleBase<T> *t, int _start, int _len)
: allocation(t)
{
if (allocation) {
set(allocation->content() + _start,
(_len < 0)?allocation->Length():_len);
check();
allocation->upcount();
}
}
// Reference Sub-Tuple
template <class T>
Vector<T>::Vector(TupleBase<T> &t, int _start, int _len)
: allocation(&t)
{
if (allocation) {
set(allocation->content() + _start,
(_len < 0)?allocation->Length():_len);
check();
allocation->upcount();
}
}
// Reference a Vector<T>'s contents
template <class T>
Vector<T>::Vector(const Vector<T> *v)
: allocation(v->Allocation())
{
if (allocation) {
set(v->content(), v->Length());
check();
allocation->upcount();
}
}
template <class T>
Vector<T>::Vector(const Vector<T> &v)
: allocation(v.Allocation())
{
if (allocation) {
set(v.content(), v.Length());
check();
allocation->upcount();
}
}
// Share a subrange of Vector<T>'s contents
template <class T>
Vector<T>::Vector(const Vector<T> *v, int _start, int _len)
: allocation(v->Allocation())
{
if (allocation) {
set(v->content() + _start, (_len < 0) ?(v->Length() - _start) :_len);
check();
allocation->upcount();
}
}
template <class T>
Vector<T>::Vector(const Vector<T> &v, int _start, int _len)
: allocation(v.Allocation())
{
if (allocation) {
set(v.content() + _start, (_len < 0) ?(v.Length() - _start) :_len);
check();
allocation->upcount();
}
}
// union vector constructor - returns a vector of v1 + v2
template <class T>
Vector<T>::Vector(const Vector<T> *v1, const Vector<T> *v2)
: allocation(new (actual_allocation(v1->len + v2->len))
TupleBase<T>(actual_allocation(v1->len + v2->len)))
{
v1->check();
v2->check();
set(allocation->content(), v1->len + v2->len);
T::dup(start, v1->start, v1->len);
T::dup(start + v1->len, v2->start, v2->len);
allocation->upcount();
}
template <class T>
Vector<T>::Vector(const Vector<T> &v1, const Vector<T> &v2)
: allocation(new (actual_allocation(v1.len + v2.len))
TupleBase<T>(actual_allocation(v1.len + v2.len)))
{
v1.check();
v2.check();
set(allocation->content(), v1.len + v2.len);
T::dup(start, v1.start, v1.len);
T::dup(start + v1.len, v2.start, v2.len);
allocation->upcount();
}
template <class T>
Vector<T>::~Vector()
{
if (allocation) {
allocation->dncount();
}
}
// doDel - delete but don't shrink (used by replace)
template <class T>
Vector<T> *Vector<T>::doDel(int where, int what)
{
DEBLOG(cerr << this << "->Vector<>::doDel("
<< where << ", " << what << ")\n");
if (!start || len == 0)
throw new Error("nil", 0, "Destination of delete is empty");
// negative where is end-relative
if ((where = endRelative(where)) < 0)
throw new Error("range", where, "End is before start");
if (where >= len)
throw new Error("range", where, "Start is after end");
// negative location is end-relative
if (what < 0)
what = len - where + what + 1;
// check bounds on deletion
if ((where + what) > len)
throw new Error("range", where, "End is after end");
// trivial deletion of no items
if (what == 0)
return this;
// can't delete more than is there
if (what > len)
throw new Error("range", what, "Deleting too much");
// check allocation's refcount, copy if necessary
if (allocation && (allocation->refcount() > 1))
rlloc(len);
// destroy the segment to be elided
T::destroy(start+where, what);
check();
if ((where+what) == len) {
// reduction in strength - deletion at end just reduces len
T::init(start + len - what, what);
check();
} else if (where == 0) {
// reduction in strength - deletion at beginning just increases start
T::init(start, what);
check();
start += what;
} else {
// move the relevant parts down
T::move(start+where, start + where + what, len - where - what);
check();
T::init(start + len - what, what);
check();
}
// adjust length
len -= what;
check();
return this;
}
template <class T>
Vector<T> *Vector<T>::del(int where, int what)
{
check();
doDel(where, what);
shrink();
return this;
}
// append values to right
template <class T>
Vector<T> *Vector<T>::vconcat(const T *addT, int additional)
{
check();
// appending NULL always works
if (!addT || !additional)
return this;
T::check(addT, additional);
check();
// check allocation's refcount, copy if necessary
int oldlen = len;
if (allocation && (allocation->refcount() > 1))
rlloc(len + additional);
else {
resize(len + additional); // ensure there's enough space
}
if (start + oldlen + additional > allocation->last()) {
// insufficient space on the right.
// we have to move the contents left anyway,
// so move it to the allocation start
T::move(allocation->content(), start, oldlen);
start = allocation->content();
}
// there's now enough space to add to the right
T::dup(start+oldlen, addT, additional);
check();
return this;
}
// insert values before point
template <class T>
Vector<T> *Vector<T>::vinsert(int where, const T *addT, int what)
{
DEBLOG(cerr << this << "->Vector<>::vinsert("
<< where << ", " << addT << ", " << what << ")\n");
check();
// inserting null always succeeds
if (!addT || !what)
return this;
T::check(addT, what);
// negative where is end-relative
if ((where = endRelative(where)) < 0)
throw new Error("range", where, "End is before start");
// check bounds on insertion point
if (where > len)
throw new Error("range", where, "Start is after end");
if (where == len) {
// strength-reduction: inserting at/after the end is adding
return vconcat(addT, what);
}
// we're inserting contents in the middle
// check allocation's refcount, copy if necessary
int oldlen = len;
if (allocation && (allocation->refcount() > 1))
rlloc(len + what);
else
resize(len + what);
DEBLOG(cerr << *this << ' ' << oldlen
<< " Vector<>::vinsert post-resize "
<< where << " " << what << '\n');
if (start > allocation->content()) {
// make hole leftward then fill it
if (start - what > allocation->content()) {
// we can slide the start left and do the complete insertion
T::move(start - what, start, where); // slide some left
start -= what; // adjust start
} else {
// there's not enough space to the left, but there's some,
// slide left to the start of allocation
int diff = what - (start - allocation->content()); // right-space needed
T::move(start+where+diff, start + where, oldlen - where); // slide some right
T::move(allocation->content(), start, where);// slide some left
start = allocation->content(); // adjust start
}
} else {
// make hole rightward
T::move(start+where+what, start + where, oldlen - where);// slide some right
}
T::init(start + where, what); // zero the opened space
T::dup(start+where, addT, what); // add in new content
check();
return this;
}
// replace range with array
template <class T>
Vector<T> *Vector<T>::Replace(int where, int what,
const T *addT, int additional)
{
DEBLOG(cerr << this << "->Vector<>::replace("
<< where << ", " << what << ", " << addT
<< ", " << additional << ")\n");
assert(what > 0);
check();
T::check(addT, additional);
if ((where = endRelative(where)) < 0)
throw new Error("range", where, "End is before start");
doDel(where, what);
if (where > len)
where = len;
return vinsert(where, addT, additional);
}
// add an element to the set, true if added
template <class T>
bool Vector<T>::set_add(const T &d)
{
check();
T::check(&d, 1);
int index;
if (tsearch(d, index)) {
return false;
} else {
// not yet present
vinsert(index, &d, 1);
// qsort(); shouldn't be necessary if tsearch is stable
return true;
}
}
// delete an element from the set, true if deleted
template <class T>
bool Vector<T>::set_remove(const T &d)
{
check();
T::check(&d, 1);
int pos;
if (tsearch(d, pos)) {
// found it
doDel(pos, 1);
shrink();
return true;
} else {
// not present
return false;
}
}
// convert Vector to set
template <class T>
void Vector<T>::toset()
{
check();
if (len) {
// check allocation's refcount, copy if necessary
if (allocation->refcount() > 1)
rlloc(len);
qsort();
// remove duplicates
for (int i = 0; i < len - 1; i++) {
if (*(start + i) == *(start + i+1)) {
doDel(i,1);
i--;
}
}
shrink();
}
}
// destroy contents
template <class T>
void Vector<T>::destroy(int len)
{
assert(len > 0);
allocation->dncount();
}
// dump Vector to file
template <class T>
ostream& operator<< (ostream& out, const Vector<T> & vec)
{
if (&vec && vec.allocation) {
out.form("[0x%08x,%d] [0x%08x,%d] ",
vec.allocation->content(), vec.allocation->Length(),
vec.content(), vec.Length());
out << "\"";
const T *contents = vec.content();
for (int i = 0; i < vec.Length(); i++)
out << contents[i];
out << "\"";
} else {
out << "[NULL]\n";
}
return out;
}
#endif
| Generated by: colin@sharedtech.dhis.org on Sat Nov 6 11:59:24 199. |