cmLinkedTree.h 5.2 KB
Newer Older
1 2
/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file Copyright.txt or https://cmake.org/licensing for details.  */
3 4 5
#ifndef cmLinkedTree_h
#define cmLinkedTree_h

6 7
#include <cmConfigure.h>

8
#include <assert.h>
9 10
#include <iterator>
#include <vector>
11 12 13 14 15 16 17 18 19

/**
  @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.

20
  An empty cmLinkedTree provides a Root() method, and an Push() method,
21 22 23 24 25 26 27
  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.
 */
28
template <typename T>
29 30 31 32 33
class cmLinkedTree
{
  typedef typename std::vector<T>::size_type PositionType;
  typedef T* PointerType;
  typedef T& ReferenceType;
34

35 36 37 38 39 40 41 42 43 44
public:
  class iterator : public std::iterator<std::forward_iterator_tag, T>
  {
    friend class cmLinkedTree;
    cmLinkedTree* Tree;

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

    iterator(cmLinkedTree* tree, PositionType pos)
45 46
      : Tree(tree)
      , Position(pos)
47 48 49 50 51
    {
    }

  public:
    iterator()
Daniel Pfeifer's avatar
Daniel Pfeifer committed
52
      : Tree(CM_NULLPTR)
53
      , Position(0)
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
    {
    }

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

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

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

84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
    ReferenceType operator*() const
    {
      assert(this->Tree);
      assert(this->Tree->UpPositions.size() == this->Tree->Data.size());
      assert(this->Position <= this->Tree->Data.size());
      assert(this->Position > 0);
      return this->Tree->GetReference(this->Position - 1);
    }

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

102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
    bool operator==(iterator other) const
    {
      assert(this->Tree);
      assert(this->Tree->UpPositions.size() == this->Tree->Data.size());
      assert(this->Tree == other.Tree);
      return this->Position == other.Position;
    }

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

    bool IsValid() const
    {
119
      if (!this->Tree) {
120
        return false;
121
      }
122 123
      return this->Position <= this->Tree->Data.size();
    }
124 125 126 127 128 129 130

    bool StrictWeakOrdered(iterator other) const
    {
      assert(this->Tree);
      assert(this->Tree == other.Tree);
      return this->Position < other.Position;
    }
131 132 133 134 135 136 137
  };

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

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

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

142
  bool IsLast(iterator it) { return it.Position == this->Data.size(); }
Brad King's avatar
Brad King committed
143 144

  iterator Pop(iterator it)
145
  {
Brad King's avatar
Brad King committed
146 147 148 149 150 151
    assert(!this->Data.empty());
    assert(this->UpPositions.size() == this->Data.size());
    bool const isLast = this->IsLast(it);
    ++it;
    // If this is the last entry then no other entry can refer
    // to it so we can drop its storage.
152
    if (isLast) {
Brad King's avatar
Brad King committed
153 154 155
      this->Data.pop_back();
      this->UpPositions.pop_back();
    }
156 157
    return it;
  }
Brad King's avatar
Brad King committed
158

159 160
  iterator Truncate()
  {
161
    assert(!this->UpPositions.empty());
162 163
    this->UpPositions.erase(this->UpPositions.begin() + 1,
                            this->UpPositions.end());
164
    assert(!this->Data.empty());
165 166 167 168
    this->Data.erase(this->Data.begin() + 1, this->Data.end());
    return iterator(this, 1);
  }

169 170 171 172 173 174
  void Clear()
  {
    this->UpPositions.clear();
    this->Data.clear();
  }

175
private:
176
  T& GetReference(PositionType pos) { return this->Data[pos]; }
177

178
  T* GetPointer(PositionType pos) { return &this->Data[pos]; }
179

180
  iterator Push_impl(iterator it, T t)
181 182 183 184 185 186 187 188 189 190 191 192 193
  {
    assert(this->UpPositions.size() == this->Data.size());
    assert(it.Position <= this->UpPositions.size());
    this->UpPositions.push_back(it.Position);
    this->Data.push_back(t);
    return iterator(this, this->UpPositions.size());
  }

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

#endif