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)
CFX_BaseArray(iGrowSize,sizeof (baseType))70       : CFX_BaseArray(iGrowSize, sizeof(baseType)) {}
CFX_BaseArrayTemplate(int32_t iGrowSize,int32_t iBlockSize)71   CFX_BaseArrayTemplate(int32_t iGrowSize, int32_t iBlockSize)
72       : CFX_BaseArray(iGrowSize, iBlockSize) {}
GetSize()73   int32_t GetSize() const { return CFX_BaseArray::GetSize(); }
GetBlockSize()74   int32_t GetBlockSize() const { return CFX_BaseArray::GetBlockSize(); }
AddSpace()75   baseType* AddSpace() {
76     return (baseType*)CFX_BaseArray::AddSpaceTo(CFX_BaseArray::GetSize());
77   }
Add(const baseType & element)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   }
GetBuffer()83   baseType* GetBuffer() const { return (baseType*)CFX_BaseArray::GetBuffer(); }
GetAt(int32_t index)84   baseType& GetAt(int32_t index) const {
85     return *(baseType*)CFX_BaseArray::GetAt(index);
86   }
GetPtrAt(int32_t index)87   baseType* GetPtrAt(int32_t index) const {
88     return (baseType*)CFX_BaseArray::GetAt(index);
89   }
SetAt(int32_t index,const baseType & element)90   void SetAt(int32_t index, const baseType& element) {
91     *(baseType*)CFX_BaseArray::GetAt(index) = element;
92   }
SetAtGrow(int32_t index,const baseType & element)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)
CFX_BaseArray(iGrowSize,sizeof (baseType))120       : CFX_BaseArray(iGrowSize, sizeof(baseType)) {}
~CFX_ObjectBaseArrayTemplate()121   ~CFX_ObjectBaseArrayTemplate() { RemoveAll(FALSE); }
GetSize()122   int32_t GetSize() const { return CFX_BaseArray::GetSize(); }
GetBlockSize()123   int32_t GetBlockSize() const { return CFX_BaseArray::GetBlockSize(); }
Add(const baseType & element)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   }
GetAt(int32_t index)130   baseType& GetAt(int32_t index) const {
131     return *(baseType*)CFX_BaseArray::GetAt(index);
132   }
GetPtrAt(int32_t index)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)
CFX_BaseMassArray(iChunkSize,sizeof (baseType))236       : CFX_BaseMassArray(iChunkSize, sizeof(baseType)) {}
CFX_MassArrayTemplate(int32_t iChunkSize,int32_t iBlockSize)237   CFX_MassArrayTemplate(int32_t iChunkSize, int32_t iBlockSize)
238       : CFX_BaseMassArray(iChunkSize, iBlockSize) {}
GetSize()239   int32_t GetSize() const { return CFX_BaseMassArray::GetSize(); }
AddSpace()240   baseType* AddSpace() {
241     return (baseType*)CFX_BaseMassArray::AddSpaceTo(
242         CFX_BaseMassArray::GetSize());
243   }
Add(const baseType & element)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   }
GetAt(int32_t index)249   baseType& GetAt(int32_t index) const {
250     return *(baseType*)CFX_BaseMassArray::GetAt(index);
251   }
GetPtrAt(int32_t index)252   baseType* GetPtrAt(int32_t index) const {
253     return (baseType*)CFX_BaseMassArray::GetAt(index);
254   }
SetAt(int32_t index,const baseType & element)255   void SetAt(int32_t index, const baseType& element) {
256     *(baseType*)CFX_BaseMassArray::GetAt(index) = element;
257   }
SetAtGrow(int32_t index,const baseType & element)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)
CFX_BaseMassArray(iChunkSize,sizeof (baseType))288       : CFX_BaseMassArray(iChunkSize, sizeof(baseType)) {}
~CFX_ObjectMassArrayTemplate()289   ~CFX_ObjectMassArrayTemplate() { RemoveAll(FALSE); }
GetSize()290   int32_t GetSize() const { return CFX_BaseMassArray::GetSize(); }
Add(const baseType & element)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   }
GetAt(int32_t index)297   baseType& GetAt(int32_t index) const {
298     return *(baseType*)CFX_BaseMassArray::GetAt(index);
299   }
GetPtrAt(int32_t index)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)
CFX_BaseDiscreteArray(iChunkSize,sizeof (baseType))378       : CFX_BaseDiscreteArray(iChunkSize, sizeof(baseType)) {}
GetAt(int32_t index,const baseType & defValue)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   }
GetPtrAt(int32_t index)383   baseType* GetPtrAt(int32_t index) const {
384     return (baseType*)CFX_BaseDiscreteArray::GetAt(index);
385   }
SetAtGrow(int32_t index,const baseType & element)386   void SetAtGrow(int32_t index, const baseType& element) {
387     *(baseType*)CFX_BaseDiscreteArray::AddSpaceTo(index) = element;
388   }
RemoveAll()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)
CFX_BaseStack(iChunkSize,sizeof (baseType))410       : CFX_BaseStack(iChunkSize, sizeof(baseType)) {}
Push(const baseType & element)411   int32_t Push(const baseType& element) {
412     int32_t index = CFX_BaseStack::GetSize();
413     *(baseType*)CFX_BaseStack::Push() = element;
414     return index;
415   }
Pop()416   void Pop() { CFX_BaseStack::Pop(); }
GetTopElement()417   baseType* GetTopElement() const {
418     return (baseType*)CFX_BaseStack::GetTopElement();
419   }
GetSize()420   int32_t GetSize() const { return CFX_BaseStack::GetSize(); }
GetAt(int32_t index)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)
CFX_BaseStack(iChunkSize,sizeof (baseType))436       : CFX_BaseStack(iChunkSize, sizeof(baseType)) {}
~CFX_ObjectStackTemplate()437   ~CFX_ObjectStackTemplate() { RemoveAll(); }
Push(const baseType & element)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   }
Pop()444   void Pop() {
445     baseType* p = (baseType*)CFX_BaseStack::GetTopElement();
446     if (p != NULL) {
447       p->~baseType();
448     }
449     CFX_BaseStack::Pop();
450   }
GetTopElement()451   baseType* GetTopElement() const {
452     return (baseType*)CFX_BaseStack::GetTopElement();
453   }
GetSize()454   int32_t GetSize() const { return CFX_BaseStack::GetSize(); }
GetAt(int32_t index)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;
CFX_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   };
GetNode(TreeNode eNode)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   }
SetParentNode(CPLTreeNode * pNode)617   void SetParentNode(CPLTreeNode* pNode) { m_pParentNode = pNode; }
CountChildNodes()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   }
GetChildNode(int32_t iIndex)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   }
GetNodeIndex()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   }
IsParentNode(const CPLTreeNode * pNode)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   }
IsChildNode(const CPLTreeNode * pNode)658   FX_BOOL IsChildNode(const CPLTreeNode* pNode) const {
659     if (pNode == NULL) {
660       return FALSE;
661     }
662     return pNode->IsParentNode((const CPLTreeNode*)this);
663   }
SetChildNode(CPLTreeNode * pNode)664   void SetChildNode(CPLTreeNode* pNode) { m_pChildNode = pNode; }
SetPrevNode(CPLTreeNode * pNode)665   void SetPrevNode(CPLTreeNode* pNode) { m_pPrevNode = pNode; }
SetNextNode(CPLTreeNode * pNode)666   void SetNextNode(CPLTreeNode* pNode) { m_pNextNode = pNode; }
GetNodeLevel()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   }
IsRootNode()675   FX_BOOL IsRootNode() const { return m_pParentNode == NULL; }
GetData()676   baseType GetData() const { return m_Data; }
SetData(baseType 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;
CFX_CPLTree()691   CFX_CPLTree() : m_Root() {}
~CFX_CPLTree()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   }
GetRoot()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