Elm  2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
Vector.h
1 /*
2  * Vector class interface
3  *
4  * This file is part of OTAWA
5  * Copyright (c) 2016, IRIT UPS.
6  *
7  * OTAWA is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * OTAWA is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with OTAWA; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 #ifndef INCLUDE_ELM_DATA_VECTOR_H_
22 #define INCLUDE_ELM_DATA_VECTOR_H_
23 
24 #include "custom.h"
25 #include "Array.h"
26 #include "Manager.h"
27 
28 #include <elm/array.h>
29 #include <elm/compat.h>
30 
31 namespace elm {
32 
33 template <class T, class E = Equiv<T>, class A = DefaultAlloc >
34 class Vector: public E, public A {
35  inline T *newVec(int size)
36  { T *t = static_cast<T *>(A::allocate(size * sizeof(T)));
37  array::construct(t, size); return t; }
38  inline void deleteVec(T *t, int size) { array::destruct(t, size); A::free(t); }
39 
40 public:
41  typedef T t;
43 
44  inline Vector(int _cap = 8): tab(newVec(_cap)), cap(_cap), cnt(0) { }
45  inline Vector(const Vector<T>& vec): tab(0), cap(0), cnt(0) { copy(vec); }
46  inline ~Vector(void) { if(tab) deleteVec(tab, cap); }
47  inline const E& equivalence() const { return *this; }
48  inline E& equivalence() { return *this; }
49  inline const A& allocator() const { return *this; }
50  inline A& allocator() { return *this; }
51 
52  inline int capacity(void) const { return cap; }
53  inline Array<const T> asArray(void) const { return Array<const T>(count(), tab); }
54  inline Array<T> asArray(void) { return Array<T>(count(), tab); }
55  inline Array<T> detach(void)
56  { T *rt = tab; int rc = cnt; tab = 0; cnt = 0; return Array<T>(rc, rt); }
57  void grow(int new_cap)
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; }
60  void setLength(int new_length)
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++]; }
65 
66  class PreIter {
67  friend class Vector;
68  public:
69  inline PreIter(const self_t& vec, int idx = 0): _vec(&vec), i(idx) { }
70  inline bool ended(void) const { return i >= _vec->length(); }
71  inline void next(void) { i++; }
72  inline int index(void) const { return i; }
73  inline bool equals(const PreIter& it) const { return _vec == it._vec && i == it.i; }
74  protected:
75  const self_t *_vec;
76  int i;
77  };
78 
79  // Collection concept
80  class Iter: public PreIter, public elm::ConstPreIter<Iter, T>, public elm::PreIter<Iter, T> {
81  public:
83  inline const T& item() const { return (*PreIter::_vec)[PreIter::i]; }
84  };
85  inline Iter begin() const { return Iter(*this); }
86  inline Iter end() const { return Iter(*this, count()); }
87 
88  inline int count(void) const { return cnt; }
89  bool contains(const T& v) const
90  { for(Iter i(*this); i(); i++) if(v == *i) return true; return false; }
91  template <class C> inline bool containsAll(const C& items)
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; }
95 
96  template <class C> inline bool equals(const C& c) const {
97  int i = 0; for(const auto& x: c)
98  { if(i >= count() || !E::equals(tab[i], x)) return false; i++; } return i == count(); }
99  inline bool operator==(const Vector<T>& v) const { return equals(v); }
100  inline bool operator!=(const Vector<T>& v) const { return !equals(v); }
101 
102  static const Vector<T, E, A> null;
103 
104  // MutableCollection concept
105  class MutIter: public PreIter, public MutPreIter<MutIter, T>, public elm::PreIter<MutIter, T> {
106  public:
108  inline T& item() const { return (*const_cast<self_t *>(PreIter::_vec))[PreIter::i]; }
109  inline operator Iter() const { return Iter(*PreIter::_vec, PreIter::i); }
110  };
111  inline MutIter begin() { return MutIter(*this); }
112  inline MutIter end() { return MutIter(*this, count()); }
113 
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); }
118  inline void remove(const T& value) { int i = indexOf(value); if(i >= 0) removeAt(i); }
119  template <class C> inline void removeAll(const C& c)
120  { for(const auto x: c) remove(x); }
121  inline void remove(const Iter& i) { removeAt(i.i); }
122  inline Vector<T>& operator+=(const T x) { add(x); return *this; }
123  inline Vector<T>& operator-=(const T x) { remove(x); return *this; }
124  void copy(const Vector& vec)
125  { if(!tab || vec.cnt > cap) { if(tab) deleteVec(tab, cap); cap = vec.cap; tab = newVec(vec.cap); }
126  cnt = vec.cnt; array::copy(tab, vec.tab, cnt); }
127  inline Vector<T>& operator=(const Vector& vec) { copy(vec); return *this; };
128 
129  // Array concept
130  inline int length(void) const { return count(); }
131  inline const T& get(int i) const
132  { ASSERTP(0 <= i && i < cnt, "index out of bounds"); return tab[i]; }
133  inline int indexOf(const T& v, int p = 0) const
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; }
136  inline int lastIndexOf(const T& v, int p = -1) const
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; }
139  inline const T & operator[](int i) const { return get(i); }
140 
141  // MutableArray concept
142  inline void shrink(int l)
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; }
146  inline void set (const Iter &i, const T &v) { set(i.i, v); }
147  inline T& get(int index)
148  { ASSERTP(index < cnt, "index out of bounds"); return tab[index]; }
149  inline T& get(const Iter& i) { return get(i.index()); }
150  inline T & operator[](int i) { return get(i); }
151  inline T & operator[](const Iter& i) { return get(i); }
152  void insert(int i, const T& v)
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);
155  tab[i] = v; cnt++; }
156  inline void insert(const Iter &i, const T &v) { insert(i.i, v); }
157  void removeAt(int i)
158  { ASSERTP(0 <= i && i <= cnt, "index out of bounds");
159  array::move(tab + i, tab + i + 1, cnt - i - 1); cnt--; }
160  inline void removeAt(const Iter& i) { removeAt(i.i); }
161 
162  // List concept
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]; }
165  inline Iter find(const T &v) const
166  { Iter i(*this); while(i() && !E::equals(*i, v)) i++; return i; }
167  inline Iter find (const T &v, const Iter &p) const
168  { Iter i(p); while(i() && !E::equals(*i, v)) i++; return i; }
169  inline const T& nth(int i) const { return get(i); }
170 
171  // MutableList concept
172  inline T& first() { ASSERT(cnt > 0); return tab[0]; }
173  inline T& last() { ASSERT(cnt > 0); return tab[cnt - 1]; }
174  inline void addFirst(const T &v) { insert(0, v); }
175  inline void addLast(const T &v) { add(v); }
176  inline void removeFirst(void) { removeAt(0); }
177  inline void removeLast(void) { removeAt(cnt - 1); }
178  inline void addAfter(const Iter &i, const T &v) { insert(i.i + 1, v); }
179  inline void addBefore(const Iter &i, const T &v) { insert(i.i, v); }
180  inline void removeBefore(const Iter& i) { removeAt(i.i - 1); }
181  inline void removeAfter(const Iter& i) { removeAt(i.i + 1); }
182 
183  // Stack concept
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]; }
187  inline void push(const T &v) { add(v); }
188  inline void reset(void) { clear(); }
189 
190  // deprecated
191  inline Iter operator*(void) const { return items(); }
192  inline Iter items(void) const { return Iter(*this); }
193 
194 private:
195  T *tab;
196  int cap, cnt;
197 };
198 
199 template <class T, class E, class A>
201 
202 } // elm
203 
204 #endif /* INCLUDE_ELM_DATA_VECTOR_H_ */
Definition: Array.h:33
Definition: iter.h:84
Definition: iter.h:92
Definition: iter.h:69
Definition: Vector.h:80
const T & item() const
Definition: Vector.h:83
Definition: Vector.h:105
T & item() const
Definition: Vector.h:108
Definition: Vector.h:66
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
Definition: Vector.h:34
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
Definition: adapter.h:26