int getWorldFrameLoop(const UndirectedTree & undirected_tree,
                          const KDL::CoDyCo::GeneralizedJntPositions &q,
                          const Traversal & traversal,
                          const int distal_link_index,
                          Frame & frame_world_link)
    {
        LinkMap::const_iterator distal_it = undirected_tree.getLink(distal_link_index);
        LinkMap::const_iterator proximal_it = traversal.getBaseLink();

        Frame currentFrame;
        Frame resultFrame = Frame::Identity();
        for(LinkMap::const_iterator link=distal_it; link != proximal_it; link = traversal.getParentLink(link) ) {
            LinkMap::const_iterator parent_link = traversal.getParentLink(link);
            assert( parent_link != undirected_tree.getInvalidLinkIterator() );

            double joint_position;

            if( link->getAdjacentJoint(parent_link)->getJoint().getType() != Joint::None ) {
                joint_position = q.jnt_pos((link->getAdjacentJoint(parent_link))->getDOFIndex());
            } else {
                joint_position =0;
            }

            currentFrame = link->pose(parent_link,
                                             joint_position);

            resultFrame = currentFrame*resultFrame;
        }

        frame_world_link = q.base_pos*resultFrame;

        return 0;
    }

void NistXmlDocument::annotateSentence(uint sentno, const std::string &annot) {
	typedef Arabica::DOM::Traversal::DocumentTraversal<std::string> Traversal;
	typedef Arabica::DOM::Comment<std::string> Comment;

	Traversal dt = outnode_.getOwnerDocument().createDocumentTraversal();
	SegNodeFilter filter;
	Traversal::TreeWalkerT it = dt.createTreeWalker(outnode_,
					static_cast<unsigned long>(Arabica::DOM::Traversal::SHOW_TEXT),
					filter, true);

	for(uint i = 0; i < sentno; i++)
		assert(it.nextNode() != 0);

	Traversal::NodeT n = it.nextNode(); // the filter finds the next node inside the <seg> element
	assert(n != 0);
	n = n.getParentNode(); // get the <seg>

	Comment comm = n.getOwnerDocument().createComment(" SEG " + annot + " ");

	Traversal::NodeT p = n.getPreviousSibling();
	Traversal::NodeT txt;
	if(p != 0 && p.getNodeType() == Arabica::DOM::Node<std::string>::TEXT_NODE) {
		txt = p;
		p = p.getPreviousSibling();
	}

	if(p != 0 && p.getNodeType() == Arabica::DOM::Node<std::string>::COMMENT_NODE &&
			boost::starts_with(p.getNodeValue(), " SEG "))
		p.getParentNode().replaceChild(comm, p);
	else {
		n.getParentNode().insertBefore(comm, n);
		if(txt != 0)
			n.getParentNode().insertBefore(txt.cloneNode(false), n);
	}
}

    int getFramesLoop(const UndirectedTree & undirected_tree,
                      const KDL::JntArray &q,
                      const Traversal & traversal,
                      std::vector<Frame> & X_base,
                      KDL::Frame world2base)
    {
          for(int i=0; i < (int)traversal.getNrOfVisitedLinks(); i++) {
            double joint_pos;
            LinkMap::const_iterator link_it = traversal.getOrderedLink(i);
            int link_nmbr = link_it->getLinkIndex();
            if( i == 0 ) {
                assert( traversal.getParentLink(link_nmbr) == undirected_tree.getInvalidLinkIterator() );
                X_base[link_nmbr] = world2base;
            } else {
                LinkMap::const_iterator parent_it = traversal.getParentLink(link_it);
                int parent_nmbr = parent_it->getLinkIndex();

                if( link_it->getAdjacentJoint(parent_it)->getJoint().getType() != Joint::None ) {
                    int dof_nr = link_it->getAdjacentJoint(parent_it)->getDOFIndex();
                    joint_pos = q(dof_nr);
                } else {
                    joint_pos =  0.0;
                }
                KDL::Frame X_parent_son = link_it->pose(parent_it,joint_pos);
                X_base[link_nmbr] = X_base[parent_nmbr]*X_parent_son;
            }
        }
        return 0;
    }

