/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file Copyright.txt or https://cmake.org/licensing for details.  */
#pragma once

#include "cmConfigure.h" // IWYU pragma: keep

#include <cassert>
#include <vector>

/**
  @brief A adaptor for traversing a tree structure in a vector

  This class is not intended to be wholly generic like a standard library
  container adaptor.  Mostly it exists to facilitate code sharing for the
  needs of the cmState.  For example, the Truncate() method is a specific
  requirement of the cmState.

  An empty cmLinkedTree provides a Root() method, and an Push() method,
  each of which return iterators.  A Tree can be built up by extending
  from the root, and then extending from any other iterator.

  An iterator resulting from this tree construction can be
  forward-only-iterated toward the root.  Extending the tree never
  invalidates existing iterators.
 */
template <typename T>
class cmLinkedTree
{
  using PositionType = typename std::vector<T>::size_type;
  using PointerType = T*;
  using ReferenceType = T&;

public:
  class iterator
  {
    friend class cmLinkedTree;
    cmLinkedTree* Tree;

    // The Position is always 'one past the end'.
    PositionType Position;

    iterator(cmLinkedTree* tree, PositionType pos)
      : Tree(tree)
      , Position(pos)
    {
    }

  public:
    iterator()
      : Tree(nullptr)
      , Position(0)
    {
    }

    void operator++()
    {
      assert(Tree);
      assert(Tree->UpPositions.size() == Tree->Data.size());
      assert(Position <= Tree->Data.size());
      assert(Position > 0);
      Position = Tree->UpPositions[Position - 1];
    }

    PointerType operator->() const
    {
      assert(Tree);
      assert(Tree->UpPositions.size() == Tree->Data.size());
      assert(Position <= Tree->Data.size());
      assert(Position > 0);
      return Tree->GetPointer(Position - 1);
    }

    PointerType operator->()
    {
      assert(Tree);
      assert(Tree->UpPositions.size() == Tree->Data.size());
      assert(Position <= Tree->Data.size());
      assert(Position > 0);
      return Tree->GetPointer(Position - 1);
    }

    ReferenceType operator*() const
    {
      assert(Tree);
      assert(Tree->UpPositions.size() == Tree->Data.size());
      assert(Position <= Tree->Data.size());
      assert(Position > 0);
      return Tree->GetReference(Position - 1);
    }

    ReferenceType operator*()
    {
      assert(Tree);
      assert(Tree->UpPositions.size() == Tree->Data.size());
      assert(Position <= Tree->Data.size());
      assert(Position > 0);
      return Tree->GetReference(Position - 1);
    }

    bool operator==(iterator other) const
    {
      assert(Tree);
      assert(Tree->UpPositions.size() == Tree->Data.size());
      assert(Tree == other.Tree);
      return Position == other.Position;
    }

    bool operator!=(iterator other) const
    {
      assert(Tree);
      assert(Tree->UpPositions.size() == Tree->Data.size());
      return !(*this == other);
    }

    bool IsValid() const
    {
      if (!Tree) {
        return false;
      }
      return Position <= Tree->Data.size();
    }

    bool StrictWeakOrdered(iterator other) const
    {
      assert(Tree);
      assert(Tree == other.Tree);
      return Position < other.Position;
    }
  };

  iterator Root() const
  {
    return iterator(const_cast<cmLinkedTree*>(this), 0);
  }

  iterator Push(iterator it) { return Push_impl(it, T()); }

  iterator Push(iterator it, T t) { return Push_impl(it, std::move(t)); }

  bool IsLast(iterator it) { return it.Position == Data.size(); }

  iterator Pop(iterator it)
  {
    assert(!Data.empty());
    assert(UpPositions.size() == Data.size());
    bool const isLast = IsLast(it);
    ++it;
    // If this is the last entry then no other entry can refer
    // to it so we can drop its storage.
    if (isLast) {
      Data.pop_back();
      UpPositions.pop_back();
    }
    return it;
  }

  iterator Truncate()
  {
    assert(!UpPositions.empty());
    UpPositions.erase(UpPositions.begin() + 1, UpPositions.end());
    assert(!Data.empty());
    Data.erase(Data.begin() + 1, Data.end());
    return iterator(this, 1);
  }

  void Clear()
  {
    UpPositions.clear();
    Data.clear();
  }

private:
  T& GetReference(PositionType pos) { return Data[pos]; }

  T* GetPointer(PositionType pos) { return &Data[pos]; }

  iterator Push_impl(iterator it, T&& t)
  {
    assert(UpPositions.size() == Data.size());
    assert(it.Position <= UpPositions.size());
    UpPositions.push_back(it.Position);
    Data.push_back(std::move(t));
    return iterator(this, UpPositions.size());
  }

  std::vector<T> Data;
  std::vector<PositionType> UpPositions;
};
