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