int
main ( int argc, char* argv[] )
   {
  // Build the abstract syntax tree
     SgProject* project = frontend(argc,argv);
     ROSE_ASSERT (project != NULL);

  // Build the inherited attribute
     InheritedAttribute inheritedAttribute;

  // Define the traversal
     Traversal myTraversal;

  // Call the traversal starting at the project (root) node of the AST
     myTraversal.traverseInputFiles(project,inheritedAttribute);

  // Demonstrate the the transformation will pass the AST tests.
     AstTests::runAllTests (project);

  // Output an optional graph of the AST (just the tree, when active)
     generateDOT ( *project );

  // Output an optional graph of the AST (the whole graph, of bounded complexity, when active)
     const int MAX_NUMBER_OF_IR_NODES_TO_GRAPH_FOR_WHOLE_GRAPH = 10000;
     generateAstGraph(project,MAX_NUMBER_OF_IR_NODES_TO_GRAPH_FOR_WHOLE_GRAPH,"");

     return backend (project);	// only backend error code is reported
   }

void checkComputeTraversal(const Model & model)
{
    Traversal traversal;
    bool ok = model.computeFullTreeTraversal(traversal);

    ASSERT_EQUAL_DOUBLE(ok,true);
    ASSERT_EQUAL_DOUBLE(traversal.getNrOfVisitedLinks(),model.getNrOfLinks());
}

bool Model::computeFullTreeTraversal(Traversal & traversal, const LinkIndex traversalBase) const
{
    if( traversalBase < 0 || traversalBase >= (LinkIndex)this->getNrOfLinks() )
    {
        reportError("Model","computeFullTreeTraversal","requested traversalBase is out of bounds");
        return false;
    }

    // Resetting the traversal for populating it
    traversal.reset(*this);

    // A link is considered visit when all its child (given the traversalBase)
    // have been added to the traversal
    std::deque<stackEl> linkToVisit;

    // We add as first link the requested traversalBase
    addBaseLinkToTraversal(*this,traversal,traversalBase,linkToVisit);

    // while there is some link still to visit
    while( linkToVisit.size() > 0 )
    {
        assert(linkToVisit.size() <= this->getNrOfLinks());

        // DPS : we use linkToVisit as a stack
        LinkConstPtr visitedLink = linkToVisit.back().link;
        LinkConstPtr visitedLinkParent = linkToVisit.back().parent;
        LinkIndex visitedLinkIndex = visitedLink->getIndex();
        linkToVisit.pop_back();

        for(unsigned int neigh_i=0; neigh_i < this->getNrOfNeighbors(visitedLinkIndex); neigh_i++ )
        {
            // add to the stack all the neighbors, except for parent link
            // (if the visited link is the base one, add all the neighbors)
            // the visited link is already in the Traversal, so we can use it
            // to check for its parent
            Neighbor neighb = this->getNeighbor(visitedLinkIndex,neigh_i);
            if( visitedLinkParent == 0 || neighb.neighborLink != visitedLinkParent->getIndex() )
            {
                addLinkToTraversal(*this,traversal,neighb.neighborLink,
                    neighb.neighborJoint,visitedLink->getIndex(),linkToVisit);
            }
        }
    }

    // At this point the traversal should contain all the links
    // of the model
    assert(traversal.getNrOfVisitedLinks() == this->getNrOfLinks());

    return true;
}

    void getFloatingBaseJacobianLoop(const UndirectedTree & undirected_tree,
                                     const GeneralizedJntPositions &q,
                                     const Traversal & traversal,
                                     const int link_index,
                                     Jacobian & jac)
    {
        Frame T_total = Frame::Identity(); //The transformation between link_index frame and current_link frame

        assert(link_index < (int)undirected_tree.getNrOfLinks());

        KDL::CoDyCo::LinkMap::const_iterator current_link;
        current_link = undirected_tree.getLink(link_index);

        //All the columns not modified are zero
        SetToZero(jac);

        KDL::CoDyCo::LinkMap::const_iterator parent_link=traversal.getParentLink(current_link);
        while(current_link != traversal.getBaseLink()) {
            double joint_pos = 0.0;
            if( current_link->getAdjacentJoint(parent_link)->getNrOfDOFs() == 1 ) {
                KDL::Twist jac_col;

                int dof_index = current_link->getAdjacentJoint(parent_link)->getDOFIndex();

                joint_pos = q.jnt_pos(dof_index);
                KDL::Twist S_current_parent = parent_link->S(current_link,joint_pos);

                jac_col = T_total*S_current_parent;

                assert(6+dof_index < (int)jac.columns());
                assert( dof_index < (int)undirected_tree.getNrOfDOFs() );
                jac.setColumn(6+dof_index,jac_col);
            }

            KDL::Frame X_current_parent = parent_link->pose(current_link,joint_pos);

            T_total = T_total*X_current_parent;

            current_link = parent_link;
            parent_link = traversal.getParentLink(current_link);
        }

        //Setting the floating part of the Jacobian
        T_total = T_total*KDL::Frame(q.base_pos.M.Inverse());

        jac.data.block(0,0,6,6) = TwistTransformationMatrix(T_total);

        jac.changeBase(T_total.M.Inverse());
    }

