OCCT

// Created on: 2002-04-17
// Created by: Alexander Kartomin (akm)
// Copyright (c) 2002-2014 OPEN CASCADE SAS
//
// This file is part of Open CASCADE Technology software library.
//
// This library is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License version 2.1 as published
// by the Free Software Foundation, with special exception defined in the file
// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
// distribution for complete text of the license and disclaimer of any warranty.
//
// Alternatively, this file may be used under the terms of Open CASCADE
// commercial license or contractual agreement.

#ifndef NCollection_List_HeaderFile
#define NCollection_List_HeaderFile

#include <NCollection_BaseList.hxx>
#include <NCollection_TListNode.hxx>

#include <Standard_NoSuchObject.hxx>

#include <cstddef>
#include <initializer_list>
#include <type_traits>

/**
 * Purpose:      Simple list to link  items together keeping the first
 *               and the last one.
 *               Inherits BaseList, adding the data item to each node.
 */
template <class TheItemType>
class NCollection_List : public NCollection_BaseList
{
public:
  //! STL-compliant typedef for value type
  typedef TheItemType value_type;
  using size_type       = size_t;
  using difference_type = std::ptrdiff_t;
  using pointer         = TheItemType*;
  using const_pointer   = const TheItemType*;
  using reference       = TheItemType&;
  using const_reference = const TheItemType&;

public:
  typedef NCollection_TListNode<TheItemType> ListNode;
  using iterator       = NCollection_BaseList::BasicIterator<ListNode, TheItemType, false>;
  using const_iterator = NCollection_BaseList::BasicIterator<ListNode, TheItemType, true>;

  //! Legacy OCCT cursor backed by the standard iterator state.
  class Iterator : public iterator
  {
  public:
    Iterator() noexcept = default;

    explicit Iterator(NCollection_List& theList) noexcept
        : iterator(theList)
    {
    }

    Iterator(const NCollection_List& theList) noexcept
        : iterator(const_cast<NCollection_List&>(theList))
    {
    }

    //! Legacy conversion preserving the historical mutable cursor API.
    Iterator(const const_iterator& theOther) noexcept
        : iterator()
    {
      this->myCurrent  = theOther.myCurrent;
      this->myPrevious = theOther.myPrevious;
    }

    //! Legacy assignment preserving the historical mutable cursor API.
    Iterator& operator=(const const_iterator& theOther) noexcept
    {
      this->myCurrent  = theOther.myCurrent;
      this->myPrevious = theOther.myPrevious;
      return *this;
    }

    void Init(NCollection_List& theList) noexcept { *this = Iterator(theList); }

    void Init(const NCollection_List& theList) noexcept { *this = Iterator(theList); }

    void Initialize(NCollection_List& theList) noexcept { Init(theList); }

    void Initialize(const NCollection_List& theList) noexcept { Init(theList); }

    bool IsEqual(const Iterator& theOther) const noexcept
    {
      return iterator::operator==(static_cast<const iterator&>(theOther));
    }
  };

  //! Returns an iterator pointing to the first element in the list.
  iterator begin() noexcept { return iterator(*this); }

  //! Returns an iterator referring to the past-the-end element in the list.
  iterator end() noexcept { return iterator(); }

  //! Returns a const iterator pointing to the first element in the list.
  const_iterator begin() const noexcept { return const_iterator(*this); }

  //! Returns a const iterator referring to the past-the-end element in the list.
  const_iterator end() const noexcept { return const_iterator(); }

  //! Returns a const iterator pointing to the first element in the list.
  const_iterator cbegin() const noexcept { return begin(); }

  //! Returns a const iterator referring to the past-the-end element in the list.
  const_iterator cend() const noexcept { return const_iterator(); }

public:
  // ---------- PUBLIC METHODS ------------

  //! Empty constructor.
  NCollection_List()
      : NCollection_BaseList(occ::handle<NCollection_BaseAllocator>())
  {
  }

  //! Constructor
  explicit NCollection_List(const occ::handle<NCollection_BaseAllocator>& theAllocator)
      : NCollection_BaseList(theAllocator)
  {
  }

