/*
 * ************************************************************************************************************
 * Author: Marcin Załęczny
 * Copyright (C)2010 Marcin Załęczny <mzaleczny@hotmail.com>
 * License: The GNU Lesser General Public License, version 3.0 (LGPLv3)
 * Library Name: mzstd
 * Version: 1.07
 * First release date:   2010-11-08
 * Current release date: 2011-03-04
 *
 *
 * This file is part of mzstd library
 * 
 * mzstd library is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * mzstd library 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 Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 * ************************************************************************************************************
 */

#include "mzTree.h"
#include "mzString.h"
#include "mzArrayList.h"
#include "mzStringList.h"
#include "mzMath.h"

CTreeNode::CTreeNode() {
    this->data = 0;
    this->sdata = COMMON_EMPTY_STRING;
    this->id = COMMON_EMPTY_STRING;
    this->nodes = NULL;
};

CTreeNode::CTreeNode(WCHAR* id, WCHAR* sdata, LONG data) {
    this->data = data;
    this->sdata = sdata;
    this->id = id;
    this->nodes = NULL;
};

CTreeNode::~CTreeNode() {
    if (this->nodes) {
        CTreeNode* node;
        for (ULONG i = 0; i < this->nodes->size(); i++) {
            node = (CTreeNode*)this->nodes->getAt(i);
            delete node;
        }
        this->nodes->clear();
        delete this->nodes;
        this->nodes = NULL;
    }
}



CTree::CTree() {
    this->setRealClassName(L"CTree");
    this->_root = new CTreeNode();
    this->_root->id = "root";
}

CTree::~CTree() {
    this->clear();
    this->_root = NULL;
}

CTreeNode *CTree::getNode(CString path) {
    LONG length = 0;
    if (path.length() > 1) {
        path.rtrim(L'/');
    }
    CStringList* nodes = path.explode('/');
    if (!nodes || nodes->size() < 1) {
        return NULL;
    }

    length = nodes->size();
    CString current;
    ULONG j;

    CTreeNode *node = this->_root;
    CTreeNode *tmpNode;

    for (LONG i = 1; i < length; i++) {
        current = nodes->getAt(i);
        if (current == "") {
            break;
        }
        ULONG currentNodeSize = node->nodes->size();
        if (!node->nodes || currentNodeSize < 1) {
            node = NULL;
            break;
        }
        for (j = 0; j < currentNodeSize; j++) {
            tmpNode = (CTreeNode*)node->nodes->getAt(j);
            if (tmpNode->id == current) {
                node = tmpNode;
                break;
            }
        }
        // jeśli nie znaleziono odpowiedniego noda, to kończymy
        // poszukiwanie
        if (j == currentNodeSize) {
            node = NULL;
            break;
        }
    }

    return node;
}


CTreeNode *CTree::getParentNode(CString path) {
    if (path.length() > 1) {
        path.rtrim(L'/');
    }
    if (path == "/") {
        return NULL;
    }

    CTreeNode* node = NULL;
    CString parentPath = path;
    parentPath.cutAtLast('/');
    if (parentPath == "") {
        parentPath = "/";
    }

    node = this->getNode(parentPath);
    return node;
}

CTreeNode* CTree::appendNode(CString path, LONG data, WCHAR* id, WCHAR* sdata) {
    CTreeNode *node = this->getNode(path);
    return this->appendNode(node, data, id, sdata);
}

CTreeNode* CTree::addAsFirst(CString path, LONG data, WCHAR* id, WCHAR* sdata) {
    CTreeNode *node = this->getNode(path);
    return this->addAsFirst(node, data, id, sdata);
}

CTreeNode* CTree::insertNode(CString path, ULONG pos, LONG data, WCHAR* id, WCHAR* sdata) {
    CTreeNode *node = this->getNode(path);
    return this->insertNode(node, pos, data, id, sdata);
}

CTreeNode* CTree::appendNode(CTreeNode* parent, LONG data, WCHAR* id, WCHAR* sdata) {
    CTreeNode *node = parent;

    if (node) {
        if (!node->nodes) {
            node->nodes = new CArrayList();
        }
        CString sID = id;
        if (sID.length() == 0) {
            ULONG randomValue = random();
            sID = L"Node";
            sID += randomValue;
        }
        CTreeNode *newNode = new CTreeNode(sID.getBuffer(), sdata, data);
        node->nodes->append((LONG)newNode);
        return newNode;
    }

    return NULL;
}

