1 // Copyright 2017 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 XFA_FXFA_PARSER_CXFA_NODEITERATORTEMPLATE_H_
8 #define XFA_FXFA_PARSER_CXFA_NODEITERATORTEMPLATE_H_
9 
10 #include "core/fxcrt/unowned_ptr.h"
11 
12 template <class NodeType,
13           class TraverseStrategy,
14           typename HolderType = UnownedPtr<NodeType>>
15 class CXFA_NodeIteratorTemplate {
16  public:
CXFA_NodeIteratorTemplate(NodeType * pRoot)17   explicit CXFA_NodeIteratorTemplate(NodeType* pRoot)
18       : m_pRoot(pRoot), m_pCurrent(pRoot) {}
19 
GetRoot()20   NodeType* GetRoot() const { return m_pRoot.Get(); }
GetCurrent()21   NodeType* GetCurrent() const { return m_pCurrent.Get(); }
22 
Reset()23   void Reset() { m_pCurrent = m_pRoot; }
SetCurrent(NodeType * pNode)24   bool SetCurrent(NodeType* pNode) {
25     if (!RootReachableFromNode(pNode)) {
26       m_pCurrent = nullptr;
27       return false;
28     }
29     m_pCurrent.Reset(pNode);
30     return true;
31   }
32 
MoveToPrev()33   NodeType* MoveToPrev() {
34     if (!m_pRoot)
35       return nullptr;
36     if (!m_pCurrent) {
37       m_pCurrent.Reset(LastDescendant(m_pRoot.Get()));
38       return m_pCurrent.Get();
39     }
40     NodeType* pSibling = PreviousSiblingWithinSubtree(m_pCurrent.Get());
41     if (pSibling) {
42       m_pCurrent.Reset(LastDescendant(pSibling));
43       return m_pCurrent.Get();
44     }
45     NodeType* pParent = ParentWithinSubtree(m_pCurrent.Get());
46     if (pParent)
47       m_pCurrent.Reset(pParent);
48     return pParent;
49   }
50 
MoveToNext()51   NodeType* MoveToNext() {
52     if (!m_pRoot || !m_pCurrent)
53       return nullptr;
54     NodeType* pChild = TraverseStrategy::GetFirstChild(m_pCurrent.Get());
55     if (pChild) {
56       m_pCurrent.Reset(pChild);
57       return pChild;
58     }
59     return SkipChildrenAndMoveToNext();
60   }
61 
SkipChildrenAndMoveToNext()62   NodeType* SkipChildrenAndMoveToNext() {
63     if (!m_pRoot)
64       return nullptr;
65     NodeType* pNode = m_pCurrent.Get();
66     while (pNode) {
67       NodeType* pSibling = NextSiblingWithinSubtree(pNode);
68       if (pSibling) {
69         m_pCurrent.Reset(pSibling);
70         return pSibling;
71       }
72       pNode = ParentWithinSubtree(pNode);
73     }
74     m_pCurrent = nullptr;
75     return nullptr;
76   }
77 
78  private:
RootReachableFromNode(NodeType * pNode)79   bool RootReachableFromNode(NodeType* pNode) {
80     return pNode && (pNode == m_pRoot ||
81                      RootReachableFromNode(TraverseStrategy::GetParent(pNode)));
82   }
83 
ParentWithinSubtree(NodeType * pNode)84   NodeType* ParentWithinSubtree(NodeType* pNode) {
85     return pNode && pNode != m_pRoot ? TraverseStrategy::GetParent(pNode)
86                                      : nullptr;
87   }
88 
NextSiblingWithinSubtree(NodeType * pNode)89   NodeType* NextSiblingWithinSubtree(NodeType* pNode) {
90     return pNode != m_pRoot ? TraverseStrategy::GetNextSibling(pNode) : nullptr;
91   }
92 
PreviousSiblingWithinSubtree(NodeType * pNode)93   NodeType* PreviousSiblingWithinSubtree(NodeType* pNode) {
94     NodeType* pParent = ParentWithinSubtree(pNode);
95     if (!pParent)
96       return nullptr;
97     NodeType* pCurrent = TraverseStrategy::GetFirstChild(pParent);
98     NodeType* pPrevious = nullptr;
99     while (pCurrent != pNode) {
100       pPrevious = pCurrent;
101       pCurrent = TraverseStrategy::GetNextSibling(pCurrent);
102     }
103     return pPrevious;
104   }
105 
LastChild(NodeType * pNode)106   NodeType* LastChild(NodeType* pNode) {
107     NodeType* pPrevious = nullptr;
108     NodeType* pChild = TraverseStrategy::GetFirstChild(pNode);
109     while (pChild) {
110       pPrevious = pChild;
111       pChild = NextSiblingWithinSubtree(pChild);
112     }
113     return pPrevious;
114   }
115 
LastDescendant(NodeType * pNode)116   NodeType* LastDescendant(NodeType* pNode) {
117     NodeType* pChild = LastChild(pNode);
118     return pChild ? LastDescendant(pChild) : pNode;
119   }
120 
121   HolderType m_pRoot;
122   HolderType m_pCurrent;
123 };
124 
125 #endif  // XFA_FXFA_PARSER_CXFA_NODEITERATORTEMPLATE_H_
126