1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
/*
* TList.h, a simple double-linked list template class
*
* Copyright (C) 2001 Massimiliano Ghilardi
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the Free
* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
* MA 02111-1307, USA
*/
class s_TT {
public:
s_TT *Prev, *Next;
const void *V;
};
typedef s_TT *TT;
class TListV {
public:
TListV() { Count = 0; Head = Tail = Current = (TT)0; }
~TListV() { deleteTT(); }
inline int count( ) const { return Count; }
inline void *current( ) const { return getV(getCurrent()); }
inline void *first( ) { return getV(setCurrent(getHead())); }
inline void *last( ) { return getV(setCurrent(getTail())); }
inline void *next( ) { return getV(setCurrent(getNext())); }
inline void *prev( ) { return getV(setCurrent(getPrev())); }
inline void *getFirst() { return first(); }
inline void *getLast() { return last(); }
inline bool clear( ) { return deleteTT(); }
inline bool remove( ) { return deleteTT(getCurrent()); }
inline bool removeFirst( ) { first(); return remove(); }
inline bool removeLast( ) { last(); return remove(); }
void append( const void *d )
{
TT node = new s_TT();
node->Prev = Tail;
node->Next = (TT)0;
node->V = d;
if (Tail)
Tail->Next = node;
else
Head = node;
Tail = node;
Count++;
}
void inSort( const void *d, int (*compar)(const void *, const void *) )
{
/* start searching from current position */
const void *C;
if (!current())
first();
if (!(C = current())) {
append(d);
return;
}
int i = (*compar)(d, C);
if (i < 0) {
while ((C = prev()) && (*compar)(d, C) < 0)
;
insert(d, Current, Current ? Current->Next : Head);
} else if (i > 0) {
while ((C = next()) && (*compar)(d, C) > 0)
;
insert(d, Current ? Current->Prev : Tail, Current);
} else
insert(d, Current, Current ? Current->Next : Head);
}
const void *at( int n )
{
if (n < count() / 2) {
first();
while (n-- > 0 && next())
;
} else {
last();
n = count() - n - 1;
while (n-- > 0 && prev())
;
}
return current();
}
protected:
int Count;
TT Head, Tail, Current;
inline TT getHead( ) const { return Head; }
inline TT getTail( ) const { return Tail; }
inline TT getCurrent( ) const { return Current; }
inline TT getPrev( ) const { return Current ? Current->Prev : Current; }
inline TT getNext( ) const { return Current ? Current->Next : Current; }
inline TT setCurrent( TT curr ) { return Current = curr; }
inline void *getV( TT curr ) const { return curr ? (void *)curr->V : (void *)0; }
inline bool deleteTT( ) { while (deleteTT(getHead())) ; return TRUE; }
void insert(const void *d, TT _Prev, TT _Next)
{
TT node = new s_TT();
node->V = d;
if (_Prev)
_Next = _Prev->Next;
else if (_Next)
_Prev = _Next->Prev;
if ((node->Prev = _Prev))
_Prev->Next = node;
else
Head = node;
if ((node->Next = _Next))
_Next->Prev = node;
else
Tail = node;
Count++;
}
bool deleteTT( TT curr )
{
if (curr) {
if (curr->Prev)
curr->Prev->Next = curr->Next;
else
Head = curr->Next;
if (curr->Next)
curr->Next->Prev = curr->Prev;
else
Tail = curr->Prev;
curr->~s_TT();
Count--;
}
return !!curr;
}
};
template<class type> class TList : public TListV {
public:
TList( ) { }
TList( const TList<type> &l ) { }
inline type *current( ) const { return getT(getCurrent()); }
inline type *first( ) { return getT(setCurrent(getHead())); }
inline type *last( ) { return getT(setCurrent(getTail())); }
inline type *next( ) { return getT(setCurrent(getNext())); }
inline type *prev( ) { return getT(setCurrent(getPrev())); }
inline type *getFirst() { return first(); }
inline type *getLast() { return last(); }
inline void append( const type *d ){ TListV::append((const void *)d); }
inline void inSort( const type *d )
{
TListV::inSort((const void *)d, (int (*)(const void *, const void *))compar);
}
inline const type *at(int n) { return (const type *)TListV::at(n); }
protected:
inline type *getT( TT curr ) const { return (type *)getV(curr); }
static int compar(const type *a, const type *b) { return *a<*b ? -1 : *a>*b ? 1 : 0; }
};
|