void Tree::ToFileNodeRooted(TextFile &File, unsigned uNodeIndex) const
	{
	assert(IsRooted());

	bool bGroup = !IsLeaf(uNodeIndex) || IsRoot(uNodeIndex);
	if (bGroup)
		File.PutString("(\n");

	if (IsLeaf(uNodeIndex))
		File.PutString(GetName(uNodeIndex));
	else
		{
		ToFileNodeRooted(File, GetLeft(uNodeIndex));
		File.PutString(",\n");
		ToFileNodeRooted(File, GetRight(uNodeIndex));
		}

	if (bGroup)
		File.PutString(")");

	if (!IsRoot(uNodeIndex))
		{
		unsigned uParent = GetParent(uNodeIndex);
		if (HasEdgeLength(uNodeIndex, uParent))
			File.PutFormat(":%g", GetEdgeLength(uNodeIndex, uParent));
		}
	File.PutString("\n");
	}

/*virtual*/ string ComputationNodeBase::FormatOperationPrototype(const string& extraArgs) const
{
    string prototype;
    prototype += msra::strfun::strprintf("%ls = %ls", NodeName().c_str(), OperationName().c_str());

    // arguments of operation
    if (IsLeaf())
        prototype += "()";
    else
    {
        prototype += " (";
        for (size_t i = 0; i < GetNumInputs(); i++)
        {
            const auto& child = m_inputs[i];
            if (i > 0)
                prototype += ", ";

            if (child)
                prototype += msra::strfun::strprintf("%ls", child->NodeName().c_str());
            else
                prototype += "NULL";
        }
        prototype += extraArgs;
        prototype += ")";
    }

    // type (tensor dimensions) of operation
    prototype += " : ";

    if (!IsLeaf())
    {
        //prototype += "(";
        for (size_t i = 0; i < GetNumInputs(); i++)
        {
            const auto& child = m_inputs[i];
            if (i > 0)
                prototype += ", ";

            if (child == nullptr)
            {
                prototype += "NULL";
                continue;
            }
            prototype += child->ShapeDescription().c_str();
        }
        prototype += extraArgs;
        //prototype += ")";
    }

    prototype += msra::strfun::strprintf(" -> %s", ShapeDescription().c_str());

    return prototype;
}

void unitTest() {
    TreeType tree = InitTree();
    printf("After initlizing tree:\n");
    PrintTree(tree);
    PositionType question = 0;
    PositionType answer = 5;
    printf("IsLeaf test 1: %s\n", IsLeaf(tree, question) ? "error" : "pass");
    printf("IsLeaf test 2: %s\n", IsLeaf(tree, answer) ? "pass" : "error");
    printf("Top test: %s\n", Top(tree) == 0 ? "pass" : "error");
    printf("Question test 1: %s\n", strcmp(Question(tree, question), "Is it furry?") == 0 ? "pass" : "error");
    printf("Question test 2: %s\n", strcmp(Question(tree, answer), "Is it a lizard?") == 0 ? "pass" : "error");
    printf("%s\n", Question(tree, answer));
    ReplaceNode(tree, 7, "a kitten", "Is it an adult?");
    PrintTree(tree);
}

/*
 *  Play the "animal" game, in which the program attempts to guess an animal
 *  that the user is thinking of by asking yes or no questions. Eventually,
 *  the program either will guess the user's animal or run out of questions
 *  to ask. In the latter case, the program will ask the user to provide a
 *  yes-or-no question that would distinguish between the user's animal and
 *  the program's best guess.
 *  The data structure of questions and guesses is essentially a binary tree,
 *  with each internal node having a "yes" branch and a "no" branch. Leaves
 *  of the tree represent animals to be guessed by the program. If the program
 *  fails to guess the user's animal, it replaces one of the leaves of the tree
 *  by a node containing the new question, whose children are the program's
 *  best guess and the animal provided by the user.
 *  The structure of the program is simple. It initializes the question/guess
 *  data structure, then plays games as long as the user is interested. In each
 *  game, the program starts at the top of the tree (the root) and progresses
 *  toward the bottom (the leaves) depending on the user's responses. Once it
 *  reaches a leaf, it either has won or lost, and handles the situation as
 *  described above.
 */
