21 #ifndef ELM_DATA_LIST_H
22 #define ELM_DATA_LIST_H
24 #include <elm/assert.h>
25 #include <elm/PreIterator.h>
26 #include <elm/inhstruct/SLList.h>
28 #include <elm/equiv.h>
33 template <
class T,
class E = Equiv<T>,
class A = DefaultAlloc>
34 class List:
public E,
public A {
41 inline Node *next(
void)
const {
return nextNode(); }
42 inline Node *nextNode(
void)
const {
return static_cast<Node *
>(SLNode::next()); }
43 inline static void *
operator new(
size_t s,
List<T, E, A> *l) {
return l->A::allocate(s); }
46 inline ~Node(
void) { }
60 for(item++; item(); item++) { cur->insertAfter(
new(
this) Node(*item)); cur = cur->next(); }
67 inline Iter(
void): node(0) { }
68 inline Iter(
const List& _list): node(_list.firstNode()) { }
70 inline bool ended(
void)
const {
return !node; }
71 inline const T&
item(
void)
const { ASSERT(node);
return node->val; }
72 inline void next(
void) { ASSERT(node); node = node->next(); }
73 inline bool equals(
const Iter& i)
const {
return node == i.node; }
81 inline operator Iter(
void)
const {
return items(); }
90 inline PrecIter(
const List& _list): node(_list.firstNode()), prev(0) { }
91 inline operator Iter(
void)
const {
Iter i; i.node = node;
return i; }
95 inline bool ended(
void)
const {
return !node; }
96 inline const T&
item(
void)
const { ASSERT(node);
return node->val; }
97 inline void next(
void) { ASSERT(node); prev = node; node = node->next(); }
109 inline const T&
item(
void)
const {
return *c; }
110 inline void next(
void) { c++; }
112 inline operator Iter(
void)
const {
return c; }
121 {
for(
Iter iter(*
this);
iter();
iter++)
if(E::isEqual(item, *
iter))
return true;
return false; }
125 {
Iter i1(*
this), i2(l);
while(i1() && i2()) {
if(!E::isEqual(*i1, *i2))
return false; i1++; i2++; }
return !i1 && !i2; }
126 inline const T&
at(
const Iter& i)
const {
return i.node->val; }
130 {
while(!_list.
isEmpty()) { Node *node = firstNode(); _list.
removeFirst(); node->free(
this); } }
133 {
for(
typename C::Iter i(
items); i(); i++)
add(*i); }
138 for(Node *prev = firstNode(), *cur = prev->nextNode(); cur; prev = cur, cur = cur->nextNode())
139 if(E::isEqual(cur->val,
value)) { prev->removeNext(); cur->free(
this);
return; }
141 inline T&
at(
const Iter& i) {
return i.node->val; }
145 inline T&
first(
void) {
return firstNode()->val; }
146 inline const T&
first(
void)
const {
return firstNode()->val; }
147 inline T&
last(
void) {
return lastNode()->val; }
148 inline const T&
last(
void)
const {
return lastNode()->val; }
149 inline T&
nth(
int n) {
Iter i(*
this);
while(n) { ASSERT(i); i++; n--; } ASSERT(i);
return i.node->val; };
150 inline const T&
nth(
int n)
const {
Iter i(*
this);
while(n) { ASSERT(i); i++; n--; } ASSERT(i);
return *i; };
152 {
Iter i;
for(i =
items(); i(); i++)
if(E::isEqual(item, *i))
break;
return i; }
154 {
Iter i = pos;
for(i++; i(); i++)
if(E::isEqual(item, *i))
break;
return i; }
160 { ASSERT(pos.node); pos.node->insertAfter(
new(
this) Node(
value)); }
163 else { pos.prev->insertAfter(
new(
this) Node(
value)); pos.prev = pos.prev->next(); } }
166 inline void set(
const Iter &pos,
const T &item) { ASSERT(pos.node); pos.node->val = item; }
169 inline const T&
top(
void)
const {
return first(); }
189 inline Node *firstNode(
void)
const {
return static_cast<Node *
>(_list.
first()); }
190 inline Node *lastNode(
void)
const {
return static_cast<Node *
>(_list.
last()); }
191 void remove(Node* prev, Node*& cur)
192 { ASSERT(cur);
if(!prev) {
removeFirst(); cur = firstNode(); }
193 else { prev->removeNext(); cur->free(
this); cur = prev->next(); } }
void free(t::ptr p) const
Definition: custom.h:32
void next(void)
Definition: List.h:72
const T & item(void) const
Definition: List.h:71
Iter(const List &_list)
Definition: List.h:68
bool ended(void) const
Definition: List.h:70
Iter(void)
Definition: List.h:67
bool equals(const Iter &i) const
Definition: List.h:73
bool operator!=(const PrecIter &i)
Definition: List.h:93
PrecIter(const List &_list)
Definition: List.h:90
PrecIter(void)
Definition: List.h:89
void next(void)
Definition: List.h:97
bool operator==(const PrecIter &i)
Definition: List.h:92
const T & item(void) const
Definition: List.h:96
bool ended(void) const
Definition: List.h:95
SubIter(void)
Definition: List.h:106
Iter asIter(void) const
Definition: List.h:111
SubIter(Iter begin, Iter end)
Definition: List.h:107
void next(void)
Definition: List.h:110
const T & item(void) const
Definition: List.h:109
bool ended(void) const
Definition: List.h:108
void addLast(const T &value)
Definition: List.h:158
Iter find(const T &item, const Iter &pos) const
Definition: List.h:153
List()
Definition: List.h:51
void removeFirst(void)
Definition: List.h:164
void addAll(const C &items)
Definition: List.h:132
bool contains(const T &item) const
Definition: List.h:120
void addBefore(PrecIter &pos, const T &value)
Definition: List.h:161
void reset(void)
Definition: List.h:172
void removeLast(void)
Definition: List.h:165
Iter find(const T &item) const
Definition: List.h:151
bool operator==(const List< T > &l) const
Definition: List.h:179
const T & top(void) const
Definition: List.h:169
List(const List< T, E, A > &list)
Definition: List.h:52
void addFirst(const T &value)
Definition: List.h:157
const T & nth(int n) const
Definition: List.h:150
const T & operator[](int k) const
Definition: List.h:178
A & allocator()
Definition: List.h:56
E & equivalence()
Definition: List.h:54
Iter begin(void) const
Definition: List.h:82
bool equals(const List< T > &l) const
Definition: List.h:124
T & first(void)
Definition: List.h:145
int count(void) const
Definition: List.h:119
T pop(void)
Definition: List.h:170
const E & equivalence() const
Definition: List.h:55
T & operator[](int k)
Definition: List.h:177
const T & at(const Iter &i) const
Definition: List.h:126
void removeAll(const C &items)
Definition: List.h:134
List< T > & operator+=(const T &h)
Definition: List.h:181
T & last(void)
Definition: List.h:147
List< T > & operator-=(const List< T > &l)
Definition: List.h:184
void add(const T &value)
Definition: List.h:131
void push(const T &i)
Definition: List.h:171
void copy(const List< T, E, A > &list)
Definition: List.h:58
void remove(const T &value)
Definition: List.h:136
void remove(PrecIter &iter)
Definition: List.h:142
Iter end(void) const
Definition: List.h:83
List< T > & operator+=(const List< T > &l)
Definition: List.h:182
bool operator&(const T &e) const
Definition: List.h:176
T & at(const Iter &i)
Definition: List.h:141
Iter operator*(void) const
Definition: List.h:80
void addAfter(const Iter &pos, const T &value)
Definition: List.h:159
void set(const Iter &pos, const T &item)
Definition: List.h:166
bool operator!=(const List< T > &l) const
Definition: List.h:180
T & nth(int n)
Definition: List.h:149
Iter items(void) const
Definition: List.h:79
const T & first(void) const
Definition: List.h:146
const T & last(void) const
Definition: List.h:148
void clear(void)
Definition: List.h:129
List & operator=(const List &list)
Definition: List.h:175
List< T > & operator-=(const T &h)
Definition: List.h:183
bool isEmpty(void) const
Definition: List.h:122
~List(void)
Definition: List.h:53
static List< T, E, A > null
Definition: List.h:118
void removeFirst(void)
Definition: SLList.h:67
void addFirst(SLNode *node)
Definition: SLList.h:63
void removeLast(void)
Definition: inhstruct_SLList.cpp:102
int count(void) const
Definition: inhstruct_SLList.cpp:74
SLNode * first(void) const
Definition: SLList.h:60
SLNode * last(void) const
Definition: inhstruct_SLList.cpp:59
void addLast(SLNode *node)
Definition: inhstruct_SLList.cpp:90
bool isEmpty(void) const
Definition: SLList.h:70
Definition: util_WAHVector.cpp:157
void iter(const C &c, const F &f)
Definition: util.h:95
ListPrinter< T > list(const T &l, cstring s="", typename ListPrinter< T >::fun_t f=ListPrinter< T >::asis)
Definition: Output.h:321