// size_t getLocalScopeNum ( SgFunctionDefinition* func_def, const SgScopeStatement* target)
size_t
getLocalScopeNum (const SgFunctionDefinition* func_def, const SgScopeStatement* target)
{
#if SKIP_BLOCK_NUMBER_CACHING
  // DQ (10/4/2006): This takes too long and stalls the compilation of 
  // some large codes (plum hall e.g. cvs06a/conform/ch7_22.c).  It is 
  // rewritten below to use a cache mechanisk link to a cache invalidation 
  // mechanism.

  // Preorder traversal to count the number of basic blocks preceeding 'target'
  class Traversal : public AstSimpleProcessing
  {
  public:
    Traversal (const SgScopeStatement* target)
      : target_ (target), count_ (0), found_ (false)
    {}
    void visit (SgNode* node)
    {
      if (!found_)
        {
          const SgScopeStatement* stmt = isSgScopeStatement (node);
          if (stmt)
            {
              count_++;
              found_ = (stmt == target_);
            }
        }
    }
    size_t count (void) const { return found_ ? count_ : 0; }
  private:
    const SgScopeStatement* target_; // Target scope statement
    size_t count_; // found_ ? number of target : number of last block seen
    bool found_; // true <==> target_ has been found
  };

  Traversal counter (target);
  counter.traverse (const_cast<SgFunctionDefinition *> (func_def), preorder);
  return counter.count ();
#else
  // DQ (10/6/2006): Implemented caching of computed lables for scopes in 
  // functions to avoid quadratic behavior of previous implementation.  The model
  // for this is the same a s what will be done to support caching of mangled names.
  // printf ("getLocalScopeNum calling func_def->get_scope_number(target)! \n");

     return func_def->get_scope_number(target);
#endif
}

int
main ( int argc, char* argv[] )
   {
  // Build the abstract syntax tree
     SgProject* project = frontend(argc,argv);
     ROSE_ASSERT (project != NULL);

  // Build the inherited attribute
     InheritedAttribute inheritedAttribute = false;

  // Define the traversal
     Traversal myTraversal;

  // Call the traversal starting at the project (root) node of the AST
     myTraversal.traverseInputFiles(project,inheritedAttribute);

  // This program only does analysis, so it need not call the backend to generate code.
     return 0;
   }

int
main ( int argc, char* argv[] )
   {
  // Initialize and check compatibility. See rose::initialize
     ROSE_INITIALIZE;

     SgProject* project = frontend(argc,argv);
     ROSE_ASSERT (project != NULL);

  // Build the inherited attribute
     InheritedAttribute inheritedAttribute;

     Traversal myTraversal;

  // Call the traversal starting at the sageProject node of the AST
     myTraversal.traverseInputFiles(project,inheritedAttribute);

     return 0;
   }

void  addBaseLinkToTraversal(const Model & model, Traversal & traversal,
                                    LinkIndex linkToAdd, std::deque<stackEl> & linkToVisit)
{
    traversal.addTraversalBase(model.getLink(linkToAdd));

    stackEl el;
    el.link = model.getLink(linkToAdd);
    el.parent = 0;

    linkToVisit.push_back(el);
}