CTreeNode* CTree::addAsFirst(CTreeNode* parent, LONG data, WCHAR* id, WCHAR* sdata) {
    CTreeNode *node = parent;

    if (node) {
        if (!node->nodes) {
            node->nodes = new CArrayList();
        }
        CString sID = id;
        if (sID.length() == 0) {
            ULONG randomValue = random();
            sID = L"Node";
            sID += randomValue;
        }
        CTreeNode *newNode = new CTreeNode(sID.getBuffer(), sdata, data);
        node->nodes->addAsFirst((LONG)newNode);
        return newNode;
    }

    return NULL;
}

CTreeNode* CTree::insertNode(CTreeNode* parent, ULONG pos, LONG data, WCHAR* id, WCHAR* sdata) {
    CTreeNode *node = parent;

    if (node) {
        if (!node->nodes) {
            node->nodes = new CArrayList();
        }
        CString sID = id;
        if (sID.length() == 0) {
            ULONG randomValue = random();
            sID = L"Node";
            sID += randomValue;
        }
        CTreeNode *newNode = new CTreeNode(sID.getBuffer(), sdata, data);
        node->nodes->insert(pos, (LONG)newNode);
        return newNode;
    }

    return NULL;
}

VOID CTree::delNode(CString path) {
    CTreeNode *node = this->getNode(path);
    CTreeNode *parentNode = this->getParentNode(path);

    if (node) {
        if (parentNode) {
            parentNode->nodes->delFirst((LONG)node);
        }
        delete node;
    }
}

LONG CTree::delSubNodeWithData(CString path, LONG data) {
    CTreeNode *node = this->getNode(path);
    CTreeNode *tmpNode;
    LONG removed = 0;

    if (node) {
        if (node->nodes) {
            for (LONG i = (LONG)node->nodes->size() - 1; i >= 0; i--) {
                tmpNode = (CTreeNode*)node->nodes->getAt(i);
                if (tmpNode->data == data) {
                    node->nodes->delAt(i);
                    delete tmpNode;
                    removed++;
                }
            }
        }
    }

    return removed;
}

LONG CTree::delSubNodeWithId(CString path, CString id) {
    CTreeNode *node = this->getNode(path);
    CTreeNode *tmpNode;
    LONG removed = 0;

    if (node) {
        if (node->nodes) {
            for (LONG i = (LONG)node->nodes->size() - 1; i >= 0; i--) {
                tmpNode = (CTreeNode*)node->nodes->getAt(i);
                if (tmpNode->id == id) {
                    node->nodes->delAt(i);
                    delete tmpNode;
                    removed++;
                }
            }
        }
    }

    return removed;
}

BOOL CTree::delFirstNode(CString path, LONG data) {
    CTreeNode *node = this->getNode(path);
    CTreeNode *tmpNode;
    LONG removed = 0;

    if (node) {
        if (node->nodes) {
            for (LONG i = (LONG)node->nodes->size() - 1; i >= 0; i--) {
                tmpNode = (CTreeNode*)node->nodes->getAt(i);
                if (tmpNode->data == data) {
                    node->nodes->delAt(i);
                    delete tmpNode;
                    removed++;
                    break;
                }
            }
        }
    }

    return removed == 1;
}

BOOL CTree::delFirstNodeWithId(CString path, CString id) {
    CTreeNode *node = this->getNode(path);
    CTreeNode *tmpNode;
    LONG removed = 0;

    if (node) {
        if (node->nodes) {
            for (LONG i = (LONG)node->nodes->size() - 1; i >= 0; i--) {
                tmpNode = (CTreeNode*)node->nodes->getAt(i);
                if (tmpNode->id == id) {
                    node->nodes->delAt(i);
                    delete tmpNode;
                    removed++;
                    break;
                }
            }
        }
    }

    return removed == 1;
}

BOOL CTree::delNodeAt(CString path, ULONG pos) {
    CTreeNode *node = this->getNode(path);
    CTreeNode *tmpNode;
    LONG removed = 0;

    if (node) {
        if (node->nodes && pos < node->nodes->size()) {
            tmpNode = (CTreeNode*)node->nodes->getAt(pos);
            node->nodes->delAt(pos);
            delete tmpNode;
            removed++;
        }
    }

    return removed == 1;
}