  //! Copy constructor
  NCollection_List(const NCollection_List& theOther)
      : NCollection_BaseList(theOther.myAllocator)
  {
    appendList(theOther.pFirst());
  }

  //! Move constructor
  NCollection_List(NCollection_List&& theOther) noexcept
      : NCollection_BaseList(theOther.myAllocator)
  {
    myFirst          = theOther.myFirst;
    myLast           = theOther.myLast;
    myLength         = theOther.myLength;
    theOther.myFirst = theOther.myLast = nullptr;
    theOther.myLength                  = 0;
  }

  //! Initializer list constructor
  //! @param theInitList initializer list of elements to populate the list
  //! @param theAllocator optional allocator for memory management
  NCollection_List(std::initializer_list<TheItemType>            theInitList,
                   const occ::handle<NCollection_BaseAllocator>& theAllocator =
                     occ::handle<NCollection_BaseAllocator>())
      : NCollection_BaseList(theAllocator)
  {
    for (const auto& anItem : theInitList)
    {
      Append(anItem);
    }
  }

  //! Replace this list by the items of another list (theOther parameter).
  //! This method does not change the internal allocator.
  NCollection_List& Assign(const NCollection_List& theOther)
  {
    if (this != &theOther)
    {
      Clear();
      appendList(theOther.pFirst());
    }
    return *this;
  }

  //! Replacement operator
  NCollection_List& operator=(const NCollection_List& theOther) { return Assign(theOther); }

  //! Move operator
  NCollection_List& operator=(NCollection_List&& theOther) noexcept
  {
    if (this == &theOther)
    {
      return *this;
    }
    Clear(theOther.myAllocator);
    myFirst          = theOther.myFirst;
    myLast           = theOther.myLast;
    myLength         = theOther.myLength;
    theOther.myFirst = theOther.myLast = nullptr;
    theOther.myLength                  = 0;
    return *this;
  }

  //! Clear this list
  void Clear(const occ::handle<NCollection_BaseAllocator>& theAllocator = nullptr)
  {
    pClear(ListNode::delNode);
    if (!theAllocator.IsNull())
      this->myAllocator = theAllocator;
  }

  //! First item
  const TheItemType& First() const
  {
    Standard_NoSuchObject_Raise_if(IsEmpty(), "NCollection_List::First");
    return ((const ListNode*)pFirst())->Value();
  }

  //! First item (non-const)
  TheItemType& First()
  {
    Standard_NoSuchObject_Raise_if(IsEmpty(), "NCollection_List::First");
    return ((ListNode*)pFirst())->ChangeValue();
  }

  //! Last item
  const TheItemType& Last() const
  {
    Standard_NoSuchObject_Raise_if(IsEmpty(), "NCollection_List::Last");
    return ((const ListNode*)pLast())->Value();
  }

  //! Last item (non-const)
  TheItemType& Last()
  {
    Standard_NoSuchObject_Raise_if(IsEmpty(), "NCollection_List::Last");
    return ((ListNode*)pLast())->ChangeValue();
  }

  //! Append one item at the end
  TheItemType& Append(const TheItemType& theItem)
  {
    ListNode* pNew = new (this->myAllocator) ListNode(theItem);
    pAppend(pNew);
    return ((ListNode*)pLast())->ChangeValue();
  }

  //! Append one item at the end
  TheItemType& Append(TheItemType&& theItem)
  {
    ListNode* pNew = new (this->myAllocator) ListNode(std::forward<TheItemType>(theItem));
    pAppend(pNew);
    return ((ListNode*)pLast())->ChangeValue();
  }

  //! Append one item at the end and output iterator
  //!   pointing at the appended item
  void Append(const TheItemType& theItem, Iterator& theIter)
  {
    ListNode* pNew = new (this->myAllocator) ListNode(theItem);
    pAppend(pNew, theIter);
  }

  //! Append one item at the end and output iterator
  //!   pointing at the appended item
  void Append(TheItemType&& theItem, Iterator& theIter)
  {
    ListNode* pNew = new (this->myAllocator) ListNode(std::forward<TheItemType>(theItem));
    pAppend(pNew, theIter);
  }

