1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
/* -*- Mode: C++ -*-
* Worldvisions Weaver Software:
* Copyright (C) 1997-2002 Net Integration Technologies, Inc.
*
* Provides an auto-resizing array data structure.
*/
#ifndef __WVVECTOR_H
#define __WVVECTOR_H
#include "wvxplc.h"
#include "wvlink.h"
#include <string.h>
/**
* The untyped vector base type.
* @see WvVector
*/
class WvVectorBase
{
protected:
static const int MINALLOC = 4;
/*!< the minimum number of slots to allocate */
void **xseq; /*!< the controlled sequence */
int xcount; /*!< the number of elements in the sequence */
int xslots; /*!< the capacity of the array */
bool auto_free; /*!< whether to auto-delete the elements when removed */
/** Creates an empty vector. */
WvVectorBase(bool _auto_free);
/** Computes the number of slots needed to grow to at least minslots. */
int growcapacity(int minslots);
/** Computes the number of slots needed to shrink down to maxslots. */
int shrinkcapacity(int maxslots);
/** A shorthand for memmove() with size adjustment. */
void moveelems(void *dst, void *src, int nelems)
{ memmove(dst, src, nelems * sizeof(void *)); }
/** Removes the element at the specified slot. */
void remove(int slot);
/** Inserts an element at the specified slot. */
void insert(int slot, void *elem);
/** Appends an element onto the tail of the vector. */
void append(void *elem);
public:
/** Returns the number of elements actually stored in the vector. */
int count() const
{ return xcount; }
/** Returns true if the vector is empty. */
bool isempty() const
{ return xcount == 0; }
/** The number of elements that could be stored without resizing. */
int capacity() const
{ return xslots; }
/**
* Adjusts the capacity of the vector.
*
* If the new capacity is greater than the old one, extends the array
* size without actually filling in any elements.
*/
void setcapacity(int newslots);
/** Compacts the vector to minimize its footprint. */
void compact()
{ setcapacity(count()); }
};
/**
* A dynamic array data structure with constant time lookup,
* linear time insertion / removal, and expected logarithmic time
* append.
*/
template<class T>
class WvVector : public WvVectorBase
{
public:
/** Creates an empty vector. */
WvVector(bool _auto_free) : WvVectorBase(_auto_free)
{ }
/** Destroys the vector and all of its contents. */
~WvVector()
{ zap(); }
/** Dereferences a particular slot of the vector. */
T *operator[] (int slot)
{ return ptr()[slot]; }
/** Removes all elements from the vector. */
void zap()
{
// guard against potential side-effects
T **oldarray = ptr();
int oldcount = xcount;
xcount = 0;
xslots = 0;
xseq = NULL;
if (auto_free)
{
while (oldcount > 0)
delete oldarray[--oldcount];
}
deletev oldarray;
}
void remove(int slot, bool never_delete = false)
{
T *obj = (*this)[slot];
WvVectorBase::remove(slot);
if (auto_free && !never_delete)
delete obj;
}
/** Removes the last element */
void remove_last()
{ if (xcount) { remove(xcount-1); } }
T *last()
{ return xcount ? (*this)[xcount-1] : NULL; }
void insert(int slot, T *elem)
{ WvVectorBase::insert(slot, elem); }
void append(T *elem)
{ WvVectorBase::append(elem); }
// FIXME: I'd rather not give public access to this, since it's dangerous!
T **ptr()
{ return reinterpret_cast<T **>(xseq); }
/** A simple iterator that walks through all elements in the list. */
class Iter
{
WvVector<T> *list;
int count;
protected:
/** _list is allowed to be NULL, and this will still work. */
Iter(WvVector<T> *_list) : list(_list)
{ count = -1; }
public:
Iter(WvVector<T> &_list) : list(&_list)
{ count = -1; }
void rewind()
{ count = -1; }
bool next()
{ count++; return cur(); }
bool cur()
{ return list && count >= 0 && count < list->count(); }
T *ptr() const
{ return (*list)[count]; }
WvIterStuff(T);
};
};
#endif // __WVVECTOR_H
|