LONG CTree::pos(CString path, LONG data) {
    CTreeNode *node = this->getNode(path);
    CTreeNode *tmpNode;
    LONG foundPos = -1;

    if (node) {
        if (node->nodes) {
            for (ULONG i = 0; i < node->nodes->size(); i++) {
                tmpNode = (CTreeNode*)node->nodes->getAt(i);
                if (tmpNode->data == data) {
                    foundPos = i;
                    break;
                }
            }
        }
    }

    return foundPos;
}

LONG CTree::posWithId(CString path, CString id) {
    CTreeNode *node = this->getNode(path);
    CTreeNode *tmpNode;
    LONG foundPos = -1;

    if (node) {
        if (node->nodes) {
            for (ULONG i = 0; i < node->nodes->size(); i++) {
                tmpNode = (CTreeNode*)node->nodes->getAt(i);
                if (tmpNode->id == id) {
                    foundPos = i;
                    break;
                }
            }
        }
    }

    return foundPos;
}

CString CTree::getNodePath(LONG data, CTreeNode *startAtNode) {
    CTreeNode *node;
    CString path = "";
    if (startAtNode) {
        node = startAtNode;
    } else {
        node = this->_root;
    }
    CTreeNode *tmpNode;
    CString p;

    if (node) {
        if (node->nodes) {
            for (ULONG i = 0; i < node->nodes->size(); i++) {
                tmpNode = (CTreeNode*)node->nodes->getAt(i);
                if (tmpNode->data == data) {
                    path += tmpNode->id;
                    if (!startAtNode) {
                        path.prepend("/");
                    }
                    return path;
                }
                p = this->getNodePath(data, tmpNode);
                if (p.length() > 0) {
                    path += tmpNode->id + "/" + p;
                    if (!startAtNode) {
                        path.prepend("/");
                    }
                    return path;
                }
            }
        }
    }

    return path;
}

CString CTree::getNodeWithIdPath(CString id, CTreeNode *startAtNode) {
    CTreeNode *node;
    CString path = "";
    if (startAtNode) {
        node = startAtNode;
    } else {
        node = this->_root;
    }
    CTreeNode *tmpNode;
    CString p;

    if (node) {
        if (node->nodes) {
            for (ULONG i = 0; i < node->nodes->size(); i++) {
                tmpNode = (CTreeNode*)node->nodes->getAt(i);
                if (tmpNode->id == id) {
                    path += tmpNode->id;
                    if (!startAtNode) {
                        path.prepend("/");
                    }
                    return path;
                }
                p = this->getNodeWithIdPath(id, tmpNode);
                if (p.length() > 0) {
                    path += tmpNode->id + "/" + p;
                    if (!startAtNode) {
                        path.prepend("/");
                    }
                    return path;
                }
            }
        }
    }

    return path;
}

BOOL CTree::contains(LONG data) {
    CString path = this->getNodePath(data);
    return path.length() > 0;
}

BOOL CTree::contains(CString id) {
    CString path = this->getNodeWithIdPath(id);
    return path.length() > 0;
}

BOOL CTree::contains(CString path, LONG data) {
    CTreeNode* node = this->getNode(path);
    CTreeNode* tmpNode;

    if (node) {
        if (node->nodes) {
            for (ULONG i = 0; i < node->nodes->size(); i++) {
                tmpNode = (CTreeNode*)node->nodes->getAt(i);
                if (tmpNode->data == data) {
                    return TRUE;
                }
            }
        }
    }

    return FALSE;
}

BOOL CTree::containsNodeWithId(CString path, CString id) {
    CTreeNode* node = this->getNode(path);
    CTreeNode* tmpNode;

    if (node) {
        if (node->nodes) {
            for (ULONG i = 0; i < node->nodes->size(); i++) {
                tmpNode = (CTreeNode*)node->nodes->getAt(i);
                if (tmpNode->id == id) {
                    return TRUE;
                }
            }
        }
    }

    return FALSE;
}

VOID CTree::clear() {
    delete this->_root;
}

CString CTree::simplePrintTree() {
    return this->simplePrintNode(this->_root, "");
}

CString CTree::simplePrintNode(CTreeNode *node, CString indent) {
    CString retval = indent + node->id + "\n";

    if (!node->nodes || node->nodes->size() < 1) {
        return retval;
    }

    CTreeNode *tmpNode;
    for (ULONG i = 0; i < node->nodes->size(); i++) {
        tmpNode = (CTreeNode*)node->nodes->getAt(i);
        retval += this->simplePrintNode(tmpNode, indent + "    ");
    }

    return retval;
}