  //! Append another list at the end.
  //! After this operation, theOther list will be cleared.
  void Append(NCollection_List& theOther)
  {
    if (this == &theOther || theOther.Extent() < 1)
      return;
    if (this->myAllocator == theOther.myAllocator)
    {
      // Then we take the list and glue it to our end -
      // deallocation will bring no problem
      pAppend(theOther);
    }
    else
    {
      // No - this list has different memory scope
      appendList(theOther.myFirst);
      theOther.Clear();
    }
  }

  //! Prepend one item at the beginning
  TheItemType& Prepend(const TheItemType& theItem)
  {
    ListNode* pNew = new (this->myAllocator) ListNode(theItem);
    pPrepend(pNew);
    return ((ListNode*)pFirst())->ChangeValue();
  }

  //! Prepend one item at the beginning
  TheItemType& Prepend(TheItemType&& theItem)
  {
    ListNode* pNew = new (this->myAllocator) ListNode(std::forward<TheItemType>(theItem));
    pPrepend(pNew);
    return ((ListNode*)pFirst())->ChangeValue();
  }

  //! Prepend another list at the beginning
  void Prepend(NCollection_List& theOther)
  {
    if (this == &theOther || theOther.Extent() < 1)
      return;
    if (this->myAllocator == theOther.myAllocator)
    {
      // Then we take the list and glue it to our head -
      // deallocation will bring no problem
      pPrepend(theOther);
    }
    else
    {
      // No - this list has different memory scope
      Iterator it(*this);
      prependList(theOther.pFirst(), it);
      theOther.Clear();
    }
  }

  //! RemoveFirst item
  void RemoveFirst() { pRemoveFirst(ListNode::delNode); }

  //! Remove item pointed by iterator theIter;
  //! theIter is then set to the next item
  void Remove(Iterator& theIter) { pRemove(theIter, ListNode::delNode); }

  //! Remove the first occurrence of the object.
  template <typename TheValueType> // instantiate this method on first call only for types defining
                                   // equality operator
  bool Remove(const TheValueType& theObject)
  {
    for (Iterator anIter(*this); anIter.More(); anIter.Next())
    {
      if (anIter.Value() == theObject)
      {
        Remove(anIter);
        return true;
      }
    }
    return false;
  }

  //! InsertBefore
  TheItemType& InsertBefore(const TheItemType& theItem, Iterator& theIter)
  {
    ListNode* pNew = new (this->myAllocator) ListNode(theItem);
    pInsertBefore(pNew, theIter);
    return pNew->ChangeValue();
  }

  //! InsertBefore
  TheItemType& InsertBefore(TheItemType&& theItem, Iterator& theIter)
  {
    ListNode* pNew = new (this->myAllocator) ListNode(std::forward<TheItemType>(theItem));
    pInsertBefore(pNew, theIter);
    return pNew->ChangeValue();
  }

  //! InsertBefore
  void InsertBefore(NCollection_List& theOther, Iterator& theIter)
  {
    if (this == &theOther)
      return;

    if (this->myAllocator == theOther.myAllocator)
    {
      // Then we take the list and glue it to our head -
      // deallocation will bring no problem
      pInsertBefore(theOther, theIter);
    }
    else
    {
      // No - this list has different memory scope
      prependList(theOther.myFirst, theIter);
      theOther.Clear();
    }
  }

  //! InsertAfter
  TheItemType& InsertAfter(const TheItemType& theItem, Iterator& theIter)
  {
    ListNode* pNew = new (this->myAllocator) ListNode(theItem);
    pInsertAfter(pNew, theIter);
    return pNew->ChangeValue();
  }

  //! InsertAfter
  TheItemType& InsertAfter(TheItemType&& theItem, Iterator& theIter)
  {
    ListNode* pNew = new (this->myAllocator) ListNode(std::forward<TheItemType>(theItem));
    pInsertAfter(pNew, theIter);
    return pNew->ChangeValue();
  }

