Home | History | Annotate | Download | only in include 
      1 // Copyright 2014 PDFium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
      6 
      7 #ifndef _FX_UTILS
      8 #define _FX_UTILS
      9 
     10 #include "fx_mem.h"
     11 #include "core/include/fxcrt/fx_coordinates.h"  // For CFX_Rect.
     12 
     13 class CFX_ThreadLock;
     14 class CFX_BaseArray;
     15 template <class baseType>
     16 class CFX_BaseArrayTemplate;
     17 template <class baseType>
     18 class CFX_ObjectBaseArrayTemplate;
     19 class CFX_BaseMassArray;
     20 class CFX_BaseMassArrayImp;
     21 template <class baseType>
     22 class CFX_MassArrayTemplate;
     23 template <class baseType>
     24 class CFX_ObjectMassArrayTemplate;
     25 class CFX_BaseDiscreteArray;
     26 template <class baseType>
     27 class CFX_DiscreteArrayTemplate;
     28 class CFX_BaseStack;
     29 template <class baseType>
     30 class CFX_StackTemplate;
     31 template <class baseType>
     32 class CFX_ObjectStackTemplate;
     33 template <class baseType>
     34 class CFX_CPLTreeNode;
     35 template <class baseType>
     36 class CFX_CPLTree;
     37 class FX_BASEARRAYDATA;
     38 
     39 class CFX_ThreadLock {
     40  public:
     41   CFX_ThreadLock();
     42   virtual ~CFX_ThreadLock();
     43   void Lock();
     44   void Unlock();
     45 };
     46 class CFX_BaseArray : public CFX_Target {
     47  protected:
     48   CFX_BaseArray(int32_t iGrowSize, int32_t iBlockSize);
     49   ~CFX_BaseArray();
     50   int32_t GetSize() const;
     51   int32_t GetBlockSize() const;
     52   uint8_t* AddSpaceTo(int32_t index);
     53   uint8_t* GetAt(int32_t index) const;
     54   uint8_t* GetBuffer() const;
     55   int32_t Append(const CFX_BaseArray& src,
     56                  int32_t iStart = 0,
     57                  int32_t iCount = -1);
     58   int32_t Copy(const CFX_BaseArray& src,
     59                int32_t iStart = 0,
     60                int32_t iCount = -1);
     61   int32_t RemoveLast(int32_t iCount = -1);
     62   void RemoveAll(FX_BOOL bLeaveMemory = FALSE);
     63 
     64   FX_BASEARRAYDATA* m_pData;
     65 };
     66 template <class baseType>
     67 class CFX_BaseArrayTemplate : public CFX_BaseArray {
     68  public:
     69   CFX_BaseArrayTemplate(int32_t iGrowSize = 100)
     70       : CFX_BaseArray(iGrowSize, sizeof(baseType)) {}
     71   CFX_BaseArrayTemplate(int32_t iGrowSize, int32_t iBlockSize)
     72       : CFX_BaseArray(iGrowSize, iBlockSize) {}
     73   int32_t GetSize() const { return CFX_BaseArray::GetSize(); }
     74   int32_t GetBlockSize() const { return CFX_BaseArray::GetBlockSize(); }
     75   baseType* AddSpace() {
     76     return (baseType*)CFX_BaseArray::AddSpaceTo(CFX_BaseArray::GetSize());
     77   }
     78   int32_t Add(const baseType& element) {
     79     int32_t index = CFX_BaseArray::GetSize();
     80     *(baseType*)CFX_BaseArray::AddSpaceTo(index) = element;
     81     return index;
     82   }
     83   baseType* GetBuffer() const { return (baseType*)CFX_BaseArray::GetBuffer(); }
     84   baseType& GetAt(int32_t index) const {
     85     return *(baseType*)CFX_BaseArray::GetAt(index);
     86   }
     87   baseType* GetPtrAt(int32_t index) const {
     88     return (baseType*)CFX_BaseArray::GetAt(index);
     89   }
     90   void SetAt(int32_t index, const baseType& element) {
     91     *(baseType*)CFX_BaseArray::GetAt(index) = element;
     92   }
     93   void SetAtGrow(int32_t index, const baseType& element) {
     94     *(baseType*)CFX_BaseArray::AddSpaceTo(index) = element;
     95   }
     96   int32_t Append(const CFX_BaseArrayTemplate& src,
     97                  int32_t iStart = 0,
     98                  int32_t iCount = -1) {
     99     return CFX_BaseArray::Append(src, iStart, iCount);
    100   }
    101   int32_t Copy(const CFX_BaseArrayTemplate& src,
    102                int32_t iStart = 0,
    103                int32_t iCount = -1) {
    104     return CFX_BaseArray::Copy(src, iStart, iCount);
    105   }
    106   int32_t RemoveLast(int32_t iCount = -1) {
    107     return CFX_BaseArray::RemoveLast(iCount);
    108   }
    109   void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    110     CFX_BaseArray::RemoveAll(bLeaveMemory);
    111   }
    112 };
    113 typedef CFX_BaseArrayTemplate<void*> CFDE_PtrArray;
    114 typedef CFX_BaseArrayTemplate<FX_DWORD> CFDE_DWordArray;
    115 typedef CFX_BaseArrayTemplate<FX_WORD> CFDE_WordArray;
    116 template <class baseType>
    117 class CFX_ObjectBaseArrayTemplate : public CFX_BaseArray {
    118  public:
    119   CFX_ObjectBaseArrayTemplate(int32_t iGrowSize = 100)
    120       : CFX_BaseArray(iGrowSize, sizeof(baseType)) {}
    121   ~CFX_ObjectBaseArrayTemplate() { RemoveAll(FALSE); }
    122   int32_t GetSize() const { return CFX_BaseArray::GetSize(); }
    123   int32_t GetBlockSize() const { return CFX_BaseArray::GetBlockSize(); }
    124   int32_t Add(const baseType& element) {
    125     int32_t index = CFX_BaseArray::GetSize();
    126     baseType* p = (baseType*)CFX_BaseArray::AddSpaceTo(index);
    127     new ((void*)p) baseType(element);
    128     return index;
    129   }
    130   baseType& GetAt(int32_t index) const {
    131     return *(baseType*)CFX_BaseArray::GetAt(index);
    132   }
    133   baseType* GetPtrAt(int32_t index) const {
    134     return (baseType*)CFX_BaseArray::GetAt(index);
    135   }
    136   int32_t Append(const CFX_ObjectBaseArrayTemplate& src,
    137                  int32_t iStart = 0,
    138                  int32_t iCount = -1) {
    139     FXSYS_assert(GetBlockSize() == src.GetBlockSize());
    140     if (iCount == 0) {
    141       return 0;
    142     }
    143     int32_t iSize = src.GetSize();
    144     FXSYS_assert(iStart > -1 && iStart < iSize);
    145     if (iCount < 0) {
    146       iCount = iSize;
    147     }
    148     if (iStart + iCount > iSize) {
    149       iCount = iSize - iStart;
    150     }
    151     if (iCount < 1) {
    152       return 0;
    153     }
    154     iSize = CFX_BaseArray::GetSize();
    155     CFX_BaseArray::AddSpaceTo(iSize + iCount - 1);
    156     uint8_t** pStart = CFX_BaseArray::GetAt(iSize);
    157     int32_t iBlockSize = CFX_BaseArray::GetBlockSize();
    158     iSize = iStart + iCount;
    159     for (int32_t i = iStart; i < iSize; i++) {
    160       FXTARGET_NewWith((void*)pStart) baseType(src.GetAt(i));
    161       pStart += iBlockSize;
    162     }
    163     return iCount;
    164   }
    165   int32_t Copy(const CFX_ObjectBaseArrayTemplate& src,
    166                int32_t iStart = 0,
    167                int32_t iCount = -1) {
    168     FXSYS_assert(GetBlockSize() == src.GetBlockSize());
    169     if (iCount == 0) {
    170       return 0;
    171     }
    172     int32_t iSize = src.GetSize();
    173     FXSYS_assert(iStart > -1 && iStart < iSize);
    174     if (iCount < 0) {
    175       iCount = iSize;
    176     }
    177     if (iStart + iCount > iSize) {
    178       iCount = iSize - iStart;
    179     }
    180     if (iCount < 1) {
    181       return 0;
    182     }
    183     RemoveAll(TRUE);
    184     CFX_BaseArray::AddSpaceTo(iCount - 1);
    185     uint8_t** pStart = CFX_BaseArray::GetAt(0);
    186     int32_t iBlockSize = CFX_BaseArray::GetBlockSize();
    187     iSize = iStart + iCount;
    188     for (int32_t i = iStart; i < iSize; i++) {
    189       new ((void*)pStart) baseType(src.GetAt(i));
    190       pStart += iBlockSize;
    191     }
    192     return iCount;
    193   }
    194   int32_t RemoveLast(int32_t iCount = -1) {
    195     int32_t iSize = CFX_BaseArray::GetSize();
    196     if (iCount < 0 || iCount > iSize) {
    197       iCount = iSize;
    198     }
    199     if (iCount == 0) {
    200       return iSize;
    201     }
    202     for (int32_t i = iSize - iCount; i < iSize; i++) {
    203       ((baseType*)GetPtrAt(i))->~baseType();
    204     }
    205     return CFX_BaseArray::RemoveLast(iCount);
    206   }
    207   void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    208     int32_t iSize = CFX_BaseArray::GetSize();
    209     for (int32_t i = 0; i < iSize; i++) {
    210       ((baseType*)GetPtrAt(i))->~baseType();
    211     }
    212     CFX_BaseArray::RemoveAll(bLeaveMemory);
    213   }
    214 };
    215 class CFX_BaseMassArray : public CFX_Target {
    216  protected:
    217   CFX_BaseMassArray(int32_t iChunkSize, int32_t iBlockSize);
    218   ~CFX_BaseMassArray();
    219   int32_t GetSize() const;
    220   uint8_t* AddSpaceTo(int32_t index);
    221   uint8_t* GetAt(int32_t index) const;
    222   int32_t Append(const CFX_BaseMassArray& src,
    223                  int32_t iStart = 0,
    224                  int32_t iCount = -1);
    225   int32_t Copy(const CFX_BaseMassArray& src,
    226                int32_t iStart = 0,
    227                int32_t iCount = -1);
    228   int32_t RemoveLast(int32_t iCount = -1);
    229   void RemoveAll(FX_BOOL bLeaveMemory = FALSE);
    230   CFX_BaseMassArrayImp* m_pData;
    231 };
    232 template <class baseType>
    233 class CFX_MassArrayTemplate : public CFX_BaseMassArray {
    234  public:
    235   CFX_MassArrayTemplate(int32_t iChunkSize = 100)
    236       : CFX_BaseMassArray(iChunkSize, sizeof(baseType)) {}
    237   CFX_MassArrayTemplate(int32_t iChunkSize, int32_t iBlockSize)
    238       : CFX_BaseMassArray(iChunkSize, iBlockSize) {}
    239   int32_t GetSize() const { return CFX_BaseMassArray::GetSize(); }
    240   baseType* AddSpace() {
    241     return (baseType*)CFX_BaseMassArray::AddSpaceTo(
    242         CFX_BaseMassArray::GetSize());
    243   }
    244   int32_t Add(const baseType& element) {
    245     int32_t index = CFX_BaseMassArray::GetSize();
    246     *(baseType*)CFX_BaseMassArray::AddSpaceTo(index) = element;
    247     return index;
    248   }
    249   baseType& GetAt(int32_t index) const {
    250     return *(baseType*)CFX_BaseMassArray::GetAt(index);
    251   }
    252   baseType* GetPtrAt(int32_t index) const {
    253     return (baseType*)CFX_BaseMassArray::GetAt(index);
    254   }
    255   void SetAt(int32_t index, const baseType& element) {
    256     *(baseType*)CFX_BaseMassArray::GetAt(index) = element;
    257   }
    258   void SetAtGrow(int32_t index, const baseType& element) {
    259     *(baseType*)CFX_BaseMassArray::AddSpaceTo(index) = element;
    260   }
    261   int32_t Append(const CFX_MassArrayTemplate& src,
    262                  int32_t iStart = 0,
    263                  int32_t iCount = -1) {
    264     return CFX_BaseMassArray::Append(src, iStart, iCount);
    265   }
    266   int32_t Copy(const CFX_MassArrayTemplate& src,
    267                int32_t iStart = 0,
    268                int32_t iCount = -1) {
    269     return CFX_BaseMassArray::Copy(src, iStart, iCount);
    270   }
    271   int32_t RemoveLast(int32_t iCount = -1) {
    272     return CFX_BaseMassArray::RemoveLast(iCount);
    273   }
    274   void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    275     CFX_BaseMassArray::RemoveAll(bLeaveMemory);
    276   }
    277 };
    278 typedef CFX_MassArrayTemplate<void*> CFX_PtrMassArray;
    279 typedef CFX_MassArrayTemplate<int32_t> CFX_Int32MassArray;
    280 typedef CFX_MassArrayTemplate<FX_DWORD> CFX_DWordMassArray;
    281 typedef CFX_MassArrayTemplate<FX_WORD> CFX_WordMassArray;
    282 typedef CFX_MassArrayTemplate<CFX_Rect> CFX_RectMassArray;
    283 typedef CFX_MassArrayTemplate<CFX_RectF> CFX_RectFMassArray;
    284 template <class baseType>
    285 class CFX_ObjectMassArrayTemplate : public CFX_BaseMassArray {
    286  public:
    287   CFX_ObjectMassArrayTemplate(int32_t iChunkSize = 100)
    288       : CFX_BaseMassArray(iChunkSize, sizeof(baseType)) {}
    289   ~CFX_ObjectMassArrayTemplate() { RemoveAll(FALSE); }
    290   int32_t GetSize() const { return CFX_BaseMassArray::GetSize(); }
    291   int32_t Add(const baseType& element) {
    292     int32_t index = CFX_BaseMassArray::GetSize();
    293     baseType* p = (baseType*)CFX_BaseMassArray::AddSpaceTo(index);
    294     new ((void*)p) baseType(element);
    295     return index;
    296   }
    297   baseType& GetAt(int32_t index) const {
    298     return *(baseType*)CFX_BaseMassArray::GetAt(index);
    299   }
    300   baseType* GetPtrAt(int32_t index) const {
    301     return (baseType*)CFX_BaseMassArray::GetAt(index);
    302   }
    303   int32_t Append(const CFX_ObjectMassArrayTemplate& src,
    304                  int32_t iStart = 0,
    305                  int32_t iCount = -1) {
    306     if (iCount == 0) {
    307       return CFX_BaseMassArray::GetSize();
    308     }
    309     int32_t iSize = src.GetSize();
    310     FXSYS_assert(iStart > -1 && iStart < iSize);
    311     if (iCount < 0) {
    312       iCount = iSize;
    313     }
    314     int32_t iEnd = iStart + iCount;
    315     if (iEnd > iSize) {
    316       iEnd = iSize;
    317     }
    318     for (int32_t i = iStart; i < iEnd; i++) {
    319       Add(src.GetAt(i));
    320     }
    321     return CFX_BaseMassArray::GetSize();
    322   }
    323   int32_t Copy(const CFX_ObjectMassArrayTemplate& src,
    324                int32_t iStart = 0,
    325                int32_t iCount = -1) {
    326     if (iCount == 0) {
    327       return CFX_BaseMassArray::GetSize();
    328     }
    329     int32_t iSize = src.GetSize();
    330     FXSYS_assert(iStart > -1 && iStart < iSize);
    331     if (iCount < 0) {
    332       iCount = iSize;
    333     }
    334     int32_t iEnd = iStart + iCount;
    335     if (iEnd > iSize) {
    336       iEnd = iSize;
    337     }
    338     RemoveAll(TRUE);
    339     for (int32_t i = iStart; i < iEnd; i++) {
    340       Add(src.GetAt(i));
    341     }
    342     return CFX_BaseMassArray::GetSize();
    343   }
    344   int32_t RemoveLast(int32_t iCount = -1) {
    345     int32_t iSize = CFX_BaseMassArray::GetSize();
    346     if (iCount < 0 || iCount > iSize) {
    347       iCount = iSize;
    348     }
    349     if (iCount == 0) {
    350       return iSize;
    351     }
    352     for (int32_t i = iSize - iCount; i < iSize; i++) {
    353       ((baseType*)GetPtrAt(i))->~baseType();
    354     }
    355     return CFX_BaseMassArray::RemoveLast(iCount);
    356   }
    357   void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    358     int32_t iSize = CFX_BaseMassArray::GetSize();
    359     for (int32_t i = 0; i < iSize; i++) {
    360       ((baseType*)GetPtrAt(i))->~baseType();
    361     }
    362     CFX_BaseMassArray::RemoveAll(bLeaveMemory);
    363   }
    364 };
    365 class CFX_BaseDiscreteArray : public CFX_Target {
    366  protected:
    367   CFX_BaseDiscreteArray(int32_t iChunkSize, int32_t iBlockSize);
    368   ~CFX_BaseDiscreteArray();
    369   uint8_t* AddSpaceTo(int32_t index);
    370   uint8_t* GetAt(int32_t index) const;
    371   void RemoveAll();
    372   void* m_pData;
    373 };
    374 template <class baseType>
    375 class CFX_DiscreteArrayTemplate : public CFX_BaseDiscreteArray {
    376  public:
    377   CFX_DiscreteArrayTemplate(int32_t iChunkSize = 100)
    378       : CFX_BaseDiscreteArray(iChunkSize, sizeof(baseType)) {}
    379   baseType& GetAt(int32_t index, const baseType& defValue) const {
    380     baseType* p = (baseType*)CFX_BaseDiscreteArray::GetAt(index);
    381     return p == NULL ? (baseType&)defValue : *p;
    382   }
    383   baseType* GetPtrAt(int32_t index) const {
    384     return (baseType*)CFX_BaseDiscreteArray::GetAt(index);
    385   }
    386   void SetAtGrow(int32_t index, const baseType& element) {
    387     *(baseType*)CFX_BaseDiscreteArray::AddSpaceTo(index) = element;
    388   }
    389   void RemoveAll() { CFX_BaseDiscreteArray::RemoveAll(); }
    390 };
    391 typedef CFX_DiscreteArrayTemplate<void*> CFX_PtrDiscreteArray;
    392 typedef CFX_DiscreteArrayTemplate<FX_DWORD> CFX_DWordDiscreteArray;
    393 typedef CFX_DiscreteArrayTemplate<FX_WORD> CFX_WordDiscreteArray;
    394 class CFX_BaseStack : public CFX_Target {
    395  protected:
    396   CFX_BaseStack(int32_t iChunkSize, int32_t iBlockSize);
    397   ~CFX_BaseStack();
    398   uint8_t* Push();
    399   void Pop();
    400   uint8_t* GetTopElement() const;
    401   int32_t GetSize() const;
    402   uint8_t* GetAt(int32_t index) const;
    403   void RemoveAll(FX_BOOL bLeaveMemory = FALSE);
    404   CFX_BaseMassArrayImp* m_pData;
    405 };
    406 template <class baseType>
    407 class CFX_StackTemplate : public CFX_BaseStack {
    408  public:
    409   CFX_StackTemplate(int32_t iChunkSize = 100)
    410       : CFX_BaseStack(iChunkSize, sizeof(baseType)) {}
    411   int32_t Push(const baseType& element) {
    412     int32_t index = CFX_BaseStack::GetSize();
    413     *(baseType*)CFX_BaseStack::Push() = element;
    414     return index;
    415   }
    416   void Pop() { CFX_BaseStack::Pop(); }
    417   baseType* GetTopElement() const {
    418     return (baseType*)CFX_BaseStack::GetTopElement();
    419   }
    420   int32_t GetSize() const { return CFX_BaseStack::GetSize(); }
    421   baseType* GetAt(int32_t index) const {
    422     return (baseType*)CFX_BaseStack::GetAt(index);
    423   }
    424   void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    425     CFX_BaseStack::RemoveAll(bLeaveMemory);
    426   }
    427 };
    428 typedef CFX_StackTemplate<void*> CFX_PtrStack;
    429 typedef CFX_StackTemplate<FX_DWORD> CFX_DWordStack;
    430 typedef CFX_StackTemplate<FX_WORD> CFX_WordStack;
    431 typedef CFX_StackTemplate<int32_t> CFX_Int32Stack;
    432 template <class baseType>
    433 class CFX_ObjectStackTemplate : public CFX_BaseStack {
    434  public:
    435   CFX_ObjectStackTemplate(int32_t iChunkSize = 100)
    436       : CFX_BaseStack(iChunkSize, sizeof(baseType)) {}
    437   ~CFX_ObjectStackTemplate() { RemoveAll(); }
    438   int32_t Push(const baseType& element) {
    439     int32_t index = CFX_BaseStack::GetSize();
    440     baseType* p = (baseType*)CFX_BaseStack::Push();
    441     new ((void*)p) baseType(element);
    442     return index;
    443   }
    444   void Pop() {
    445     baseType* p = (baseType*)CFX_BaseStack::GetTopElement();
    446     if (p != NULL) {
    447       p->~baseType();
    448     }
    449     CFX_BaseStack::Pop();
    450   }
    451   baseType* GetTopElement() const {
    452     return (baseType*)CFX_BaseStack::GetTopElement();
    453   }
    454   int32_t GetSize() const { return CFX_BaseStack::GetSize(); }
    455   baseType* GetAt(int32_t index) const {
    456     return (baseType*)CFX_BaseStack::GetAt(index);
    457   }
    458   void RemoveAll(FX_BOOL bLeaveMemory = FALSE) {
    459     int32_t iSize = CFX_BaseStack::GetSize();
    460     for (int32_t i = 0; i < iSize; i++) {
    461       ((baseType*)CFX_BaseStack::GetAt(i))->~baseType();
    462     }
    463     CFX_BaseStack::RemoveAll(bLeaveMemory);
    464   }
    465   int32_t Copy(const CFX_ObjectStackTemplate& src,
    466                int32_t iStart = 0,
    467                int32_t iCount = -1) {
    468     if (iCount == 0) {
    469       return CFX_BaseStack::GetSize();
    470     }
    471     int32_t iSize = src.GetSize();
    472     FXSYS_assert(iStart > -1 && iStart < iSize);
    473     if (iCount < 0) {
    474       iCount = iSize;
    475     }
    476     int32_t iEnd = iStart + iCount;
    477     if (iEnd > iSize) {
    478       iEnd = iSize;
    479     }
    480     RemoveAll(TRUE);
    481     for (int32_t i = iStart; i < iEnd; i++) {
    482       Push(*src.GetAt(i));
    483     }
    484     return CFX_BaseStack::GetSize();
    485   }
    486 };
    487 template <class baseType>
    488 class CFX_CPLTreeNode : public CFX_Target {
    489  public:
    490   typedef CFX_CPLTreeNode<baseType> CPLTreeNode;
    491   CFX_CPLTreeNode()
    492       : m_pParentNode(NULL),
    493         m_pChildNode(NULL),
    494         m_pPrevNode(NULL),
    495         m_pNextNode(NULL),
    496         m_Data() {}
    497   enum TreeNode {
    498     Root = 0,
    499     Parent,
    500     FirstSibling,
    501     PreviousSibling,
    502     NextSibling,
    503     LastSibling,
    504     FirstNeighbor,
    505     PreviousNeighbor,
    506     NextNeighbor,
    507     LastNeighbor,
    508     FirstChild,
    509     LastChild
    510   };
    511   CPLTreeNode* GetNode(TreeNode eNode) const {
    512     switch (eNode) {
    513       case Root: {
    514         CPLTreeNode* pParent = (CPLTreeNode*)this;
    515         CPLTreeNode* pTemp;
    516         while ((pTemp = pParent->m_pParentNode) != NULL) {
    517           pParent = pTemp;
    518         }
    519         return pParent;
    520       }
    521       case Parent:
    522         return m_pParentNode;
    523       case FirstSibling: {
    524         CPLTreeNode* pNode = (CPLTreeNode*)this;
    525         CPLTreeNode* pTemp;
    526         while ((pTemp = pNode->m_pPrevNode) != NULL) {
    527           pNode = pTemp;
    528         }
    529         return pNode == (CPLTreeNode*)this ? NULL : pNode;
    530       }
    531       case PreviousSibling:
    532         return m_pPrevNode;
    533       case NextSibling:
    534         return m_pNextNode;
    535       case LastSibling: {
    536         CPLTreeNode* pNode = (CPLTreeNode*)this;
    537         CPLTreeNode* pTemp;
    538         while ((pTemp = pNode->m_pNextNode) != NULL) {
    539           pNode = pTemp;
    540         }
    541         return pNode == (CPLTreeNode*)this ? NULL : pNode;
    542       }
    543       case FirstNeighbor: {
    544         CPLTreeNode* pParent = (CPLTreeNode*)this;
    545         CPLTreeNode* pTemp;
    546         while ((pTemp = pParent->m_pParentNode) != NULL) {
    547           pParent = pTemp;
    548         }
    549         return pParent == (CPLTreeNode*)this ? NULL : pParent;
    550       }
    551       case PreviousNeighbor: {
    552         if (m_pPrevNode == NULL) {
    553           return m_pParentNode;
    554         }
    555         CPLTreeNode* pNode = m_pPrevNode;
    556         CPLTreeNode* pTemp;
    557         while ((pTemp = pNode->m_pChildNode) != NULL) {
    558           pNode = pTemp;
    559           while ((pTemp = pNode->m_pNextNode) != NULL) {
    560             pNode = pTemp;
    561           }
    562         }
    563         return pNode;
    564       }
    565       case NextNeighbor: {
    566         if (m_pChildNode != NULL) {
    567           return m_pChildNode;
    568         }
    569         if (m_pNextNode != NULL) {
    570           return m_pNextNode;
    571         }
    572         CPLTreeNode* pNode = m_pParentNode;
    573         while (pNode != NULL) {
    574           if (pNode->m_pNextNode != NULL) {
    575             return pNode->m_pNextNode;
    576           }
    577           pNode = pNode->m_pParentNode;
    578         }
    579         return NULL;
    580       }
    581       case LastNeighbor: {
    582         CPLTreeNode* pNode = (CPLTreeNode*)this;
    583         CPLTreeNode* pTemp;
    584         while ((pTemp = pNode->m_pParentNode) != NULL) {
    585           pNode = pTemp;
    586         }
    587         while (TRUE) {
    588           CPLTreeNode* pTemp;
    589           while ((pTemp = pNode->m_pNextNode) != NULL) {
    590             pNode = pTemp;
    591           }
    592           if (pNode->m_pChildNode == NULL) {
    593             break;
    594           }
    595           pNode = pNode->m_pChildNode;
    596         }
    597         return pNode == (CPLTreeNode*)this ? NULL : pNode;
    598       }
    599       case FirstChild:
    600         return m_pChildNode;
    601       case LastChild: {
    602         if (m_pChildNode == NULL) {
    603           return NULL;
    604         }
    605         CPLTreeNode* pChild = m_pChildNode;
    606         CPLTreeNode* pTemp;
    607         while ((pTemp = pChild->m_pNextNode) != NULL) {
    608           pChild = pTemp;
    609         }
    610         return pChild;
    611       }
    612       default:
    613         break;
    614     }
    615     return NULL;
    616   }
    617   void SetParentNode(CPLTreeNode* pNode) { m_pParentNode = pNode; }
    618   int32_t CountChildNodes() const {
    619     int32_t iCount = 0;
    620     CPLTreeNode* pNode = m_pChildNode;
    621     while (pNode) {
    622       iCount++;
    623       pNode = pNode->m_pNextNode;
    624     }
    625     return iCount;
    626   }
    627   CPLTreeNode* GetChildNode(int32_t iIndex) const {
    628     int32_t iCount = 0;
    629     CPLTreeNode* pNode = m_pChildNode;
    630     while (pNode) {
    631       if (iIndex == iCount) {
    632         return pNode;
    633       }
    634       iCount++;
    635       pNode = pNode->m_pNextNode;
    636     }
    637     return NULL;
    638   }
    639   int32_t GetNodeIndex() const {
    640     int32_t index = 0;
    641     CPLTreeNode* pNode = m_pPrevNode;
    642     while (pNode != NULL) {
    643       index++;
    644       pNode = pNode->m_pPrevNode;
    645     }
    646     return index;
    647   }
    648   FX_BOOL IsParentNode(const CPLTreeNode* pNode) const {
    649     CPLTreeNode* pParent = m_pParentNode;
    650     while (pParent != NULL) {
    651       if (pParent == pNode) {
    652         return TRUE;
    653       }
    654       pParent = pParent->GetTreeNode(Parent);
    655     }
    656     return FALSE;
    657   }
    658   FX_BOOL IsChildNode(const CPLTreeNode* pNode) const {
    659     if (pNode == NULL) {
    660       return FALSE;
    661     }
    662     return pNode->IsParentNode((const CPLTreeNode*)this);
    663   }
    664   void SetChildNode(CPLTreeNode* pNode) { m_pChildNode = pNode; }
    665   void SetPrevNode(CPLTreeNode* pNode) { m_pPrevNode = pNode; }
    666   void SetNextNode(CPLTreeNode* pNode) { m_pNextNode = pNode; }
    667   int32_t GetNodeLevel() const {
    668     int32_t iLevel = 0;
    669     CPLTreeNode* pNode = (CPLTreeNode*)this;
    670     while ((pNode = pNode->m_pParentNode) != NULL) {
    671       iLevel++;
    672     }
    673     return iLevel;
    674   }
    675   FX_BOOL IsRootNode() const { return m_pParentNode == NULL; }
    676   baseType GetData() const { return m_Data; }
    677   void SetData(baseType data) { m_Data = data; }
    678 
    679  protected:
    680   CPLTreeNode* m_pParentNode;
    681   CPLTreeNode* m_pChildNode;
    682   CPLTreeNode* m_pPrevNode;
    683   CPLTreeNode* m_pNextNode;
    684   baseType m_Data;
    685   friend class CFX_CPLTree<baseType>;
    686 };
    687 template <class baseType>
    688 class CFX_CPLTree {
    689  public:
    690   typedef CFX_CPLTreeNode<baseType> CPLTreeNode;
    691   CFX_CPLTree() : m_Root() {}
    692   ~CFX_CPLTree() {
    693     CPLTreeNode* pNode = m_Root.GetNode(CPLTreeNode::LastNeighbor);
    694     while (pNode != NULL) {
    695       if (pNode->IsRootNode()) {
    696         break;
    697       }
    698       CPLTreeNode* pTemp = pNode->GetNode(CPLTreeNode::PreviousNeighbor);
    699       delete pNode;
    700       pNode = pTemp;
    701     }
    702   }
    703   CPLTreeNode* GetRoot() { return &m_Root; }
    704   CPLTreeNode* AddChild(baseType data, CPLTreeNode* pParent = NULL) {
    705     if (pParent == NULL) {
    706       pParent = &m_Root;
    707     }
    708     CPLTreeNode* pChild = new CPLTreeNode;
    709     pChild->SetParentNode(pParent);
    710     pChild->SetData(data);
    711     if (pParent->m_pChildNode == NULL) {
    712       pParent->m_pChildNode = pChild;
    713     } else {
    714       CPLTreeNode* pLast = pParent->GetNode(CPLTreeNode::LastChild);
    715       pChild->SetPrevNode(pLast);
    716       pLast->SetNextNode(pChild);
    717     }
    718     return pChild;
    719   }
    720 
    721  protected:
    722   CPLTreeNode m_Root;
    723 };
    724 #endif
    725