int main () {
    TreeType tree;
    PositionType pos;
    char *newQuestion, *newAnswer;
    tree = InitTree ();

    // unitTest();
    printf("%s", "Think of an animal. I will try to guess what it is.\n"
         "Please answer my questions with yes or no.\n");

    while (TRUE) {
        pos = Top (tree);
        while (!IsLeaf (tree, pos)) {
            pos = Answer (Question (tree, pos))?
            YesNode (tree, pos): NoNode (tree, pos);
        }
        if (Answer (Guess (tree, pos))) {
            printf ("I got it right!\n");
        } else {
            GetNewInfo (tree, pos, &newAnswer, &newQuestion);
            ReplaceNode (tree, pos, newAnswer, newQuestion);
        }
        if (!Answer ("Want to play again? ")) {
            exit (0);
        }
    }
    return 0;
}

unsigned Tree::GetAnyNonLeafNode() const
	{
	for (unsigned uNodeIndex = 0; uNodeIndex < m_uNodeCount; ++uNodeIndex)
		if (!IsLeaf(uNodeIndex))
			return uNodeIndex;
	return NULL_NEIGHBOR;
	}

float* Node::GetIncrement()
{
    if(!IsLeaf())
        return NULL;
    else
        return mpCut->GetIncrement();
}

uint32 RemoveTile(TileGroup* node, Tile* to_delete)
{
    uint32 num_removed = 0;

    if(IsLeaf(node))
    {
        for(uint8 i = 0; i < node->contained_colliders; ++i)
        {
            if(node->colliders[i] == to_delete)
            {
                num_removed++;
                auto remaining = (MAX_LEAF_SIZE - 1) - node->contained_colliders;
                if(remaining > 0)
                {
                    memmove(&node->colliders[i], &node->colliders[i + 1], sizeof((uint32)node->colliders[i] * remaining));
                    node->colliders[i + 1] = 0;
                }
                else
                {
                    node->colliders[i] = 0; // This is the last one in the array
                }
            }
        }
    }
    else
    {
        TileGroup* child_node = node->child_nodes;
        for(uint32 i = 0; i < QUADTREE_CHILDREN; ++i)
        {
            num_removed += RemoveTile(child_node, to_delete);
        }
    }

    return num_removed;
}

void BVHNode<BoundingVolumeType>::Insert(Collider* collider, BoundingVolumeType& volume)
{
    // If we are a leaf node, we need to create two new children and put the new body in one of them
    if (IsLeaf())
    {
        m_children[0] = new BVHNode<BoundingVolumeType>(this, m_collider, m_volume);
        m_children[1] = new BVHNode<BoundingVolumeType>(this, collider, volume);

        m_collider = NULL;          // We are no longer a leaf node, so clear our collider

        RecalculateBoundingVolume();
    }
    // Otherwise, we need to decide which child gets to keep the inserted collider.
    // We will give it to the child that would grow the least to incorporate it.
    else
    {
        if (m_children[0]->m_volume.GetGrowth(volume) < m_children[1]->m_volume.GetGrowth(volume))
        {
            m_children[0]->Insert(collider, volume);
        }
        else
        {
            m_children[1]->Insert(collider, volume);
        }
    }
}

 MenuItem* MenuItem::FindFurthestVisitedItem() {
     if (IsLeaf() || !subitems[markedSubitemIndex]->IsVisited()) {
         return this;
     } else {
         return subitems[markedSubitemIndex]->FindFurthestVisitedItem();
     }
 }

inline size_t SpillTree<MetricType, StatisticType, MatType, HyperplaneType,
    SplitType>::NumPoints() const
{
  if (IsLeaf())
    return count;
  return 0;
}