  //! InsertAfter
  void InsertAfter(NCollection_List& theOther, Iterator& theIter)
  {
    if (!theIter.More())
    {
      Append(theOther);
      return;
    }
    if (this->myAllocator == theOther.myAllocator)
    {
      // Then we take the list and glue it to our head -
      // deallocation will bring no problem
      pInsertAfter(theOther, theIter);
    }
    else
    {
      // No - this list has different memory scope
      Iterator anIter;
      anIter.myPrevious = theIter.myCurrent;
      anIter.myCurrent  = theIter.myCurrent->Next();
      prependList(theOther.pFirst(), anIter);
      theOther.Clear();
    }
  }

  //! Emplace one item at the end, constructing it in-place
  //! @param theArgs arguments forwarded to TheItemType constructor
  //! @return reference to the newly constructed item
  template <typename... Args>
  TheItemType& EmplaceAppend(Args&&... theArgs)
  {
    ListNode* pNew =
      new (this->myAllocator) ListNode(std::in_place, nullptr, std::forward<Args>(theArgs)...);
    pAppend(pNew);
    return ((ListNode*)pLast())->ChangeValue();
  }

  //! Emplace one item at the beginning, constructing it in-place
  //! @param theArgs arguments forwarded to TheItemType constructor
  //! @return reference to the newly constructed item
  template <typename... Args>
  TheItemType& EmplacePrepend(Args&&... theArgs)
  {
    ListNode* pNew =
      new (this->myAllocator) ListNode(std::in_place, nullptr, std::forward<Args>(theArgs)...);
    pPrepend(pNew);
    return ((ListNode*)pFirst())->ChangeValue();
  }

  //! Emplace one item before the iterator position, constructing it in-place
  //! @param theIter iterator pointing to the position before which to insert
  //! @param theArgs arguments forwarded to TheItemType constructor
  //! @return reference to the newly constructed item
  template <typename... Args>
  TheItemType& EmplaceBefore(Iterator& theIter, Args&&... theArgs)
  {
    ListNode* pNew =
      new (this->myAllocator) ListNode(std::in_place, nullptr, std::forward<Args>(theArgs)...);
    pInsertBefore(pNew, theIter);
    return pNew->ChangeValue();
  }

  //! Emplace one item after the iterator position, constructing it in-place
  //! @param theIter iterator pointing to the position after which to insert
  //! @param theArgs arguments forwarded to TheItemType constructor
  //! @return reference to the newly constructed item
  template <typename... Args>
  TheItemType& EmplaceAfter(Iterator& theIter, Args&&... theArgs)
  {
    ListNode* pNew =
      new (this->myAllocator) ListNode(std::in_place, nullptr, std::forward<Args>(theArgs)...);
    pInsertAfter(pNew, theIter);
    return pNew->ChangeValue();
  }

  //! Reverse the list
  void Reverse() noexcept { pReverse(); }

  //! Exchange the content of two lists without re-allocations.
  //! Swaps all internal state including allocators, ensuring correct
  //! deallocation. Existing iterators remain valid but will point to
  //! the other list's elements.
  void Exchange(NCollection_List& theOther) noexcept { pExchange(theOther); }

  //! Return true if object is stored in the list.
  template <typename TheValueType> // instantiate this method on first call only for types defining
                                   // equality operator
  bool Contains(const TheValueType& theObject) const
  {
    for (Iterator anIter(*this); anIter.More(); anIter.Next())
    {
      if (anIter.Value() == theObject)
      {
        return true;
      }
    }
    return false;
  }

  //! Destructor - clears the List
  ~NCollection_List() { Clear(); }

private:
  // ----------- PRIVATE METHODS -----------

  //! append the list headed by the given ListNode
  void appendList(const NCollection_ListNode* pCur)
  {
    while (pCur)
    {
      NCollection_ListNode* pNew =
        new (this->myAllocator) ListNode(((const ListNode*)(pCur))->Value());
      pAppend(pNew);
      pCur = pCur->Next();
    }
  }

  //! insert the list headed by the given ListNode before the given iterator
  void prependList(const NCollection_ListNode* pCur, Iterator& theIter)
  {
    while (pCur)
    {
      NCollection_ListNode* pNew =
        new (this->myAllocator) ListNode(((const ListNode*)(pCur))->Value());
      pInsertBefore(pNew, theIter);
      pCur = pCur->Next();
    }
  }
};

#endif