int main(int argc, char *argv[])
{
	int arr1[] = { 1, 2, 4, 5, 3, 6 };
	int len1 = sizeof(arr1) / sizeof(arr1[0]);
	vector<int> pre(arr1, arr1+len1);
	int arr2[] = { 4, 2, 5, 1, 6, 3 };
	int len2 = sizeof(arr2) / sizeof(arr2[0]);
	vector<int> in(arr2, arr2+len2);
    Solution s;

	print(pre);
	print(in);
    TreeNode *tree = s.buildTree(pre, in);
	cout << tree->val << endl;
	cout << tree->right << endl;
	Traversal tra;
    print(tra.preorder(tree));
	print(tra.inorder(tree));

    return 0;
}

 void check(Traversal &t) {
     Ans got(t.event(), t.vertex(), t.edge());
     if (!isGood_ || current_>=ans_.size() || got!=ans_[current_]) {
         if (isGood_) {
             for (size_t i=0; i<current_; ++i) {
                 std::cout <<"    correct: " <<std::setw(3) <<i <<toString(ans_[i]) <<"\n";
             }
         }
         if (current_ >= ans_.size()) {
             std::cout <<"    FAILED: past end of answer\n";
             std::cout <<"       got:     " <<toString(got) <<"\n";
         } else if (got!=ans_[current_]) {
             std::cout <<"    FAILED:  " <<std::setw(3) <<current_ <<toString(ans_[current_]) <<"\n";
             std::cout <<"       got:     " <<toString(got) <<"\n";
         } else {
             std::cout <<"    correct: " <<std::setw(3) <<current_ <<toString(ans_[current_]) <<"\n";
         }
         isGood_ = false;
     }
     ++current_;
 }

int main ( int argc, char* argv[] ) {
   SgProject* project = frontend(argc,argv);
   ROSE_ASSERT (project != NULL);

   // Call function to declare function to be called to recode use of all functions in the AST
   beforeWrite.buildDeclaration(project);
   beforeRead.buildDeclaration(project);

   // Build the inherited attribute
   InheritedAttribute inheritedAttribute;

   Traversal myTraversal;

   // Call the traversal starting at the sageProject node of the AST
   myTraversal.traverseInputFiles(project,inheritedAttribute);

   // Generate Code and compile it with backend (vendor) compiler to generate object code
   // or executable (as specified on commandline using vendor compiler's command line).
   // Returns error code form compilation using vendor's compiler.
   return backend(project);
}

void testAST( SgProject* project )
   {
     class Traversal : public SgSimpleProcessing
        {
          public:
               Traversal() {}
               void visit ( SgNode* n )
                  {
                    SgLocatedNode* locatedNode = isSgLocatedNode(n); 
                    if (locatedNode != NULL)
                       {
                         AttachedPreprocessingInfoType* comments = locatedNode->getAttachedPreprocessingInfo();

                         if (comments != NULL)
                            {
                              printf ("Found attached comments (at %p of type: %s): \n",locatedNode,locatedNode->sage_class_name());
                              AttachedPreprocessingInfoType::iterator i;
                              for (i = comments->begin(); i != comments->end(); i++)
                                 {
                                   ROSE_ASSERT ( (*i) != NULL );
                                   printf ("          Attached Comment (relativePosition=%s): %s\n",
                                        ((*i)->getRelativePosition() == PreprocessingInfo::before) ? "before" : "after",
                                        (*i)->getString().c_str());
#if 1
                                // This does not appear to be a valid object when read in from an AST file.
                                   printf ("Comment/Directive getNumberOfLines = %d getColumnNumberOfEndOfString = %d \n",(*i)->getNumberOfLines(),(*i)->getColumnNumberOfEndOfString());
#endif
#if 1
                                // This does not appear to be a valid object when read in from an AST file.
                                   (*i)->get_file_info()->display("comment/directive location");
#endif
                                 }
                            }
                       }
                  }
        };

     Traversal counter;
     counter.traverse(project,preorder);
   }

    void getRelativeJacobianLoop(const UndirectedTree & undirected_tree,
                                const KDL::JntArray &q,
                                const Traversal & traversal,
                                const int link_index,
                                Jacobian & jac)
    {
        Frame T_total = Frame::Identity(); //The transformation between link_index frame and current_link frame

        KDL::CoDyCo::LinkMap::const_iterator current_link;
        current_link = undirected_tree.getLink(link_index);

        //All the columns not modified are zero
        SetToZero(jac);

        KDL::CoDyCo::LinkMap::const_iterator parent_link=traversal.getParentLink(current_link);
        while(current_link != traversal.getBaseLink()) {
            double joint_pos = 0.0;
            if( current_link->getAdjacentJoint(parent_link)->getNrOfDOFs() == 1 ) {
                KDL::Twist jac_col;

                int dof_index = current_link->getAdjacentJoint(parent_link)->getDOFIndex();

                joint_pos = q(dof_index);
                KDL::Twist S_current_parent = parent_link->S(current_link,joint_pos);

                jac_col = T_total*S_current_parent;

                jac.setColumn(dof_index,jac_col);
            }

            KDL::Frame X_current_parent = parent_link->pose(current_link,joint_pos);

            T_total = T_total*X_current_parent;

            current_link = parent_link;
            parent_link = traversal.getParentLink(current_link);
        }

    }

