151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)/* 251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * Copyright (C) 2012 Apple Inc. All rights reserved. 351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * 451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * Redistribution and use in source and binary forms, with or without 551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * modification, are permitted provided that the following conditions 651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * are met: 751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * 1. Redistributions of source code must retain the above copyright 851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * notice, this list of conditions and the following disclaimer. 951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * 2. Redistributions in binary form must reproduce the above copyright 1051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * notice, this list of conditions and the following disclaimer in the 1151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * documentation and/or other materials provided with the distribution. 1251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * 1351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' 1451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 1551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 1651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS 1751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 1851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 1951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 2251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 2351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) * THE POSSIBILITY OF SUCH DAMAGE. 2451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) */ 2551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 2651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)#include "config.h" 2751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 2851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)#include "wtf/TreeNode.h" 2951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 3051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)#include "wtf/PassRefPtr.h" 3151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)#include "wtf/RefCounted.h" 3251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)#include "wtf/RefPtr.h" 3351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)#include <gtest/gtest.h> 3451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 3551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)namespace { 3651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 3751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)class TestTree : public RefCounted<TestTree>, public TreeNode<TestTree> { 3851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)public: 3951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) static PassRefPtr<TestTree> create() { return adoptRef(new TestTree()); } 4051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)}; 4151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 42f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo LiuTEST(TreeNodeTest, AppendChild) 4351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles){ 4451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> root = TestTree::create(); 4551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> firstChild = TestTree::create(); 4651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> lastChild = TestTree::create(); 4751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 4851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) root->appendChild(firstChild.get()); 496f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->firstChild(), firstChild.get()); 506f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->lastChild(), firstChild.get()); 516f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(firstChild->parent(), root.get()); 5251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 5351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) root->appendChild(lastChild.get()); 546f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->firstChild(), firstChild.get()); 556f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->lastChild(), lastChild.get()); 566f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(lastChild->previous(), firstChild.get()); 576f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(firstChild->next(), lastChild.get()); 586f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(lastChild->parent(), root.get()); 5951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)} 6051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 61f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo LiuTEST(TreeNodeTest, InsertBefore) 6251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles){ 6351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> root = TestTree::create(); 6451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> firstChild = TestTree::create(); 6551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> middleChild = TestTree::create(); 6651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> lastChild = TestTree::create(); 6751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 6851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) // Inserting single node 6951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) root->insertBefore(lastChild.get(), 0); 706f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(lastChild->parent(), root.get()); 716f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->firstChild(), lastChild.get()); 726f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->lastChild(), lastChild.get()); 7351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 7451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) // Then prepend 7551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) root->insertBefore(firstChild.get(), lastChild.get()); 766f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(firstChild->parent(), root.get()); 776f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->firstChild(), firstChild.get()); 786f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->lastChild(), lastChild.get()); 796f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(firstChild->next(), lastChild.get()); 806f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(firstChild.get(), lastChild->previous()); 8151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 8251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) // Inserting in the middle 8351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) root->insertBefore(middleChild.get(), lastChild.get()); 846f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(middleChild->parent(), root.get()); 856f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->firstChild(), firstChild.get()); 866f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->lastChild(), lastChild.get()); 876f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(middleChild->previous(), firstChild.get()); 886f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(middleChild->next(), lastChild.get()); 896f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(firstChild->next(), middleChild.get()); 906f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(lastChild->previous(), middleChild.get()); 9151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 9251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)} 9351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 94f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo LiuTEST(TreeNodeTest, RemoveSingle) 9551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles){ 9651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> root = TestTree::create(); 9751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> child = TestTree::create(); 9851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> nullNode; 9951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 10051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) root->appendChild(child.get()); 10151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) root->removeChild(child.get()); 1026f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(child->next(), nullNode.get()); 1036f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(child->previous(), nullNode.get()); 1046f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(child->parent(), nullNode.get()); 1056f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->firstChild(), nullNode.get()); 1066f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(root->lastChild(), nullNode.get()); 10751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)} 10851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 10951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)class Trio { 11051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)public: 11151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) Trio() 11251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) : root(TestTree::create()) 11351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) , firstChild(TestTree::create()) 11451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) , middleChild(TestTree::create()) 11551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) , lastChild(TestTree::create()) 11651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) { 11751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) } 11851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 11951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) void appendChildren() 12051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) { 12151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) root->appendChild(firstChild.get()); 12251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) root->appendChild(middleChild.get()); 12351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) root->appendChild(lastChild.get()); 12451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) } 12551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 12651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> root; 12751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> firstChild; 12851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> middleChild; 12951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> lastChild; 13051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)}; 13151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 132f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo LiuTEST(TreeNodeTest, RemoveMiddle) 13351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles){ 13451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) Trio trio; 13551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.appendChildren(); 13651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 13751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.root->removeChild(trio.middleChild.get()); 1386f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_TRUE(trio.middleChild->orphan()); 1396f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(trio.firstChild->next(), trio.lastChild.get()); 1406f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(trio.lastChild->previous(), trio.firstChild.get()); 1416f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(trio.root->firstChild(), trio.firstChild.get()); 1426f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(trio.root->lastChild(), trio.lastChild.get()); 14351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)} 14451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 145f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo LiuTEST(TreeNodeTest, RemoveLast) 14651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles){ 14751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> nullNode; 14851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) Trio trio; 14951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.appendChildren(); 15051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 15151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.root->removeChild(trio.lastChild.get()); 1526f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_TRUE(trio.lastChild->orphan()); 1536f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(trio.middleChild->next(), nullNode.get()); 1546f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(trio.root->firstChild(), trio.firstChild.get()); 1556f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(trio.root->lastChild(), trio.middleChild.get()); 15651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)} 15751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 158f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo LiuTEST(TreeNodeTest, RemoveFirst) 15951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles){ 16051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> nullNode; 16151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) Trio trio; 16251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.appendChildren(); 16351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 16451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.root->removeChild(trio.firstChild.get()); 1656f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_TRUE(trio.firstChild->orphan()); 1666f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(trio.middleChild->previous(), nullNode.get()); 1676f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(trio.root->firstChild(), trio.middleChild.get()); 1686f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(trio.root->lastChild(), trio.lastChild.get()); 16951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)} 17051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 171f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo LiuTEST(TreeNodeTest, TakeChildrenFrom) 17210f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch{ 17310f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch RefPtr<TestTree> newParent = TestTree::create(); 17410f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch Trio trio; 17510f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch trio.appendChildren(); 17610f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch 17710f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch newParent->takeChildrenFrom(trio.root.get()); 17810f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch 17910f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch EXPECT_FALSE(trio.root->hasChildren()); 18010f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch EXPECT_TRUE(newParent->hasChildren()); 18110f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch EXPECT_EQ(trio.firstChild.get(), newParent->firstChild()); 18210f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch EXPECT_EQ(trio.middleChild.get(), newParent->firstChild()->next()); 18310f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch EXPECT_EQ(trio.lastChild.get(), newParent->lastChild()); 18410f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch} 18510f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch 18651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)class TrioWithGrandChild : public Trio { 18751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)public: 18851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) TrioWithGrandChild() 18951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) : grandChild(TestTree::create()) 19051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) { 19151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) } 19251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 19351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) void appendChildren() 19451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) { 19551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) Trio::appendChildren(); 19651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) middleChild->appendChild(grandChild.get()); 19751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) } 19851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 19951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) RefPtr<TestTree> grandChild; 20051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)}; 20151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 202f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo LiuTEST(TreeNodeTest, TraverseNext) 20351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles){ 20451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) TrioWithGrandChild trio; 20551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.appendChildren(); 20651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 20751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) TestTree* order[] = { 20851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.root.get(), trio.firstChild.get(), trio.middleChild.get(), 20951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.grandChild.get(), trio.lastChild.get() 21051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) }; 21151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 21251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) unsigned orderIndex = 0; 21351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) for (TestTree* node = trio.root.get(); node; node = traverseNext(node), orderIndex++) 2146f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(node, order[orderIndex]); 2156f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*)); 21651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)} 21751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 218f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo LiuTEST(TreeNodeTest, TraverseNextPostORder) 21951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles){ 22051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) TrioWithGrandChild trio; 22151b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.appendChildren(); 22251b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 22351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 22451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) TestTree* order[] = { 22551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.firstChild.get(), 22651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) trio.grandChild.get(), trio.middleChild.get(), trio.lastChild.get(), trio.root.get() 22751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) }; 22851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 22951b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) unsigned orderIndex = 0; 23051b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) for (TestTree* node = traverseFirstPostOrder(trio.root.get()); node; node = traverseNextPostOrder(node), orderIndex++) 2316f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(node, order[orderIndex]); 2326f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch EXPECT_EQ(orderIndex, sizeof(order) / sizeof(TestTree*)); 23351b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 23451b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)} 23551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 23651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 23751b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles)} // namespace 238