/////////////////////////////////////////////////////////////////////////////// 
// Copyright (C) 2002-2016, Open Design Alliance (the "Alliance"). 
// All rights reserved. 
// 
// This software and its documentation and related materials are owned by 
// the Alliance. The software may only be incorporated into application 
// programs owned by members of the Alliance, subject to a signed 
// Membership Agreement and Supplemental Software License Agreement with the
// Alliance. The structure and organization of this software are the valuable  
// trade secrets of the Alliance and its suppliers. The software is also 
// protected by copyright law and international treaty provisions. Application  
// programs incorporating this software must include the following statement 
// with their copyright notices:
//   
//   This application incorporates Teigha(R) software pursuant to a license 
//   agreement with Open Design Alliance.
//   Teigha(R) Copyright (C) 2002-2016 by Open Design Alliance. 
//   All rights reserved.
//
// By use of this software, its documentation or related materials, you 
// acknowledge and accept the above terms.
///////////////////////////////////////////////////////////////////////////////

#ifndef _ODA_UNIDIRECTIONALLISTT_H_
#define _ODA_UNIDIRECTIONALLISTT_H_

#include "OdArrayMemAlloc.h"

#include "TD_PackPush.h"

template<class T, class A = OdObjectsAllocator<T>, class Mm = OdrxMemoryManager> class OdUnidirectionalList;

/** \details
    This class declares the unidirectional list.
    Library:  TD_Db
    <group Other_Classes> 
*/
template<class T, class A, class Mm>
class OdUnidirectionalList
{
  struct SNode
  {
    SNode()
    : m_pNext(NULL)
    {
    }

  public:
    SNode* m_pNext;
    T m_value;
  };

  class CmpValues
  {
  public:
    CmpValues(const T& value)
    : m_value(value) 
    {
    }

    bool operator()(const T& value) const
    {
      return (m_value == value);
    }

  protected:
    const T& m_value;
  };

public:
  class ConstIterator
  {
  public:
    ConstIterator(SNode* pNode = NULL)
    : m_pNode(pNode)
    {
    }

    const T& operator*() const
    {
      ODA_ASSERT(m_pNode != NULL);

      return m_pNode->m_value;
    }

    const T* operator->() const
    {
      ODA_ASSERT(m_pNode != NULL);

      return &(m_pNode->m_value);
    }

    ConstIterator& operator++()
    {
      ODA_ASSERT(m_pNode != NULL);

      m_pNode = m_pNode->m_pNext;

      return *this;
    }

    ConstIterator operator++(int)
    {
      ODA_ASSERT(m_pNode != NULL);

      return ConstIterator(m_pNode->m_pNext);
    }

    bool operator==(const ConstIterator& it) const
    {
      return (m_pNode == it.m_pNode);
    }

    bool operator!=(const ConstIterator& it) const
    {
      return (m_pNode != it.m_pNode);
    }

    SNode* node()
    {
      return m_pNode;
    }

    void setNode(SNode* pNode)
    {
      m_pNode = pNode;
    }

  private:
    ConstIterator& operator--()
    {
      return *this;
    }

    ConstIterator operator--(int)
    {
      return ConstIterator();
    }

  protected:
    SNode* m_pNode;
  };

  class Iterator : public ConstIterator
  {
  public:
    Iterator(SNode* pNode = NULL)
    : ConstIterator(pNode)
    {
    }

    T& operator*()
    {
      ODA_ASSERT(ConstIterator::m_pNode != NULL);

      return ConstIterator::m_pNode->m_value;
    }

    T* operator->()
    {
      ODA_ASSERT(ConstIterator::m_pNode != NULL);

      return &(ConstIterator::m_pNode->m_value);
    }

    Iterator& operator++()
    {
      ODA_ASSERT(ConstIterator::m_pNode != NULL);

      ConstIterator::m_pNode = ConstIterator::m_pNode->m_pNext;

      return *this;
    }

    Iterator operator++(int)
    {
      ODA_ASSERT(ConstIterator::m_pNode != NULL);

      return Iterator(ConstIterator::m_pNode->m_pNext);
    }

  private:
    Iterator& operator--()
    {
      return *this;
    }

    Iterator operator--(int)
    {
      return Iterator();
    }
  };

  typedef typename A::size_type size_type;
  typedef Iterator iterator;
  typedef ConstIterator const_iterator;

public:
  OdUnidirectionalList();
  OdUnidirectionalList(const OdUnidirectionalList& list);

  ~OdUnidirectionalList();

  OdUnidirectionalList& operator=(const OdUnidirectionalList& list);

  iterator begin();
  const_iterator begin() const;
  iterator end();
  const_iterator end() const;

