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
|
// svec.C
//
// This program is free software. See the file COPYING for details.
// Author: Mattias Engdegrd, 1997-1999
// implement a stretchy vector class:
// An Svec<T> grows automatically (doubles when full), so that adding
// elements to the end has an amortized cost of O(1).
// For now, only use this for types not requiring a con/destructor.
#ifndef SVEC_C
#define SVEC_C
#include "svec.h"
template<class T>
Svec<T>::Svec(int max)
: alloced(max), used(0)
{
vect = (T *)malloc(max * sizeof(T));
}
template<class T>
Svec<T>::Svec(const Svec<T> &s)
{
int n = s.size();
if(n < 8) n = 8;
vect = (T *)malloc(n * sizeof(T));
alloced = n;
used = s.size();
for(int i = 0; i < used; i++)
vect[i] = s[i];
}
template<class T>
Svec<T> &Svec<T>::operator=(const Svec<T> &s)
{
if(this != &s) {
if(alloced < s.size()) {
alloced = s.size();
vect = (T *)realloc(vect, alloced * sizeof(T));
}
for(int i = 0; i < s.size(); i++) {
vect[i] = s.vect[i];
}
used = s.size();
}
return *this;
}
template<class T>
void Svec<T>::indexerr(int index) const
{
fatal("Svec: index out of range (%d, valid is 0..%d)", index, used - 1);
}
template<class T>
void Svec<T>::setSize(int newsize)
{
while(newsize > alloced) grow();
used = newsize;
}
template<class T>
void Svec<T>::setextend(int index, T value)
{
#ifdef CHECK_INDICES
if(index < 0)
fatal("const Svec: negative index");
#endif
while(index >= alloced) grow();
if(index >= used) used = index + 1;
vect[index] = value;
}
template<class T>
void Svec<T>::remove(int index)
{
#ifdef CHECK_INDICES
if(index < 0 || index >= used)
fatal("Svec: index out of range");
#endif
for(int j = index; j < used - 1; j++)
vect[j] = vect[j + 1];
used--;
}
// Assuming T is "pointer to U", delete all contents.
// Warning: duplicated objects will be deleted twice --- doubleplusungood
template<class T>
void Svec<T>::purge()
{
for(int i = 0; i < used; i++)
delete vect[i];
used = 0;
}
template<class T>
void Svec<T>::sort(int (*compare)(const T *a, const T *b))
{
qsort(vect, used, sizeof(T), (int (*)(const void *, const void *))compare);
}
#endif // SVEC_C
|