void HQBSPTreeNode::TraverseBtoF(const HQVector4& eye , const HQPlane * frustum , HQPolygonList &listOut)//traverse front to back.<listOut> will store polygons in back to front order. 
{
	if (this->boundingBox.Cull(frustum , 6) == HQ_CULLED)//nhánh này hoàn toàn nằm ngoài thể tích nhìn
		return;
	if(IsLeaf())
	{
		HQPolyListNode *pNode = headNode;
		while(pNode != NULL)
		{
			const HQPolygon3D* poly = pNode->GetPolygon();

			listOut.AddPolygon(poly);

			pNode = pNode->pNext;
		}
	}
	else
	{
		HQPlane::Side side = splitter.CheckSide(eye);
		if(side == HQPlane::BACK_PLANE)
		{
			frontNode->TraverseBtoF(eye , frustum , listOut);
			backNode->TraverseBtoF(eye , frustum , listOut);
		}
		else
		{
			backNode->TraverseBtoF(eye , frustum , listOut);
			frontNode->TraverseBtoF(eye , frustum , listOut);
		}
	}
}

POSTINGSPTR treesearch_page_buildLL(int PageNo, char *key, struct node *root) { // ROOT, word
    POSTINGSPTR  result;
    struct PageHdr *PagePtr = FetchPage(PageNo);
    if (PagePtr != NULL) {
        root = (struct node *) malloc(sizeof(struct node *));
        root->value = PagePtr->PgNum;
        root->next = head;
        head = root;
    }
    if (IsLeaf(PagePtr)) { /* found leaf */
        result = PageNo;
        head = root;
    } else if ((IsNonLeaf(PagePtr)) && (PagePtr->NumKeys == 0)) {
        /* keys, if any, will be stored in Page# 2
           THESE PIECE OF CODE SHOULD GO soon! **/
        result = treesearch_page_buildLL(FIRSTLEAFPG, key, root);
    } else if ((IsNonLeaf(PagePtr)) && (PagePtr->NumKeys > 0)) {
        PAGENO ChildPage = FindPageNumOfChild(PagePtr, PagePtr->KeyListPtr, key,
                PagePtr->NumKeys);
        result = treesearch_page_buildLL(ChildPage, key, root);
    } else {
        assert(0 && "this should never happen");
    }
    FreePage(PagePtr);
    return result;
}

CShadowTree* CShadowTree::FindLeaf(CString partialRefName)
{
	if(IsLeaf())
	{
		if(m_csRefName.GetLength() > partialRefName.GetLength())
			return NULL;
		if(partialRefName.Right(m_csRefName.GetLength()) == m_csRefName)
		{
			//Match of leaf name. Try match on total name.
			CString totalRefName = GetRefName();
			if(totalRefName.Right(partialRefName.GetLength()) == partialRefName)
				return this; //Also match. Found.
		}
	}
	else
	{
		//Not a leaf. Search all nodes.
		for(TShadowTreeMap::iterator itShadowTree = m_ShadowTree.begin(); itShadowTree != m_ShadowTree.end(); ++itShadowTree)
		{
			CShadowTree* pSubtree = itShadowTree->second.FindLeaf(partialRefName);
			if(pSubtree != NULL)
				return pSubtree; //Found
		}
	}
	return NULL;//Not found
}

void QuadTreeNode::Split()
{
    if(!IsLeaf())
		this->DestroyAllChildren();

	CreateNewChildren();
}

void CItem::RecurseCollectExtensionData(CExtensionData *ed)
{
	GetApp()->PeriodicalUpdateRamUsage();

	if (IsLeaf(GetType()))
	{
		if (GetType() == IT_FILE)
		{
			CString ext = GetExtension();
			SExtensionRecord r;
			if (ed->Lookup(ext, r))
			{
				r.bytes += GetSize();
				r.files++;
			}
			else
			{
				r.bytes = GetSize();
				r.files = 1;
			}
			ed->SetAt(ext, r);
		}
	}
	else
	{
		for (int i=0; i < GetChildrenCount(); i++)
		{
			GetChild(i)->RecurseCollectExtensionData(ed);
		}
	}
}

