00001
00003 #ifndef __gdtlist__
00004 #define __gdtlist__
00005
00006 #include <assert.h>
00007 #include <iostream>
00008
00009
00010 #define UNKNOWN_COUNTER -1
00011 #define __DLINKP (dlink*)
00012 #define AFTER 0
00013 #define BEFORE 1
00014
00015
00016 typedef void* list_item;
00017
00018
00019 namespace gdt {
00020
00021 template<class T>
00022 void Swap(T& x, T& y) {
00023 T aux = x;
00024 x = y;
00025 y = aux;
00026 }
00027
00028 enum { after = AFTER, before = BEFORE };
00029
00030 typedef ::list_item list_item;
00031
00032 template <class F>
00033 class Record {
00034 public:
00035 Record<F> *succ;
00036 Record<F> *pred;
00037 F inf;
00038 };
00039
00040
00041
00042 template <class E>
00043 class gdtlist {
00044
00045 public:
00046
00047 typedef void* item;
00048
00049 private:
00050
00051
00052 typedef Record<E> Item;
00053
00054
00055 Item *firstitem;
00056
00057
00058 Item *lastitem;
00059
00060
00061 int counter;
00062
00063
00064
00065 Item *buffer;
00066
00067
00068 void clear_buffer();
00069
00070
00071 void assign_buffer(Item *i) {
00072 if (buffer) clear_buffer();
00073 buffer = i;
00074 }
00075
00076
00077
00078 int count() const;
00079
00080
00081 void inc_counter();
00082
00083
00084 void dec_counter();
00085
00086
00087
00088 void copy(const gdtlist<E>& l);
00089
00090 public:
00091
00092
00093
00094
00095
00096
00097
00098 gdtlist();
00099
00100
00101 gdtlist(const gdtlist<E>& l);
00102
00103
00104 ~gdtlist();
00105
00106 gdtlist<E>& operator = (const gdtlist<E>& l);
00107
00108 bool operator == (const gdtlist<E>& l2) const;
00109
00110
00111
00112
00113
00114
00115
00116
00117 inline Item* first_item() const;
00118 inline Item* last_item() const;
00119 inline Item* next_item(gdt::list_item p) const;
00120 inline Item* pred_item(gdt::list_item p) const;
00121
00122
00123
00124
00125
00126
00127
00128
00129 int length() const;
00130
00131 int size() const;
00132
00133 bool empty() const;
00134
00135 gdt::list_item first() const;
00136
00137 gdt::list_item last() const;
00138
00139
00140
00141
00142
00143 gdt::list_item get_item(int i) const;
00144
00145 inline gdt::list_item succ(gdt::list_item li) const;
00146
00147 inline gdt::list_item pred(gdt::list_item li) const;
00148
00149 inline gdt::list_item cyclic_succ(gdt::list_item li) const;
00150
00151 inline gdt::list_item cyclic_pred(gdt::list_item li) const;
00152
00153 inline const E& contents(gdt::list_item li) const;
00154
00155 inline const E& inf(gdt::list_item it) const;
00156
00157 inline const E& front() const;
00158
00159 inline const E& head() const;
00160
00161 inline const E& back() const;
00162
00163 inline const E& tail() const;
00164
00165
00166
00167
00168
00169
00170 int rank(const E& x) const;
00171
00172
00173
00174
00175
00176
00177
00178 inline gdt::list_item push(const E& x);
00179
00180 inline gdt::list_item push_front(const E& x);
00181
00182 inline gdt::list_item append(const E& x);
00183
00184 inline gdt::list_item push_back(const E& x);
00185
00186 gdt::list_item insert(const E& x, gdt::list_item _pos, int dir = AFTER);
00187 const E& operator[] (list_item it) const;
00188
00189 E& operator[] (list_item it);
00190
00191
00192
00193 void swap_items(gdt::list_item it1, gdt::list_item it2);
00194
00195 inline const E& pop();
00196
00197 inline const E& pop_front();
00198
00199 inline const E& Pop();
00200
00201 inline const E& pop_back();
00202
00203 const E& del_item(gdt::list_item it);
00204
00205 const E& del(gdt::list_item it);
00206
00207 void erase(gdt::list_item it);
00208
00209 void remove(const E& x);
00210
00211 void assign(gdt::list_item li, const E& x);
00212
00213 void conc(gdtlist<E>& L1, int dir = AFTER);
00214
00215 void split(gdt::list_item _it, gdtlist<E>& L1, gdtlist<E>& L2);
00216
00217 void reverse_items();
00218
00219 void reverse();
00220
00221
00222
00223
00224
00225
00226
00227 list_item search(const E& x) const;
00228
00229
00230
00231
00232
00233
00234
00235
00236 void print(std::ostream& os, char space = ' ') const;
00237
00238 void print(char space = ' ') const;
00239
00240 void clear();
00241
00242 bool check_item(gdt::list_item lit) const ;
00243
00244 bool consistency_check() const;
00245 };
00246
00247
00248 template <class E>
00249 void gdtlist<E>::clear_buffer() {
00250
00251 Item *i = buffer;
00252 delete i;
00253 }
00254
00255
00256
00257 template <class E>
00258 int gdtlist<E>::count() const {
00259 if (counter == UNKNOWN_COUNTER) {
00260 list_item li = first();
00261 int &c = const_cast< gdtlist<E>* >(this)->counter;
00262 c = 0;
00263 while (li) { ++c; li = succ(li); }
00264 }
00265 return counter;
00266 }
00267
00268
00269 template <class E>
00270 void gdtlist<E>::inc_counter() {
00271 if (counter != UNKNOWN_COUNTER) ++counter;
00272 }
00273
00274
00275 template <class E>
00276 void gdtlist<E>::dec_counter() {
00277 if (counter != UNKNOWN_COUNTER) --counter;
00278 }
00279
00280
00281
00282 template <class E>
00283 void gdtlist<E>::copy(const gdtlist<E>& l) {
00284 clear();
00285 list_item it = l.first();
00286 while (it) { append(l.inf(it));it = l.succ(it); }
00287
00288 }
00289
00290
00291
00292
00293
00294
00295
00296 template <class E>
00297 gdtlist<E>::gdtlist() : firstitem(NULL), lastitem(NULL), counter(0), buffer(NULL) {}
00298
00299
00300
00301 template <class E>
00302 gdtlist<E>::gdtlist(const gdtlist<E>& l) : firstitem(NULL), lastitem(NULL), counter(0), buffer(NULL) {
00303
00304 copy(l);
00305
00306 }
00307
00308
00309
00310
00311 template <class E>
00312 gdtlist<E>::~gdtlist() {
00313
00314 clear();
00315 if (buffer) clear_buffer();
00316 }
00317
00318
00319 template <class E>
00320 gdtlist<E>& gdtlist<E>::operator = (const gdtlist<E>& l) {
00321 copy(l);
00322
00323 return *this;
00324 }
00325
00326 template <class E>
00327 bool gdtlist<E>::operator == (const gdtlist<E>& l2) const {
00328 list_item i1 = first();
00329 list_item i2 = l2.first();
00330
00331 while (i1 && i2 && inf(i1) == l2.inf(i2)) {
00332 i1 = succ(i1);
00333 i2 = l2.succ(i2);
00334 }
00335
00336
00337 return (i1 == i2);
00338 }
00339
00340
00341
00342
00343
00344
00345
00346
00347 template <class E>
00348 typename gdtlist<E>::Item* gdtlist<E>::first_item() const { return firstitem; }
00349 template <class E>
00350 typename gdtlist<E>::Item* gdtlist<E>::last_item() const { return lastitem; }
00351 template <class E>
00352 typename gdtlist<E>::Item* gdtlist<E>::next_item(gdt::list_item p) const { return (Item*) (p != NULL ? succ(p) : NULL); }
00353 template <class E>
00354 typename gdtlist<E>::Item* gdtlist<E>::pred_item(gdt::list_item p) const { return (Item*) (p != NULL ? pred(p) : NULL); }
00355
00356
00357
00358
00359
00360
00361
00362 template <class E>
00363 int gdtlist<E>::length() const {
00364
00365 count();
00366
00367 return counter;
00368 }
00369
00370 template <class E>
00371 int gdtlist<E>::size() const { return length(); }
00372
00373 template <class E>
00374 bool gdtlist<E>::empty() const { return firstitem == NULL; }
00375
00376 template <class E>
00377 gdt::list_item gdtlist<E>::first() const {
00378 return firstitem;
00379 }
00380
00381 template <class E>
00382 gdt::list_item gdtlist<E>::last() const { return lastitem; }
00383
00384 template <class E>
00385 gdt::list_item gdtlist<E>::get_item(int i) const {
00386
00387
00388 gdt::list_item li = first();
00389 int j = 0;
00390 while (j < i) {li = succ(li); ++j;}
00391
00392
00393
00394 return li;
00395 }
00396
00397 template <class E>
00398 gdt::list_item gdtlist<E>::succ(gdt::list_item li) const {
00399
00400 Item *i = static_cast<Item *>((void *) li);
00401 return i->succ;
00402 }
00403
00404 template <class E>
00405 gdt::list_item gdtlist<E>::pred(gdt::list_item li) const {
00406
00407 Item *i = static_cast<Item *>((void *) li);
00408 return i->pred;
00409 }
00410
00411 template <class E>
00412 gdt::list_item gdtlist<E>::cyclic_succ(gdt::list_item li) const {
00413
00414 return li != last() ? succ(li) : first();
00415 }
00416
00417 template <class E>
00418 gdt::list_item gdtlist<E>::cyclic_pred(gdt::list_item li) const {
00419
00420 return li != first() ? pred(li) : last();
00421 }
00422
00423 template <class E>
00424 const E& gdtlist<E>::contents(gdt::list_item li) const {
00425
00426
00427
00428 Item *i = static_cast<Item *>((void*)li);
00429
00430 return i->inf;
00431 }
00432
00433 template <class E>
00434 const E& gdtlist<E>::inf(gdt::list_item it) const {
00435
00436 return contents(it);
00437 }
00438
00439 template <class E>
00440 const E& gdtlist<E>::front() const {
00441
00442 return contents(first());
00443 }
00444
00445 template <class E>
00446 const E& gdtlist<E>::head() const { return front(); }
00447
00448 template <class E>
00449 const E& gdtlist<E>::back() const {
00450
00451 return contents(last());
00452 }
00453
00454 template <class E>
00455 const E& gdtlist<E>::tail() const { return back(); }
00456
00457
00458
00459
00460
00461
00462 template <class E>
00463 int gdtlist<E>::rank(const E& x) const
00464 {
00465
00466 int i = 1;
00467 gdt::list_item li = first();
00468 while(li != NULL && contents(li) != x) {li = succ(li); ++i;};
00469
00470
00471
00472 return li != NULL ? i : 0;
00473 }
00474
00475
00476
00477
00478
00479
00480
00481 template <class E>
00482 gdt::list_item gdtlist<E>::push(const E& x) { return insert(x, first(), gdt::before); }
00483
00484 template <class E>
00485 gdt::list_item gdtlist<E>::push_front(const E& x) { return push(x); }
00486
00487 template <class E>
00488 gdt::list_item gdtlist<E>::append(const E& x) { return insert(x, last(), gdt::after); }
00489
00490 template <class E>
00491 gdt::list_item gdtlist<E>::push_back(const E& x) { return append(x); }
00492
00493 template <class E>
00494 gdt::list_item gdtlist<E>::insert(const E& x, gdt::list_item _pos, int dir) {
00495
00496
00497
00498
00499
00500 Item* newitem = new Item;
00501 Item* pos = static_cast<Item*>((void*)_pos);
00502 newitem->inf = x;
00503 if (empty()) {
00504 firstitem = newitem;
00505 lastitem = newitem;
00506 newitem->succ = NULL;
00507 newitem->pred = NULL;
00508 }
00509 else {
00510
00511 if (dir == gdt::after) {
00512
00513 newitem->succ = pos->succ;
00514 if (pos->succ)
00515 pos->succ->pred = newitem;
00516 else
00517 lastitem = newitem;
00518 newitem->pred = pos;
00519 pos->succ = newitem;
00520 }
00521 else {
00522
00523 newitem->pred = pos->pred;
00524 if (pos->pred) pos->pred->succ = newitem;
00525 else firstitem = newitem;
00526 newitem->succ = pos;
00527 pos->pred = newitem;
00528 }
00529 }
00530 inc_counter();
00531
00532
00533 return newitem;
00534 }
00535
00536 template <class E>
00537 const E& gdtlist<E>::operator[] (list_item it) const {
00538 return contents(it);
00539 }
00540
00541 template <class E>
00542 E& gdtlist<E>::operator[] (list_item it) {
00543
00544 Item* i = (Item *) it;
00545 return i->inf;
00546 }
00547
00548
00549
00550 template <class E>
00551 void gdtlist<E>::swap_items(gdt::list_item it1, gdt::list_item it2) {
00552
00553
00554 Item* i1 = (Item*) it1;
00555 Item* i2 = (Item*) it2;
00556 Item* p1 = i1->pred;
00557 Item* s1 = i1->succ;
00558 Item* p2 = i2->pred;
00559 Item* s2 = i2->succ;
00560
00561 if (p1 == NULL) firstitem = i2;
00562 if (p2 == NULL) firstitem = i1;
00563 if (s1 == NULL) lastitem = i2;
00564 if (s2 == NULL) lastitem = i1;
00565
00566 if (s1 == i2) {
00567
00568
00569 i2->succ = i1;
00570 i1->pred = i2;
00571
00572 i1->succ = s2;
00573 i2->pred = p1;
00574
00575 ass_succ(p1, i2);
00576 ass_pred(s2, i1);
00577 }
00578 else if (s2 == i1) {
00579
00580
00581 i1->succ = i2;
00582 i2->pred = i1;
00583
00584 i2->succ = s1;
00585 i1->pred = p2;
00586
00587 ass_succ(p2, i1);
00588 ass_pred(s1, i2);
00589 }
00590 else {
00591
00592
00593 i2->succ = s1;
00594 i1->pred = p2;
00595 ass_pred(s1, i2);
00596 ass_succ(p2, i1);
00597
00598 i1->succ = s2;
00599 i2->pred = p1;
00600
00601 ass_succ(p1, i2);
00602 ass_pred(s2, i1);
00603 }
00604
00605
00606 }
00607
00608 template <class E>
00609 const E& gdtlist<E>::pop() { return del_item(first()); }
00610
00611 template <class E>
00612 const E& gdtlist<E>::pop_front() { return pop(); }
00613
00614 template <class E>
00615 const E& gdtlist<E>::Pop() { return del_item(last()); }
00616
00617 template <class E>
00618 const E& gdtlist<E>::pop_back() { return Pop(); }
00619
00620 template <class E>
00621 const E& gdtlist<E>::del_item(gdt::list_item it) {
00622
00623
00624 if (buffer) clear_buffer();
00625 buffer = static_cast<Item*>((void*)it);
00626 if (buffer->pred) buffer->pred->succ = buffer->succ;
00627 else firstitem = buffer->succ;
00628 if (buffer->succ) buffer->succ->pred = buffer->pred;
00629 else lastitem = buffer->pred;
00630
00631 dec_counter();
00632
00633
00634 return buffer->inf;
00635 }
00636
00637 template <class E>
00638 const E& gdtlist<E>::del(gdt::list_item it) { return del_item(it); }
00639
00640 template <class E>
00641 void gdtlist<E>::erase(gdt::list_item it) { del_item(it); }
00642
00643 template <class E>
00644 void gdtlist<E>::remove(const E& x) {
00645
00646 Item *it = firstitem;
00647 while (it) {
00648 Item *itsucc = it->succ;
00649 if (inf(it) == x) del_item(it);
00650 it = itsucc;
00651 }
00652
00653
00654 }
00655
00656 template <class E>
00657 void gdtlist<E>::assign(gdt::list_item li, const E& x) {
00658
00659
00660 Item *i = static_cast<Item*>(li);
00661 i->inf = x;
00662
00663
00664 }
00665
00666 template <class E>
00667 void gdtlist<E>::conc(gdtlist<E>& L1, int dir) {
00668
00669
00670
00671
00672 if (dir == gdt::after) {
00673 if (lastitem) lastitem->succ = L1.firstitem;
00674 else firstitem = L1.firstitem;
00675
00676 if (L1.firstitem) L1.firstitem->pred = lastitem;
00677
00678 if (L1.lastitem) lastitem = L1.lastitem;
00679
00680 }
00681 else {
00682 if (firstitem) firstitem->pred = L1.lastitem;
00683 else lastitem = L1.lastitem;
00684
00685 if (L1.lastitem) L1.lastitem->succ = firstitem;
00686
00687 if (L1.firstitem) firstitem = L1.firstitem;
00688
00689 }
00690
00691 if (counter != UNKNOWN_COUNTER && L1.counter != UNKNOWN_COUNTER)
00692 counter += L1.counter;
00693 else counter = UNKNOWN_COUNTER;
00694
00695
00696 L1.firstitem = NULL;
00697 L1.lastitem = NULL;
00698 L1.counter = 0;
00699
00700
00701 }
00702
00703
00704 template <class E>
00705 void gdtlist<E>::split(gdt::list_item _it, gdtlist<E>& L1, gdtlist<E>& L2) {
00706
00707
00708
00709
00710 Item* it = (Item*) _it;
00711 Item* temp_firstitem = firstitem;
00712 Item* temp_lastitem = lastitem;
00713 int temp_counter = counter;
00714
00715 if (it) {
00716
00717 L1.lastitem = it->pred;
00718 L1.firstitem = temp_firstitem == it ? NULL : temp_firstitem;
00719 L1.counter = UNKNOWN_COUNTER;
00720
00721
00722 if (it->pred) it->pred->succ = NULL;
00723
00724
00725 it->pred = NULL;
00726 L2.firstitem = it;
00727 L2.lastitem = temp_lastitem;
00728 L2.counter = UNKNOWN_COUNTER;
00729 }
00730 else {
00731
00732 L1.firstitem = NULL;
00733 L1.lastitem = NULL;
00734 L1.counter = 0;
00735
00736
00737 L2.firstitem = temp_firstitem;
00738 L2.lastitem = temp_lastitem;
00739 L2.counter = temp_counter;
00740 }
00741
00742
00743 if (&L1 != this && &L2 != this) {
00744 firstitem = NULL;
00745 lastitem = NULL;
00746 counter = 0;
00747
00748 }
00749 else {
00750
00751 }
00752
00753
00754
00755
00756 }
00757
00758
00759
00760
00761
00762
00763
00764
00765 template <class E>
00766 void gdtlist<E>::reverse_items() {
00767
00768 Swap(firstitem, lastitem);
00769 Item *it = lastitem;
00770 while (it) {
00771 Swap(it->succ, it->pred);
00772 it = it->pred;
00773 }
00774
00775 }
00776
00777 template <class E>
00778 void gdtlist<E>::reverse() { reverse_items(); }
00779
00780
00781
00782
00783
00784
00785
00786 template <class E>
00787 list_item gdtlist<E>::search(const E& x) const {
00788
00789 list_item li = first();
00790 while (li && inf(li) != x) {li = succ(li);}
00791 return li;
00792 }
00793
00794
00795
00796
00797
00798
00799
00800 template <class E>
00801 void gdtlist<E>::print(std::ostream& os, char space) const {
00802 list_item li;
00803 os << "{";
00804 if (!empty()) {
00805 li = first();
00806 while (li != last()) {
00807 os << inf(li) << ",";
00808 li = succ(li);
00809 }
00810 os << back();
00811 }
00812 os << "}";
00813 }
00814
00815 template <class E>
00816 void gdtlist<E>::print(char space) const {
00817 print(std::cout, space);
00818 }
00819
00820
00821
00822 template <class E>
00823 void gdtlist<E>::clear() { while (!empty()) pop(); }
00824
00825 template <class E>
00826 bool gdtlist<E>::check_item(gdt::list_item lit) const {
00827 Item *it = firstitem;
00828 while (it && lit != it) it = it->succ;
00829 return it == lit;
00830 }
00831
00832 template <class E>
00833 bool gdtlist<E>::consistency_check() const {
00834 Item *it = firstitem;
00835 Item *predit = NULL;
00836 int number_of_items = 0;
00837
00838 while (it) {
00839 ++number_of_items;
00840 if (predit != it->pred)
00841 return false;
00842 predit = it;
00843 it = it->succ;
00844 }
00845
00846 if (predit != lastitem)
00847 return false;
00848 if (counter != UNKNOWN_COUNTER && number_of_items != counter)
00849 return false;
00850
00851 return true;
00852 }
00853
00854 };
00855
00856
00857 template <class OS, class E>
00858 OS& operator << (OS& os, const gdt::gdtlist<E>& l) {
00859 gdt::list_item li;
00860 os << "{";
00861 if (!l.empty()) {
00862 li = l.first();
00863 while (li != l.last()) {
00864 os << l.inf(li) << ",";
00865 li = l.succ(li);
00866 }
00867 os << l.back();
00868 }
00869 os << "}";
00870 return os;
00871 }
00872
00873
00874 template <class IS, class E>
00875 IS& operator >> (IS& is, gdt::gdtlist<E>& l) {
00876
00877 std::cout << "Operatore << non implementato" << std::endl;
00878 return is;
00879 }
00880
00882
00884
00885
00886
00887
00888
00889
00890
00891
00892
00893
00894
00895
00896
00897
00898
00899
00900
00901
00902
00903
00904
00905
00906
00907
00908
00909
00910
00911
00912
00913
00914
00915
00916
00917
00918
00919
00920
00921
00922
00923
00924
00925
00926
00927
00928
00929
00930 #define forall_items(it,S) \
00931 for(it=(S).first(); it; it=(S).succ(it))
00932
00933
00934
00935
00936
00937 #if (defined(__GNUC__) && __GNUC_MINOR__ <= 7) || defined(__ELSE_SCOPE_BUG__)
00938 #define __FORALL_PREAMBLE
00939 #define LOOP_CAT(x,y) x ## y
00940 #define LOOP_VAR(y) LOOP_CAT(loop_var_,y)
00941 #define LOOP_VAR1(y) LOOP_CAT(loop_var1_,y)
00942 #else
00943 #define __FORALL_PREAMBLE if (0); else
00944 #define LOOP_VAR(y) loop_var
00945 #define LOOP_VAR1(y) loop_var1
00946 #endif
00947
00948
00949 #define LOOP_ITEM(p) (typename T::item)p
00950
00951 #if defined(__NO_CAST_TO_LOCAL_TYPE__)
00952 template <class T>
00953 inline T cast_to_item(T,void* p) { return (T)p; }
00954 #undef LOOP_ITEM
00955 #define LOOP_ITEM(p) cast_to_item(S.first_item(),p)
00956 #endif
00957
00958
00959 template<class T>
00960 inline bool LoopSucc(const T& S, void*& p)
00961 { if (p) { p = S.next_item(LOOP_ITEM(p)); return true; }
00962 else return false;
00963 }
00964
00965 template<class T>
00966 inline bool LoopPred(const T& S, void*& p)
00967 { if (p) { p = S.pred_item(LOOP_ITEM(p)); return true; }
00968 else return false;
00969 }
00970
00971 template<class T, class var_type>
00972 inline void LoopInf(const T& S, var_type& x, void* p)
00973 { if (p) x = S.inf(LOOP_ITEM(p)); }
00974
00975 template<class T, class var_type>
00976 inline void LoopKey(const T& S, var_type& x, void* p)
00977 { if (p) x = S.key(LOOP_ITEM(p)); }
00978
00979
00980 #define forall(x,S)\
00981 __FORALL_PREAMBLE \
00982 for(void* LOOP_VAR(__LINE__) = (S).first_item();\
00983 LoopInf(S,x,LOOP_VAR(__LINE__)), LoopSucc(S,LOOP_VAR(__LINE__)); )
00984
00985
00986 #endif
00987
00988