// Copyright 2014 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.

// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com

#ifndef _FX_UTILS
#define _FX_UTILS

#include "fx_mem.h"
#include "core/include/fxcrt/fx_coordinates.h"  // For CFX_Rect.

class CFX_ThreadLock;
class CFX_BaseArray;
template <class baseType>
class CFX_BaseArrayTemplate;
template <class baseType>
class CFX_ObjectBaseArrayTemplate;
class CFX_BaseMassArray;
class CFX_BaseMassArrayImp;
template <class baseType>
class CFX_MassArrayTemplate;
template <class baseType>
class CFX_ObjectMassArrayTemplate;
class CFX_BaseDiscreteArray;
template <class baseType>
class CFX_DiscreteArrayTemplate;
class CFX_BaseStack;
template <class baseType>
class CFX_StackTemplate;
template <class baseType>
class CFX_ObjectStackTemplate;
template <class baseType>
class CFX_CPLTreeNode;
template <class baseType>
class CFX_CPLTree;
class FX_BASEARRAYDATA;

class CFX_ThreadLock {
 public:
  CFX_ThreadLock();
  virtual ~CFX_ThreadLock();
  void Lock();
  void Unlock();
};
class CFX_BaseArray : public CFX_Target {
 protected:
  CFX_BaseArray(int32_t iGrowSize, int32_t iBlockSize);
  ~CFX_BaseArray();
  int32_t GetSize() const;
  int32_t GetBlockSize() const;
  uint8_t* AddSpaceTo(int32_t index);
  uint8_t* GetAt(int32_t index) const;
  uint8_t* GetBuffer() const;
  int32_t Append(const CFX_BaseArray& src,
                 int32_t iStart = 0,
                 int32_t iCount = -1);
  int32_t Copy(const CFX_BaseArray& src,
               int32_t iStart = 0,
               int32_t iCount = -1);
  int32_t RemoveLast(int32_t iCount = -1);
  void RemoveAll(FX_BOOL bLeaveMemory = FALSE);

