blob: 7ed4c6c46895563bd1157cea6b672fdcf8901cd0 (
plain)
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
|
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
template <typename T>
struct llink {
llink<T>* before = nullptr;
llink<T>* after = nullptr;
T* value;
llink () { };
llink (T* val) : value(val) { }
~llink ();
void unlink ();
};
template <typename T>
struct llist {
llink<T>* head;
llink<T>* tail;
llink<T>* __cur;
T* cur() { return __cur->value; }
int length = 0;
llist ();
void push ( T* );
T& peek ();
T& pop ();
/*
* Adds two linked lists together.
* O(1) time.
* destroys new__ in the process, but keeps the elements.
* make sure to free(new__) after.
*/
void operator += (llist<T>& other);
int size () { return length; }
bool empty () { return length == 0; }
};
template <typename T>
llist<T>::llist () {
this->__cur = this->head = new llink<T>;
this->tail = new llink<T>;
head->after = tail;
tail->before = head;
}
#define FIRST(lst) (lst)->head->after
#define FIRST_V(lst) (lst)->head->after->value
#define LAST(lst) (lst)->tail->before
#define LAST_V(lst) (lst)->tail->before->value
template <typename T>
void llist<T>::push(T* val) {
auto l = new llink<T>(val);
l->after = FIRST(this);
FIRST(this) = l;
l->after->before = l;
l->before = this->head;
++this->length;
// TODO do I want to change that?
this->__cur = l;
}
// template <typename T>
// std::ostream& std::operator<<(std::ostream&, llist<T>);
#if 0
DEEP_COPY
LINK(TYPE)* n = FIRST(src);
while (n->after != NULL) {
NEW(TYPE, cpy);
DEEP_COPY(TYPE)(cpy, n->value);
PUSH(LLIST(TYPE)) ( dest, cpy );
n = n->after;
}
return 0;
#endif
/*
* Resets a linked list by removing all it's objects.
* FREE's all elements stored in the list.
*/
// int RESET(LLIST(TYPE)) ( LLIST(TYPE)* llist );
#if 0
LLIST(TYPE)* RESOLVE(LLIST(TYPE)) (LLIST(TYPE)* dest, LLIST(TYPE)* new_);
if (dest == NULL) return new__;
APPEND(LLIST(TYPE))(dest, new__);
return dest;
#endif
#endif /* LINKED_LIST_H */
|
