/[pearpc]/src/tools/data.cc
This is repository of my old source code which isn't updated any more. Go to git.rot13.org for current projects!
ViewVC logotype

Contents of /src/tools/data.cc

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1 - (show annotations)
Wed Sep 5 17:11:21 2007 UTC (16 years, 6 months ago) by dpavlin
File size: 34590 byte(s)
import upstream CVS
1 /*
2 * HT Editor
3 * data.cc
4 *
5 * Copyright (C) 2002 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 #include <new>
23 #include <cstring>
24 #include <cstdlib>
25 #include <typeinfo>
26
27 #include "data.h"
28
29 #ifdef HAVE_HT_OBJECTS
30 #include "atom.h"
31 #include "except.h"
32 #endif
33
34 #include "data.h"
35 #include "debug.h"
36 #include "snprintf.h"
37 #include "stream.h"
38
39 int autoCompare(const Object *a, const Object *b)
40 {
41 #ifdef HAVE_HT_OBJECTS
42 // FIXME: better use instanceOf
43 // SB: warum auskommentieren?
44 // SW: weil nicht so gute logik
45 // wie gesagt FIXME, aber bin mir unsicher wie genau
46
47 /* uint ida = a->getObjectID();
48 uint idb = b->getObjectID();
49 if (ida != idb) return ida-idb;*/
50 #endif
51 return a->compareTo(b);
52 }
53
54 /*
55 * Class Object
56 */
57
58 int Object::compareTo(const Object *obj) const
59 {
60 #ifdef HAVE_HT_OBJECTS
61 throw NotImplementedException(HERE);
62 #else
63 return 1;
64 #endif
65 }
66
67 int Object::toString(char *buf, int buflen) const
68 {
69 #ifdef HAVE_HT_OBJECTS
70 ObjectID oid = getObjectID();
71 unsigned char c[16];
72 int l = 4;
73 c[0] = (oid >> 24) & 0xff;
74 c[1] = (oid >> 16) & 0xff;
75 c[2] = (oid >> 8) & 0xff;
76 c[3] = oid & 0xff;
77 for (int i=0; i<l; i++) {
78 if ((c[i]<32) || (c[i]>127)) {
79 c[i+1] = "0123456789abcdef"[c[i]>>4];
80 c[i+2] = "0123456789abcdef"[c[i]&0xf];
81 c[i] = '\\';
82 l += 2;
83 }
84 }
85 c[l] = 0;
86 return ht_snprintf(buf, buflen, "Object-%s", c);
87 #else
88 return ht_snprintf(buf, buflen, "Object");
89 #endif
90 }
91
92 Object *Object::clone() const
93 {
94 #ifdef HAVE_HT_OBJECTS
95 throw NotImplementedException(HERE);
96 #else
97 return NULL;
98 #endif
99 }
100
101 #ifdef HAVE_HT_OBJECTS
102
103 bool Object::idle()
104 {
105 return false;
106 }
107
108 bool Object::instanceOf(ObjectID id) const
109 {
110 return id == getObjectID();
111 }
112
113 bool Object::instanceOf(Object *o) const
114 {
115 return instanceOf(o->getObjectID());
116 }
117
118 ObjectID Object::getObjectID() const
119 {
120 return OBJID_OBJECT;
121 }
122
123 #endif /* HAVE_HT_OBJECTS */
124
125 /*
126 * Class Enumerator
127 */
128
129 Enumerator::Enumerator()
130 {
131 }
132
133 Object *Enumerator::operator [] (int idx) const
134 {
135 ObjHandle h = findByIdx(idx);
136 return (h != InvObjHandle) ? get(h) : NULL;
137 }
138
139 ObjHandle Enumerator::find(const Object *key) const
140 {
141 ObjHandle h = findFirst();
142 while (h != InvObjHandle) {
143 if (compareObjects(get(h), key) == 0) return h;
144 h = findNext(h);
145 }
146 return InvObjHandle;
147 }
148
149 ObjHandle Enumerator::findGE(const Object *key) const
150 {
151 ObjHandle h = findFirst();
152 ObjHandle best = InvObjHandle;
153 while (h != InvObjHandle) {
154 int c = compareObjects(get(h), key);
155 if (c == 0) return h;
156 if (c > 0) {
157 // h is greater than key
158 if (best != InvObjHandle) {
159 if (compareObjects(get(h), get(best)) < 0) best = h;
160 } else {
161 best = h;
162 }
163 }
164 h = findNext(h);
165 }
166 return best;
167 }
168
169 ObjHandle Enumerator::findLE(const Object *key) const
170 {
171 ObjHandle h = findFirst();
172 ObjHandle best = InvObjHandle;
173 while (h != InvObjHandle) {
174 int c = compareObjects(get(h), key);
175 if (c == 0) return h;
176 if (c < 0) {
177 // h is lower than key
178 if (best != InvObjHandle) {
179 if (compareObjects(get(h), get(best)) > 0) best = h;
180 } else {
181 best = h;
182 }
183 }
184 h = findNext(h);
185 }
186 return best;
187 }
188
189 int Enumerator::toString(char *buf, int buflen) const
190 {
191 ObjHandle h = findFirst();
192 int n = 0;
193 if (buflen>1) { *buf++ = '('; buflen--; n++; }
194 while ((buflen>0) && h) {
195 Object *d = get(h);
196 int k = d->toString(buf, buflen);
197 buflen -= k;
198 buf += k;
199 n += k;
200 bool comma;
201 if (buflen>1) { *buf++ = ','; buflen--; n++; comma = true; } else comma = false;
202 h = findNext(h);
203 if (!h && comma) { buf--; buflen++; n--; }
204 }
205 if (buflen>1) { *buf++ = ')'; buflen--; n++; }
206 if (buflen>0) *buf++ = 0;
207 return n;
208 }
209
210 /*
211 * Class Container
212 */
213
214 Container::Container()
215 {
216 hom_objid = OBJID_TEMP;
217 }
218
219 bool Container::delObj(Object *sig)
220 {
221 return del(find(sig));
222 }
223
224 ObjHandle Container::findOrInsert(Object *obj, bool &inserted)
225 {
226 ObjHandle h = find(obj);
227 if (h == InvObjHandle) {
228 h = insert(obj);
229 inserted = true;
230 } else {
231 inserted = false;
232 }
233 return h;
234 }
235
236 void Container::notifyInsertOrSet(const Object *o)
237 {
238 if (!o) return;
239 if (hom_objid == OBJID_TEMP) {
240 hom_objid = o->getObjectID();
241 } else if (hom_objid != OBJID_INVALID) {
242 if (hom_objid != o->getObjectID()) hom_objid = OBJID_INVALID;
243 }
244 }
245
246 Object *Container::removeObj(const Object *sig)
247 {
248 return remove(find(sig));
249 }
250
251 /*
252 * List
253 */
254 List::List()
255 {
256 }
257
258 /*
259 * Class Array
260 */
261
262 #define ARRAY_ALLOC_MIN 4
263
264
265 /*
266 * grow array size by factor (ARRAY_ALLOC_GROW_NUM / ARRAY_ALLOC_GROW_DENOM)
267 * but never by more than ARRAY_ALLOC_GROW_ABSMAX.
268 */
269 #define ARRAY_ALLOC_GROW_NUM 3
270 #define ARRAY_ALLOC_GROW_DENOM 2
271
272 #define ARRAY_ALLOC_GROW_ABSMAX 64*1024
273
274 Array::Array(bool oo, int prealloc)
275 {
276 own_objects = oo;
277 ecount = 0;
278 acount = 0;
279 elems = NULL;
280
281 realloc(prealloc);
282 }
283
284 Array::~Array()
285 {
286 delAll();
287 }
288
289 void Array::delAll()
290 {
291 // SB: Doppelte ueberpruefung von oo
292 if (elems) {
293 if (own_objects) {
294 for (uint i=0; i<ecount; i++) {
295 freeObj(elems[i]);
296 }
297 }
298 free(elems);
299 }
300 ecount = 0;
301 acount = 0;
302 elems = NULL;
303 }
304
305 Array *Array::clone() const
306 {
307 Array *a = new Array(own_objects, ecount);
308 for (uint i = 0; i<ecount; i++) {
309 Object *e = get(findByIdx(i));
310 if (own_objects) e = e->clone();
311 a->insert(e);
312 }
313 return a;
314 }
315
316 // SB: kann man die funktionen nicht alphabetisch sortieren?
317 // SW: doch aber hab keinen bock dazu, kommt am schluss
318
319 #ifdef HAVE_HT_OBJECTS
320 bool Array::instanceOf(ObjectID id) const
321 {
322 return (id == getObjectID()) || List::instanceOf(id);
323 }
324
325 ObjectID Array::getObjectID() const
326 {
327 return OBJID_ARRAY;
328 }
329
330 #endif /* HAVE_HT_OBJECTS */
331
332 int Array::calcNewBufferSize(int curbufsize, int min_newbufsize) const
333 {
334 int n = curbufsize;
335 if (n < ARRAY_ALLOC_MIN) n = ARRAY_ALLOC_MIN;
336 if (n < min_newbufsize) {
337 while (n < min_newbufsize) {
338 n *= ARRAY_ALLOC_GROW_NUM;
339 n /= ARRAY_ALLOC_GROW_DENOM;
340 }
341 } else {
342 while (n > min_newbufsize) {
343 n *= ARRAY_ALLOC_GROW_DENOM;
344 n /= ARRAY_ALLOC_GROW_NUM;
345 }
346 }
347 if (n-curbufsize > ARRAY_ALLOC_GROW_ABSMAX) {
348 n = curbufsize + ARRAY_ALLOC_GROW_ABSMAX;
349 }
350 if (n < ARRAY_ALLOC_MIN) n = ARRAY_ALLOC_MIN;
351 if (n < min_newbufsize) {
352 n = min_newbufsize;
353 }
354
355 return n;
356 }
357
358 void Array::checkShrink()
359 {
360 // FIXME: implement automatic shrinking
361 }
362
363 void Array::freeObj(Object *obj)
364 {
365 if (own_objects && obj) {
366 obj->done();
367 delete obj;
368 }
369 }
370
371 void Array::realloc(int n)
372 {
373 if (n == 0) n = 1; /* alloc'ing 0 bytes not allowed */
374 ASSERT((uint)n >= ecount);
375 elems = (Object**)::realloc(elems, sizeof (*elems) * n);
376 acount = n;
377 memset(elems+ecount, 0, (acount-ecount)*sizeof(*elems));
378 }
379
380 /**
381 * Prepare a write access
382 * @param i position of planned write access
383 */
384 void Array::prepareWriteAccess(int i)
385 {
386 uint n = calcNewBufferSize(acount, i+1);
387 if (n > acount) realloc(n);
388 }
389
390 uint Array::count() const
391 {
392 return ecount;
393 }
394
395 int Array::compareObjects(const Object *a, const Object *b) const
396 {
397 return autoCompare(a, b);
398 }
399
400 void Array::forceSetByIdx(int i, Object *obj)
401 {
402 // FIXME: sanity check, better idea ?
403 if (i<0) ASSERT(0);
404 prepareWriteAccess(i);
405 freeObj(elems[i]);
406 elems[i] = obj;
407 notifyInsertOrSet(obj);
408 if (i>=ecount) ecount = i+1;
409 }
410
411 Object *Array::get(ObjHandle h) const
412 {
413 uint i = handleToNative(h);
414 return validHandle(h) ? elems[i] : NULL;
415 }
416
417 uint Array::getObjIdx(ObjHandle h) const
418 {
419 return h == InvObjHandle ? InvIdx : handleToNative(h);
420 }
421
422 ObjHandle Array::findByIdx(int i) const
423 {
424 return validHandle(nativeToHandle(i)) ? nativeToHandle(i) : InvObjHandle;
425 }
426
427 ObjHandle Array::findFirst() const
428 {
429 return ecount ? nativeToHandle(0) : InvObjHandle;
430 }
431
432 ObjHandle Array::findLast() const
433 {
434 return ecount ? nativeToHandle(ecount-1) : InvObjHandle;
435 }
436
437 ObjHandle Array::findNext(ObjHandle h) const
438 {
439 if (!validHandle(h)) return findFirst();
440 uint i = handleToNative(h);
441 return (i<ecount-1) ? nativeToHandle(i+1) : InvObjHandle;
442 }
443
444 ObjHandle Array::findPrev(ObjHandle h) const
445 {
446 if (!validHandle(h)) return findLast();
447 uint i = handleToNative(h);
448 return (i>0) ? nativeToHandle(i-1) : InvObjHandle;
449 }
450
451 ObjHandle Array::insert(Object *obj)
452 {
453 prepareWriteAccess(ecount);
454 elems[ecount++] = obj;
455 notifyInsertOrSet(obj);
456 return nativeToHandle(ecount-1);
457 }
458
459 bool Array::del(ObjHandle h)
460 {
461 if (!validHandle(h)) return false;
462 freeObj(remove(h));
463 return true;
464 }
465
466 bool Array::moveTo(ObjHandle from, ObjHandle to)
467 {
468 if (!validHandle(from)) return false;
469 if (!validHandle(to)) return false;
470 uint i = handleToNative(from);
471 uint t = handleToNative(to);
472 Object *o = elems[i];
473 memmove(elems+i, elems+i+1, sizeof (*elems) * (ecount - i - 1));
474 ecount--;
475 insertAt(nativeToHandle(t), o);
476 return true;
477 }
478
479 Object *Array::remove(ObjHandle h)
480 {
481 if (!validHandle(h)) return NULL;
482 uint i = handleToNative(h);
483 Object *o = elems[i];
484 memmove(elems+i, elems+i+1, sizeof (*elems) * (ecount - i - 1));
485 ecount--;
486 checkShrink();
487 return o;
488 }
489
490 bool Array::set(ObjHandle h, Object *obj)
491 {
492 if (!validHandle(h)) return false;
493 uint i = handleToNative(h);
494 freeObj(elems[i]);
495 elems[i] = obj;
496 notifyInsertOrSet(obj);
497 return true;
498 }
499
500 bool Array::swap(ObjHandle h, ObjHandle i)
501 {
502 if (!validHandle(h)) return false;
503 if (!validHandle(i)) return false;
504 uint H = handleToNative(h);
505 uint I = handleToNative(i);
506 Object *t = elems[H];
507 elems[H] = elems[I];
508 elems[I] = t;
509 return true;
510 }
511
512 bool Array::validHandle(ObjHandle h) const
513 {
514 return (handleToNative(h) < ecount);
515 }
516
517 uint Array::handleToNative(ObjHandle h) const
518 {
519 return (Object**)h-elems;
520 }
521
522 ObjHandle Array::nativeToHandle(uint i) const
523 {
524 return elems+i;
525 }
526
527 void Array::insertAt(ObjHandle h, Object *obj)
528 {
529 if (!validHandle(h)) {
530 insert(obj);
531 } else {
532 uint i = handleToNative(h);
533 if (i<ecount) {
534 prepareWriteAccess(ecount);
535 memmove(elems+i+1, elems+i, sizeof (*elems) * (ecount - i));
536 ecount++;
537 } else {
538 prepareWriteAccess(i);
539 memset(elems+ecount, 0, sizeof (*elems) * (i - ecount));
540 ecount = i+1;
541 }
542 elems[i] = obj;
543 notifyInsertOrSet(obj);
544 }
545 }
546
547 /*
548 * Class Stack
549 */
550
551 Stack::Stack(bool own_objects) : Array(own_objects)
552 {
553 }
554
555 void Stack::push(Object *obj)
556 {
557 insert(obj);
558 }
559
560 Object *Stack::pop()
561 {
562 return remove(findLast());
563 }
564
565 #ifdef HAVE_HT_OBJECTS
566 bool Stack::instanceOf(ObjectID id) const
567 {
568 return (id == getObjectID()) || Array::instanceOf(id);
569 }
570
571 ObjectID Stack::getObjectID() const
572 {
573 return OBJID_STACK;
574 }
575 #endif
576 /*
577 * Class LinkedList
578 */
579
580 LinkedList::LinkedList(bool oo)
581 {
582 own_objects = oo;
583 ecount = 0;
584 first = last = NULL;
585 }
586
587 LinkedList::~LinkedList()
588 {
589 delAll();
590 }
591
592 void LinkedList::delAll()
593 {
594 LinkedListNode *n = first, *m;
595 while (n) {
596 m = n->next;
597 freeObj(n->obj);
598 deleteNode(n);
599 n = m;
600 }
601 ecount = 0;
602 first = last = NULL;
603 }
604
605 LinkedListNode *LinkedList::allocNode() const
606 {
607 return new LinkedListNode;
608 }
609
610 void LinkedList::deleteNode(LinkedListNode *node) const
611 {
612 delete node;
613 }
614
615 void LinkedList::freeObj(Object *obj) const
616 {
617 if (own_objects && obj) {
618 obj->done();
619 delete obj;
620 }
621 }
622
623 LinkedList *LinkedList::clone() const
624 {
625 LinkedList *l = new LinkedList(own_objects);
626 LinkedListNode *n = first, *m;
627 while (n) {
628 m = n->next;
629 Object *o = m->obj;
630 if (own_objects) o = o->clone();
631 l->insert(o);
632 n = m;
633 }
634 return l;
635 }
636
637 #ifdef HAVE_HT_OBJECTS
638 bool LinkedList::instanceOf(ObjectID id) const
639 {
640 return (id == getObjectID()) || List::instanceOf(id);
641 }
642
643 ObjectID LinkedList::getObjectID() const
644 {
645 return OBJID_LINKED_LIST;
646 }
647
648 #endif
649 uint LinkedList::count() const
650 {
651 return ecount;
652 }
653
654 int LinkedList::compareObjects(const Object *a, const Object *b) const
655 {
656 return autoCompare(a, b);
657 }
658
659 void LinkedList::forceSetByIdx(int idx, Object *obj)
660 {
661 // FIXME:
662 throw NotImplementedException(HERE);
663 }
664
665 Object *LinkedList::get(ObjHandle h) const
666 {
667 LinkedListNode *n = handleToNative(h);
668 return validHandle(h) ? n->obj : NULL;
669 }
670
671 uint LinkedList::getObjIdx(ObjHandle g) const
672 {
673 int i = 0;
674 ObjHandle h = findFirst();
675 Object *obj = get(g);
676 while (h != InvObjHandle) {
677 if (compareObjects(get(h), obj) == 0) return i;
678 i++;
679 h = findNext(h);
680 }
681 return InvIdx;
682 }
683
684 ObjHandle LinkedList::findByIdx(int i) const
685 {
686 ObjHandle h = findFirst();
687 while (h != InvObjHandle) {
688 if (!i--) break;
689 h = findNext(h);
690 }
691 return h;
692 }
693
694 ObjHandle LinkedList::findFirst() const
695 {
696 return nativeToHandle(first);
697 }
698
699 ObjHandle LinkedList::findLast() const
700 {
701 return nativeToHandle(last);
702 }
703
704 ObjHandle LinkedList::findNext(ObjHandle h) const
705 {
706 if (!validHandle(h)) return findFirst();
707 LinkedListNode *n = handleToNative(h);
708 return nativeToHandle(n->next);
709 }
710
711 ObjHandle LinkedList::findPrev(ObjHandle g) const
712 {
713 if (!validHandle(g)) return findLast();
714 LinkedListNode *ng = handleToNative(g);
715 if (ng == first) return InvObjHandle;
716 ObjHandle h = findFirst();
717 while (h != InvObjHandle) {
718 LinkedListNode *nh = handleToNative(h);
719 if (nh->next == ng) return nativeToHandle(nh);
720 h = findNext(h);
721 }
722 return InvObjHandle;
723 }
724
725 bool LinkedList::del(ObjHandle h)
726 {
727 if (!h) return false;
728 freeObj(remove(h));
729 return true;
730 }
731
732 ObjHandle LinkedList::insert(Object *obj)
733 {
734 LinkedListNode *n = allocNode();
735 n->obj = obj;
736 n->next = NULL;
737 if (last) {
738 last->next = n;
739 last = n;
740 } else {
741 first = last = n;
742 }
743 ecount++;
744 notifyInsertOrSet(obj);
745 return nativeToHandle(n);
746 }
747
748 Object *LinkedList::remove(ObjHandle h)
749 {
750 if (!validHandle(h)) return NULL;
751 LinkedListNode *n = handleToNative(h);
752 Object *o = n->obj;
753 if (n == first) {
754 if (n == last) {
755 first = NULL;
756 last = NULL;
757 } else {
758 first = n->next;
759 }
760 } else {
761 LinkedListNode *p = handleToNative(findPrev(h));
762 p->next = n->next;
763 if (n == last) last = p;
764 }
765 deleteNode(n);
766 ecount--;
767 return o;
768 }
769
770 void LinkedList::insertAt(ObjHandle h, Object *obj)
771 {
772 /* if (h == InvObjHandle) {
773 insert(obj);
774 return;
775 }
776 ObjHandle q = i ? findByIdx(i-1) : InvObjHandle;
777 LinkedListNode *n;
778 if (q != InvObjHandle) {
779 n = (LinkedListNode*)q;
780 } else if (i==0) {
781 n = NULL;
782 } else {
783 insert(obj);
784 return;
785 }
786 LinkedListNode *m = allocNode();
787 m->obj = obj;
788 if (n) {
789 m->next = n->next;
790 n->next = m;
791 if (n == last) last = m;
792 } else {
793 m->next = first;
794 first = m;
795 if (!last) last = m;
796 }
797 ecount++;
798 notifyInsertOrSet(obj);*/
799 ASSERT(0); // code needs review
800 }
801
802 bool LinkedList::moveTo(ObjHandle from, ObjHandle to)
803 {
804 // FIXME:
805 throw NotImplementedException(HERE);
806 }
807
808 bool LinkedList::set(ObjHandle h, Object *obj)
809 {
810 LinkedListNode *n = handleToNative(h);
811 if (!n) return false;
812 freeObj(n->obj);
813 n->obj = obj;
814 return true;
815 }
816
817 bool LinkedList::swap(ObjHandle h, ObjHandle i)
818 {
819 LinkedListNode *H = handleToNative(h);
820 LinkedListNode *I = handleToNative(i);
821 Object *t = H->obj;
822 H->obj = I->obj;
823 I->obj = t;
824 return true;
825 }
826
827 bool LinkedList::validHandle(ObjHandle h) const
828 {
829 return h != InvObjHandle;
830 }
831
832 LinkedListNode* LinkedList::handleToNative(ObjHandle h) const
833 {
834 return (LinkedListNode*)h;
835 }
836
837 ObjHandle LinkedList::nativeToHandle(LinkedListNode *n) const
838 {
839 return (ObjHandle)n;
840 }
841
842 /*
843 * Class Queue
844 */
845
846 Queue::Queue(bool own_objects) : LinkedList(own_objects)
847 {
848 }
849
850
851 #ifdef HAVE_HT_OBJECTS
852 bool Queue::instanceOf(ObjectID id) const
853 {
854 return (id == getObjectID()) || LinkedList::instanceOf(id);
855 }
856
857 ObjectID Queue::getObjectID() const
858 {
859 return OBJID_QUEUE;
860 }
861 #endif
862
863 /*
864 * BinaryTree
865 */
866 BinaryTree::BinaryTree(bool oo, Comparator comp)
867 {
868 root = NULL;
869 own_objects = oo;
870 compare = comp;
871 ecount = 0;
872 }
873
874 BinaryTree::~BinaryTree()
875 {
876 delAll();
877 }
878
879 void BinaryTree::delAll()
880 {
881 freeAll(root);
882 root = NULL;
883 ecount = 0;
884 }
885
886 BinTreeNode *BinaryTree::allocNode() const
887 {
888 return new BinTreeNode;
889 }
890
891 void BinaryTree::deleteNode(BinTreeNode *node) const
892 {
893 delete node;
894 }
895
896 BinTreeNode **BinaryTree::findNodePtr(BinTreeNode **nodeptr, const Object *obj) const
897 {
898 BinTreeNode **x = nodeptr;
899 while (x) {
900 int c = compareObjects((*x)->key, obj);
901 if (c < 0) {
902 x = &(*x)->right;
903 } else if (c > 0) {
904 x = &(*x)->left;
905 } else break;
906 }
907 return x;
908 }
909
910 BinTreeNode *BinaryTree::findNode(BinTreeNode *node, const Object *obj) const
911 {
912 while (node) {
913 int c = compareObjects(node->key, obj);
914 if (c < 0) {
915 node = node->right;
916 } else if (c > 0) {
917 node = node->left;
918 } else break;
919 }
920 return node;
921 }
922
923 BinTreeNode *BinaryTree::findNodeG(BinTreeNode *node, const Object *obj) const
924 {
925 if (!node) return NULL;
926 BinTreeNode *lastGreater = NULL;
927 while (true) {
928 int c = compareObjects(obj, node->key);
929 if (c < 0) {
930 if (!node->left) return node;
931 lastGreater = node;
932 node = node->left;
933 } else {
934 if (!node->right) return lastGreater;
935 node = node->right;
936 }
937 }
938 }
939
940 BinTreeNode *BinaryTree::findNodeGE(BinTreeNode *node, const Object *obj) const
941 {
942 if (!node) return NULL;
943 BinTreeNode *lastGreater = NULL;
944 while (true) {
945 int c = compareObjects(obj, node->key);
946 if (c < 0) {
947 if (!node->left) return node;
948 lastGreater = node;
949 node = node->left;
950 } else if (c > 0) {
951 if (!node->right) return lastGreater;
952 node = node->right;
953 } else {
954 return node;
955 }
956 }
957 }
958
959 BinTreeNode *BinaryTree::findNodeL(BinTreeNode *node, const Object *obj) const
960 {
961 if (!node) return NULL;
962 BinTreeNode *lastLower = NULL;
963 while (true) {
964 int c = compareObjects(obj, node->key);
965 if (c <= 0) {
966 if (!node->left) return lastLower;
967 node = node->left;
968 } else {
969 if (!node->right) return node;
970 lastLower = node;
971 node = node->right;
972 }
973 }
974 }
975
976 BinTreeNode *BinaryTree::findNodeLE(BinTreeNode *node, const Object *obj) const
977 {
978 if (!node) return NULL;
979 BinTreeNode *lastLower = NULL;
980 while (true) {
981 int c = compareObjects(obj, node->key);
982 if (c < 0) {
983 if (!node->left) return lastLower;
984 node = node->left;
985 } else if (c > 0) {
986 if (!node->right) return node;
987 lastLower = node;
988 node = node->right;
989 } else {
990 return node;
991 }
992 }
993 }
994
995 void BinaryTree::freeAll(BinTreeNode *n)
996 {
997 if (!n) return;
998 freeAll(n->left);
999 freeObj(n->key);
1000 freeAll(n->right);
1001 deleteNode(n);
1002 }
1003
1004 void BinaryTree::freeObj(Object *obj) const
1005 {
1006 if (own_objects && obj) {
1007 obj->done();
1008 delete obj;
1009 }
1010 }
1011
1012 ObjHandle BinaryTree::findByIdxR(BinTreeNode *n, int &i) const
1013 {
1014 if (!n) return InvObjHandle;
1015 ObjHandle h;
1016 if ((h = findByIdxR(n->left, i))) return h;
1017 if (i == 0) return nativeToHandle(n);
1018 i--;
1019 if ((h = findByIdxR(n->right, i))) return h;
1020 return InvObjHandle;
1021 }
1022
1023 BinTreeNode *BinaryTree::getLeftmost(BinTreeNode *node) const
1024 {
1025 if (node) while (node->left) node = node->left;
1026 return node;
1027 }
1028
1029 BinTreeNode *BinaryTree::getRightmost(BinTreeNode *node) const
1030 {
1031 if (node) while (node->right) node = node->right;
1032 return node;
1033 }
1034
1035 BinTreeNode **BinaryTree::getLeftmostPtr(BinTreeNode **p) const
1036 {
1037 if (*p) while ((*p)->left) p = &(*p)->left;
1038 return p;
1039 }
1040
1041 BinTreeNode **BinaryTree::getRightmostPtr(BinTreeNode **p) const
1042 {
1043 if (*p) while ((*p)->right) p = &(*p)->right;
1044 return p;
1045 }
1046
1047 void BinaryTree::cloneR(BinTreeNode *node)
1048 {
1049 if (!node) return;
1050 Object *o = own_objects ? node->key->clone() : node->key;
1051 // SB: nicht gut: (unnoetige compares)
1052 insert(o);
1053
1054 cloneR(node->left);
1055 cloneR(node->right);
1056 }
1057
1058 BinaryTree *BinaryTree::clone() const
1059 {
1060 BinaryTree *c = new BinaryTree(own_objects, compare);
1061 c->cloneR(root);
1062 return c;
1063 }
1064
1065 ObjectID BinaryTree::getObjectID() const
1066 {
1067 return OBJID_BINARY_TREE;
1068 }
1069
1070 uint BinaryTree::count() const
1071 {
1072 return ecount;
1073 }
1074
1075 int BinaryTree::compareObjects(const Object *a, const Object *b) const
1076 {
1077 return compare(a, b);
1078 }
1079
1080 ObjHandle BinaryTree::find(const Object *key) const
1081 {
1082 return findNode(root, key);
1083 }
1084
1085 ObjHandle BinaryTree::findG(const Object *key) const
1086 {
1087 return findNodeG(root, key);
1088 }
1089
1090 ObjHandle BinaryTree::findGE(const Object *key) const
1091 {
1092 return findNodeGE(root, key);
1093 }
1094
1095 ObjHandle BinaryTree::findL(const Object *key) const
1096 {
1097 return findNodeL(root, key);
1098 }
1099
1100 ObjHandle BinaryTree::findLE(const Object *key) const
1101 {
1102 return findNodeLE(root, key);
1103 }
1104
1105 Object *BinaryTree::get(ObjHandle h) const
1106 {
1107 BinTreeNode *n = handleToNative(h);
1108 return validHandle(h) ? n->key : NULL;
1109 }
1110
1111 uint BinaryTree::getObjIdx(ObjHandle h) const
1112 {
1113 // FIXME: implement it
1114 throw NotImplementedException(HERE);
1115 }
1116
1117 ObjHandle BinaryTree::findByIdx(int i) const
1118 {
1119 return findByIdxR(root, i);
1120 }
1121
1122 ObjHandle BinaryTree::findFirst() const
1123 {
1124 return nativeToHandle(getLeftmost(root));
1125 }
1126
1127 ObjHandle BinaryTree::findLast() const
1128 {
1129 return nativeToHandle(getRightmost(root));
1130 }
1131
1132 ObjHandle BinaryTree::findNext(ObjHandle h) const
1133 {
1134 if (!validHandle(h)) return findFirst();
1135 BinTreeNode *n = handleToNative(h);
1136 if (n->right) return nativeToHandle(getLeftmost(n->right));
1137 BinTreeNode *x = root, *result = NULL;
1138 while (x) {
1139 int c = compareObjects(x->key, n->key);
1140 if (c > 0) {
1141 result = x;
1142 x = x->left;
1143 } else {
1144 x = x->right;
1145 }
1146 }
1147 return nativeToHandle(result);
1148 }
1149
1150 ObjHandle BinaryTree::findPrev(ObjHandle h) const
1151 {
1152 if (!validHandle(h)) return findLast();
1153 BinTreeNode *n = handleToNative(h);
1154 if (n->left) return nativeToHandle(getRightmost(n->left));
1155 BinTreeNode *x = root, *result = NULL;
1156 while (x) {
1157 int c = compareObjects(x->key, n->key);
1158 if (c < 0) {
1159 result = x;
1160 x = x->right;
1161 } else {
1162 x = x->left;
1163 }
1164 }
1165 return nativeToHandle(result);
1166 }
1167
1168 bool BinaryTree::del(ObjHandle h)
1169 {
1170 if (!validHandle(h)) return false;
1171 BinTreeNode *n = handleToNative(h);
1172 Object *obj = n->key;
1173 bool r = remove(h);
1174 freeObj(obj);
1175 return r;
1176 }
1177
1178 // SB: ich haette gerne noch ein findOrInsert (besserer Name noetig),
1179 // das entweder einfuegt oder - wenns das schon gibt -
1180 // das ObjHandle zurueckgibt (bzw immer das objHandle zurueckgibt)
1181 // SW: interface + naive implementierung in Container sind da
1182 ObjHandle BinaryTree::insert(Object *obj)
1183 {
1184 return insertR(root, obj);
1185 }
1186
1187 ObjHandle BinaryTree::insertR(BinTreeNode *&node, Object *obj)
1188 {
1189 if (!node) {
1190 node = allocNode();
1191 node->key = obj;
1192 node->left = NULL;
1193 node->right = NULL;
1194 ecount++;
1195 notifyInsertOrSet(obj);
1196 return nativeToHandle(node);
1197 }
1198 int c = compareObjects(obj, node->key);
1199 if (c > 0) {
1200 return insertR(node->right, obj);
1201 } else if (c < 0) {
1202 return insertR(node->left, obj);
1203 } else return InvObjHandle;
1204 }
1205
1206 Object *BinaryTree::remove(ObjHandle h)
1207 {
1208 if (!validHandle(h)) return NULL;
1209 /* n is the node, whose key has to be removed */
1210 BinTreeNode *n = handleToNative(h);
1211 /* d is node that is to be removed - not necessarily n. */
1212 BinTreeNode *d;
1213
1214 Object *o = n->key;
1215 if (n->left && n->right) {
1216 /* p is pointer to left/right inside Parent(d) with: *p = d */
1217 BinTreeNode **p = getLeftmostPtr(&n->right);
1218 d = *p;
1219 *p = (*p)->right;
1220 } else if (n->left || n->right) {
1221 d = n->left ? n->left : n->right;
1222 n->left = d->left;
1223 n->right = d->right;
1224 } else {
1225 // SB: hier wuerde ein remove(Object *o) mit integriertem find()
1226 // auch (etwas) schneller sein, da man kein findNodePtr mehr braucht
1227 // SW: interface ist da: remove(Object *o)
1228 BinTreeNode **p = findNodePtr(&root, n->key);
1229 d = *p;
1230 *p = NULL;
1231 }
1232
1233 n->key = d->key;
1234 deleteNode(d);
1235 ecount--;
1236 return o;
1237 }
1238
1239 void BinaryTree::setNodeIdentity(BinTreeNode *node, BinTreeNode *newident)
1240 {
1241 node->key = newident->key;
1242 }
1243
1244 /*
1245 * AVLTree
1246 */
1247 AVLTree::AVLTree(bool aOwnObjects, Comparator aComparator)
1248 : BinaryTree(aOwnObjects, aComparator)
1249 {
1250
1251 }
1252
1253 void AVLTree::cloneR(BinTreeNode *node)
1254 {
1255 if (!node) return;
1256 Object *o = own_objects ? node->key->clone() : node->key;
1257 // SB: nicht gut: (unnoetige compares)
1258 insert(o);
1259
1260 cloneR(node->left);
1261 cloneR(node->right);
1262 }
1263
1264 AVLTree *AVLTree::clone() const
1265 {
1266 AVLTree *c = new AVLTree(own_objects, compare);
1267 c->cloneR(root);
1268 return c;
1269 }
1270
1271
1272 ObjectID AVLTree::getObjectID() const
1273 {
1274 return OBJID_AVL_TREE;
1275 }
1276
1277 ObjHandle AVLTree::insert(Object *obj)
1278 {
1279 /* t will point to the node where rebalancing may be necessary */
1280 BinTreeNode **t = &root;
1281 /* *pp will walk through the tree */
1282 BinTreeNode **pp = &root;
1283 // Search
1284 while (*pp) {
1285 int c = compareObjects(obj, (*pp)->key);
1286 if (c < 0) {
1287 pp = &(*pp)->left;
1288 } else if (c > 0) {
1289 pp = &(*pp)->right;
1290 } else {
1291 // element found
1292 return InvObjHandle;
1293 }
1294 if (*pp && (*pp)->unbalance) {
1295 t = pp;
1296 }
1297 }
1298
1299 /* s points to the node where rebalancing may be necessary */
1300 BinTreeNode *s = *t;
1301
1302 // Insert
1303 *pp = allocNode();
1304 BinTreeNode *retval = *pp;
1305 retval->key = obj;
1306 retval->left = retval->right = NULL;
1307 retval->unbalance = 0;
1308 ecount++;
1309 notifyInsertOrSet(obj);
1310 if (!s) return nativeToHandle(retval);
1311
1312 // Rebalance
1313 int a;
1314 BinTreeNode *r;
1315 BinTreeNode *p;
1316 if (compareObjects(obj, s->key) < 0) {
1317 a = -1;
1318 r = p = s->left;
1319 } else {
1320 a = 1;
1321 r = p = s->right;
1322 }
1323 while (p != retval) {
1324 if (compareObjects(obj, p->key) < 0) {
1325 p->unbalance = -1;
1326 p = p->left;
1327 } else {
1328 p->unbalance = 1;
1329 p = p->right;
1330 }
1331 }
1332 if (!s->unbalance) {
1333 // tree was balanced before insertion
1334 s->unbalance = a;
1335 } else if (s->unbalance == -a) {
1336 // tree has become more balanced
1337 s->unbalance = 0;
1338 } else {
1339 // tree is out of balance
1340 if (r->unbalance == a) {
1341 // single rotation
1342 p = r;
1343 if (a < 0) {
1344 s->left = r->right;
1345 r->right = s;
1346 } else {
1347 s->right = r->left;
1348 r->left = s;
1349 }
1350 s->unbalance = r->unbalance = 0;
1351 } else {
1352 // double rotation
1353 if (a < 0) {
1354 p = r->right;
1355 r->right = p->left;
1356 p->left = r;
1357 s->left = p->right;
1358 p->right = s;
1359 } else {
1360 p = r->left;
1361 r->left = p->right;
1362 p->right = r;
1363 s->right = p->left;
1364 p->left = s;
1365 }
1366 s->unbalance = (p->unbalance == a) ? -a : 0;
1367 r->unbalance = (p->unbalance == -a) ? a : 0;
1368 p->unbalance = 0;
1369 }
1370 // finalization
1371 *t = p;
1372 }
1373 ASSERT(root);
1374 return nativeToHandle(retval);
1375 }
1376
1377 BinTreeNode *AVLTree::removeR(Object *key, BinTreeNode *&node, int &change, int cmp)
1378 {
1379 if (node == NULL) {
1380 change = 0;
1381 return NULL;
1382 }
1383
1384 BinTreeNode *found = NULL;
1385 int decrease = 0;
1386
1387 int result;
1388 if (!cmp) {
1389 result = compareObjects(key, node->key);
1390 if (result < 0) {
1391 result = -1;
1392 } else if (result > 0) {
1393 result = 1;
1394 }
1395 } else if (cmp < 0) {
1396 result = (node->left == NULL) ? 0 : -1;
1397 } else {
1398 result = (node->right == NULL) ? 0 : 1;
1399 }
1400
1401 if (result) {
1402 found = removeR(key, (result < 0) ? node->left : node->right, change, cmp);
1403 if (!found) return NULL;
1404 decrease = result * change;
1405 } else {
1406 found = node;
1407
1408 /*
1409 * Same logic as in BinaryTree::remove()
1410 */
1411 if (!node->left && !node->right) {
1412 node = NULL;
1413 change = 1;
1414 return found;
1415 } else if (!node->left || !node->right) {
1416 node = node->right ? node->right : node->left;
1417 change = 1;
1418 return found;
1419 } else {
1420 BinTreeNode *n = removeR(key, node->right, decrease, -1);
1421 setNodeIdentity(node, n);
1422 found = n;
1423 }
1424 }
1425
1426 node->unbalance -= decrease;
1427
1428 if (decrease) {
1429 if (node->unbalance) {
1430 change = 0;
1431 int a;
1432 BinTreeNode *r = NULL;
1433 if (node->unbalance < -1) {
1434 a = -1;
1435 r = node->left;
1436 } else if (node->unbalance > 1) {
1437 a = 1;
1438 r = node->right;
1439 } else {
1440 a = 0;
1441 }
1442 if (a) {
1443 /*
1444 * If r->unbalance == 0 do also a single rotation.
1445 * This case cant occure with insert operations.
1446 */
1447 if (r->unbalance == -a) {
1448 /*
1449 * double rotation.
1450 * See insert
1451 */
1452 BinTreeNode *p;
1453 if (a > 0) {
1454 p = r->left;
1455 r->left = p->right;
1456 p->right = r;
1457 node->right = p->left;
1458 p->left = node;
1459 } else {
1460 p = r->right;
1461 r->right = p->left;
1462 p->left = r;
1463 node->left = p->right;
1464 p->right = node;
1465 }
1466 node->unbalance = (p->unbalance == a) ? -a: 0;
1467 r->unbalance = (p->unbalance == -a) ? a: 0;
1468 p->unbalance = 0;
1469 node = p;
1470 change = 1;
1471 } else {
1472 /*
1473 * single rotation
1474 * Height of tree changes if r is/was unbalanced
1475 */
1476 change = r->unbalance?1:0;
1477 if (a > 0) {
1478 node->right = r->left;
1479 r->left = node;
1480 r->unbalance--;
1481 } else {
1482 node->left = r->right;
1483 r->right = node;
1484 r->unbalance++;
1485 }
1486 node->unbalance = - r->unbalance;
1487 node = r;
1488 }
1489 }
1490 } else {
1491 /*
1492 * Tree has become more balanced
1493 */
1494 change = 1;
1495 }
1496 } else {
1497 change = 0;
1498 }
1499
1500 return found;
1501 }
1502
1503 Object *AVLTree::remove(ObjHandle h)
1504 {
1505 if (!validHandle(h)) return NULL;
1506 BinTreeNode *n = handleToNative(h);
1507 Object *o = n->key;
1508 int change;
1509 BinTreeNode *node = removeR(n->key, root, change, 0);
1510 if (node) {
1511 deleteNode(node);
1512 ecount--;
1513 return o;
1514 }
1515 return NULL;
1516 }
1517
1518 /*
1519 * Class Set
1520 */
1521
1522 Set::Set(bool oo)
1523 : AVLTree(oo)
1524 {
1525 }
1526
1527 #ifdef HAVE_HT_OBJECTS
1528 bool Set::instanceOf(ObjectID id) const
1529 {
1530 return (id == getObjectID()) || AVLTree::instanceOf(id);
1531 }
1532
1533 ObjectID Set::getObjectID() const
1534 {
1535 return OBJID_SET;
1536 }
1537 #endif
1538
1539 void Set::intersectWith(Set *b)
1540 {
1541 foreach(Object, elem, *this,
1542 if (!b->contains(elem)) delObj(elem);
1543 );
1544 }
1545
1546 void Set::unionWith(Set *b)
1547 {
1548 foreach(Object, elem, *b,
1549 if (!contains(elem)) insert(own_objects ? elem->clone() : elem);
1550 );
1551 }
1552
1553 /*
1554 *
1555 */
1556
1557 KeyValue::KeyValue(Object *aKey, Object *aValue)
1558 {
1559 mKey = aKey;
1560 mValue = aValue;
1561 }
1562
1563 KeyValue::~KeyValue()
1564 {
1565 mKey->done();
1566 delete mKey;
1567 // mValue->done();
1568 delete mValue;
1569 }
1570
1571 KeyValue *KeyValue::clone() const
1572 {
1573 return new KeyValue(mKey->clone(), mValue ? mValue->clone() : NULL);
1574 }
1575
1576 int KeyValue::compareTo(const Object *obj) const
1577 {
1578 return mKey->compareTo(((KeyValue*)obj)->mKey);
1579 }
1580
1581 int KeyValue::toString(char *buf, int buflen) const
1582 {
1583 return ht_snprintf(buf, buflen, "[Key: %y; Value: %y]", mKey, mValue);
1584 }
1585
1586 #ifdef HAVE_HT_OBJECTS
1587 bool KeyValue::instanceOf(ObjectID id) const
1588 {
1589 return id == getObjectID();
1590 }
1591
1592 ObjectID KeyValue::getObjectID() const
1593 {
1594 return OBJID_KEYVALUE;
1595 }
1596
1597 #endif
1598
1599 /*
1600 * Class SInt
1601 */
1602
1603 SInt::SInt(signed int i)
1604 {
1605 value = i;
1606 }
1607
1608 SInt *SInt::clone() const
1609 {
1610 return new SInt(value);
1611 }
1612
1613 int SInt::compareTo(const Object *obj) const
1614 {
1615 SInt *s = (SInt*)obj;
1616 return value - s->value;
1617 }
1618
1619 int SInt::toString(char *buf, int buflen) const
1620 {
1621 return ht_snprintf(buf, buflen, "%d", value);
1622 }
1623
1624 #ifdef HAVE_HT_OBJECTS
1625
1626 bool SInt::instanceOf(ObjectID id) const
1627 {
1628 return id == getObjectID();
1629 }
1630
1631 ObjectID SInt::getObjectID() const
1632 {
1633 return OBJID_SINT;
1634 }
1635
1636 #endif
1637
1638 /*
1639 * A signed Integer (64-bit)
1640 */
1641
1642 SInt64::SInt64(sint64 i)
1643 {
1644 value = i;
1645 }
1646
1647 SInt64 *SInt64::clone() const
1648 {
1649 return new SInt64(value);
1650 }
1651
1652 int SInt64::compareTo(const Object *obj) const
1653 {
1654 SInt64 *u = (SInt64*)obj;
1655
1656 if (value < u->value) {
1657 return -1;
1658 } else if (value > u->value) {
1659 return 1;
1660 } else {
1661 return 0;
1662 }
1663 }
1664
1665 int SInt64::toString(char *buf, int buflen) const
1666 {
1667 return ht_snprintf(buf, buflen, "%qd", value);
1668 }
1669
1670 #ifdef HAVE_HT_OBJECTS
1671 bool SInt64::instanceOf(ObjectID id) const
1672 {
1673 return id == getObjectID();
1674 }
1675
1676 ObjectID SInt64::getObjectID() const
1677 {
1678 return OBJID_SINT64;
1679 }
1680
1681 #endif
1682
1683 /*
1684 * Class UInt
1685 */
1686
1687 UInt::UInt(unsigned int i)
1688 {
1689 value = i;
1690 }
1691
1692 UInt *UInt::clone() const
1693 {
1694 return new UInt(value);
1695 }
1696
1697 int UInt::compareTo(const Object *obj) const
1698 {
1699 UInt *u = (UInt*)obj;
1700
1701 if (value < u->value) {
1702 return -1;
1703 } else if (value > u->value) {
1704 return 1;
1705 } else {
1706 return 0;
1707 }
1708 }
1709
1710 int UInt::toString(char *buf, int buflen) const
1711 {
1712 return ht_snprintf(buf, buflen, "%u", value);
1713 }
1714
1715 #ifdef HAVE_HT_OBJECTS
1716
1717 bool UInt::instanceOf(ObjectID id) const
1718 {
1719 return id == getObjectID();
1720 }
1721
1722 ObjectID UInt::getObjectID() const
1723 {
1724 return OBJID_UINT;
1725 }
1726
1727 #endif
1728
1729 /*
1730 * A unsigned Integer (64-bit)
1731 */
1732 UInt64::UInt64(uint64 i)
1733 {
1734 value = i;
1735 }
1736
1737 UInt64 *UInt64::clone() const
1738 {
1739 return new UInt64(value);
1740 }
1741
1742 int UInt64::compareTo(const Object *obj) const
1743 {
1744 UInt64 *u = (UInt64*)obj;
1745
1746 if (value < u->value) {
1747 return -1;
1748 } else if (value > u->value) {
1749 return 1;
1750 } else {
1751 return 0;
1752 }
1753 }
1754
1755 int UInt64::toString(char *buf, int buflen) const
1756 {
1757 return ht_snprintf(buf, buflen, "%qu", value);
1758 }
1759
1760 #ifdef HAVE_HT_OBJECTS
1761 bool UInt64::instanceOf(ObjectID id) const
1762 {
1763 return id == getObjectID();
1764 }
1765
1766 ObjectID UInt64::getObjectID() const
1767 {
1768 return OBJID_UINT64;
1769 }
1770
1771 #endif
1772
1773 /*
1774 * A floating-point number (FIXME: no portable storage yet)
1775 */
1776
1777 Float::Float(double d)
1778 {
1779 value = d;
1780 }
1781
1782 Float *Float::clone() const
1783 {
1784 return new Float(value);
1785 }
1786
1787 int Float::compareTo(const Object *obj) const
1788 {
1789 // FIXME: do we want to compare for equality using some error term epsilon ?
1790 Float *f = (Float*)obj;
1791
1792 if (value < f->value) {
1793 return -1;
1794 } else if (value > f->value) {
1795 return 1;
1796 } else {
1797 return 0;
1798 }
1799 }
1800
1801 int Float::toString(char *buf, int buflen) const
1802 {
1803 return ht_snprintf(buf, buflen, "%f", value);
1804 }
1805
1806 #ifdef HAVE_HT_OBJECTS
1807 bool Float::instanceOf(ObjectID id) const
1808 {
1809 return id == getObjectID();
1810 }
1811
1812 ObjectID Float::getObjectID() const
1813 {
1814 return OBJID_FLOAT;
1815 }
1816
1817 #endif
1818
1819 /*
1820 * Class Pointer
1821 */
1822
1823 Pointer::Pointer(void *p)
1824 {
1825 value = p;
1826 }
1827
1828 /**
1829 * A memory area.
1830 */
1831
1832 MemArea::MemArea(const void *p, uint s, bool d)
1833 {
1834 duplicate = d;
1835 size = s;
1836 if (duplicate) {
1837 ptr = malloc(size);
1838 if (!ptr) throw std::bad_alloc();
1839 memcpy(ptr, p, size);
1840 } else {
1841 // FIXME: un-const'ing p
1842 ptr = (void*)p;
1843 }
1844 }
1845
1846 MemArea::~MemArea()
1847 {
1848 if (duplicate) free(ptr);
1849 }
1850
1851 MemArea *MemArea::clone() const
1852 {
1853 return new MemArea(ptr, size, true);
1854 }
1855
1856 int MemArea::compareTo(const Object *obj) const
1857 {
1858 const MemArea *a = this;
1859 const MemArea *b = (const MemArea*)obj;
1860 if (a->size != b->size) return a->size - b->size;
1861 return memcmp(a->ptr, b->ptr, a->size);
1862 }
1863
1864 int MemArea::toString(char *buf, int buflen) const
1865 {
1866 throw NotImplementedException(HERE);
1867 }
1868
1869 #ifdef HAVE_HT_OBJECTS
1870 bool MemArea::instanceOf(ObjectID id) const
1871 {
1872 return (id == getObjectID()) || Object::instanceOf(id);
1873 }
1874
1875 ObjectID MemArea::getObjectID() const
1876 {
1877 return OBJID_MEMAREA;
1878 }
1879
1880 #endif
1881
1882 /*
1883 * sorter
1884 */
1885
1886 static void quickSortR(List &list, int l, int r)
1887 {
1888 int m = (l+r)/2;
1889 int L = l;
1890 int R = r;
1891 Object *c = list[m];
1892 do {
1893 while ((l<=r) && (list.compareObjects(list[l], c)<0)) l++;
1894 while ((l<=r) && (list.compareObjects(list[r], c)>0)) r--;
1895 if (l<=r) {
1896 list.swap(list.findByIdx(l), list.findByIdx(r));
1897 l++;
1898 r--;
1899 }
1900 } while (l<r);
1901 if (L<r) quickSortR(list, L, r);
1902 if (l<R) quickSortR(list, l, R);
1903 }
1904
1905 bool quickSort(List &l)
1906 {
1907 int c = l.count();
1908 if (c) quickSortR(l, 0, c-1);
1909 return true;
1910 }
1911
1912 /*
1913 * Module Init/Done
1914 */
1915
1916 bool initData()
1917 {
1918 return true;
1919 }
1920
1921 void doneData()
1922 {
1923 }

  ViewVC Help
Powered by ViewVC 1.1.26