  FX_BASEARRAYDATA* m_pData;
};
template <class baseType>
class CFX_BaseArrayTemplate : public CFX_BaseArray {
 public:
  CFX_BaseArrayTemplate(int32_t iGrowSize = 100)
      : CFX_BaseArray(iGrowSize, sizeof(baseType)) {}
  CFX_BaseArrayTemplate(int32_t iGrowSize, int32_t iBlockSize)
      : CFX_BaseArray(iGrowSize, iBlockSize) {}
  int32_t GetSize() const { return CFX_BaseArray::GetSize(); }
  int32_t GetBlockSize() const { return CFX_BaseArray::GetBlockSize(); }
  baseType* AddSpace() {
    return (baseType*)CFX_BaseArray::AddSpaceTo(CFX_BaseArray::GetSize());
  }
  int32_t Add(const baseType& element) {
    int32_t index = CFX_BaseArray::GetSize();
    *(baseType*)CFX_BaseArray::AddSpaceTo(index) = element;
    return index;
  }
  baseType* GetBuffer() const { return (baseType*)CFX_BaseArray::GetBuffer(); }
  baseType& GetAt(int32_t index) const {
    return *(baseType*)CFX_BaseArray::GetAt(index);
  }
  baseType* GetPtrAt(int32_t index) const {
    return (baseType*)CFX_BaseArray::GetAt(index);
  }
  void SetAt(int32_t index, const baseType& element) {
    *(baseType*)CFX_BaseArray::GetAt(index) = element;
  }
  void SetAtGrow(int32_t index, const baseType& element) {
    *(baseType*)CFX_BaseArray::AddSpaceTo(index) = element;
  }
  int32_t Append(const CFX_BaseArrayTemplate& src,
                 int32_t iStart = 0,
                 int32_t iCount = -1) {
    return CFX_BaseArray::Append(src, iStart, iCount);
  }
  int32_t Copy(const CFX_BaseArrayTemplate& src,
               int32_t iStart = 0,
               int32_t iCount = -1) {
    return CFX_BaseArray::Copy(src, iStart, iCount);
  }
  int32_t RemoveLast(int32_t iCount = -1) {
    return CFX_BaseArray::RemoveLast(iCount);
  }
  void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    CFX_BaseArray::RemoveAll(bLeaveMemory);
  }
};
typedef CFX_BaseArrayTemplate<void*> CFDE_PtrArray;
typedef CFX_BaseArrayTemplate<FX_DWORD> CFDE_DWordArray;
typedef CFX_BaseArrayTemplate<FX_WORD> CFDE_WordArray;
template <class baseType>
class CFX_ObjectBaseArrayTemplate : public CFX_BaseArray {
 public:
  CFX_ObjectBaseArrayTemplate(int32_t iGrowSize = 100)
      : CFX_BaseArray(iGrowSize, sizeof(baseType)) {}
  ~CFX_ObjectBaseArrayTemplate() { RemoveAll(FALSE); }
  int32_t GetSize() const { return CFX_BaseArray::GetSize(); }
  int32_t GetBlockSize() const { return CFX_BaseArray::GetBlockSize(); }
  int32_t Add(const baseType& element) {
    int32_t index = CFX_BaseArray::GetSize();
    baseType* p = (baseType*)CFX_BaseArray::AddSpaceTo(index);
    new ((void*)p) baseType(element);
    return index;
  }
  baseType& GetAt(int32_t index) const {
    return *(baseType*)CFX_BaseArray::GetAt(index);
  }
  baseType* GetPtrAt(int32_t index) const {
    return (baseType*)CFX_BaseArray::GetAt(index);
  }
  int32_t Append(const CFX_ObjectBaseArrayTemplate& src,
                 int32_t iStart = 0,
                 int32_t iCount = -1) {
    FXSYS_assert(GetBlockSize() == src.GetBlockSize());
    if (iCount == 0) {
      return 0;
    }
    int32_t iSize = src.GetSize();
    FXSYS_assert(iStart > -1 && iStart < iSize);
    if (iCount < 0) {
      iCount = iSize;
    }
    if (iStart + iCount > iSize) {
      iCount = iSize - iStart;
    }
    if (iCount < 1) {
      return 0;
    }
    iSize = CFX_BaseArray::GetSize();
    CFX_BaseArray::AddSpaceTo(iSize + iCount - 1);
    uint8_t** pStart = CFX_BaseArray::GetAt(iSize);
    int32_t iBlockSize = CFX_BaseArray::GetBlockSize();
    iSize = iStart + iCount;
    for (int32_t i = iStart; i < iSize; i++) {
      FXTARGET_NewWith((void*)pStart) baseType(src.GetAt(i));
      pStart += iBlockSize;
    }
    return iCount;
  }
  int32_t Copy(const CFX_ObjectBaseArrayTemplate& src,
               int32_t iStart = 0,
               int32_t iCount = -1) {
    FXSYS_assert(GetBlockSize() == src.GetBlockSize());
    if (iCount == 0) {
      return 0;
    }
    int32_t iSize = src.GetSize();
    FXSYS_assert(iStart > -1 && iStart < iSize);
    if (iCount < 0) {
      iCount = iSize;
    }
    if (iStart + iCount > iSize) {
      iCount = iSize - iStart;
    }
    if (iCount < 1) {
      return 0;
    }
    RemoveAll(TRUE);
    CFX_BaseArray::AddSpaceTo(iCount - 1);
    uint8_t** pStart = CFX_BaseArray::GetAt(0);
    int32_t iBlockSize = CFX_BaseArray::GetBlockSize();
    iSize = iStart + iCount;
    for (int32_t i = iStart; i < iSize; i++) {
      new ((void*)pStart) baseType(src.GetAt(i));
      pStart += iBlockSize;
    }
    return iCount;
  }
  int32_t RemoveLast(int32_t iCount = -1) {
    int32_t iSize = CFX_BaseArray::GetSize();
    if (iCount < 0 || iCount > iSize) {
      iCount = iSize;
    }
    if (iCount == 0) {
      return iSize;
    }
    for (int32_t i = iSize - iCount; i < iSize; i++) {
      ((baseType*)GetPtrAt(i))->~baseType();
    }
    return CFX_BaseArray::RemoveLast(iCount);
  }
  void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    int32_t iSize = CFX_BaseArray::GetSize();
    for (int32_t i = 0; i < iSize; i++) {
      ((baseType*)GetPtrAt(i))->~baseType();
    }
    CFX_BaseArray::RemoveAll(bLeaveMemory);
  }
};
class CFX_BaseMassArray : public CFX_Target {
 protected:
  CFX_BaseMassArray(int32_t iChunkSize, int32_t iBlockSize);
  ~CFX_BaseMassArray();
  int32_t GetSize() const;
  uint8_t* AddSpaceTo(int32_t index);
  uint8_t* GetAt(int32_t index) const;
  int32_t Append(const CFX_BaseMassArray& src,
                 int32_t iStart = 0,
                 int32_t iCount = -1);
  int32_t Copy(const CFX_BaseMassArray& src,
               int32_t iStart = 0,
               int32_t iCount = -1);
  int32_t RemoveLast(int32_t iCount = -1);
  void RemoveAll(FX_BOOL bLeaveMemory = FALSE);
  CFX_BaseMassArrayImp* m_pData;
};
template <class baseType>
class CFX_MassArrayTemplate : public CFX_BaseMassArray {
 public:
  CFX_MassArrayTemplate(int32_t iChunkSize = 100)
      : CFX_BaseMassArray(iChunkSize, sizeof(baseType)) {}
  CFX_MassArrayTemplate(int32_t iChunkSize, int32_t iBlockSize)
      : CFX_BaseMassArray(iChunkSize, iBlockSize) {}
  int32_t GetSize() const { return CFX_BaseMassArray::GetSize(); }
  baseType* AddSpace() {
    return (baseType*)CFX_BaseMassArray::AddSpaceTo(
        CFX_BaseMassArray::GetSize());
  }
  int32_t Add(const baseType& element) {
    int32_t index = CFX_BaseMassArray::GetSize();
    *(baseType*)CFX_BaseMassArray::AddSpaceTo(index) = element;
    return index;
  }
  baseType& GetAt(int32_t index) const {
    return *(baseType*)CFX_BaseMassArray::GetAt(index);
  }
  baseType* GetPtrAt(int32_t index) const {
    return (baseType*)CFX_BaseMassArray::GetAt(index);
  }
  void SetAt(int32_t index, const baseType& element) {
    *(baseType*)CFX_BaseMassArray::GetAt(index) = element;
  }
  void SetAtGrow(int32_t index, const baseType& element) {
    *(baseType*)CFX_BaseMassArray::AddSpaceTo(index) = element;
  }
  int32_t Append(const CFX_MassArrayTemplate& src,
                 int32_t iStart = 0,
                 int32_t iCount = -1) {
    return CFX_BaseMassArray::Append(src, iStart, iCount);
  }
  int32_t Copy(const CFX_MassArrayTemplate& src,
               int32_t iStart = 0,
               int32_t iCount = -1) {
    return CFX_BaseMassArray::Copy(src, iStart, iCount);
  }
  int32_t RemoveLast(int32_t iCount = -1) {
    return CFX_BaseMassArray::RemoveLast(iCount);
  }
  void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    CFX_BaseMassArray::RemoveAll(bLeaveMemory);
  }
};
typedef CFX_MassArrayTemplate<void*> CFX_PtrMassArray;
typedef CFX_MassArrayTemplate<int32_t> CFX_Int32MassArray;
typedef CFX_MassArrayTemplate<FX_DWORD> CFX_DWordMassArray;
typedef CFX_MassArrayTemplate<FX_WORD> CFX_WordMassArray;
typedef CFX_MassArrayTemplate<CFX_Rect> CFX_RectMassArray;
typedef CFX_MassArrayTemplate<CFX_RectF> CFX_RectFMassArray;
template <class baseType>
class CFX_ObjectMassArrayTemplate : public CFX_BaseMassArray {
 public:
  CFX_ObjectMassArrayTemplate(int32_t iChunkSize = 100)
      : CFX_BaseMassArray(iChunkSize, sizeof(baseType)) {}
  ~CFX_ObjectMassArrayTemplate() { RemoveAll(FALSE); }
  int32_t GetSize() const { return CFX_BaseMassArray::GetSize(); }
  int32_t Add(const baseType& element) {
    int32_t index = CFX_BaseMassArray::GetSize();
    baseType* p = (baseType*)CFX_BaseMassArray::AddSpaceTo(index);
    new ((void*)p) baseType(element);
    return index;
  }
  baseType& GetAt(int32_t index) const {
    return *(baseType*)CFX_BaseMassArray::GetAt(index);
  }
  baseType* GetPtrAt(int32_t index) const {
    return (baseType*)CFX_BaseMassArray::GetAt(index);
  }
  int32_t Append(const CFX_ObjectMassArrayTemplate& src,
                 int32_t iStart = 0,
                 int32_t iCount = -1) {
    if (iCount == 0) {
      return CFX_BaseMassArray::GetSize();
    }
    int32_t iSize = src.GetSize();
    FXSYS_assert(iStart > -1 && iStart < iSize);
    if (iCount < 0) {
      iCount = iSize;
    }
    int32_t iEnd = iStart + iCount;
    if (iEnd > iSize) {
      iEnd = iSize;
    }
    for (int32_t i = iStart; i < iEnd; i++) {
      Add(src.GetAt(i));
    }
    return CFX_BaseMassArray::GetSize();
  }
  int32_t Copy(const CFX_ObjectMassArrayTemplate& src,
               int32_t iStart = 0,
               int32_t iCount = -1) {
    if (iCount == 0) {
      return CFX_BaseMassArray::GetSize();
    }
    int32_t iSize = src.GetSize();
    FXSYS_assert(iStart > -1 && iStart < iSize);
    if (iCount < 0) {
      iCount = iSize;
    }
    int32_t iEnd = iStart + iCount;
    if (iEnd > iSize) {
      iEnd = iSize;
    }
    RemoveAll(TRUE);
    for (int32_t i = iStart; i < iEnd; i++) {
      Add(src.GetAt(i));
    }
    return CFX_BaseMassArray::GetSize();
  }
  int32_t RemoveLast(int32_t iCount = -1) {
    int32_t iSize = CFX_BaseMassArray::GetSize();
    if (iCount < 0 || iCount > iSize) {
      iCount = iSize;
    }
    if (iCount == 0) {
      return iSize;
    }
    for (int32_t i = iSize - iCount; i < iSize; i++) {
      ((baseType*)GetPtrAt(i))->~baseType();
    }
    return CFX_BaseMassArray::RemoveLast(iCount);
  }
  void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    int32_t iSize = CFX_BaseMassArray::GetSize();
    for (int32_t i = 0; i < iSize; i++) {
      ((baseType*)GetPtrAt(i))->~baseType();
    }
    CFX_BaseMassArray::RemoveAll(bLeaveMemory);
  }
};
class CFX_BaseDiscreteArray : public CFX_Target {
 protected:
  CFX_BaseDiscreteArray(int32_t iChunkSize, int32_t iBlockSize);
  ~CFX_BaseDiscreteArray();
  uint8_t* AddSpaceTo(int32_t index);
  uint8_t* GetAt(int32_t index) const;
  void RemoveAll();
  void* m_pData;
};
template <class baseType>
class CFX_DiscreteArrayTemplate : public CFX_BaseDiscreteArray {
 public:
  CFX_DiscreteArrayTemplate(int32_t iChunkSize = 100)
      : CFX_BaseDiscreteArray(iChunkSize, sizeof(baseType)) {}
  baseType& GetAt(int32_t index, const baseType& defValue) const {
    baseType* p = (baseType*)CFX_BaseDiscreteArray::GetAt(index);
    return p == NULL ? (baseType&)defValue : *p;
  }
  baseType* GetPtrAt(int32_t index) const {
    return (baseType*)CFX_BaseDiscreteArray::GetAt(index);
  }
  void SetAtGrow(int32_t index, const baseType& element) {
    *(baseType*)CFX_BaseDiscreteArray::AddSpaceTo(index) = element;
  }
  void RemoveAll() { CFX_BaseDiscreteArray::RemoveAll(); }
};
typedef CFX_DiscreteArrayTemplate<void*> CFX_PtrDiscreteArray;
typedef CFX_DiscreteArrayTemplate<FX_DWORD> CFX_DWordDiscreteArray;
typedef CFX_DiscreteArrayTemplate<FX_WORD> CFX_WordDiscreteArray;
class CFX_BaseStack : public CFX_Target {
 protected:
  CFX_BaseStack(int32_t iChunkSize, int32_t iBlockSize);
  ~CFX_BaseStack();
  uint8_t* Push();
  void Pop();
  uint8_t* GetTopElement() const;
  int32_t GetSize() const;
  uint8_t* GetAt(int32_t index) const;
  void RemoveAll(FX_BOOL bLeaveMemory = FALSE);
  CFX_BaseMassArrayImp* m_pData;
};
template <class baseType>
class CFX_StackTemplate : public CFX_BaseStack {
 public:
  CFX_StackTemplate(int32_t iChunkSize = 100)
      : CFX_BaseStack(iChunkSize, sizeof(baseType)) {}
  int32_t Push(const baseType& element) {
    int32_t index = CFX_BaseStack::GetSize();
    *(baseType*)CFX_BaseStack::Push() = element;
    return index;
  }
  void Pop() { CFX_BaseStack::Pop(); }
  baseType* GetTopElement() const {
    return (baseType*)CFX_BaseStack::GetTopElement();
  }
  int32_t GetSize() const { return CFX_BaseStack::GetSize(); }
  baseType* GetAt(int32_t index) const {
    return (baseType*)CFX_BaseStack::GetAt(index);
  }
  void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    CFX_BaseStack::RemoveAll(bLeaveMemory);
  }
};
typedef CFX_StackTemplate<void*> CFX_PtrStack;
typedef CFX_StackTemplate<FX_DWORD> CFX_DWordStack;
typedef CFX_StackTemplate<FX_WORD> CFX_WordStack;
typedef CFX_StackTemplate<int32_t> CFX_Int32Stack;
template <class baseType>
class CFX_ObjectStackTemplate : public CFX_BaseStack {
 public:
  CFX_ObjectStackTemplate(int32_t iChunkSize = 100)
      : CFX_BaseStack(iChunkSize, sizeof(baseType)) {}
  ~CFX_ObjectStackTemplate() { RemoveAll(); }
  int32_t Push(const baseType& element) {
    int32_t index = CFX_BaseStack::GetSize();
    baseType* p = (baseType*)CFX_BaseStack::Push();
    new ((void*)p) baseType(element);
    return index;
  }
  void Pop() {
    baseType* p = (baseType*)CFX_BaseStack::GetTopElement();
    if (p != NULL) {
      p->~baseType();
    }
    CFX_BaseStack::Pop();
  }
  baseType* GetTopElement() const {
    return (baseType*)CFX_BaseStack::GetTopElement();
  }
  int32_t GetSize() const { return CFX_BaseStack::GetSize(); }
  baseType* GetAt(int32_t index) const {
    return (baseType*)CFX_BaseStack::GetAt(index);
  }
  void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    int32_t iSize = CFX_BaseStack::GetSize();
    for (int32_t i = 0; i < iSize; i++) {
      ((baseType*)CFX_BaseStack::GetAt(i))->~baseType();
    }
    CFX_BaseStack::RemoveAll(bLeaveMemory);
  }
  int32_t Copy(const CFX_ObjectStackTemplate& src,
               int32_t iStart = 0,
               int32_t iCount = -1) {
    if (iCount == 0) {
      return CFX_BaseStack::GetSize();
    }
    int32_t iSize = src.GetSize();
    FXSYS_assert(iStart > -1 && iStart < iSize);
    if (iCount < 0) {
      iCount = iSize;
    }
    int32_t iEnd = iStart + iCount;
    if (iEnd > iSize) {
      iEnd = iSize;
    }
    RemoveAll(TRUE);
    for (int32_t i = iStart; i < iEnd; i++) {
      Push(*src.GetAt(i));
    }
    return CFX_BaseStack::GetSize();
  }
};
template <class baseType>
class CFX_CPLTreeNode : public CFX_Target {
 public:
  typedef CFX_CPLTreeNode<baseType> CPLTreeNode;
  CFX_CPLTreeNode()
      : m_pParentNode(NULL),
        m_pChildNode(NULL),
        m_pPrevNode(NULL),
        m_pNextNode(NULL),
        m_Data() {}
  enum TreeNode {
    Root = 0,
    Parent,
    FirstSibling,
    PreviousSibling,
    NextSibling,
    LastSibling,
    FirstNeighbor,
    PreviousNeighbor,
    NextNeighbor,
    LastNeighbor,
    FirstChild,
    LastChild
  };
  CPLTreeNode* GetNode(TreeNode eNode) const {
    switch (eNode) {
      case Root: {
        CPLTreeNode* pParent = (CPLTreeNode*)this;
        CPLTreeNode* pTemp;
        while ((pTemp = pParent->m_pParentNode) != NULL) {
          pParent = pTemp;
        }
        return pParent;
      }
      case Parent:
        return m_pParentNode;
      case FirstSibling: {
        CPLTreeNode* pNode = (CPLTreeNode*)this;
        CPLTreeNode* pTemp;
        while ((pTemp = pNode->m_pPrevNode) != NULL) {
          pNode = pTemp;
        }
        return pNode == (CPLTreeNode*)this ? NULL : pNode;
      }
      case PreviousSibling:
        return m_pPrevNode;
      case NextSibling:
        return m_pNextNode;
      case LastSibling: {
        CPLTreeNode* pNode = (CPLTreeNode*)this;
        CPLTreeNode* pTemp;
        while ((pTemp = pNode->m_pNextNode) != NULL) {
          pNode = pTemp;
        }
        return pNode == (CPLTreeNode*)this ? NULL : pNode;
      }
      case FirstNeighbor: {
        CPLTreeNode* pParent = (CPLTreeNode*)this;
        CPLTreeNode* pTemp;
        while ((pTemp = pParent->m_pParentNode) != NULL) {
          pParent = pTemp;
        }
        return pParent == (CPLTreeNode*)this ? NULL : pParent;
      }
      case PreviousNeighbor: {
        if (m_pPrevNode == NULL) {
          return m_pParentNode;
        }
        CPLTreeNode* pNode = m_pPrevNode;
        CPLTreeNode* pTemp;
        while ((pTemp = pNode->m_pChildNode) != NULL) {
          pNode = pTemp;
          while ((pTemp = pNode->m_pNextNode) != NULL) {
            pNode = pTemp;
          }
        }
        return pNode;
      }
      case NextNeighbor: {
        if (m_pChildNode != NULL) {
          return m_pChildNode;
        }
        if (m_pNextNode != NULL) {
          return m_pNextNode;
        }
        CPLTreeNode* pNode = m_pParentNode;
        while (pNode != NULL) {
          if (pNode->m_pNextNode != NULL) {
            return pNode->m_pNextNode;
          }
          pNode = pNode->m_pParentNode;
        }
        return NULL;
      }
      case LastNeighbor: {
        CPLTreeNode* pNode = (CPLTreeNode*)this;
        CPLTreeNode* pTemp;
        while ((pTemp = pNode->m_pParentNode) != NULL) {
          pNode = pTemp;
        }
        while (TRUE) {
          CPLTreeNode* pTemp;
          while ((pTemp = pNode->m_pNextNode) != NULL) {
            pNode = pTemp;
          }
          if (pNode->m_pChildNode == NULL) {
            break;
          }
          pNode = pNode->m_pChildNode;
        }
        return pNode == (CPLTreeNode*)this ? NULL : pNode;
      }
      case FirstChild:
        return m_pChildNode;
      case LastChild: {
        if (m_pChildNode == NULL) {
          return NULL;
        }
        CPLTreeNode* pChild = m_pChildNode;
        CPLTreeNode* pTemp;
        while ((pTemp = pChild->m_pNextNode) != NULL) {
          pChild = pTemp;
        }
        return pChild;
      }
      default:
        break;
    }
    return NULL;
  }
  void SetParentNode(CPLTreeNode* pNode) { m_pParentNode = pNode; }
  int32_t CountChildNodes() const {
    int32_t iCount = 0;
    CPLTreeNode* pNode = m_pChildNode;
    while (pNode) {
      iCount++;
      pNode = pNode->m_pNextNode;
    }
    return iCount;
  }
  CPLTreeNode* GetChildNode(int32_t iIndex) const {
    int32_t iCount = 0;
    CPLTreeNode* pNode = m_pChildNode;
    while (pNode) {
      if (iIndex == iCount) {
        return pNode;
      }
      iCount++;
      pNode = pNode->m_pNextNode;
    }
    return NULL;
  }
  int32_t GetNodeIndex() const {
    int32_t index = 0;
    CPLTreeNode* pNode = m_pPrevNode;
    while (pNode != NULL) {
      index++;
      pNode = pNode->m_pPrevNode;
    }
    return index;
  }
  FX_BOOL IsParentNode(const CPLTreeNode* pNode) const {
    CPLTreeNode* pParent = m_pParentNode;
    while (pParent != NULL) {
      if (pParent == pNode) {
        return TRUE;
      }
      pParent = pParent->GetTreeNode(Parent);
    }
    return FALSE;
  }
  FX_BOOL IsChildNode(const CPLTreeNode* pNode) const {
    if (pNode == NULL) {
      return FALSE;
    }
    return pNode->IsParentNode((const CPLTreeNode*)this);
  }
  void SetChildNode(CPLTreeNode* pNode) { m_pChildNode = pNode; }
  void SetPrevNode(CPLTreeNode* pNode) { m_pPrevNode = pNode; }
  void SetNextNode(CPLTreeNode* pNode) { m_pNextNode = pNode; }
  int32_t GetNodeLevel() const {
    int32_t iLevel = 0;
    CPLTreeNode* pNode = (CPLTreeNode*)this;
    while ((pNode = pNode->m_pParentNode) != NULL) {
      iLevel++;
    }
    return iLevel;
  }
  FX_BOOL IsRootNode() const { return m_pParentNode == NULL; }
  baseType GetData() const { return m_Data; }
  void SetData(baseType data) { m_Data = data; }

