// Segment - weak Vector
// Copyright (C) 1998,1999 Colin McCormack,
// see LICENSE (MD5 f5220f8f599e5e926f37cf32efe3ab68) for terms
// $Id: Segment_hh.html,v 1.1.1.1 2000/04/09 01:07:51 skeptopotamus Exp $
#ifndef SEGMENT_HH
#define SEGMENT_HH
#include <string.h>
//#include <qvmm.h>
#include <assert.h>
template <class T>
class TupleBase;
/** Segment<T> templated class for weak @see Vector
A Segment<T> is a pair (T *start, length) designed to implement a
weak Vector<T> (that is, one which doesn't manage its own storage)
Segment may be constructed from a length, an explicit (start,len) pair,
or another Segment
Segment may only be constructed by a derived type.
Segment performs no content manipulation in its operation,
nor bounds checking, but defines the predicate segEncloses
for that purpose in a derived type.
*/
template <class T>
class Segment
{
protected:
/** start of segment (or (T*)0)
*/
T *start;
/** length of segment (or 0)
*/
int len;
/** explicitly set the segment's value
*/
void set(T* t, int size=0);
public:
//////////////////////////////////////////////
// Simple Constructors
/** default constructor - NULL segment
*/
Segment()
: start((T*)0), len(0) {}
/** construct a singleton Segment
*/
Segment(T &thing)
: start(&thing), len(1) {}
/** construct a Segment conforming to a @see TupleBase
*/
Segment(TupleBase<T> &t)
: start(t.content()), len(t.Length()) {}
/** construct a Segment conforming to a @see TupleBase
*/
Segment(TupleBase<T> *t)
: start(t->content()), len(t->Length()) {}
//////////////////////////////////////////////
// Storage operators
/** allocate an array of T's
*/
static T *alloc(int nelem, void *allocator = (void*)0);
/** Deallocate storage pointed at by Segment
*/
void dealloc();
//////////////////////////////////////////////
// Constructors
#if 0
// allocate a new Segment of a given size (possibly NULL)
Segment(int _len, void *allocator = (void*)0)
: start((T*)((_len > 0)? alloc(_len, allocator) :(T*)0)), len(_len)
{
assert(len >= 0);
}
#endif
/** construct a Segment from an address/len pair
*/
Segment(T *_start, int _len)
: start(_start), len(_len) {
assert(len >= 0);
}
/** Copy Constructor: construct a prefix sub-Segment of another Segment
*/
Segment(const Segment<T> &seg, int _len = 0, int offset = 0)
: start(seg.start + offset),
len(seg.len - _len) {
assert((len >= 0) && seg.segEncloses(*this));
}
#if 0
Segment<T> operator=(T *location) { // Segment assignment
start = location;
len = 0;
return *this;
}
Segment<T> operator=(Segment<T> *location) { // Segment assignment
start = location->start;
len = location->len;
return *this;
}
#endif
/** Segment assignment
*/
Segment<T> operator=(const Segment<T> &location) { // Segment assignment
start = location.start;
len = location.len;
return *this;
}
//////////////////////////////////////////////
// Limit mutators
/** advance lower edge of Segment by amount
*/
Segment *operator+=(int advance) {
start += advance;
len -= advance;
return len?this:(Segment*)0;
}
/** advance lower edge of Segment by 1
*/
Segment *operator++(int) {
return (*this) += 1;
}
public:
virtual ~Segment() {}
/** find occurrence in Segment
*/
int search(const T* what, int whatlen, int offset = 0) const;
/** find occurrence in Segment
*/
int search(const T &what, int offset = 0) const {
return search(&what, 1, offset);
}
/** find occurrence in Segment
*/
int search(const T *what, int offset = 0) const {
return search(what, T::findNull(what), offset);
}
/** find occurrence in Segment
*/
int search(const Segment<T> &what, int offset = 0) const {
return search(what.content(), what.Length(), offset);
}
/** find occurrence in Segment
*/
int search(const Segment<T>* what, int offset = 0) const {
return search(what->content(), what->Length(), offset);
}
//////////////////////////////////////////////
// Element accessors
/** Segment array accessor
*/
T &operator[](int offset) const {
assert(offset >= 0);
return start[offset];
}
/** return in-bounds const element
*/
const T &const_element(int index) const {
assert((index >= 0) && (index < len));
return start[index];
}
/** return in-bounds const element
*/
T &element(int index) const {
assert((index >= 0) && (index < len));
return start[index];
}
/** Segment length
*/
int Length() const {
return (start) ?len: 0;
}
/** Segment content
*/
T* content() const {
return start;
}
/** Segment to basetype conversion
*/
operator T* () const {
return start;
}
////////////////////////////////////////
// convenience accessors
/** pointer to start of Segment
*/
T *segFirst() const {
return start;
}
/** ref to first in Segment
*/
const T &first() const {
return *start;
}
/** pointer to end of Segment
*/
T *segLast() const {
return start + len - 1;
}
/** ref to last in Segment
*/
const T &last() const {
return start[len - 1];
}
//////////////////////////////////////////////
// predicates
/** Predicate: Segment encloses a given range
*/
bool segEncloses(const T * const _start, int _len) const {
assert(_len > 0);
return (_start >= start) && ((_start + _len) <= (start + len));
}
/** Predicate: Segment encloses another segment
*/
bool segEncloses(Segment<T> const &seg) const {
return segEncloses(seg.start, seg.len);
}
/** return the offset of T *t in content
*/
int in(T *t, int tlen = 0) const {
if (segEncloses(t, tlen)) {
return t - start;
} else {
return -1;
}
}
/** predicate: Segment is empty
*/
bool empty() const {
return !start || (len <= 0);
}
/** predicate: Segment is empty
*/
operator bool () const {
return empty();
}
//////////////////////////////////////////////
// comparison operators
static int cmp(const T *l, const T *r);
int order(const Segment<T> &that) const;
bool operator==(const Segment<T> &d) const {
return (this == &d) || (order(d) == 0);
}
bool operator!=(const Segment<T> &d) const {
return (this != &d) && (order(d) != 0);
}
bool operator>=(const Segment<T> &d) const {
return (order(d) >= 0);
}
bool operator>(const Segment<T> &d) const {
return (this != &d) && (order(d) > 0);
}
bool operator<=(const Segment<T> &d) const {
return (this != &d) && (order(d) <= 0);
}
bool operator< (const Segment<T> &d) const {
return (this != &d) && (order(d) < 0);
}
//////////////////////////////////////////////
// element ordering operations
/** qsort Segment contents
*/
Segment<T> *qsort();
/** reverse Vector
*/
Segment<T> *reverse();
/** bsearch sorted Vector
*/
bool tsearch(const T &key, int &idx) const;
////////////////////////////////////
// set operations on Segment
/** Predicate: is an element a member of the set?
*/
bool isMember(const T &d) {
int junk;
return tsearch(d, junk);
}
protected:
//////////////////////////////////////////////
// accessory operators
/** argument range modifier
*/
int endRelative(int where) const {
// negative where is end-relative
return (where < 0)? len + where: where;
}
/** duplicate a range of basetype
*/
T *dup(T* to, const T* from, int range);
};
#if 0
// allocate an array of T's
template <class T>
T *Segment<T>::alloc(int nelem, void *allocator)
{
return (T*)memset(memory->alloc(nelem * sizeof(T), allocator), nelem, sizeof(T));
}
// Deallocate storage pointed at by Segment
template <class T>
void Segment<T>::dealloc()
{
DEBLOG(cerr << memory << "->Segment<T>::dealloc(" << start << ")\n");
memory->free(start); // caller warrants that Segment was alloced by Segment(int)
start = (T*)0;
len = 0;
}
#endif
// duplicate a range of basetype
template <class T>
T *Segment<T>::dup(T* to, const T* from, int range)
{
assert(range >= 0);
for (int i = 0; i < range; i++) {
*(to + i) = *(from + i);
}
return to;
}
template <class T>
void Segment<T>::set(T* t, int size)
{
assert(size >= 0);
start = t;
len = size;
}
// compare two Segment<T>s (used by Segment::qsort and Segment::tsearch)
// find a needle in this haystack
typedef int (*Cmp)(const void*, const void*); // qsort comparison operator type
template <class T>
int Segment<T>::cmp(const T *l, const T *r)
{
return T::order(*l, *r);
}
// qsort Vector contents
template <class T>
Segment<T> *Segment<T>::qsort() {
if (len) {
::qsort(start, len, sizeof(T), (Cmp)cmp);
}
// check();
return this;
}
// binary search sorted Segment for match
template <class T>
bool Segment<T>::tsearch(const T &key, int &idx) const
{
if (len) {
size_t lower = 0;
size_t upper = len;
while (lower < upper) {
idx = (lower + upper) / 2;
int comparison = cmp(&key, &element(idx));
if (comparison < 0)
upper = idx;
else if (comparison > 0)
lower = idx + 1;
else
return true;
}
return false;
} else {
idx = 0;
return false;
}
}
// reverse Segment
template <class T>
Segment<T> *Segment<T>::reverse()
{
T tmp;
// check();
if (len) {
for (int i = 0; i < len / 2; i++) {
T::move(&tmp, start + i, 1);
T::move(start + i, start + len - i - 1, 1);
T::move(start + len - i - 1, &tmp, 1);
}
}
return this;
}
// find occurrence in vector
template <class T>
int Segment<T>::search(const T* what, int whatlen, int offset) const
{
// check();
// searching for NULL always fails
if (empty() || !what || !whatlen)
return -1;
// null terminated string
if (whatlen < 0) {
whatlen = T::findNull(what);
}
//what->check(whatlen);
// negative where is end-relative
if ((offset = endRelative(offset)) < 0)
return -1;
const T *found = NULL;
if (whatlen == 1) {
// strength reduction - single item search
found = T::find(start + offset, *what, len - offset);
} else {
// segment search
found = T::search(start + offset, what, whatlen, len - offset);
}
if (!found) {
return -1;
} else {
assert(segEncloses(found, whatlen));
return (found - start);
}
}
// order - ordering between Segments
template <class T>
int Segment<T>::order (const Segment<T> &that) const
{
int _cmp;
for (int i = 0; i < Length() && i < that.Length(); i++) {
if (!(_cmp = cmp(start + i, that.content() + i)))
continue;
else
return _cmp;
}
return Length() - that.Length();
}
#endif
| Generated by: colin@sharedtech.dhis.org on Sat Nov 6 11:59:24 199. |