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