LinkedList.h 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203
  1. #ifndef CORE_LINKED_LIST_H
  2. #define CORE_LINKED_LIST_H
  3. #include "utils/ArrayString.h"
  4. namespace Core {
  5. template<typename T>
  6. struct LinkedList final {
  7. class Node {
  8. friend LinkedList;
  9. Node* next;
  10. Node* previous;
  11. public:
  12. T data;
  13. template<typename... Args>
  14. Node(Args&&... args)
  15. : next(nullptr), previous(nullptr),
  16. data(Core::forward<Args>(args)...) {
  17. }
  18. };
  19. template<typename NT, typename R>
  20. struct IteratorBase final {
  21. NT* current;
  22. public:
  23. IteratorBase& operator++() {
  24. current = current->next;
  25. return *this;
  26. }
  27. bool operator!=(const IteratorBase& other) const {
  28. return current != other.current;
  29. }
  30. R& operator*() const {
  31. return current->data;
  32. }
  33. };
  34. using Iterator = IteratorBase<Node, T>;
  35. using ConstIterator = IteratorBase<const Node, const T>;
  36. private:
  37. Node* first;
  38. Node* last;
  39. int length;
  40. public:
  41. LinkedList() : first(nullptr), last(nullptr), length(0) {
  42. }
  43. LinkedList(const LinkedList& other) = delete;
  44. LinkedList(LinkedList&& other) : LinkedList() {
  45. swap(other);
  46. }
  47. ~LinkedList() {
  48. clear();
  49. }
  50. LinkedList& operator=(const LinkedList& other) = delete;
  51. LinkedList& operator=(LinkedList&& other) {
  52. swap(other);
  53. return *this;
  54. }
  55. // returns true on error and calls the error callback
  56. check_return bool copyFrom(const LinkedList& other) {
  57. LinkedList copy;
  58. for(const T& t : other) {
  59. if(copy.add(t) == nullptr) {
  60. return true;
  61. }
  62. }
  63. swap(copy);
  64. return false;
  65. }
  66. // returns a nullptr on error and calls the error callback
  67. template<typename... Args>
  68. check_return Node* add(Args&&... args) {
  69. Node* n = new Node(Core::forward<Args>(args)...);
  70. if(n == nullptr) {
  71. CORE_ERROR(Error::OUT_OF_MEMORY);
  72. return nullptr;
  73. }
  74. length++;
  75. if(first == nullptr) {
  76. first = n;
  77. last = n;
  78. return n;
  79. }
  80. last->next = n;
  81. n->previous = last;
  82. last = n;
  83. return n;
  84. }
  85. Iterator begin() {
  86. return {first};
  87. }
  88. Iterator end() {
  89. return {nullptr};
  90. }
  91. ConstIterator begin() const {
  92. return {first};
  93. }
  94. ConstIterator end() const {
  95. return {nullptr};
  96. }
  97. int getLength() const {
  98. return length;
  99. }
  100. void clear() {
  101. Node* n = first;
  102. while(n != nullptr) {
  103. Node* next = n->next;
  104. delete n;
  105. n = next;
  106. }
  107. length = 0;
  108. first = nullptr;
  109. last = nullptr;
  110. }
  111. // returns true on error and calls the error callback
  112. template<int L>
  113. check_return bool toString(ArrayString<L>& s) const {
  114. if(s.append("[")) {
  115. return true;
  116. }
  117. auto iter = begin();
  118. for(int i = 0; i < length - 1; i++) {
  119. if(s.append(*iter) || s.append(", ")) {
  120. return true;
  121. }
  122. ++iter;
  123. }
  124. if(length > 0 && s.append(*iter)) {
  125. return true;
  126. }
  127. return s.append("]");
  128. }
  129. void remove(Node*& n) {
  130. if(n == nullptr) {
  131. return;
  132. }
  133. if(n == first) {
  134. if(first->next != nullptr) {
  135. first->next->previous = nullptr;
  136. }
  137. first = first->next;
  138. }
  139. if(n == last) {
  140. if(last->previous != nullptr) {
  141. last->previous->next = nullptr;
  142. }
  143. last = last->previous;
  144. }
  145. if(n->previous != nullptr) {
  146. n->previous->next = n->next;
  147. }
  148. if(n->next != nullptr) {
  149. n->next->previous = n->previous;
  150. }
  151. length--;
  152. delete n;
  153. n = nullptr;
  154. }
  155. void removeFirst() {
  156. Node* n = first; // prevent first from becoming null
  157. remove(n);
  158. }
  159. void removeLast() {
  160. Node* n = last; // prevent last from becoming null
  161. remove(n);
  162. }
  163. private:
  164. void swap(LinkedList& other) {
  165. Core::swap(first, other.first);
  166. Core::swap(last, other.last);
  167. Core::swap(length, other.length);
  168. }
  169. };
  170. }
  171. #endif