21 #ifndef INCLUDE_ELM_DATA_BIDILIST_H_
22 #define INCLUDE_ELM_DATA_BIDILIST_H_
24 #include <elm/assert.h>
25 #include <elm/inhstruct/DLList.h>
26 #include <elm/PreIterator.h>
27 #include <elm/data/Manager.h>
32 template <
class T,
class E = Equiv<T>,
class A = DefaultAlloc>
38 inline Node(
const T& v): val(v) { }
39 inline static void *
operator new(
size_t s,
BiDiList<T, E, A> *l) {
return l->A::allocate(s); }
42 inline ~Node(
void) { }
61 inline Iter(
const BackIter& i) {
if(i) n = i;
else n = i.n->next(); }
63 inline bool ended(
void)
const {
return n->atEnd(); }
64 inline const T&
item(
void)
const {
return n->val; }
65 inline void next(
void) { n =
_(n->next()); }
66 inline bool equals(
const Iter& i)
const {
return i.n == n; }
75 inline BackIter(
const Iter& i) {
if(i) n = i.n;
else n =
_(i.n->previous()); }
76 inline bool ended(
void)
const {
return n->atBegin()(); }
77 inline const T&
item(
void)
const {
return n->val; }
78 inline void next(
void) { n =
_(n->previous()); }
89 {
for(
const auto x: c)
if(!
contains(x))
return false;
return true; }
95 {
Iter i1(*
this), i2(l);
while(i1() && i2()) {
if(!E::isEqual(*i1, *i2))
return false; i1++; i2++; }
return !i1 && !i2; }
104 template <
class C>
inline void addAll(
const C& c)
105 {
for(
const auto x: c)
add(x); }
108 {
for(
const auto x: c)
remove(x); }
109 inline void remove(
const Iter &i) { ASSERT(i());
_(i.n)->remove(); }
110 inline void remove(
Iter &i) { ASSERT(i()); Node *n =
_(i.n->next()); ((Node *)i.n)->remove(); i.n = n; }
119 inline const T&
first(
void)
const {
return _(_list.
first())->val; }
120 inline const T&
last(
void)
const {
return _(_list.
last())->val; }
122 {
Iter i;
for(i =
begin(); i(); i++)
if(E::isEqual(item, *i))
break;
return i; }
124 {
Iter i = pos;
for(i++; i(); i++)
if(E::isEqual(item, *i))
break;
return i; }
125 inline Iter nth(
int n)
const {
Iter i(*
this);
while(n) { ASSERT(i); i++; n--; } ASSERT(i);
return i; };
134 inline void addBefore(
const Iter& i,
const T& v) { ASSERT(i); i.n->insertBefore(
new(
this) Node(v)); }
137 void removeBefore(
const Iter& i) { Node *n =
_(i.n->previous()); i.n->removePrevious(); n->free(
this); }
138 void removeAfter(
const Iter& i) { Node *n =
_(i.n->next()); i.n->removeNext(); n->free(
this); }
139 inline void set(
const Iter &i,
const T &v) { ASSERT(i); i.n->val = v; }
Definition: BiDiList.h:71
BackIter(const BiDiList &l)
Definition: BiDiList.h:74
void next(void)
Definition: BiDiList.h:78
BackIter(const Iter &i)
Definition: BiDiList.h:75
const T & item(void) const
Definition: BiDiList.h:77
bool ended(void) const
Definition: BiDiList.h:76
Definition: BiDiList.h:56
Iter(const BackIter &i)
Definition: BiDiList.h:61
Iter(const BiDiList &l, bool end)
Definition: BiDiList.h:62
void next(void)
Definition: BiDiList.h:65
const T & item(void) const
Definition: BiDiList.h:64
Iter(const BiDiList &l)
Definition: BiDiList.h:60
bool ended(void) const
Definition: BiDiList.h:63
Iter(void)
Definition: BiDiList.h:59
bool equals(const Iter &i) const
Definition: BiDiList.h:66
Definition: BiDiList.h:33
void addAll(const C &c)
Definition: BiDiList.h:104
bool operator==(const BiDiList< T > &l) const
Definition: BiDiList.h:96
Iter find(const T &item, const Iter &pos) const
Definition: BiDiList.h:123
BiDiList< T > & operator+=(const T &h)
Definition: BiDiList.h:111
const A & allocator() const
Definition: BiDiList.h:52
void removeAfter(const Iter &i)
Definition: BiDiList.h:138
void addLast(const T &v)
Definition: BiDiList.h:132
bool contains(const T &item) const
Definition: BiDiList.h:86
void reset(void)
Definition: BiDiList.h:147
T & top()
Definition: BiDiList.h:144
const T & last(void) const
Definition: BiDiList.h:120
const T get(void)
Definition: BiDiList.h:151
void removeFirst()
Definition: BiDiList.h:135
void put(const T &v)
Definition: BiDiList.h:152
const T & first(void) const
Definition: BiDiList.h:119
Iter end(void) const
Definition: BiDiList.h:93
BiDiList & operator=(const BiDiList &list)
Definition: BiDiList.h:116
Iter nth(int n) const
Definition: BiDiList.h:125
const T & head() const
Definition: BiDiList.h:150
const T & operator[](int k) const
Definition: BiDiList.h:126
A & allocator()
Definition: BiDiList.h:53
E & equivalence()
Definition: BiDiList.h:51
Iter begin(void) const
Definition: BiDiList.h:92
T & first(void)
Definition: BiDiList.h:129
int count(void) const
Definition: BiDiList.h:85
const E & equivalence() const
Definition: BiDiList.h:50
BiDiList(const BiDiList< T > &list)
Definition: BiDiList.h:48
bool containsAll(const C &c) const
Definition: BiDiList.h:88
bool operator!=(const BiDiList< T > &l) const
Definition: BiDiList.h:97
T & operator[](int k)
Definition: BiDiList.h:140
bool equals(const BiDiList< T > &l) const
Definition: BiDiList.h:94
const T & top() const
Definition: BiDiList.h:143
void remove(const T &v)
Definition: BiDiList.h:106
T & last(void)
Definition: BiDiList.h:130
BiDiList< T > & operator-=(const BiDiList< T > &l)
Definition: BiDiList.h:114
void remove(Iter &i)
Definition: BiDiList.h:110
~BiDiList(void)
Definition: BiDiList.h:49
BiDiList< T > & operator-=(const T &h)
Definition: BiDiList.h:113
void add(const T &value)
Definition: BiDiList.h:103
void push(const T &i)
Definition: BiDiList.h:146
Iter find(const T &item) const
Definition: BiDiList.h:121
BiDiList(void)
Definition: BiDiList.h:47
void copy(const BiDiList< T > &l)
Definition: BiDiList.h:115
void addBefore(const Iter &i, const T &v)
Definition: BiDiList.h:134
void addAfter(const Iter &i, const T &value)
Definition: BiDiList.h:133
Iter operator*(void) const
Definition: BiDiList.h:155
BiDiList< T > & operator+=(const BiDiList< T > &l)
Definition: BiDiList.h:112
void remove(const Iter &i)
Definition: BiDiList.h:109
T pop()
Definition: BiDiList.h:145
Iter reversedItems(void) const
Definition: BiDiList.h:82
void addFirst(const T &v)
Definition: BiDiList.h:131
void clear(void)
Definition: BiDiList.h:101
static const BiDiList< T, E, A > null
Definition: BiDiList.h:98
bool isEmpty(void) const
Definition: BiDiList.h:90
void set(const Iter &i, const T &v)
Definition: BiDiList.h:139
void removeBefore(const Iter &i)
Definition: BiDiList.h:137
void removeAll(const C &c)
Definition: BiDiList.h:107
void removeLast()
Definition: BiDiList.h:136
void free(t::ptr p) const
Definition: custom.h:32
void removeFirst(void)
Definition: DLList.h:110
void addLast(DLNode *node)
Definition: DLList.h:108
void addFirst(DLNode *node)
Definition: DLList.h:106
void removeLast(void)
Definition: DLList.h:112
DLNode * last(void) const
Definition: DLList.h:94
int count(void) const
Definition: DLList.h:99
bool isEmpty(void) const
Definition: DLList.h:95
DLNode * first(void) const
Definition: DLList.h:93
Definition: util_WAHVector.cpp:157
void iter(const C &c, const F &f)
Definition: util.h:95
AutoStringStartup & _
Definition: debug_CrashHandler.cpp:235
ListPrinter< T > list(const T &l, cstring s="", typename ListPrinter< T >::fun_t f=ListPrinter< T >::asis)
Definition: Output.h:321