 protected:
  CPLTreeNode* m_pParentNode;
  CPLTreeNode* m_pChildNode;
  CPLTreeNode* m_pPrevNode;
  CPLTreeNode* m_pNextNode;
  baseType m_Data;
  friend class CFX_CPLTree<baseType>;
};
template <class baseType>
class CFX_CPLTree {
 public:
  typedef CFX_CPLTreeNode<baseType> CPLTreeNode;
  CFX_CPLTree() : m_Root() {}
  ~CFX_CPLTree() {
    CPLTreeNode* pNode = m_Root.GetNode(CPLTreeNode::LastNeighbor);
    while (pNode != NULL) {
      if (pNode->IsRootNode()) {
        break;
      }
      CPLTreeNode* pTemp = pNode->GetNode(CPLTreeNode::PreviousNeighbor);
      delete pNode;
      pNode = pTemp;
    }
  }
  CPLTreeNode* GetRoot() { return &m_Root; }
  CPLTreeNode* AddChild(baseType data, CPLTreeNode* pParent = NULL) {
    if (pParent == NULL) {
      pParent = &m_Root;
    }
    CPLTreeNode* pChild = new CPLTreeNode;
    pChild->SetParentNode(pParent);
    pChild->SetData(data);
    if (pParent->m_pChildNode == NULL) {
      pParent->m_pChildNode = pChild;
    } else {
      CPLTreeNode* pLast = pParent->GetNode(CPLTreeNode::LastChild);
      pChild->SetPrevNode(pLast);
      pLast->SetNextNode(pChild);
    }
    return pChild;
  }

 protected:
  CPLTreeNode m_Root;
};
#endif