blob: 2d96971bed2ff3b77231001178fdad213c4adac5 [file] [log] [blame]
// Copyright 2019 PDFium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef CORE_FXCRT_TREE_NODE_H_
#define CORE_FXCRT_TREE_NODE_H_
#include <stdint.h>
#include "third_party/base/check.h"
namespace fxcrt {
// Implements the usual DOM/XML-ish trees.
template <typename T, typename PtrType = T*>
class TreeNode {
public:
TreeNode() = default;
virtual ~TreeNode() = default;
T* GetParent() const { return m_pParent; }
T* GetFirstChild() const { return m_pFirstChild; }
T* GetLastChild() const { return m_pLastChild; }
T* GetNextSibling() const { return m_pNextSibling; }
T* GetPrevSibling() const { return m_pPrevSibling; }
bool HasChild(const T* child) const {
return child != this && child->m_pParent == this;
}
T* GetNthChild(int32_t n) {
if (n < 0)
return nullptr;
T* result = GetFirstChild();
while (n-- && result) {
result = result->GetNextSibling();
}
return result;
}
void AppendFirstChild(T* child) {
BecomeParent(child);
if (m_pFirstChild) {
CHECK(m_pLastChild);
m_pFirstChild->m_pPrevSibling = child;
child->m_pNextSibling = m_pFirstChild;
m_pFirstChild = child;
} else {
CHECK(!m_pLastChild);
m_pFirstChild = child;
m_pLastChild = child;
}
}
void AppendLastChild(T* child) {
BecomeParent(child);
if (m_pLastChild) {
CHECK(m_pFirstChild);
m_pLastChild->m_pNextSibling = child;
child->m_pPrevSibling = m_pLastChild;
m_pLastChild = child;
} else {
CHECK(!m_pFirstChild);
m_pFirstChild = child;
m_pLastChild = child;
}
}
void InsertBefore(T* child, T* other) {
if (!other) {
AppendLastChild(child);
return;
}
BecomeParent(child);
CHECK(HasChild(other));
child->m_pNextSibling = other;
child->m_pPrevSibling = other->m_pPrevSibling;
if (m_pFirstChild == other) {
CHECK(!other->m_pPrevSibling);
m_pFirstChild = child;
} else {
other->m_pPrevSibling->m_pNextSibling = child;
}
other->m_pPrevSibling = child;
}
void InsertAfter(T* child, T* other) {
if (!other) {
AppendFirstChild(child);
return;
}
BecomeParent(child);
CHECK(HasChild(other));
child->m_pNextSibling = other->m_pNextSibling;
child->m_pPrevSibling = other;
if (m_pLastChild == other) {
CHECK(!other->m_pNextSibling);
m_pLastChild = child;
} else {
other->m_pNextSibling->m_pPrevSibling = child;
}
other->m_pNextSibling = child;
}
void RemoveChild(T* child) {
CHECK(HasChild(child));
if (m_pLastChild == child) {
CHECK(!child->m_pNextSibling);
m_pLastChild = child->m_pPrevSibling;
} else {
child->m_pNextSibling->m_pPrevSibling = child->m_pPrevSibling;
}
if (m_pFirstChild == child) {
CHECK(!child->m_pPrevSibling);
m_pFirstChild = child->m_pNextSibling;
} else {
child->m_pPrevSibling->m_pNextSibling = child->m_pNextSibling;
}
child->m_pParent = nullptr;
child->m_pPrevSibling = nullptr;
child->m_pNextSibling = nullptr;
}
void RemoveAllChildren() {
while (T* child = GetFirstChild())
RemoveChild(child);
}
void RemoveSelfIfParented() {
if (T* parent = GetParent())
parent->RemoveChild(static_cast<T*>(this));
}
protected:
const PtrType& RawParent() const { return m_pParent; }
const PtrType& RawFirstChild() const { return m_pFirstChild; }
const PtrType& RawLastChild() const { return m_pLastChild; }
const PtrType& RawNextSibling() const { return m_pNextSibling; }
const PtrType& RawPrevSibling() const { return m_pPrevSibling; }
private:
// Child left in state where sibling members need subsequent adjustment.
void BecomeParent(T* child) {
CHECK(child != this); // Detect attempts at self-insertion.
if (child->m_pParent)
child->m_pParent->TreeNode<T, PtrType>::RemoveChild(child);
child->m_pParent = static_cast<T*>(this);
CHECK(!child->m_pNextSibling);
CHECK(!child->m_pPrevSibling);
}
PtrType m_pParent = nullptr; // Default: Raw, intra-tree pointer.
PtrType m_pFirstChild = nullptr; // Default: Raw, intra-tree pointer.
PtrType m_pLastChild = nullptr; // Default: Raw, intra-tree pointer.
PtrType m_pNextSibling = nullptr; // Default: Raw, intra-tree pointer
PtrType m_pPrevSibling = nullptr; // Default: Raw, intra-tree pointer
};
} // namespace fxcrt
using fxcrt::TreeNode;
#endif // CORE_FXCRT_TREE_NODE_H_