BinTree.h

/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

/*
 * Copyright (C) 2006-2010 - Frictional Games
 *
 * This file is part of HPL1 Engine.
 */

#ifndef HPL_BINTREE_H
#define HPL_BINTREE_H

#include "common/list.h"

namespace hpl {

enum eBinTreeNode {
    eBinTreeNode_Left,
    eBinTreeNode_Right
};

// TREE NODE CLASS

template<class T>
class BinTreeNode {
public:
    T *GetData() {
        return &mData;
    }

    BinTreeNode(T aData, BinTreeNode<T> *aParent, eBinTreeNode aParentDir) {
        for (int i = 0; i < 2; i++)
            mChild[i] = NULL;
        mData = aData;
        mParent = aParent;
        mParentDir = aParentDir;
    }

    BinTreeNode<T> *AddChild(eBinTreeNode i, T aData) {
        if (mChild[i] == NULL) {
            mChild[i] = hplNew(BinTreeNode<T>, (aData, this, i));
            return mChild[i];
        }
        return NULL;
    }

    BinTreeNode<T> *GetChild(eBinTreeNode i) {
        return mChild[i];
    }

    BinTreeNode<T> *GetParent() {
        return mParent;
    }

private:
    BinTreeNode<T> *mChild[2];
    BinTreeNode<T> *mParent;
    T mData;
    eBinTreeNode mParentDir;
};

// MAIN TREE CLASS

template<class T>
class BinTree {
public:
    BinTree() {
        mlNumOfNodes = 0;
        mFirstNode = NULL;
    }

    ~BinTree() {
        Clear();
    }

    int Clear() {
        mlNum = 0;
        DeleteNode(mFirstNode);
        mFirstNode = NULL;
        return mlNum;
    }

    BinTreeNode<T> *Insert(T aData) {
        if (mFirstNode == NULL) {
            mFirstNode = hplNew(BinTreeNode<T>, (aData, NULL, eBinTreeNode_Left));
            mlNumOfNodes++;

            return mFirstNode;
        }

        // Insertion other then at the root is not supported!
        BinTreeNode<T> *Node = mFirstNode;
        eBinTreeNode c;
        while (true) {
            // if(Node->GetData()<aData)
            c = eBinTreeNode_Left;
            // else
            //  c = eBinTreeNode_Right;

            if (Node->GetChild(c) == NULL) {
                Node = Node->AddChild(c, aData);
                break;
            } else {
                Node = Node->GetChild(c);
            }
        }
        mlNumOfNodes++;

        return Node;
    }

    BinTreeNode<T> *InsertAt(T aData, BinTreeNode<T> *aNode, eBinTreeNode aChild = eBinTreeNode_Left) {
        if (aNode == NULL)
            return NULL;

        if (aNode->GetChild(aChild) != NULL) {
            aChild = aChild == eBinTreeNode_Left ? eBinTreeNode_Right : eBinTreeNode_Left;
            if (aNode->GetChild(aChild) != NULL)
                return NULL;
        }

        return aNode->AddChild(aChild, aData);
    }

    int Size() {
        return mlNumOfNodes;
    }

    const Common::List<BinTreeNode<T> *> &GetLeafList() {
        mlstNodes.clear();
        PopulateLeafList(mFirstNode);
        return mlstNodes;
    }

    const Common::List<BinTreeNode<T> *> &GetNodeList() {
        mlstNodes.clear();
        PopulateNodeList(mFirstNode);
        return mlstNodes;
    }

private:
    int mlNumOfNodes;
    BinTreeNode<T> *mFirstNode;
    int mlNum;

    Common::List<BinTreeNode<T> *> mlstNodes;

    void DeleteNode(BinTreeNode<T> *aNode) {
        if (aNode == NULL)
            return;

        DeleteNode(aNode->GetChild(eBinTreeNode_Left));
        DeleteNode(aNode->GetChild(eBinTreeNode_Right));

        hplDelete(aNode);
        mlNum++;
    }

    void PopulateNodeList(BinTreeNode<T> *aNode) {
        if (aNode == NULL)
            return;

        PopulateNodeList(aNode->GetChild(eBinTreeNode_Left));
        mlstNodes.push_back(aNode);
        PopulateNodeList(aNode->GetChild(eBinTreeNode_Right));
    }

    void PopulateLeafList(BinTreeNode<T> *aNode) {
        if (aNode == NULL)
            return;

        if (aNode->GetChild(eBinTreeNode_Left) == NULL &&
            aNode->GetChild(eBinTreeNode_Right) == NULL) {
            mlstNodes.push_back(aNode);
        }

        PopulateLeafList(aNode->GetChild(eBinTreeNode_Left));
        PopulateLeafList(aNode->GetChild(eBinTreeNode_Right));
    }
};

} // namespace hpl

#endif // HPL_BINTREE_H