1 |
/* |
2 |
* HT Editor |
3 |
* data.h |
4 |
* |
5 |
* Copyright (C) 2002, 2003 Stefan Weyergraf |
6 |
* Copyright (C) 2002, 2003 Sebastian Biallas (sb@biallas.net) |
7 |
* |
8 |
* This program is free software; you can redistribute it and/or modify |
9 |
* it under the terms of the GNU General Public License version 2 as |
10 |
* published by the Free Software Foundation. |
11 |
* |
12 |
* This program 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 this program; if not, write to the Free Software |
19 |
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. |
20 |
*/ |
21 |
|
22 |
#ifndef __DATA_H__ |
23 |
#define __DATA_H__ |
24 |
|
25 |
#define HAVE_HT_OBJECTS |
26 |
|
27 |
#include "system/types.h" |
28 |
|
29 |
#ifdef HAVE_HT_OBJECTS |
30 |
typedef unsigned long ObjectID; |
31 |
|
32 |
/* actually a str => bigendian-int */ |
33 |
/** used to define ObjectIDs */ |
34 |
#define MAGIC16(magic) (((uint16)magic[0]<<8) | (uint16)magic[1]) |
35 |
#define MAGIC32(magic) (((uint32)magic[0]<<24) | ((uint32)magic[1]<<16) | ((uint32)magic[2]<<8) | (uint32)magic[3]) |
36 |
|
37 |
/** No/invalid object */ |
38 |
#define OBJID_INVALID ((ObjectID)0) |
39 |
/** A placeholder object id */ |
40 |
#define OBJID_TEMP ((ObjectID)-1) |
41 |
|
42 |
#define OBJID_OBJECT MAGIC32("DAT\x00") |
43 |
|
44 |
#define OBJID_ARRAY MAGIC32("DAT\x10") |
45 |
#define OBJID_STACK MAGIC32("DAT\x11") |
46 |
|
47 |
#define OBJID_BINARY_TREE MAGIC32("DAT\x20") |
48 |
#define OBJID_AVL_TREE MAGIC32("DAT\x21") |
49 |
#define OBJID_SET MAGIC32("DAT\x22") |
50 |
|
51 |
#define OBJID_LINKED_LIST MAGIC32("DAT\x30") |
52 |
#define OBJID_QUEUE MAGIC32("DAT\x31") |
53 |
#define OBJID_DBL_LINKED_LIST MAGIC32("DAT\x32") |
54 |
|
55 |
#define OBJID_KEYVALUE MAGIC32("DAT\x40") |
56 |
#define OBJID_SINT MAGIC32("DAT\x41") |
57 |
#define OBJID_SINT64 MAGIC32("DAT\x42") |
58 |
#define OBJID_UINT MAGIC32("DAT\x43") |
59 |
#define OBJID_UINT64 MAGIC32("DAT\x44") |
60 |
#define OBJID_FLOAT MAGIC32("DAT\x45") |
61 |
|
62 |
#define OBJID_MEMAREA MAGIC32("DAT\x48") |
63 |
|
64 |
#define OBJID_STRING MAGIC32("DAT\x50") |
65 |
#define OBJID_ISTRING MAGIC32("DAT\x51") |
66 |
|
67 |
#define OBJID_AUTO_COMPARE MAGIC32("DAT\xc0") |
68 |
|
69 |
#endif |
70 |
|
71 |
/** |
72 |
* This is THE base class. |
73 |
*/ |
74 |
class Object { |
75 |
public: |
76 |
Object() {}; |
77 |
virtual ~Object() {}; |
78 |
void init() {}; |
79 |
virtual void done() {}; |
80 |
/* new */ |
81 |
|
82 |
/** |
83 |
* Standard object duplicator. |
84 |
* @returns copy of object |
85 |
*/ |
86 |
virtual Object * clone() const; |
87 |
/** |
88 |
* Standard Object comparator. |
89 |
* @param obj object to compare to |
90 |
* @returns 0 for equality, negative number if |this<obj| and positive number if |this>obj| |
91 |
*/ |
92 |
virtual int compareTo(const Object *obj) const; |
93 |
/** |
94 |
* Stringify object. |
95 |
* Stringify object in string-buffer <i>s</i>. Never writes more than |
96 |
* <i>maxlen</i> characters to <i>s</i>. If <i>maxlen</i> is > 0, a |
97 |
* trailing zero-character is written. |
98 |
* |
99 |
* @param s pointer to buffer that receives object stringification |
100 |
* @param maxlen size of buffer that receives object stringification |
101 |
* @returns number of characters written to <i>s</i>, not including the trailing zero |
102 |
*/ |
103 |
virtual int toString(char *buf, int buflen) const; |
104 |
#ifdef HAVE_HT_OBJECTS |
105 |
/** |
106 |
* Standard Object idle function. |
107 |
* Overwrite and register with htidle.cc::register_idle() |
108 |
* (FIXME) |
109 |
* |
110 |
* @returns true if working, false if really idle |
111 |
*/ |
112 |
virtual bool idle(); |
113 |
/** |
114 |
* @returns true if <i>this</i> is an object or derived from an object of type <i>id</i>. |
115 |
*/ |
116 |
virtual bool instanceOf(ObjectID id) const; |
117 |
/** |
118 |
* @returns true if <i>this</i> is an object or derived from an object of the same type as <i>obj</i>. |
119 |
*/ |
120 |
bool instanceOf(Object *obj) const; |
121 |
/** |
122 |
* @returns unique object id. |
123 |
*/ |
124 |
virtual ObjectID getObjectID() const; |
125 |
#endif |
126 |
}; |
127 |
|
128 |
typedef int (*Comparator)(const Object *a, const Object *b); |
129 |
|
130 |
int autoCompare(const Object *a, const Object *b); |
131 |
|
132 |
typedef void* ObjHandle; |
133 |
#define InvObjHandle NULL |
134 |
#define InvIdx ((uint)-1) |
135 |
|
136 |
/** |
137 |
* An Enumerator. |
138 |
*/ |
139 |
class Enumerator: public Object { |
140 |
public: |
141 |
Enumerator(); |
142 |
/* extends Object */ |
143 |
virtual Enumerator * clone() const = 0; |
144 |
virtual int toString(char *buf, int buflen) const; |
145 |
/* new */ |
146 |
|
147 |
/** |
148 |
* Count elements. |
149 |
* |
150 |
* @returns number of objects contained in this structure |
151 |
* @throws NotImplementedException if counting of elements is not supported |
152 |
*/ |
153 |
virtual uint count() const = 0; |
154 |
|
155 |
/** |
156 |
* Compare objects. |
157 |
* Compare objects <i>a</i> and <i>b</i> and determine their (logical) |
158 |
* linear order. |
159 |
* |
160 |
* @param a object a |
161 |
* @param b object b |
162 |
* @returns 0 if <i>a</i> equals <i>b</i>, |
163 |
* a value >0 if <i>a</i> is greater than <i>b</i> and |
164 |
* a value <0 if <i>a</i> is less than <i>b</i> |
165 |
*/ |
166 |
virtual int compareObjects(const Object *a, const Object *b) const = 0; |
167 |
/** |
168 |
* Test if contained. |
169 |
* Test if an object like <i>obj</i> is contained in this structure |
170 |
* |
171 |
* @param obj signature of object to find |
172 |
* @returns true if an object like <i>obj</i> is contained, false otherwise |
173 |
*/ |
174 |
inline bool contains(const Object *obj) const |
175 |
{ |
176 |
return find(obj) != InvObjHandle; |
177 |
} |
178 |
/** |
179 |
* Test if empty. |
180 |
* @returns true if empty |
181 |
*/ |
182 |
inline bool isEmpty() const |
183 |
{ |
184 |
return count() == 0; |
185 |
} |
186 |
/** |
187 |
* Find equal object. |
188 |
* Find first object equaling <i>obj</i> in this structure |
189 |
* and if found return it's object handle. |
190 |
* |
191 |
* @param obj signature of object to find |
192 |
* @returns object handle of found object or <i>InvObjHandle</i> if not found |
193 |
*/ |
194 |
virtual ObjHandle find(const Object *obj) const; |
195 |
/** |
196 |
* Find greater-or-equal object. |
197 |
* Find first object being greater or equal compared to <i>obj</i> in this structure |
198 |
* and if found return it's object handle. |
199 |
* |
200 |
* @param obj signature of object to find |
201 |
* @returns object handle of found object or <i>InvObjHandle</i> if not found |
202 |
*/ |
203 |
virtual ObjHandle findGE(const Object *obj) const; |
204 |
/** |
205 |
* Find less-or-equal object. |
206 |
* Find first object being less or equal compared to <i>obj</i> in this structure |
207 |
* and if found return it's object handle. |
208 |
* |
209 |
* @param obj signature of object to find |
210 |
* @returns object handle of found object or <i>InvObjHandle</i> if not found |
211 |
*/ |
212 |
virtual ObjHandle findLE(const Object *obj) const; |
213 |
/** |
214 |
* Find object's handle by index. |
215 |
* |
216 |
* @param i index of object to find |
217 |
* @returns object handle of found object or <i>InvObjHandle</i> if not found |
218 |
*/ |
219 |
virtual ObjHandle findByIdx(int i) const = 0; |
220 |
/** |
221 |
* Find (logically) last element's object handle. |
222 |
* |
223 |
* @returns object handle of the last element or <i>InvObjHandle</i> |
224 |
* if the structure is empty |
225 |
*/ |
226 |
virtual ObjHandle findLast() const = 0; |
227 |
/** |
228 |
* Find (logically) previous element's object handle. |
229 |
* Find logically previous element (predecessor) of the object identified |
230 |
* by <i>h</i>. Predecessor of "the invalid object" is the last element |
231 |
* in this structure by definition. (ie. <i>findPrev(InvObjHandle) := |
232 |
* findLast()</i>). |
233 |
* |
234 |
* @param h object handle to find a predecessor to |
235 |
* @returns object handle of predecessor or <i>InvObjHandle</i> if <i>h</i> |
236 |
* identifies the first element. |
237 |
*/ |
238 |
virtual ObjHandle findPrev(ObjHandle h) const = 0; |
239 |
/** |
240 |
* Find (logically) first element's object handle. |
241 |
* |
242 |
* @returns object handle of the first element or <i>InvObjHandle</i> |
243 |
* if this structure is empty |
244 |
*/ |
245 |
virtual ObjHandle findFirst() const = 0; |
246 |
/** |
247 |
* Find (logically) next element's object handle. |
248 |
* Find logically next element (successor) of the object, identified |
249 |
* by <i>h</i>. Successor of "the invalid object" is the first element |
250 |
* in this structure by definition. (ie. <i>findNext(InvObjHandle) := |
251 |
* findFirst()</i>). |
252 |
* |
253 |
* @param h object handle to find a successor to |
254 |
* @returns object handle of successor or <i>InvObjHandle</i> if <i>h</i> |
255 |
* identifies the last element. |
256 |
*/ |
257 |
virtual ObjHandle findNext(ObjHandle h) const = 0; |
258 |
/** |
259 |
* Get object pointer from object handle. |
260 |
* |
261 |
* @param h object handle |
262 |
* @returns object pointer if <i>h</i> is valid, <i>NULL</i> otherwise |
263 |
*/ |
264 |
virtual Object * get(ObjHandle h) const = 0; |
265 |
/** |
266 |
* Get object's index from its handle. |
267 |
* |
268 |
* @param h object handle of object |
269 |
* @returns index of object if <i>h</i> is valid, <i>InvIdx</i> otherwise. |
270 |
*/ |
271 |
virtual uint getObjIdx(ObjHandle h) const = 0; |
272 |
/** |
273 |
* Get element by index. |
274 |
* Get the element with index <i>idx</i> (if possible). |
275 |
* |
276 |
* @param idx index of element to get |
277 |
* @returns pointer to the requested element or <i>NULL</i> if <i>idx</i> |
278 |
* is invalid. |
279 |
*/ |
280 |
Object * operator [] (int idx) const; |
281 |
}; |
282 |
|
283 |
#define foreach(XTYPE, X, E, code...)\ |
284 |
for (ObjHandle temp0815 = (E).findFirst(); temp0815 != InvObjHandle;) {\ |
285 |
XTYPE *X = (XTYPE*)(E).get(temp0815); \ |
286 |
temp0815 = (E).findNext(temp0815); \ |
287 |
{code;} \ |
288 |
} |
289 |
|
290 |
#define foreachbwd(XTYPE, X, E, code...)\ |
291 |
for (ObjHandle temp0815 = (E).findLast(); temp0815 != InvObjHandle;) {\ |
292 |
XTYPE *X = (XTYPE*)(E).get(temp0815); \ |
293 |
temp0815 = (E).findPrev(temp0815); \ |
294 |
{code;} \ |
295 |
} |
296 |
|
297 |
#define firstThat(XTYPE, X, E, condition) \ |
298 |
{ \ |
299 |
Object *Y = NULL; \ |
300 |
foreach(XTYPE, X, E, \ |
301 |
if (condition) { \ |
302 |
Y = X; \ |
303 |
break; \ |
304 |
} \ |
305 |
) \ |
306 |
X = Y; \ |
307 |
} |
308 |
|
309 |
#define lastThat(XTYPE, X, E, condition) \ |
310 |
{ \ |
311 |
Object *Y = NULL; \ |
312 |
foreachbwd(XTYPE, X, E, \ |
313 |
if (condition) { \ |
314 |
Y = X; \ |
315 |
break; \ |
316 |
} \ |
317 |
) \ |
318 |
X = Y; \ |
319 |
} |
320 |
|
321 |
/** |
322 |
* A Container. |
323 |
*/ |
324 |
class Container: public Enumerator { |
325 |
protected: |
326 |
#ifdef HAVE_HT_OBJECTS |
327 |
ObjectID hom_objid; |
328 |
#endif |
329 |
|
330 |
virtual void notifyInsertOrSet(const Object *o); |
331 |
public: |
332 |
Container(); |
333 |
|
334 |
virtual Container * clone() const = 0; |
335 |
/* new */ |
336 |
|
337 |
/** |
338 |
* Delete all objects. (ie. remove and free all objects) |
339 |
*/ |
340 |
virtual void delAll() = 0; |
341 |
/** |
342 |
* Delete object. |
343 |
* Delete (ie. remove and free) first object like <i>sig</i> in |
344 |
* this structure (if possible). |
345 |
* |
346 |
* @param sig signature of object to delete (may be inserted in the structure) |
347 |
* @returns true if an object has been deleted, false otherwise |
348 |
*/ |
349 |
virtual bool delObj(Object *sig); |
350 |
/** |
351 |
* Delete object. |
352 |
* Delete (ie. remove and free) object identified by <i>h</i>. |
353 |
* |
354 |
* @param h object handle of the object to delete |
355 |
* @returns true if the object has been deleted, false otherwise |
356 |
*/ |
357 |
virtual bool del(ObjHandle h) = 0; |
358 |
/** |
359 |
* Find or insert object. |
360 |
* Find first object like <i>obj</i> and if that fails, insert <i>obj</i>. |
361 |
* Ie. after call of this function it is guaranteed that <i>contains(obj)</i>. |
362 |
* |
363 |
* @param obj object to find similar one to or object to insert |
364 |
* @param inserted indicates if <i>obj</i> has been inserted |
365 |
* @returns object handle of existing or inserted object (never <i>InvObjHandle</i>) |
366 |
*/ |
367 |
virtual ObjHandle findOrInsert(Object *obj, bool &inserted); |
368 |
/** |
369 |
* Insert object. |
370 |
* Insert <i>obj</i> |
371 |
* |
372 |
* @param obj object to insert |
373 |
* @returns object handle of inserted object (never <i>InvObjHandle</i>) |
374 |
*/ |
375 |
virtual ObjHandle insert(Object *obj) = 0; |
376 |
/** |
377 |
* Remove object. |
378 |
* Remove first object like <i>sig</i> from this structure. |
379 |
* Returned object must be freed explicitly. |
380 |
* |
381 |
* @param sig signature of object to remove |
382 |
* @returns removed object |
383 |
*/ |
384 |
virtual Object * removeObj(const Object *sig); |
385 |
/** |
386 |
* Remove object. |
387 |
* Remove object identified by <i>h</i>. |
388 |
* Returned object must be freed explicitly. |
389 |
* |
390 |
* @param h object handle of object to remove |
391 |
* @returns removed object |
392 |
*/ |
393 |
virtual Object * remove(ObjHandle h) = 0; |
394 |
/** |
395 |
* Insert object. (operator-form) |
396 |
*/ |
397 |
inline ObjHandle operator += (Object *obj) { return insert(obj); } |
398 |
/** |
399 |
* Delete object. (operator-form) |
400 |
*/ |
401 |
inline bool operator -= (ObjHandle h) { return del(h); } |
402 |
/** |
403 |
* Delete object. (operator-form) |
404 |
*/ |
405 |
inline bool operator -= (Object *sig) { return (*this -= find(sig)); } |
406 |
/** |
407 |
* Delete object by index. |
408 |
* |
409 |
* @param idx index of object to delete |
410 |
* @returns true if the object has been deleted, false otherwise |
411 |
*/ |
412 |
inline bool operator -= (int idx) { return (*this -= findByIdx(idx)); } |
413 |
}; |
414 |
|
415 |
/** |
416 |
* An abstract list |
417 |
*/ |
418 |
class List: public Container { |
419 |
public: |
420 |
List(); |
421 |
virtual List * clone() const = 0; |
422 |
/* new */ |
423 |
|
424 |
/** |
425 |
* Insert object at position. |
426 |
* Insert object <i>obj</i> at the position specified by <i>h</i>. |
427 |
* if <i>h</i> does not specify a valid object handle (eg. InvObjHandle), |
428 |
* this function works like <i>insert(obj)</i>. |
429 |
* |
430 |
* @param h position to insert object at |
431 |
* @param obj pointer to object to insert |
432 |
* @returns true on success, false otherwise |
433 |
*/ |
434 |
virtual void insertAt(ObjHandle h, Object *obj) = 0; |
435 |
/** |
436 |
* Move element. |
437 |
* Move element from position <i>from</i> to position <i>to</i>. |
438 |
* |
439 |
* @param from position of element to move |
440 |
* @param to position to move element to |
441 |
* @returns true on success, false otherwise |
442 |
*/ |
443 |
virtual bool moveTo(ObjHandle from, ObjHandle to) = 0; |
444 |
/** |
445 |
* Prepend object. |
446 |
* Prepend object <i>obj</i>. |
447 |
* |
448 |
* @param obj pointer to object to prepend |
449 |
* @returns object handle of inserted object (never <i>InvObjHandle</i>) |
450 |
*/ |
451 |
inline ObjHandle prepend(Object *obj) |
452 |
{ |
453 |
insertAt(findFirst(), obj); |
454 |
return findFirst(); |
455 |
} |
456 |
/** |
457 |
* Set element. |
458 |
* Replace element at position <i>h</i> with object <i>obj</i> |
459 |
* and delete replaced object. |
460 |
* |
461 |
* @param h object handle of element to replace |
462 |
* @param obj object to replace element |
463 |
* @returns true on success, false otherwise |
464 |
*/ |
465 |
virtual bool set(ObjHandle h, Object *obj) = 0; |
466 |
/** |
467 |
* Force: Set element by index. |
468 |
* Set element at index <i>i</i> to object <i>obj</i> |
469 |
* and delete object previously located at this index if the index is valid. |
470 |
* If the index <i>i</i> does not specify a valid list-index, |
471 |
* the list is extended, so that <i>obj</i> will be the last element |
472 |
* and the newly created entries in the list will be <i>NULL</i>s. |
473 |
* |
474 |
* @param i index at which to set |
475 |
* @param obj object to set |
476 |
*/ |
477 |
virtual void forceSetByIdx(int idx, Object *obj) = 0; |
478 |
/** |
479 |
* Swap two element. |
480 |
* Swap element at position <i>h</i> with element at position <i>i</i>. |
481 |
* |
482 |
* @param h handle of one object |
483 |
* @param i handle of the other object |
484 |
* @returns true on success, false otherwise |
485 |
*/ |
486 |
virtual bool swap(ObjHandle h, ObjHandle i) = 0; |
487 |
}; |
488 |
|
489 |
#define ARRAY_CONSTR_ALLOC_DEFAULT 4 |
490 |
|
491 |
/** |
492 |
* An array |
493 |
*/ |
494 |
class Array: public List { |
495 |
private: |
496 |
bool own_objects; |
497 |
uint ecount; |
498 |
uint acount; |
499 |
Object **elems; |
500 |
|
501 |
virtual int calcNewBufferSize(int curbufsize, int min_newbufsize) const; |
502 |
virtual void checkShrink(); |
503 |
virtual void freeObj(Object *obj); |
504 |
void prepareWriteAccess(int i); |
505 |
void realloc(int n); |
506 |
inline bool validHandle(ObjHandle h) const; |
507 |
inline uint handleToNative(ObjHandle h) const; |
508 |
inline ObjHandle nativeToHandle(uint i) const; |
509 |
public: |
510 |
Array(bool own_objects, int prealloc = ARRAY_CONSTR_ALLOC_DEFAULT); |
511 |
virtual ~Array(); |
512 |
/* extends Object */ |
513 |
virtual Array * clone() const; |
514 |
#ifdef HAVE_HT_OBJECTS |
515 |
virtual bool instanceOf(ObjectID id) const; |
516 |
virtual ObjectID getObjectID() const; |
517 |
#endif |
518 |
/* extends Enumerator */ |
519 |
virtual uint count() const; |
520 |
virtual int compareObjects(const Object *a, const Object *b) const; |
521 |
virtual ObjHandle findByIdx(int i) const; |
522 |
virtual ObjHandle findFirst() const; |
523 |
virtual ObjHandle findLast() const; |
524 |
virtual ObjHandle findNext(ObjHandle h) const; |
525 |
virtual ObjHandle findPrev(ObjHandle h) const; |
526 |
virtual Object * get(ObjHandle h) const; |
527 |
virtual uint getObjIdx(ObjHandle h) const; |
528 |
/* extends Container */ |
529 |
virtual void delAll(); |
530 |
virtual bool del(ObjHandle h); |
531 |
virtual ObjHandle insert(Object *obj); |
532 |
virtual Object * remove(ObjHandle h); |
533 |
/* extends List */ |
534 |
virtual void forceSetByIdx(int idx, Object *obj); |
535 |
virtual void insertAt(ObjHandle h, Object *obj); |
536 |
virtual bool moveTo(ObjHandle from, ObjHandle to); |
537 |
virtual bool set(ObjHandle h, Object *obj); |
538 |
virtual bool swap(ObjHandle h, ObjHandle i); |
539 |
/* new */ |
540 |
inline Object * operator [](int aIndex) const |
541 |
{ |
542 |
return get(findByIdx(aIndex)); |
543 |
} |
544 |
}; |
545 |
|
546 |
/** |
547 |
* A stack |
548 |
*/ |
549 |
class Stack: public Array { |
550 |
public: |
551 |
Stack(bool own_objects); |
552 |
/* new */ |
553 |
virtual Object * pop(); |
554 |
virtual void push(Object *obj); |
555 |
#ifdef HAVE_HT_OBJECTS |
556 |
virtual bool instanceOf(ObjectID id) const; |
557 |
virtual ObjectID getObjectID() const; |
558 |
#endif |
559 |
}; |
560 |
|
561 |
/** |
562 |
* LinkedList's node structure |
563 |
*/ |
564 |
struct LinkedListNode { |
565 |
Object *obj; |
566 |
LinkedListNode *next; |
567 |
}; |
568 |
|
569 |
/** |
570 |
* A (simply) linked list |
571 |
*/ |
572 |
class LinkedList: public List { |
573 |
private: |
574 |
bool own_objects; |
575 |
uint ecount; |
576 |
LinkedListNode *first, *last; |
577 |
|
578 |
virtual LinkedListNode *allocNode() const; |
579 |
virtual void deleteNode(LinkedListNode *node) const; |
580 |
virtual void freeObj(Object *obj) const; |
581 |
inline bool validHandle(ObjHandle h) const; |
582 |
inline LinkedListNode *handleToNative(ObjHandle h) const; |
583 |
inline ObjHandle nativeToHandle(LinkedListNode *n) const; |
584 |
public: |
585 |
LinkedList(bool own_objects); |
586 |
virtual ~LinkedList(); |
587 |
/* extends Object */ |
588 |
virtual LinkedList * clone() const; |
589 |
#ifdef HAVE_HT_OBJECTS |
590 |
virtual bool instanceOf(ObjectID id) const; |
591 |
virtual ObjectID getObjectID() const; |
592 |
#endif |
593 |
/* extends Enumerator */ |
594 |
virtual uint count() const; |
595 |
virtual int compareObjects(const Object *a, const Object *b) const; |
596 |
virtual ObjHandle findByIdx(int i) const; |
597 |
virtual ObjHandle findFirst() const; |
598 |
virtual ObjHandle findLast() const; |
599 |
virtual ObjHandle findNext(ObjHandle h) const; |
600 |
virtual ObjHandle findPrev(ObjHandle h) const; |
601 |
virtual Object * get(ObjHandle h) const; |
602 |
virtual uint getObjIdx(ObjHandle h) const; |
603 |
/* extends Container */ |
604 |
virtual void delAll(); |
605 |
virtual bool del(ObjHandle h); |
606 |
virtual ObjHandle insert(Object *obj); |
607 |
virtual Object * remove(ObjHandle h); |
608 |
/* extends List */ |
609 |
virtual void forceSetByIdx(int idx, Object *obj); |
610 |
virtual void insertAt(ObjHandle h, Object *obj); |
611 |
virtual bool moveTo(ObjHandle from, ObjHandle to); |
612 |
virtual bool set(ObjHandle h, Object *obj); |
613 |
virtual bool swap(ObjHandle h, ObjHandle i); |
614 |
}; |
615 |
|
616 |
/* |
617 |
struct DblLinkedNode: public LinkedListNode { |
618 |
LinkedListNode *prev; |
619 |
}; |
620 |
*/ |
621 |
|
622 |
/** |
623 |
* A queue |
624 |
*/ |
625 |
class Queue: public LinkedList { |
626 |
public: |
627 |
Queue(bool own_objects); |
628 |
/* new */ |
629 |
|
630 |
/** |
631 |
* De-queue element. |
632 |
* Remove and return next element of the queue. |
633 |
* |
634 |
* @returns next element of the queue |
635 |
*/ |
636 |
inline Object * deQueue() |
637 |
{ |
638 |
return remove(findFirst()); |
639 |
} |
640 |
|
641 |
/** |
642 |
* En-queue element. |
643 |
* Append element <i>obj</i> to the queue. |
644 |
* |
645 |
* @param obj pointer to object to en-queue |
646 |
*/ |
647 |
inline void enQueue(Object *obj) |
648 |
{ |
649 |
insert(obj); |
650 |
} |
651 |
|
652 |
#ifdef HAVE_HT_OBJECTS |
653 |
virtual bool instanceOf(ObjectID id) const; |
654 |
virtual ObjectID getObjectID() const; |
655 |
#endif |
656 |
}; |
657 |
|
658 |
/** |
659 |
* BinaryTree's node structure |
660 |
*/ |
661 |
struct BinTreeNode { |
662 |
Object *key; |
663 |
BinTreeNode *left, *right; |
664 |
int unbalance; |
665 |
}; |
666 |
|
667 |
/** |
668 |
* A simple binary tree |
669 |
*/ |
670 |
class BinaryTree: public Container { |
671 |
protected: |
672 |
bool own_objects; |
673 |
uint ecount; |
674 |
BinTreeNode *root; |
675 |
Comparator compare; |
676 |
|
677 |
BinTreeNode * allocNode() const; |
678 |
void cloneR(BinTreeNode *node); |
679 |
virtual void deleteNode(BinTreeNode *node) const; |
680 |
BinTreeNode * findNode(BinTreeNode *node, const Object *obj) const; |
681 |
BinTreeNode * findNodeG(BinTreeNode *node, const Object *obj) const; |
682 |
BinTreeNode * findNodeGE(BinTreeNode *node, const Object *obj) const; |
683 |
BinTreeNode * findNodeL(BinTreeNode *node, const Object *obj) const; |
684 |
BinTreeNode * findNodeLE(BinTreeNode *node, const Object *obj) const; |
685 |
BinTreeNode ** findNodePtr(BinTreeNode **nodeptr, const Object *obj) const; |
686 |
void freeAll(BinTreeNode *n); |
687 |
void freeObj(Object *obj) const; |
688 |
BinTreeNode * getLeftmost(BinTreeNode *node) const; |
689 |
BinTreeNode * getRightmost(BinTreeNode *node) const; |
690 |
BinTreeNode ** getLeftmostPtr(BinTreeNode **nodeptr) const; |
691 |
BinTreeNode ** getRightmostPtr(BinTreeNode **nodeptr) const; |
692 |
ObjHandle findByIdxR(BinTreeNode *n, int &i) const; |
693 |
ObjHandle insertR(BinTreeNode *&node, Object *obj); |
694 |
virtual void setNodeIdentity(BinTreeNode *node, BinTreeNode *newident); |
695 |
inline bool validHandle(ObjHandle h) const { return (h != InvObjHandle); } |
696 |
inline BinTreeNode * handleToNative(ObjHandle h) const { return (BinTreeNode*)h; } |
697 |
inline ObjHandle nativeToHandle(BinTreeNode *n) const { return (ObjHandle*)n; } |
698 |
public: |
699 |
BinaryTree(bool own_objects, Comparator comparator = autoCompare); |
700 |
virtual ~BinaryTree(); |
701 |
/* extends Object */ |
702 |
virtual BinaryTree * clone() const; |
703 |
virtual ObjectID getObjectID() const; |
704 |
/* extends Enumerator */ |
705 |
virtual void delAll(); |
706 |
virtual uint count() const; |
707 |
virtual int compareObjects(const Object *a, const Object *b) const; |
708 |
virtual ObjHandle find(const Object *obj) const; |
709 |
virtual ObjHandle findG(const Object *obj) const; |
710 |
virtual ObjHandle findGE(const Object *obj) const; |
711 |
virtual ObjHandle findL(const Object *obj) const; |
712 |
virtual ObjHandle findLE(const Object *obj) const; |
713 |
virtual ObjHandle findByIdx(int i) const; |
714 |
virtual ObjHandle findFirst() const; |
715 |
virtual ObjHandle findLast() const; |
716 |
virtual ObjHandle findNext(ObjHandle h) const; |
717 |
virtual ObjHandle findPrev(ObjHandle h) const; |
718 |
virtual Object * get(ObjHandle h) const; |
719 |
virtual uint getObjIdx(ObjHandle h) const; |
720 |
/* extends Container */ |
721 |
virtual bool del(ObjHandle h); |
722 |
virtual ObjHandle insert(Object *obj); |
723 |
virtual Object * remove(ObjHandle h); |
724 |
}; |
725 |
|
726 |
|
727 |
/** |
728 |
* A height-balanced binary tree (AVL) |
729 |
*/ |
730 |
class AVLTree: public BinaryTree { |
731 |
private: |
732 |
void cloneR(BinTreeNode *node); |
733 |
BinTreeNode * removeR(Object *key, BinTreeNode *&root, int &change, int cmp); |
734 |
public: |
735 |
AVLTree(bool own_objects, Comparator comparator = autoCompare); |
736 |
|
737 |
void debugOut(); |
738 |
bool expensiveCheck() const; |
739 |
/* extends Object */ |
740 |
virtual AVLTree * clone() const; |
741 |
virtual ObjectID getObjectID() const; |
742 |
/* extends Container */ |
743 |
virtual ObjHandle insert(Object *obj); |
744 |
virtual Object * remove(ObjHandle h); |
745 |
}; |
746 |
|
747 |
/** |
748 |
* A finite set |
749 |
*/ |
750 |
class Set: public AVLTree { |
751 |
public: |
752 |
Set(bool own_objects); |
753 |
/* new */ |
754 |
void intersectWith(Set *b); |
755 |
void unionWith(Set *b); |
756 |
inline bool operator &(Object *obj) const |
757 |
{ |
758 |
return contains(obj); |
759 |
} |
760 |
|
761 |
#ifdef HAVE_HT_OBJECTS |
762 |
virtual bool instanceOf(ObjectID id) const; |
763 |
virtual ObjectID getObjectID() const; |
764 |
#endif |
765 |
}; |
766 |
|
767 |
/** |
768 |
* Maintains a key-value pair for easy inserting objects with "simple" keys |
769 |
* into Containers. |
770 |
* Key and Value will be <code>delete</code>d in the destructor. |
771 |
*/ |
772 |
class KeyValue: public Object { |
773 |
public: |
774 |
Object *mKey; |
775 |
Object *mValue; |
776 |
|
777 |
KeyValue(Object *aKey, Object *aValue); |
778 |
virtual ~KeyValue(); |
779 |
|
780 |
virtual KeyValue * clone() const; |
781 |
virtual int compareTo(const Object *obj) const; |
782 |
virtual int toString(char *buf, int buflen) const; |
783 |
#ifdef HAVE_HT_OBJECTS |
784 |
virtual bool instanceOf(ObjectID id) const; |
785 |
virtual ObjectID getObjectID() const; |
786 |
#endif |
787 |
}; |
788 |
|
789 |
/** |
790 |
* A signed Integer |
791 |
*/ |
792 |
class SInt: public Object { |
793 |
public: |
794 |
signed int value; |
795 |
|
796 |
SInt(signed int i); |
797 |
/* extends Object */ |
798 |
virtual SInt * clone() const; |
799 |
virtual int compareTo(const Object *obj) const; |
800 |
virtual int toString(char *buf, int buflen) const; |
801 |
#ifdef HAVE_HT_OBJECTS |
802 |
virtual bool instanceOf(ObjectID id) const; |
803 |
virtual ObjectID getObjectID() const; |
804 |
#endif |
805 |
}; |
806 |
|
807 |
typedef SInt Integer; |
808 |
|
809 |
/** |
810 |
* A signed Integer (64-bit) |
811 |
*/ |
812 |
class SInt64: public Object { |
813 |
public: |
814 |
sint64 value; |
815 |
|
816 |
SInt64(sint64 i); |
817 |
/* extends Object */ |
818 |
virtual SInt64 * clone() const; |
819 |
virtual int compareTo(const Object *obj) const; |
820 |
virtual int toString(char *buf, int buflen) const; |
821 |
#ifdef HAVE_HT_OBJECTS |
822 |
virtual bool instanceOf(ObjectID id) const; |
823 |
virtual ObjectID getObjectID() const; |
824 |
#endif |
825 |
}; |
826 |
|
827 |
/** |
828 |
* An unsigned Integer |
829 |
*/ |
830 |
class UInt: public Object { |
831 |
public: |
832 |
unsigned int value; |
833 |
|
834 |
UInt(unsigned int i); |
835 |
/* extends Object */ |
836 |
virtual UInt * clone() const; |
837 |
virtual int compareTo(const Object *obj) const; |
838 |
virtual int toString(char *buf, int buflen) const; |
839 |
#ifdef HAVE_HT_OBJECTS |
840 |
virtual bool instanceOf(ObjectID id) const; |
841 |
virtual ObjectID getObjectID() const; |
842 |
#endif |
843 |
}; |
844 |
|
845 |
/** |
846 |
* An unsigned Integer (64-bit) |
847 |
*/ |
848 |
class UInt64: public Object { |
849 |
public: |
850 |
uint64 value; |
851 |
|
852 |
UInt64(uint64 i); |
853 |
/* extends Object */ |
854 |
virtual UInt64 * clone() const; |
855 |
virtual int compareTo(const Object *obj) const; |
856 |
virtual int toString(char *buf, int buflen) const; |
857 |
#ifdef HAVE_HT_OBJECTS |
858 |
virtual bool instanceOf(ObjectID id) const; |
859 |
virtual ObjectID getObjectID() const; |
860 |
#endif |
861 |
}; |
862 |
|
863 |
/** |
864 |
* A floating-point number (FIXME: no portable storage yet) |
865 |
*/ |
866 |
class Float: public Object { |
867 |
public: |
868 |
double value; |
869 |
|
870 |
Float(double d); |
871 |
/* extends Object */ |
872 |
virtual Float * clone() const; |
873 |
virtual int compareTo(const Object *obj) const; |
874 |
virtual int toString(char *buf, int buflen) const; |
875 |
#ifdef HAVE_HT_OBJECTS |
876 |
virtual bool instanceOf(ObjectID id) const; |
877 |
virtual ObjectID getObjectID() const; |
878 |
#endif |
879 |
}; |
880 |
|
881 |
/** |
882 |
* A pointer. Cannot be stored. |
883 |
*/ |
884 |
class Pointer: public Object { |
885 |
public: |
886 |
void *value; |
887 |
|
888 |
Pointer(void *p); |
889 |
}; |
890 |
|
891 |
/** |
892 |
* A memory area. |
893 |
*/ |
894 |
class MemArea: public Object { |
895 |
private: |
896 |
bool duplicate; |
897 |
public: |
898 |
void *ptr; |
899 |
uint size; |
900 |
|
901 |
MemArea(const void *p, uint size, bool duplicate = false); |
902 |
~MemArea(); |
903 |
/* extends Object */ |
904 |
virtual MemArea * clone() const; |
905 |
virtual int compareTo(const Object *obj) const; |
906 |
virtual int toString(char *buf, int buflen) const; |
907 |
#ifdef HAVE_HT_OBJECTS |
908 |
virtual bool instanceOf(ObjectID id) const; |
909 |
virtual ObjectID getObjectID() const; |
910 |
#endif |
911 |
}; |
912 |
|
913 |
/* |
914 |
* sorter |
915 |
*/ |
916 |
bool quickSort(List &l); |
917 |
|
918 |
/* |
919 |
* Module Init/Done |
920 |
*/ |
921 |
|
922 |
bool initData(); |
923 |
void doneData(); |
924 |
|
925 |
#endif /* __DATA_H__ */ |