Annotation of parser3/src/include/pa_array.h, revision 1.104
1.24 paf 1: /** @file
1.59 paf 2: Parser: Array & Array_iterator classes decls.
1.26 paf 3:
1.100 moko 4: Copyright (c) 2001-2024 Art. Lebedev Studio (http://www.artlebedev.com)
1.87 moko 5: Authors: Konstantin Morshnev <moko@design.ru>, Alexandr Petrosian <paf@design.ru>
1.1 paf 6: */
7:
1.24 paf 8: #ifndef PA_ARRAY_H
9: #define PA_ARRAY_H
1.54 paf 10:
1.104 ! moko 11: #define IDENT_PA_ARRAY_H "$Id: pa_array.h,v 1.103 2025/05/27 15:10:24 moko Exp $"
1.24 paf 12:
1.59 paf 13: // includes
14:
15: #include "pa_memory.h"
1.90 moko 16: #include "pa_types.h"
1.59 paf 17: #include "pa_exception.h"
18:
19: // forwards
20:
21: template<typename T> class Array_iterator;
1.101 moko 22: template<typename T> class Array_robust_iterator;
1.90 moko 23: template<typename T> class Array_reverse_iterator;
1.59 paf 24:
25: // defines
26:
27: #define ARRAY_OPTION_LIMIT_ALL ((size_t)-1)
28:
29: /// Simple Array
30: template<typename T> class Array: public PA_Object {
31:
32: friend class Array_iterator<T>;
1.101 moko 33: friend class Array_robust_iterator<T>;
1.90 moko 34: friend class Array_reverse_iterator<T>;
1.59 paf 35:
36: protected:
37:
38: /// elements[growing size] here
39: T *felements;
40:
41: // allocated size
42: size_t fallocated;
43:
44: // array size
1.94 moko 45: size_t fsize;
1.1 paf 46:
47: public:
1.88 moko 48: typedef Array_iterator<T> Iterator;
1.101 moko 49: typedef Array_robust_iterator<T> RobustIterator;
1.90 moko 50: typedef Array_reverse_iterator<T> ReverseIterator;
1.88 moko 51:
1.59 paf 52: struct Action_options {
53: size_t offset;
54: size_t limit; //< ARRAY_OPTION_LIMIT_ALL means 'all'. zero limit means 'nothing'
55: bool reverse;
56: bool defined;
57:
58: Action_options(
1.95 moko 59: size_t aoffset=0,
60: size_t alimit=ARRAY_OPTION_LIMIT_ALL,
61: bool areverse=false):
1.59 paf 62: offset(aoffset), limit(alimit), reverse(areverse),
63: defined(false) {}
64:
65: bool adjust(size_t count) {
66: if(!count || !limit)
67: return false;
1.70 misha 68: if(offset>=count)
1.59 paf 69: return false;
70: // max(limit)
71: size_t m=reverse?
1.69 misha 72: offset+1
1.59 paf 73: :count-offset;
74: if(!m)
75: return false;
76: // fix limit
1.95 moko 77: if(limit>m)
1.59 paf 78: limit=m;
1.7 paf 79:
1.59 paf 80: return true;
81: }
1.1 paf 82: };
83:
1.59 paf 84: typedef T element_type;
85:
1.71 misha 86: inline Array(size_t initial=0):
87: fallocated(initial),
1.94 moko 88: fsize(0)
1.59 paf 89: {
1.77 misha 90: felements=fallocated?(T *)pa_malloc(fallocated*sizeof(T)):0;
1.59 paf 91: }
1.6 paf 92:
1.92 moko 93: #ifdef USE_DESTRUCTORS
1.73 misha 94: inline ~Array(){
1.75 misha 95: if(felements)
1.77 misha 96: pa_free(felements);
1.72 misha 97: }
1.74 misha 98: #endif
1.72 misha 99:
1.59 paf 100: /// how many items are in Array
1.94 moko 101: inline size_t count() const { return fsize; }
1.92 moko 102:
1.59 paf 103: /// append to array
1.71 misha 104: inline Array& operator+=(T src) {
1.59 paf 105: if(is_full())
1.93 moko 106: expand();
1.7 paf 107:
1.94 moko 108: felements[fsize++]=src;
1.24 paf 109:
1.59 paf 110: return *this;
111: }
1.24 paf 112:
113: /// append other Array portion to this one. starting from offset
1.98 moko 114: void append(const Array& src, size_t offset=0, size_t limit=ARRAY_OPTION_LIMIT_ALL) { //< zero limit means 'nothing'
1.59 paf 115: size_t src_count=src.count();
116: // skip tivials
117: if(!src_count || !limit || offset>=src_count)
1.98 moko 118: return;
1.59 paf 119: // max(limit)
1.82 moko 120: size_t m=src_count-offset;
1.59 paf 121: // fix limit
1.95 moko 122: if(limit>m)
1.59 paf 123: limit=m;
124:
1.94 moko 125: fit(fsize-1+limit);
1.98 moko 126: memcpy(felements+fsize, src.felements+offset, limit * sizeof(T));
1.94 moko 127: fsize+=limit;
1.59 paf 128: }
129:
130: /// get index-element
1.71 misha 131: inline T get(size_t index) const {
1.63 paf 132: assert(index<count());
1.59 paf 133: return felements[index];
134: }
135:
136: /// ref version of get
1.71 misha 137: inline T& get_ref(size_t index) const {
1.63 paf 138: assert(index<count());
1.59 paf 139: return felements[index];
140: }
141:
142: /// put index-element
1.71 misha 143: inline void put(size_t index, T element) {
1.63 paf 144: assert(index<count());
1.59 paf 145: felements[index]=element;
146: }
147:
1.82 moko 148: /// insert index-element
149: inline void insert(size_t index, T element) {
150: assert(index<=count());
151:
152: if(is_full())
1.93 moko 153: expand();
1.82 moko 154:
1.94 moko 155: memmove(felements+index+1, felements+index, (fsize-index) * sizeof(T));
1.82 moko 156:
157: felements[index]=element;
1.94 moko 158: fsize++;
1.82 moko 159: }
160:
1.80 moko 161: /// remove index-element
162: inline void remove(size_t index) {
163: assert(index<count());
1.94 moko 164: if (index<--fsize)
165: memmove(felements+index, felements+index+1, (fsize-index) * sizeof(T));
1.80 moko 166: }
167:
1.71 misha 168: inline T operator [](size_t index) const { return get(index); }
1.29 paf 169:
1.84 moko 170: inline void clear() {
1.94 moko 171: if(fsize)
1.102 moko 172: memset((void *)felements, 0, fsize * sizeof(T));
1.94 moko 173: fsize=0;
1.84 moko 174: }
175:
1.29 paf 176: /// iterate over all elements
1.59 paf 177: template<typename I> void for_each(void (*callback)(T, I), I info) const {
1.94 moko 178: T *last=felements+fsize;
1.60 paf 179: for(T *current=felements; current<last; current++)
180: callback(*current, info);
181: }
182:
183: /// iterate over all elements
1.68 paf 184: template<typename I> void for_each(bool (*callback)(T, I), I info) const {
1.94 moko 185: T *last=felements+fsize;
1.68 paf 186: for(T *current=felements; current<last; current++)
187: if(callback(*current, info))
188: return;
189: }
190:
191: /// iterate over all elements
1.60 paf 192: template<typename I> void for_each_ref(void (*callback)(T&, I), I info) {
1.94 moko 193: T *last=felements+fsize;
1.59 paf 194: for(T *current=felements; current<last; current++)
195: callback(*current, info);
196: }
1.49 paf 197:
1.59 paf 198: /// iterate over all elements until condition becomes true, return that element
199: template<typename I> T first_that(bool (*callback)(T, I), I info) const {
1.94 moko 200: T *last=felements+fsize;
1.59 paf 201: for(T *current=felements; current<last; current++)
202: if(callback(*current, info))
203: return *current;
1.1 paf 204:
1.59 paf 205: return T(0);
206: }
1.1 paf 207:
1.76 misha 208: inline T* ptr(size_t index){
209: return felements + index;
210: }
211:
1.59 paf 212: protected:
1.1 paf 213:
1.94 moko 214: inline bool is_full() {
215: return fsize == fallocated;
1.59 paf 216: }
1.88 moko 217:
1.93 moko 218: inline void expand() {
1.96 moko 219: resize(fallocated>0 ? fallocated+fallocated/2+2 : 3); // 3 is PAF default, confirmed by tests
1.93 moko 220: }
221:
1.94 moko 222: inline void fit(size_t index){
223: if(index >= fallocated)
1.99 moko 224: resize(max(fallocated+fallocated/4, index+1));
1.94 moko 225: }
226:
1.93 moko 227: void resize(size_t asize) {
1.71 misha 228: if(fallocated){
1.93 moko 229: felements=(T *)pa_realloc(felements, asize*sizeof(T));
230: fallocated=asize;
1.71 misha 231: } else {
1.93 moko 232: fallocated=asize;
233: felements=(T *)pa_malloc(asize*sizeof(T));
1.71 misha 234: }
1.1 paf 235: }
1.2 paf 236:
1.1 paf 237: private: //disabled
238:
1.59 paf 239: Array(const Array&) {}
1.12 paf 240: Array& operator = (const Array&) { return *this; }
1.42 parser 241: };
242:
1.92 moko 243:
1.91 moko 244: /// Commonly used, templated to work with any integer type
245:
246: template<typename T> char* pa_itoa(T n, T base=10){
247: char buf[MAX_NUMBER + 1];
248: char* pos=buf + MAX_NUMBER;
249: *pos='\0';
250:
251: bool negative=n < 0;
252: if (n < 0){
253: n=-n;
254: }
255:
256: do {
1.97 moko 257: *(--pos)=(char)(n % base) + '0';
1.91 moko 258: n/=base;
259: } while (n > 0);
260:
261: if (negative) {
262: *(--pos) = '-';
263: }
264: return pa_strdup(pos, buf + MAX_NUMBER - pos);
265: }
266:
267: template<typename T> char* pa_uitoa(T n, T base=10){
268: char buf[MAX_NUMBER + 1];
269: char* pos=buf + MAX_NUMBER;
270: *pos='\0';
271:
272: do {
1.97 moko 273: *(--pos)=(char)(n % base) + '0';
1.91 moko 274: n/=base;
275: } while (n > 0);
276:
277: return pa_strdup(pos, buf + MAX_NUMBER - pos);
278: }
279:
1.42 parser 280:
1.59 paf 281: /** Array iterator, usage:
282: @code
283: // Array<T> a;
1.89 moko 284: for(Array_iterator<T> i(a); i; ) {
1.59 paf 285: T& element=i.next();
286: ...
287: }
288: @endcode
289: */
290: template<typename T> class Array_iterator {
291:
292: const Array<T>& farray;
293: T *fcurrent;
294: T *flast;
295:
1.42 parser 296: public:
1.59 paf 297: Array_iterator(const Array<T>& aarray): farray(aarray) {
298: fcurrent=farray.felements;
1.94 moko 299: flast=farray.felements + farray.fsize;
1.42 parser 300: }
301:
302: /// there are still elements
1.90 moko 303: inline operator bool () {
304: return fcurrent < flast;
1.42 parser 305: }
306:
1.88 moko 307: /// returns the current element and advances the iterator
1.90 moko 308: inline T next() {
1.59 paf 309: return *(fcurrent++);
310: }
311:
1.88 moko 312: /// returns the current element
1.90 moko 313: inline T value() {
1.88 moko 314: return *(fcurrent);
315: }
316:
317: // returns the current index of the iterator
1.90 moko 318: inline size_t index() {
1.88 moko 319: return fcurrent - farray.felements;
320: }
1.101 moko 321: };
322:
323: // Slower array iterator for arrays that can be modified during iteration
324: template<typename T> class Array_robust_iterator {
325:
326: const Array<T>& farray;
327: size_t findex;
328:
329: public:
330: Array_robust_iterator(const Array<T>& aarray) : farray(aarray), findex(0) {}
331:
332: inline operator bool() {
333: return findex < farray.fsize;
334: }
335:
336: inline void next() {
337: findex++;
338: }
339:
340: inline T value() {
341: return farray.felements[findex];
342: }
343:
344: inline size_t index() {
345: return findex;
346: }
1.90 moko 347: };
348:
1.101 moko 349: // Robust as used for arrays that can be modified during iteration
1.90 moko 350: template<typename T> class Array_reverse_iterator {
351:
352: const Array<T>& farray;
1.101 moko 353: size_t findex;
1.90 moko 354:
355: public:
1.101 moko 356: Array_reverse_iterator(const Array<T>& aarray): farray(aarray), findex(aarray.fsize) {}
1.90 moko 357:
358: inline operator bool () {
1.101 moko 359: return (findex > 0) && (findex <= farray.fsize);
1.90 moko 360: }
361:
362: inline T prev() {
1.101 moko 363: return farray.felements[--findex];
1.90 moko 364: }
365:
366: inline size_t index() {
1.101 moko 367: return findex;
1.90 moko 368: }
1.59 paf 369: };
1.1 paf 370: #endif
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to pa_array.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / parser3 / src / include