List.h

#pragma once
#include <cassert>
 
namespace Cogs::Core
{
 
  struct ListNode {
    ListNode* next = nullptr;
    ListNode* prev = nullptr;
 
    bool isFree() { return next == nullptr && prev == nullptr; }
  };
 
 
  template<typename T, size_t offset>
  struct List {
 
    // Maintains next-pointer so that it is safe to delete curr inside a loop
    struct Iterator
    {
      ListNode* curr = nullptr;
      ListNode* next = nullptr;
      bool operator!=(Iterator& other) { return curr != other.curr; }
      Iterator& operator++() { curr = next; next = next->next; return *this; }
      T* operator*() { return get(curr); }
    };
 
    List() {
      head.next = &tail;
      head.prev = nullptr;
      tail.next = nullptr;
      tail.prev = &head;
      myself = this;        // List doesn't support to be memmoved, so we verify that that hasn't happened.
      count = 0;
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
    }
 
    static T* get(ListNode* n)
    {
      return reinterpret_cast<T*>(reinterpret_cast<char*>(n) - offset);
    }
 
    void remove(T* item) {
      assert(myself == this);
      assert(item);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      auto* n = reinterpret_cast<ListNode*>(reinterpret_cast<char*>(item) + offset);
 
      assert(n->next);
      assert(n->next->prev == n);
      assert(n->next->next != n);
 
      assert(n->prev);
      assert(n->prev->next == n);
      assert(n->prev->prev != n);
 
      auto* prev = n->prev;
      auto* next = n->next;
 
      next->prev = prev;
      prev->next = next;
 
      n->next = nullptr;
      n->prev = nullptr;
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
    }
 
    T* push(T* item)
    {
      assert(myself == this);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      auto* n = reinterpret_cast<ListNode*>(reinterpret_cast<char*>(item) + offset);
 
      count++;
      assert(n->next == nullptr);
      assert(n->prev == nullptr);
      auto* prev = tail.prev;
      prev->next = n;
      n->prev = prev;
      tail.prev = n;
      n->next = &tail;
 
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      return item;
    }
 
    T* shift()
    {
      assert(myself == this);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      assert(0 < count);
      count--; 
 
      auto* n = head.next;
      assert(n != &tail);
      head.next = n->next;
      head.next->prev = n->prev;
      n->next = nullptr;
      n->prev = nullptr;
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      return get(n);
    }
 
    T* pop()
    {
      assert(myself == this);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      assert(0 < count);
      count--;
      auto* n = tail.prev;
      assert(n != &head);
      tail.prev = n->prev;
      tail.prev->next = n->next;
      n->next = nullptr;
      n->prev = nullptr;
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      return get(n);
    }
 
    bool empty() const {
      assert(myself == this);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      return head.next == &tail;
    }
 
    void swap(List& that)
    {
      assert(myself == this);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      assert(that.head.next != nullptr);
      assert(that.tail.prev != nullptr);
 
      auto* thisHeadNext = head.next;
      auto* thisTailPrev = tail.prev;
      auto* thatHeadNext = that.head.next;
      auto* thatTailPrev = that.tail.prev;
 
      if (thatHeadNext == &that.tail) {
        head.next = &tail;
        tail.prev = &head;
      }
      else {
        head.next = thatHeadNext;
        tail.prev = thatTailPrev;
        thatHeadNext->prev = &head;
        thatTailPrev->next = &tail;
      }
 
      if (thisHeadNext == &tail) {
        that.head.next = &that.tail;
        that.tail.prev = &that.head;
      }
      else {
        that.head.next = thisHeadNext;
        that.tail.prev = thisTailPrev;
        thisHeadNext->prev = &that.tail;
        thisTailPrev->next = &that.head;
      }
      std::swap(count, that.count);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      assert(that.head.next != nullptr);
      assert(that.tail.prev != nullptr);
    }
 
    ListNode head;
    ListNode tail;
    List* myself = nullptr;
    size_t count = 0;
 
    T* front() {
      assert(myself == this);
      assert(head.next != &tail);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      return get(head.next);
    }
 
    T* back() {
      assert(myself == this);
      assert(tail.prev != &head);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      return get(tail.prev);
    }
 
    const T* front() const {
      assert(myself == this);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      assert(head.next != &tail);
      return get(head.next);
    }
 
    const T* back() const {
      assert(myself == this);
      assert(tail.prev != &head);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      return get(tail.prev);
    }
 
    Iterator begin() {
      assert(myself == this);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      return Iterator{ head.next, head.next->next };
    }
 
    Iterator end() {
      assert(myself == this);
      assert(head.next != nullptr);
      assert(tail.prev != nullptr);
      return Iterator{ &tail, nullptr };
    }
 
  };
 
 
}