  size_type size() const;

  bool isEmpty() const;

  iterator insertAfter(const_iterator it, const T& value = T());
  iterator insertAtBegin(const T& value = T());

  iterator removeAfter(const_iterator it);

  void clear();

  bool find(iterator& it, iterator& prevIt, const T& value
    , const_iterator prevStartIt = const_iterator()) const;
  bool find(iterator& it, const T& value) const;
  
  template<class P>
  bool findIf(iterator& it, iterator& prevIt, P pred
    , const_iterator prevStartIt = const_iterator()) const;
  template<class P>
  bool findIf(iterator& it, P pred) const;

  bool operator==(const OdUnidirectionalList& list) const;

protected:
  static SNode* createNode();
  static SNode* createNode(const T& value);

  static void destroyNode(SNode* pNode);

  static SNode* copyList(SNode* pNode);

private:
  SNode* m_pHead;
  size_type m_size;
};


template<class T, class A, class Mm>
inline OdUnidirectionalList<T, A, Mm>::OdUnidirectionalList()
: m_pHead(NULL), m_size(0)
{
}

template<class T, class A, class Mm>
inline OdUnidirectionalList<T, A, Mm>::OdUnidirectionalList(const OdUnidirectionalList<T, A, Mm>& list)
: m_pHead(copyList(list.m_pHead)), m_size(list.m_size)
{
}

template<class T, class A, class Mm>
inline OdUnidirectionalList<T, A, Mm>::~OdUnidirectionalList()
{
  clear();
}

template<class T, class A, class Mm>
inline OdUnidirectionalList<T, A, Mm>& OdUnidirectionalList<T, A, Mm>::operator=(const OdUnidirectionalList<T, A, Mm>& list)
{
  if(this != &list)
  {
    clear();

    m_pHead = copyList(list.m_pHead);
    m_size = list.m_size;
  }

  return *this;
}

template<class T, class A, class Mm>
inline typename OdUnidirectionalList<T, A, Mm>::SNode* OdUnidirectionalList<T, A, Mm>::createNode()
{
  SNode* pNewNode = reinterpret_cast<SNode*>(Mm::Alloc(sizeof(SNode)));

  if(pNewNode == NULL)
    throw OdError(eOutOfMemory);

  A::construct(&(pNewNode->m_value));

  return pNewNode;
}

template<class T, class A, class Mm>
inline typename OdUnidirectionalList<T, A, Mm>::SNode* OdUnidirectionalList<T, A, Mm>::createNode(const T& value)
{
  SNode* pNewNode = reinterpret_cast<SNode*>(Mm::Alloc(sizeof(SNode)));

  if(pNewNode == NULL)
    throw OdError(eOutOfMemory);

  A::construct(&(pNewNode->m_value), value);

  return pNewNode;
}

template<class T, class A, class Mm>
inline void OdUnidirectionalList<T, A, Mm>::destroyNode(SNode* pNode)
{
  ODA_ASSERT(pNode != NULL);

  A::destroy(&(pNode->m_value));

  Mm::Free(pNode);
}

template<class T, class A, class Mm>
inline typename OdUnidirectionalList<T, A, Mm>::SNode* OdUnidirectionalList<T, A, Mm>::copyList(SNode* pNode)
{
  SNode* pHead = NULL;

  if(pNode != NULL)
  {
    SNode* pNewNode = pHead = createNode(pNode->m_value);

    pNewNode->m_pNext = NULL;

    for(pNode = pNode->m_pNext; pNode != NULL; pNode = pNode->m_pNext)
    {
      pNewNode->m_pNext = createNode(pNode->m_value);

      pNewNode->m_pNext->m_pNext = NULL;

      pNewNode = pNewNode->m_pNext;
    }
  }

  return pHead;
}

template<class T, class A, class Mm>
inline typename OdUnidirectionalList<T, A, Mm>::iterator OdUnidirectionalList<T, A, Mm>::begin()
{
  return iterator(m_pHead);
}

template<class T, class A, class Mm>
inline typename OdUnidirectionalList<T, A, Mm>::const_iterator OdUnidirectionalList<T, A, Mm>::begin() const
{
  return const_iterator(m_pHead);
}

template<class T, class A, class Mm>
inline typename OdUnidirectionalList<T, A, Mm>::iterator OdUnidirectionalList<T, A, Mm>::end()
{
  return iterator();
}

template<class T, class A, class Mm>
inline typename OdUnidirectionalList<T, A, Mm>::const_iterator OdUnidirectionalList<T, A, Mm>::end() const
{
  return const_iterator();
}

