////////////////////////////////////////////
// Author: Reggie Meisler
// Brief: Singly and doubly linked
//        intrusive list classes. Much more
//        efficient than the traditional
//        std::list style implementation.
////////////////////////////////////////////
// Example use:
//
// class A
// {
//   public:
//
//     // A can be in multiple intrusive lists!
//     DLink<A> mLinkToBList;
//     SLink<A> mLinkToCList;
//
// };
//
// class B
// {
//   public:
//
//     IntrusiveDList<A, &A::mLinkToBList> mList;
//
// };
//
// class C
// {
//   public:
//
//     IntrusiveSList<A, &A::mLinkToCList> mList;
//
// };
//
////////////////////////////////////////////

#pragma once


namespace MF
{

template <typename T>
struct DLink
{
  T* next;
  T* prev;
};


template <typename T>
struct SLink
{
  T* next;
};


// Helper function, to grab member pointer offset value
// (Since member pointers are secretly just offsets from the this pointer,
//  all we do is cast the given value to an unsigned integer)
template<typename Parent, typename Member>
inline ptrdiff_t PointerToMemberOffset(const Member (Parent::*ptrToMember))
{
  return *(unsigned int*)(void*)&ptrToMember;
}


// Implementation class, allows for a lot of flexibility in its type definitions
template <typename T, typename U, template <typename Y> class LinkType, LinkType<T> (U::*linkPtr) = &U::link>
class BaseIntrusiveDList
{
  public:

    BaseIntrusiveDList()
    {
      Clear();
    }

    static void Unlink(T* node)
    {
      GetNext(GetPrev(node)) = GetNext(node);
      GetPrev(GetNext(node)) = GetPrev(node);
    }

    void PushBack(T* node)
    {
      // Insert node before dummy
      GetNext(node) = GetNode(mDummy);
      GetPrev(node) = mDummy.prev;
      mDummy.prev   = node;
      GetNext(GetPrev(node)) = node;
    }

    void PushFront(T* node)
    {
      // Insert node after dummy
      GetNext(node) = mDummy.next;
      mDummy.next   = node;
      GetPrev(node) = GetNode(mDummy);
      GetPrev(GetNext(node)) = node;
    }

    T* PopBack()
    {
      // Remove node from before dummy
      T* node = mDummy.prev;

      GetNext(GetPrev(mDummy.prev)) = GetNode(mDummy);
      mDummy.prev = GetPrev(mDummy.prev);

      return node;
    }

    T* PopFront()
    {
      // Remove node from after dummy
      T* node = mDummy.next;

      GetPrev(GetNext(mDummy.next)) = GetNode(mDummy);
      mDummy.next = GetNext(mDummy.next);

      return node;
    }

    // Cheap and dirty way of clearing out list
    void Clear()
    {
      mDummy.next = GetNode(mDummy);
      mDummy.prev = GetNode(mDummy);
    }

    T* GetFirst()
    {
      return mDummy.next;
    }

    T* GetLast()
    {
      return GetNode(mDummy);
    }

    bool Empty() const
    {
      return mDummy.next == GetNode(mDummy);
    }

    void Iterate(T*& itr)
    {
      itr = GetNext(itr);
    }

  protected:

    // Non-copyable
    BaseIntrusiveDList(const BaseIntrusiveDList&);
    void operator=(const BaseIntrusiveDList&);

    // Handy conversion functions from link to node and vice versa
    static LinkType<T>& GetLink(T* node)
    {
      return ((U*)node->*linkPtr);
    }

    static T*& GetNext(T* node)
    {
      return GetLink(node).next;
    }

    static T*& GetPrev(T* node)
    {
      return GetLink(node).prev;
    }

    static T* GetNode(LinkType<T>& link)
    {
      return (T*)((unsigned char*)&link - PointerToMemberOffset(linkPtr));
    }

    static const T* GetNode(const LinkType<T>& link)
    {
      return (T*)((unsigned char*)&link - PointerToMemberOffset(linkPtr));
    }

    LinkType<T>& GetDummy() const
    {
      return mDummy;
    }

  private:

    LinkType<T> mDummy;

};


// Implementation class, allows for a lot of flexibility in its type definitions
// - Optimized, non-circular, essentially acts like a stack
template <typename T, typename U, template <typename Y> class LinkType, LinkType<T> (U::*linkPtr) = &U::link>
class BaseIntrusiveSList
{
  public:

    BaseIntrusiveSList()
    {
      mDummy.next = GetNode(mDummy);
    }

    void PushFront(T* node)
    {
      // Push onto front of list
      GetNext(node) = mDummy.next;
      mDummy.next = node;
    }

    T* PopFront()
    {
      T* node = mDummy.next;
      mDummy.next = GetNext(mDummy.next);

      return node;
    }

    // Cheap and dirty way of clearing out list
    void Clear()
    {
      // Since we're an intrusive list, we are not responsible for memory cleanup!
      mDummy.next = GetNode(mDummy);
    }

    bool Contains(T* node) const
    {
      T* itr = GetNext(mDummy);

      // Empty list
      if( itr == NULL )
        return;

      // Loop around list looking for node
      while( itr != GetNode(mDummy) && GetNext(itr) != node )
      {
        itr = GetNext(itr);
      }

      return itr != GetNode(mDummy);
    }

    T* GetFirst()
    {
      return mDummy.next;
    }

    T* GetLast()
    {
      return GetNode(mDummy);
    }

    const T* GetFirst() const
    {
      return mDummy.next;
    }

    const T* GetLast() const
    {
      return GetNode(mDummy);
    }

    bool Empty()
    {
      return mDummy.next == GetNode(mDummy);
    }

    void Iterate(T*& itr)
    {
      itr = GetNext(itr);
    }

  protected:

    // Non-copyable
    BaseIntrusiveSList(const BaseIntrusiveSList&);
    void operator=(const BaseIntrusiveSList&);

    // Handy conversion functions from link to node and vice versa
    static LinkType<T>& GetLink(T* node)
    {
      return ((U*)node->*linkPtr);
    }

    static T*& GetNext(T* node)
    {
      return GetLink(node).next;
    }

    static T* GetNode(const SLink<T>& link)
    {
      return (T*)((unsigned char*)&link - PointerToMemberOffset(linkPtr));
    }

    LinkType<T>& GetDummy() const
    {
      return mDummy;
    }

  private:

    LinkType<T> mDummy;

};


// Common-use classes
template <typename T, DLink<T> (T::*linkPtr) = &T::mLink>
class IntrusiveDList : public BaseIntrusiveDList<T, T, DLink, linkPtr> {};

template <typename T, SLink<T> (T::*linkPtr) = &T::mLink>
class IntrusiveSList : public BaseIntrusiveSList<T, T, SLink, linkPtr> {};

}