void NistXmlDocument::setTranslation(const PlainTextDocument &doc) {
	typedef Arabica::DOM::Traversal::DocumentTraversal<std::string> Traversal;

	Traversal dt = outnode_.getOwnerDocument().createDocumentTraversal();
	SegNodeFilter filter;
	Traversal::TreeWalkerT it = dt.createTreeWalker(outnode_,
					static_cast<unsigned long>(Arabica::DOM::Traversal::SHOW_TEXT),
					filter, true);

	uint i = 0;
	for(;;) {
		Traversal::NodeT n = it.nextNode();
		if(n == 0)
			break;
		std::ostringstream os;
		std::copy(doc.sentence_begin(i), doc.sentence_end(i), std::ostream_iterator<Word>(os, " "));
		i++;
		std::string str = os.str();
		str.erase(str.end() - 1);
		n.setNodeValue(str);
	}
}

int main (int argc, char* argv[])
{
    // We retrieve the traversal kind from the command line
    TraversalKind traversalKind = getTraversalKind (argc, argv);

//! [snippet1_traversal]
    const char* seqs[] =
    {
        "CGCTACAGCAGCTAGTTCATCATTGTTTATCAATGATAAAATATAATAAGCTAAAAGGAAACTATAAATA",
        "CGCTACAGCAGCTAGTTCATCATTGTTTATCGATGATAAAATATAATAAGCTAAAAGGAAACTATAAATA"
        //      SNP HERE at pos 31      x
    };

    // We create a fake bank with a SNP
    IBank* bank = new BankStrings (seqs, ARRAY_SIZE(seqs));

    // We load the graph
    Graph graph = Graph::create (bank, "-abundance-min 1  -kmer-size 15  -verbose 0");

    // We create a Terminator object
    BranchingTerminator terminator (graph);

    // We create a Traversal instance according to the chosen traversal kind
    Traversal* traversal = Traversal::create (traversalKind, graph, terminator);
    LOCAL (traversal);

    // We create a node from the start of the first sequence
    Node node = graph.buildNode (seqs[0]);

    Path path;
    int len = traversal->traverse (node, DIR_OUTCOMING, path);

    // We dump the length, the starting node and the path
    cout << "length=" << len << " " << graph.toString (node) << path << endl;
//! [snippet1_traversal]

    return EXIT_SUCCESS;
}

PlainTextDocument NistXmlDocument::asPlainTextDocument() const {
	std::vector<std::vector<Word> > txt;

	typedef Arabica::DOM::Traversal::DocumentTraversal<std::string> Traversal;

	Traversal dt = topnode_.getOwnerDocument().createDocumentTraversal();
	SegNodeFilter filter;
	Traversal::TreeWalkerT it = dt.createTreeWalker(topnode_,
					static_cast<unsigned long>(Arabica::DOM::Traversal::SHOW_TEXT),
					filter, true);

	for(;;) {
		Traversal::NodeT n = it.nextNode();
		if(n == 0)
			break;
		std::string seg = n.getNodeValue();
		boost::trim(seg);
		txt.push_back(std::vector<Word>());
		boost::split(txt.back(), seg, boost::is_any_of(" "));
	}

	return PlainTextDocument(txt);
}

boost::shared_ptr<const MMAXDocument> NistXmlDocument::asMMAXDocument() const {
	typedef Arabica::DOM::Traversal::DocumentTraversal<std::string> Traversal;

	Traversal dt = topnode_.getOwnerDocument().createDocumentTraversal();
	SegNodeFilter filter;
	Traversal::TreeWalkerT it = dt.createTreeWalker(topnode_,
					static_cast<unsigned long>(Arabica::DOM::Traversal::SHOW_TEXT),
					filter, true);

	boost::shared_ptr<MMAXDocument> mmax = boost::make_shared<MMAXDocument>();
	for(;;) {
		Traversal::NodeT n = it.nextNode();
		if(n == 0)
			break;
		std::string seg = n.getNodeValue();
		boost::trim(seg);
		std::vector<Word> snt;
		boost::split(snt, seg, boost::is_any_of(" "));
		mmax->addSentence(snt.begin(), snt.end());
	}

	return mmax;
}