DoublyLinkedList.h

#pragma once
 
#include <cstddef>
 
namespace CesiumUtility {
 
template <class T> class DoublyLinkedListPointers final {
public:
  DoublyLinkedListPointers() noexcept : pNext(nullptr), pPrevious(nullptr) {}
 
  // Following the example of boost::instrusive::list's list_member_hook, the
  // copy constructor and assignment operator do nothing.
  // https://www.boost.org/doc/libs/1_73_0/doc/html/boost/intrusive/list_member_hook.html
  DoublyLinkedListPointers(DoublyLinkedListPointers& rhs) noexcept
      : DoublyLinkedListPointers() {}
 
  DoublyLinkedListPointers&
  operator=(const DoublyLinkedListPointers& /*rhs*/) noexcept {
    return *this;
  }
 
private:
  template <
      typename TElement,
      typename TElementBase,
      DoublyLinkedListPointers<TElement>(TElementBase::*Pointers)>
  friend class DoublyLinkedListAdvanced;
 
  T* pNext;
  T* pPrevious;
};
 
template <
    typename T,
    typename TPointerBase,
    DoublyLinkedListPointers<T>(TPointerBase::*Pointers)>
class DoublyLinkedListAdvanced final {
public:
  void remove(T& node) noexcept {
    DoublyLinkedListPointers<T>& nodePointers = node.*Pointers;
 
    if (nodePointers.pPrevious) {
      DoublyLinkedListPointers<T>& previousPointers =
          nodePointers.pPrevious->*Pointers;
      previousPointers.pNext = nodePointers.pNext;
      --this->_size;
    } else if (this->_pHead == &node) {
      this->_pHead = nodePointers.pNext;
      --this->_size;
    }
 
    if (nodePointers.pNext) {
      DoublyLinkedListPointers<T>& nextPointers = nodePointers.pNext->*Pointers;
      nextPointers.pPrevious = nodePointers.pPrevious;
    } else if (this->_pTail == &node) {
      this->_pTail = nodePointers.pPrevious;
    }
 
    nodePointers.pPrevious = nullptr;
    nodePointers.pNext = nullptr;
  }
 
  void insertAfter(T& after, T& node) noexcept {
    this->remove(node);
 
    DoublyLinkedListPointers<T>& afterPointers = after.*Pointers;
    DoublyLinkedListPointers<T>& nodePointers = node.*Pointers;
 
    nodePointers.pPrevious = &after;
    nodePointers.pNext = afterPointers.pNext;
    afterPointers.pNext = &node;
 
    if (nodePointers.pNext) {
      DoublyLinkedListPointers<T>& nextPointers = nodePointers.pNext->*Pointers;
      nextPointers.pPrevious = &node;
    }
 
    if (this->_pTail == &after) {
      this->_pTail = &node;
    }
 
    ++this->_size;
  }
 
  void insertBefore(T& before, T& node) noexcept {
    this->remove(node);
 
    DoublyLinkedListPointers<T>& beforePointers = before.*Pointers;
    DoublyLinkedListPointers<T>& nodePointers = node.*Pointers;
 
    nodePointers.pPrevious = beforePointers.pPrevious;
    nodePointers.pNext = &before;
    beforePointers.pPrevious = &node;
 
    if (nodePointers.pPrevious) {
      DoublyLinkedListPointers<T>& previousPointers =
          nodePointers.pPrevious->*Pointers;
      previousPointers.pNext = &node;
    }
 
    if (this->_pHead == &before) {
      this->_pHead = &node;
    }
 
    ++this->_size;
  }
 
  void insertAtHead(T& node) noexcept {
    this->remove(node);
 
    if (this->_pHead) {
      (this->_pHead->*Pointers).pPrevious = &node;
      (node.*Pointers).pNext = this->_pHead;
    } else {
      this->_pTail = &node;
    }
    this->_pHead = &node;
 
    ++this->_size;
  }
 
  void insertAtTail(T& node) noexcept {
    this->remove(node);
 
    if (this->_pTail) {
      (this->_pTail->*Pointers).pNext = &node;
      (node.*Pointers).pPrevious = this->_pTail;
    } else {
      this->_pHead = &node;
    }
    this->_pTail = &node;
 
    ++this->_size;
  }
 
  size_t size() const noexcept { return this->_size; }
 
  T* head() noexcept { return this->_pHead; }
 
  const T* head() const noexcept { return this->_pHead; }
 
  T* tail() noexcept { return this->_pTail; }
 
  const T* tail() const noexcept { return this->_pTail; }
 
  T* next(T& node) noexcept { return (node.*Pointers).pNext; }
 
  const T* next(const T& node) const noexcept { return (node.*Pointers).pNext; }
 
  T* next(T* pNode) noexcept {
    return pNode ? this->next(*pNode) : this->_pHead;
  }
 
  const T* next(const T* pNode) const noexcept {
    return pNode ? this->next(*pNode) : this->_pHead;
  }
 
  T* previous(T& node) noexcept { return (node.*Pointers).pPrevious; }
 
  const T* previous(const T& node) const noexcept {
    return (node.*Pointers).pPrevious;
  }
 
  T* previous(T* pNode) {
    return pNode ? this->previous(*pNode) : this->_pTail;
  }
 
  const T* previous(const T* pNode) const noexcept {
    return pNode ? this->previous(*pNode) : this->_pTail;
  }
 
  bool contains(const T& node) const {
    return this->next(node) != nullptr || this->previous(node) != nullptr ||
           this->_pHead == &node;
  }
 
private:
  size_t _size = 0;
  T* _pHead = nullptr;
  T* _pTail = nullptr;
};
 
template <typename T, DoublyLinkedListPointers<T>(T::*Pointers)>
using DoublyLinkedList = DoublyLinkedListAdvanced<T, T, Pointers>;
 
} // namespace CesiumUtility