template<class T, class A, class Mm>
inline typename OdUnidirectionalList<T, A, Mm>::size_type OdUnidirectionalList<T, A, Mm>::size() const
{
  return m_size;
}

template<class T, class A, class Mm>
inline bool OdUnidirectionalList<T, A, Mm>::isEmpty() const
{
  return (m_size == 0);
}

template<class T, class A, class Mm>
inline typename OdUnidirectionalList<T, A, Mm>::iterator OdUnidirectionalList<T, A, Mm>::insertAfter(const_iterator it
  , const T& value)
{
  SNode* pNode = createNode(value);

  if(it.node() != NULL)
  {
    pNode->m_pNext = it.node()->m_pNext;
    it.node()->m_pNext = pNode;

  }
  else
  {
    pNode->m_pNext = m_pHead;
    m_pHead = pNode;
  }
  
  ++m_size;

  return iterator(pNode);
}

template<class T, class A, class Mm>
inline typename OdUnidirectionalList<T, A, Mm>::iterator OdUnidirectionalList<T, A, Mm>::insertAtBegin(const T& value)
{
  SNode* pNode = createNode(value);

  pNode->m_pNext = m_pHead;
  m_pHead = pNode;
  
  ++m_size;

  return iterator(pNode);
}

template<class T, class A, class Mm>
inline typename OdUnidirectionalList<T, A, Mm>::iterator OdUnidirectionalList<T, A, Mm>::removeAfter(const_iterator it)
{
  if(it.node() != NULL)
  {
    SNode* pNode = it.node()->m_pNext;

    if(pNode != NULL)
    {
      it.node()->m_pNext = pNode->m_pNext;

      destroyNode(pNode);

      --m_size;
    }

    return iterator(it.node()->m_pNext);
  }

  SNode* pNode = m_pHead;

  m_pHead = m_pHead->m_pNext;

  destroyNode(pNode);
  
  --m_size;

  return iterator(m_pHead);
}

template<class T, class A, class Mm>
inline void OdUnidirectionalList<T, A, Mm>::clear()
{
  SNode* pNode;
  SNode* pNextNode;

  for(pNode = m_pHead; pNode != NULL; pNode = pNextNode)
  {
    pNextNode = pNode->m_pNext;

    destroyNode(pNode);
  }

  m_pHead = NULL;
  m_size = 0;
}

template<class T, class A, class Mm>
inline bool OdUnidirectionalList<T, A, Mm>::find(iterator& it, iterator& prevIt
  , const T& value, const_iterator prevStartIt) const
{
  return find(it, prevIt, CmpValues(value), prevStartIt);
}

template<class T, class A, class Mm>
inline bool OdUnidirectionalList<T, A, Mm>::find(iterator& it, const T& value) const
{
  return find(it, CmpValues(value));
}

template<class T, class A, class Mm>
template<class P>
inline bool OdUnidirectionalList<T, A, Mm>::findIf(iterator& it, iterator& prevIt
  , P pred, const_iterator prevStartIt) const
{
  if(!isEmpty())
  {
    ODA_ASSERT(m_pHead != NULL);

    SNode* pPrevNode = prevStartIt.node();
    SNode* pNode = ((pPrevNode != NULL) ? pPrevNode->m_pNext : m_pHead);

    for(; pNode != NULL; pPrevNode = pNode, pNode = pNode->m_pNext)
    {
      if(pred(pNode->m_value))
      {
        it.setNode(pNode);
        prevIt.setNode(pPrevNode);

        return true;
      }
    }
  }

  return false;
}

template<class T, class A, class Mm>
template<class P>
inline bool OdUnidirectionalList<T, A, Mm>::findIf(iterator& it, P pred) const
{
  if(!isEmpty())
  {
    ODA_ASSERT(m_pHead != NULL);

    for(SNode* pNode = m_pHead; pNode != NULL; pNode = pNode->m_pNext)
    {
      if(pred(pNode->m_value))
      {
        it.setNode(pNode);

        return true;
      }
    }
  }

  return false;
}

template<class T, class A, class Mm>
inline bool OdUnidirectionalList<T, A, Mm>::operator==(const OdUnidirectionalList<T, A, Mm>& list) const
{
  if(m_size == list.m_size)
  {
    SNode* pNode1 = m_pHead;
    SNode* pNode2 = list.m_pHead;

    for(; pNode1 != NULL; pNode1 = pNode1->m_pNext, pNode2 = pNode2->m_pNext)
    {
      ODA_ASSERT(pNode2 != NULL);

      if(pNode1->m_value != pNode2->m_value)
        return false;
    }

    return true;
  }

  return false;
}

#include "TD_PackPop.h"

#endif // _ODA_UNIDIRECTIONALLISTT_H_