/*
 *  Play the "animal" game, in which the program attempts to guess an animal
 *  that the user is thinking of by asking yes or no questions. Eventually,
 *  the program either will guess the user's animal or run out of questions
 *  to ask. In the latter case, the program will ask the user to provide a
 *  yes-or-no question that would distinguish between the user's animal and
 *  the program's best guess.
 *  The data structure of questions and guesses is essentially a binary tree,
 *  with each internal node having a "yes" branch and a "no" branch. Leaves
 *  of the tree represent animals to be guessed by the program. If the program
 *  fails to guess the user's animal, it replaces one of the leaves of the tree
 *  by a node containing the new question, whose children are the program's
 *  best guess and the animal provided by the user.
 *  The structure of the program is simple. It initializes the question/guess
 *  data structure, then plays games as long as the user is interested. In each
 *  game, the program starts at the top of the tree (the root) and progresses
 *  toward the bottom (the leaves) depending on the user's responses. Once it
 *  reaches a leaf, it either has won or lost, and handles the situation as
 *  described above.
 */
int main (int argc, char *argv[])
{
    char *treefile = NULL;
    TreeType tree;
    PositionType pos;
    char *newQuestion, *newAnswer;

    if (argc > 1) {
        treefile = argv[1];
    }
    tree = InitTree (treefile);

    printf("%s", "Think of an animal. I will try to guess what it is.\n"
		 "Please answer my questions with yes or no.\n");

    while (TRUE) {
        pos = Top (tree);
        while (!IsLeaf (tree, pos)) {
            pos = Answer(Question(tree,pos))? 
	       YesNode(tree,pos): NoNode(tree,pos);
        }
        if (Answer (Guess (tree, pos))) {
            printf ("I got it right!\n");
        } else {
            GetNewInfo (tree, pos, &newAnswer, &newQuestion);
            ReplaceNode (tree, pos, newAnswer, newQuestion);
        }

        if (!Answer ("Want to play again? ")) {
            WriteTree(tree, treefile);
            exit (0);
        }
    }
}

void 
BTnode::InsertBefore(const GiSTentry& entry, int index)
{
    // Only BTentry's can be inserted into BTnodes.
    assert(entry.IsA() == BTENTRY_CLASS);

    BTentry e((const BTentry&) entry);

    // If this is an internal node, adjust the lower/upper bounds
    if (!IsLeaf()) {
	// If not leftmost entry...
	if (index != 0) {
	    // -inf changes to the upper bound of previous item
	    BTentry *prev = (BTentry*) (*this)[index-1].Ptr();
	    if (e.LowerBound() == NegInf)
		e.SetLowerBound(prev->UpperBound());
	}
	// If not rightmost entry...
	if (index != NumEntries()) {
	    // +inf changes to the lower bound of next item
	    BTentry *next = (BTentry*) (*this)[index].Ptr();
	    if (e.UpperBound() == PosInf)
		e.SetUpperBound(next->LowerBound());
	}
    }

    // Insert it into the node
    GiSTnode::InsertBefore(e, index);
}

/*
 *  Form a question out of the string stored at position pos in the given
 *  animal tree.
 */
char *Question (TreeType tree, PositionType pos) {
    /* Your code goes here -- delete this line */
    if (IsLeaf(tree, pos)) {
        return Guess(tree, pos);
    } else {
        return tree[pos];
    }
}

uint64_t DyBitVecNode::LeafNum() const{
  if (IsLeaf()) {
    leaf->Size();
    return 1;
  }
  else return children[0]->LeafNum() +
         children[1]->LeafNum();
}

/*
 *  Print an animal tree (useful for debugging).
 */
void PrintTree (TreeType tree) {
    int i;
    for (i=0; i < MAXNUMQS; i++) {
        if(tree[i] != NULL){
            printf("%d N%d: %s\n",IsLeaf(tree, i), i, tree[i]);
        }
    }
}