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