21 #ifndef INCLUDE_ELM_DATA_VECTOR_H_
22 #define INCLUDE_ELM_DATA_VECTOR_H_
28 #include <elm/array.h>
29 #include <elm/compat.h>
33 template <
class T,
class E = Equiv<T>,
class A = DefaultAlloc >
35 inline T *newVec(
int size)
36 { T *
t =
static_cast<T *
>(A::allocate(
size *
sizeof(T)));
44 inline Vector(
int _cap = 8): tab(newVec(_cap)), cap(_cap), cnt(0) { }
46 inline ~Vector(
void) {
if(tab) deleteVec(tab, cap); }
52 inline int capacity(
void)
const {
return cap; }
56 { T *rt = tab;
int rc = cnt; tab = 0; cnt = 0;
return Array<T>(rc, rt); }
58 { ASSERTP(new_cap >= cap,
"new capacity must be bigger than old one");
59 T *new_tab = newVec(new_cap);
array::copy(new_tab, tab, cnt); deleteVec(tab, cap); tab = new_tab; cap = new_cap; }
61 {
int new_cap; ASSERTP(new_length >= 0,
"new length must be >= 0");
62 for(new_cap = 1; new_cap < new_length; new_cap *= 2);
63 if (new_cap > cap)
grow(new_cap); cnt = new_length; }
64 inline T&
addNew(
void) {
if(cnt >= cap)
grow(cap * 2);
return tab[cnt++]; }
72 inline int index(
void)
const {
return i; }
88 inline int count(
void)
const {
return cnt; }
90 {
for(
Iter i(*
this); i(); i++)
if(v == *i)
return true;
return false; }
92 {
for(
const auto& x:
items)
if(!
contains(x))
return false;
return true; }
93 inline bool isEmpty(
void)
const {
return cnt == 0; }
94 inline operator bool(
void)
const {
return cnt != 0; }
96 template <
class C>
inline bool equals(
const C& c)
const {
97 int i = 0;
for(
const auto& x: c)
114 inline void clear(
void) { cnt = 0; }
115 void add(
const T& v) {
if(cnt >= cap)
grow(cap * 2); tab[cnt++] = v; }
116 template <
class C>
inline void addAll(
const C& c)
117 {
for(
typename C::Iter i(c); i(); i++)
add(*i); }
120 {
for(
const auto x: c)
remove(x); }
125 {
if(!tab || vec.cnt > cap) {
if(tab) deleteVec(tab, cap); cap = vec.cap; tab = newVec(vec.cap); }
131 inline const T&
get(
int i)
const
132 { ASSERTP(0 <= i && i < cnt,
"index out of bounds");
return tab[i]; }
134 { ASSERTP(0 <=
p &&
p <= cnt,
"index out of bounds");
135 for(
int i =
p; i < cnt; i++)
if(E::isEqual(v, tab[i]))
return i;
return -1; }
137 { ASSERTP(
p <= cnt,
"index out of bounds");
138 for(
int i = (
p < 0 ? cnt :
p) - 1; i >= 0; i--)
if(E::isEqual(v, tab[i]))
return i;
return -1; }
143 { ASSERTP(0 <= l && l <= cnt,
"bad shrink value"); cnt = l; }
144 inline void set(
int i,
const T& v)
145 { ASSERTP(0 <= i && i < cnt,
"index out of bounds"); tab[i] = v; }
148 { ASSERTP(index < cnt,
"index out of bounds");
return tab[index]; }
153 { ASSERTP(0 <= i && i <= cnt,
"index out of bounds");
154 if(cnt >= cap)
grow(cap * 2);
array::move(tab + i + 1, tab + i, cnt - i);
158 { ASSERTP(0 <= i && i <= cnt,
"index out of bounds");
159 array::move(tab + i, tab + i + 1, cnt - i - 1); cnt--; }
163 inline const T&
first(
void)
const { ASSERT(cnt > 0);
return tab[0]; }
164 inline const T&
last(
void)
const { ASSERT(cnt > 0);
return tab[cnt - 1]; }
166 {
Iter i(*
this);
while(i() && !
E::equals(*i, v)) i++;
return i; }
169 inline const T&
nth(
int i)
const {
return get(i); }
172 inline T&
first() { ASSERT(cnt > 0);
return tab[0]; }
173 inline T&
last() { ASSERT(cnt > 0);
return tab[cnt - 1]; }
184 inline const T &
top(
void)
const {
return last(); }
185 inline T &
top(
void) {
return tab[cnt - 1]; }
186 inline T
pop(
void) { ASSERTP(cnt > 0,
"no more data to pop"); cnt--;
return tab[cnt]; }
199 template <
class T,
class E,
class A>
const T & item() const
Definition: Vector.h:83
T & item() const
Definition: Vector.h:108
bool equals(const PreIter &it) const
Definition: Vector.h:73
int index(void) const
Definition: Vector.h:72
void next(void)
Definition: Vector.h:71
const self_t * _vec
Definition: Vector.h:75
int i
Definition: Vector.h:76
PreIter(const self_t &vec, int idx=0)
Definition: Vector.h:69
bool ended(void) const
Definition: Vector.h:70
void addAll(const C &c)
Definition: Vector.h:116
void removeAt(int i)
Definition: Vector.h:157
Vector< T > & operator+=(const T x)
Definition: Vector.h:122
void removeFirst(void)
Definition: Vector.h:176
const T & get(int i) const
Definition: Vector.h:131
void insert(int i, const T &v)
Definition: Vector.h:152
const A & allocator() const
Definition: Vector.h:49
Vector(int _cap=8)
Definition: Vector.h:44
void copy(const Vector &vec)
Definition: Vector.h:124
MutIter begin()
Definition: Vector.h:111
void removeAfter(const Iter &i)
Definition: Vector.h:181
void addLast(const T &v)
Definition: Vector.h:175
T t
Definition: Vector.h:41
T & addNew(void)
Definition: Vector.h:64
Array< const T > asArray(void) const
Definition: Vector.h:53
void reset(void)
Definition: Vector.h:188
const T & last(void) const
Definition: Vector.h:164
Vector< T, E, A > self_t
Definition: Vector.h:42
void shrink(int l)
Definition: Vector.h:142
Array< T > asArray(void)
Definition: Vector.h:54
MutIter end()
Definition: Vector.h:112
const T & first(void) const
Definition: Vector.h:163
int indexOf(const T &v, int p=0) const
Definition: Vector.h:133
void addAfter(const Iter &i, const T &v)
Definition: Vector.h:178
void removeLast(void)
Definition: Vector.h:177
int lastIndexOf(const T &v, int p=-1) const
Definition: Vector.h:136
bool equals(const C &c) const
Definition: Vector.h:96
Iter begin() const
Definition: Vector.h:85
bool containsAll(const C &items)
Definition: Vector.h:91
T & get(int index)
Definition: Vector.h:147
const T & top(void) const
Definition: Vector.h:184
A & allocator()
Definition: Vector.h:50
E & equivalence()
Definition: Vector.h:48
T & operator[](const Iter &i)
Definition: Vector.h:151
T & first()
Definition: Vector.h:172
int count(void) const
Definition: Vector.h:88
const E & equivalence() const
Definition: Vector.h:47
bool contains(const T &v) const
Definition: Vector.h:89
bool operator!=(const Vector< T > &v) const
Definition: Vector.h:100
int capacity(void) const
Definition: Vector.h:52
void insert(const Iter &i, const T &v)
Definition: Vector.h:156
T & last()
Definition: Vector.h:173
int length(void) const
Definition: Vector.h:130
T & top(void)
Definition: Vector.h:185
const T & nth(int i) const
Definition: Vector.h:169
void remove(const T &value)
Definition: Vector.h:118
void set(int i, const T &v)
Definition: Vector.h:144
void add(const T &v)
Definition: Vector.h:115
Vector< T > & operator=(const Vector &vec)
Definition: Vector.h:127
~Vector(void)
Definition: Vector.h:46
void grow(int new_cap)
Definition: Vector.h:57
void setLength(int new_length)
Definition: Vector.h:60
void addBefore(const Iter &i, const T &v)
Definition: Vector.h:179
Iter find(const T &v, const Iter &p) const
Definition: Vector.h:167
Iter operator*(void) const
Definition: Vector.h:191
const T & operator[](int i) const
Definition: Vector.h:139
Vector(const Vector< T > &vec)
Definition: Vector.h:45
void remove(const Iter &i)
Definition: Vector.h:121
bool operator==(const Vector< T > &v) const
Definition: Vector.h:99
Iter end() const
Definition: Vector.h:86
void removeAt(const Iter &i)
Definition: Vector.h:160
T & operator[](int i)
Definition: Vector.h:150
Array< T > detach(void)
Definition: Vector.h:55
void addFirst(const T &v)
Definition: Vector.h:174
Iter items(void) const
Definition: Vector.h:192
Vector< T > & operator-=(const T x)
Definition: Vector.h:123
void clear(void)
Definition: Vector.h:114
bool isEmpty(void) const
Definition: Vector.h:93
void set(const Iter &i, const T &v)
Definition: Vector.h:146
T & get(const Iter &i)
Definition: Vector.h:149
Iter find(const T &v) const
Definition: Vector.h:165
void push(const T &v)
Definition: Vector.h:187
void removeBefore(const Iter &i)
Definition: Vector.h:180
void removeAll(const C &c)
Definition: Vector.h:119
T pop(void)
Definition: Vector.h:186
bool equals(const C1 &c1, const C2 &c2)
Definition: util.h:107
Printable< T, M > p(const T &data, const M &man)
Definition: Output.h:302
uint64 size
Definition: arch.h:35
void copy(T *target, const T *source, int size)
Definition: array.h:70
void destruct(T *t, int size)
Definition: array.h:84
void construct(T *t, int size)
Definition: array.h:82
void move(T *target, const T *source, int size)
Definition: array.h:74