diff --git a/linker/linked_list.h b/linker/linked_list.h
index 52af0f1108a2b8e26d41bd3e931031873001233a..a72b73ccd6753cf0d7a5b25b42819efbdcabce3f 100644 (file)
--- a/linker/linked_list.h
+++ b/linker/linked_list.h
template<typename T, typename Allocator>
class LinkedList {
public:
- LinkedList() : head_(nullptr) {}
+ LinkedList() : head_(nullptr), tail_(nullptr) {}
+ ~LinkedList() {
+ clear();
+ }
+
+ LinkedList(LinkedList&& that) {
+ this->head_ = that.head_;
+ this->tail_ = that.tail_;
+ that.head_ = that.tail_ = nullptr;
+ }
void push_front(T* const element) {
LinkedListEntry<T>* new_entry = Allocator::alloc();
new_entry->next = head_;
new_entry->element = element;
head_ = new_entry;
+ if (tail_ == nullptr) {
+ tail_ = new_entry;
+ }
+ }
+
+ void push_back(T* const element) {
+ LinkedListEntry<T>* new_entry = Allocator::alloc();
+ new_entry->next = nullptr;
+ new_entry->element = element;
+ if (tail_ == nullptr) {
+ tail_ = head_ = new_entry;
+ } else {
+ tail_->next = new_entry;
+ tail_ = new_entry;
+ }
+ }
+
+ T* pop_front() {
+ if (head_ == nullptr) {
+ return nullptr;
+ }
+
+ LinkedListEntry<T>* entry = head_;
+ T* element = entry->element;
+ head_ = entry->next;
+ Allocator::free(entry);
+
+ if (head_ == nullptr) {
+ tail_ = nullptr;
+ }
+
+ return element;
+ }
+
+ T* front() const {
+ if (head_ == nullptr) {
+ return nullptr;
+ }
+
+ return head_->element;
}
void clear() {
head_ = head_->next;
Allocator::free(p);
}
+
+ tail_ = nullptr;
}
template<typename F>
- void for_each(F&& action) {
+ void for_each(F action) const {
+ visit([&] (T* si) {
+ action(si);
+ return true;
+ });
+ }
+
+ template<typename F>
+ bool visit(F action) const {
for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
- if (e->element != nullptr) {
- action(e->element);
+ if (!action(e->element)) {
+ return false;
}
}
+ return true;
}
template<typename F>
- void remove_if(F&& predicate) {
+ void remove_if(F predicate) {
+ for (LinkedListEntry<T>* e = head_, *p = nullptr; e != nullptr;) {
+ if (predicate(e->element)) {
+ LinkedListEntry<T>* next = e->next;
+ if (p == nullptr) {
+ head_ = next;
+ } else {
+ p->next = next;
+ }
+ Allocator::free(e);
+ e = next;
+ } else {
+ p = e;
+ e = e->next;
+ }
+ }
+ }
+
+ size_t copy_to_array(T* array[], size_t array_length) const {
+ size_t sz = 0;
+ for (LinkedListEntry<T>* e = head_; sz < array_length && e != nullptr; e = e->next) {
+ array[sz++] = e->element;
+ }
+
+ return sz;
+ }
+
+ bool contains(const T* el) const {
for (LinkedListEntry<T>* e = head_; e != nullptr; e = e->next) {
- if (e->element != nullptr && predicate(e->element)) {
- e->element = nullptr;
+ if (e->element == el) {
+ return true;
}
}
+ return false;
+ }
+
+ static LinkedList make_list(T* const element) {
+ LinkedList<T, Allocator> one_element_list;
+ one_element_list.push_back(element);
+ return one_element_list;
}
private:
LinkedListEntry<T>* head_;
+ LinkedListEntry<T>* tail_;
DISALLOW_COPY_AND_ASSIGN(LinkedList);
};