|
3326
|
1 // This may look like C code, but it is really -*- C++ -*- |
|
|
2 /* |
|
|
3 Copyright (C) 1988 Free Software Foundation |
|
|
4 written by Doug Lea (dl@rocky.oswego.edu) |
|
|
5 |
|
|
6 This file is part of the GNU C++ Library. This library is free |
|
|
7 software; you can redistribute it and/or modify it under the terms of |
|
|
8 the GNU Library General Public License as published by the Free |
|
|
9 Software Foundation; either version 2 of the License, or (at your |
|
|
10 option) any later version. This library is distributed in the hope |
|
|
11 that it will be useful, but WITHOUT ANY WARRANTY; without even the |
|
|
12 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR |
|
|
13 PURPOSE. See the GNU Library General Public License for more details. |
|
|
14 You should have received a copy of the GNU Library General Public |
|
|
15 License along with this library; if not, write to the Free Software |
|
|
16 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
|
|
17 */ |
|
|
18 |
|
|
19 |
|
|
20 #ifndef _DLList_h |
|
|
21 #define _DLList_h 1 |
|
|
22 |
|
|
23 #if defined (__GNUG__) |
|
|
24 #pragma interface |
|
|
25 #endif |
|
|
26 |
|
|
27 #undef OK |
|
|
28 |
|
|
29 #include <Pix.h> |
|
|
30 |
|
|
31 struct BaseDLNode { |
|
|
32 BaseDLNode *bk; |
|
|
33 BaseDLNode *fd; |
|
|
34 void *item() {return (void*)(this+1);} //Return ((DLNode<T>*)this)->hd |
|
|
35 }; |
|
|
36 |
|
|
37 template<class T> |
|
3585
|
38 class |
|
|
39 DLNode : public BaseDLNode |
|
3326
|
40 { |
|
|
41 public: |
|
|
42 T hd; |
|
|
43 DLNode() { } |
|
|
44 DLNode(const T& h, DLNode* p = 0, DLNode* n = 0) |
|
|
45 : hd(h) { bk = p; fd = n; } |
|
|
46 ~DLNode() { } |
|
|
47 }; |
|
|
48 |
|
3585
|
49 class |
|
|
50 BaseDLList |
|
|
51 { |
|
3326
|
52 protected: |
|
|
53 BaseDLNode *h; |
|
|
54 |
|
|
55 BaseDLList() { h = 0; } |
|
|
56 void copy(const BaseDLList&); |
|
|
57 BaseDLList& operator= (const BaseDLList& a); |
|
|
58 virtual void delete_node(BaseDLNode*node) = 0; |
|
|
59 virtual BaseDLNode* copy_node(const void* datum) = 0; |
|
|
60 virtual void copy_item(void *dst, void *src) = 0; |
|
|
61 virtual ~BaseDLList() { } |
|
|
62 |
|
|
63 Pix prepend(const void*); |
|
|
64 Pix append(const void*); |
|
|
65 Pix ins_after(Pix p, const void *datum); |
|
|
66 Pix ins_before(Pix p, const void *datum); |
|
|
67 void remove_front(void *dst); |
|
|
68 void remove_rear(void *dst); |
|
|
69 void join(BaseDLList&); |
|
|
70 |
|
|
71 public: |
|
|
72 int empty() const { return h == 0; } |
|
|
73 int length() const; |
|
|
74 void clear(); |
|
|
75 void error(const char* msg) const; |
|
|
76 int owns(Pix p) const; |
|
|
77 int OK() const; |
|
|
78 void del(Pix& p, int dir = 1); |
|
|
79 void del_after(Pix& p); |
|
|
80 void del_front(); |
|
|
81 void del_rear(); |
|
|
82 }; |
|
|
83 |
|
|
84 template <class T> |
|
3585
|
85 class |
|
|
86 DLList : public BaseDLList |
|
|
87 { |
|
3326
|
88 //friend class <T>DLListTrav; |
|
|
89 |
|
|
90 virtual void delete_node(BaseDLNode *node) { delete (DLNode<T>*)node; } |
|
|
91 virtual BaseDLNode* copy_node(const void *datum) |
|
|
92 { return new DLNode<T>(*(const T*)datum); } |
|
|
93 virtual void copy_item(void *dst, void *src) { *(T*)dst = *(T*)src; } |
|
|
94 |
|
|
95 public: |
|
|
96 DLList() : BaseDLList() { } |
|
|
97 DLList(const DLList<T>& a) : BaseDLList() { copy(a); } |
|
|
98 |
|
|
99 DLList<T>& operator = (const DLList<T>& a) |
|
|
100 { BaseDLList::operator=((const BaseDLList&) a); return *this; } |
|
|
101 virtual ~DLList() { clear(); } |
|
|
102 |
|
|
103 Pix prepend(const T& item) {return BaseDLList::prepend(&item);} |
|
|
104 Pix append(const T& item) {return BaseDLList::append(&item);} |
|
|
105 |
|
|
106 void join(DLList<T>& a) { BaseDLList::join(a); } |
|
|
107 |
|
|
108 T& front() { |
|
|
109 if (h == 0) error("front: empty list"); |
|
|
110 return ((DLNode<T>*)h)->hd; } |
|
|
111 T& rear() { |
|
|
112 if (h == 0) error("rear: empty list"); |
|
|
113 return ((DLNode<T>*)h->bk)->hd; |
|
|
114 } |
|
|
115 const T& front() const { |
|
|
116 if (h == 0) error("front: empty list"); |
|
|
117 return ((DLNode<T>*)h)->hd; } |
|
|
118 const T& rear() const { |
|
|
119 if (h == 0) error("rear: empty list"); |
|
|
120 return ((DLNode<T>*)h->bk)->hd; |
|
|
121 } |
|
|
122 T remove_front() { T dst; BaseDLList::remove_front(&dst); return dst; } |
|
|
123 T remove_rear() { T dst; BaseDLList::remove_rear(&dst); return dst; } |
|
|
124 |
|
|
125 T& operator () (Pix p) { |
|
|
126 if (p == 0) error("null Pix"); |
|
|
127 return ((DLNode<T>*)p)->hd; |
|
|
128 } |
|
|
129 const T& operator () (Pix p) const { |
|
|
130 if (p == 0) error("null Pix"); |
|
|
131 return ((DLNode<T>*)p)->hd; |
|
|
132 } |
|
|
133 Pix first() const { return Pix(h); } |
|
|
134 Pix last() const { return (h == 0) ? 0 : Pix(h->bk); } |
|
|
135 void next(Pix& p) const |
|
|
136 { p = (p == 0 || h == 0 || p == h->bk)? 0 : Pix(((DLNode<T>*)p)->fd); } |
|
|
137 void prev(Pix& p) const |
|
|
138 { p = (p == 0 || p == h)? 0 : Pix(((DLNode<T>*)p)->bk); } |
|
|
139 Pix ins_after(Pix p, const T& item) |
|
|
140 {return BaseDLList::ins_after(p, &item); } |
|
|
141 Pix ins_before(Pix p, const T& item) |
|
|
142 {return BaseDLList::ins_before(p, &item);} |
|
|
143 }; |
|
|
144 |
|
|
145 #endif |
