// TortoiseSVN - a Windows shell extension for easy version control

// Copyright (C) 2007-2008, 2012, 2015 - TortoiseSVN

// 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 2
// 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, write to the Free Software Foundation,
// 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
//

#include "stdafx.h"
#include "SearchPathTree.h"
#include "FullGraphNode.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

void CSearchPathTree::DeLink()
{
    assert (parent);

    if (previous)
        previous->next = next;
    if (next)
        next->previous = previous;

    if (parent->firstChild == this)
        parent->firstChild = next;
    if (parent->lastChild == this)
        parent->lastChild = previous;

    parent = NULL;
}

void CSearchPathTree::Link (CSearchPathTree* newParent)
{
    assert (parent == NULL);
    assert (newParent != NULL);

    // ensure that for every cached path element hierarchy level
    // there is a node in the tree hierarchy

    index_t pathID = path.GetBasePath().GetIndex();
    index_t parentPathID = path.IsFullyCachedPath()
                         ? path.GetDictionary()->GetParent (pathID)
                         : pathID;

    if (newParent->path.GetBasePath().GetIndex() < parentPathID)
    {
        CDictionaryBasedPath parentPath ( path.GetDictionary()
                                        , parentPathID);
        newParent = new CSearchPathTree ( CDictionaryBasedTempPath (parentPath)
                                        , (revision_t)NO_REVISION
                                        , newParent);
    }

    parent = newParent;

    // insert into parent's child list ordered by pathID

    // O(1) insertion in most cases

    if (parent->firstChild == NULL)
    {
        // no child yet

        parent->firstChild = this;
        parent->lastChild = this;
    }
    else if (parent->lastChild->path.GetBasePath().GetIndex() <= pathID)
    {
        // insert at the end

        previous = parent->lastChild;

        parent->lastChild = this;
        previous->next = this;
    }
    else if (parent->firstChild->path.GetBasePath().GetIndex() >= pathID)
    {
        // insert at the beginning

        next = parent->firstChild;

        parent->firstChild = this;
        next->previous = this;
    }
    else
    {
        assert (parent->firstChild != parent->lastChild);

        // scan for insertion position

        CSearchPathTree* node = parent->firstChild;
        while (node->path.GetBasePath().GetIndex() < pathID)
            node = node->next;

        // insert us there

        previous = node->previous;
        next = node;

        previous->next = this;
        node->previous = this;
    }
}

// construction / destruction

CSearchPathTree::CSearchPathTree (const CPathDictionary* dictionary)
    : path (dictionary, std::string())
    , startRevision ((revision_t)NO_REVISION)
    , lastEntry (NULL)
    , parent (NULL)
    , firstChild (NULL)
    , lastChild (NULL)
    , previous (NULL)
    , next (NULL)
{
}

CSearchPathTree::CSearchPathTree ( const CDictionaryBasedTempPath& path
                                 , revision_t startrev
                                 , CSearchPathTree* parent)
    : path (path)
    , startRevision (startrev)
    , lastEntry (NULL)
    , parent (NULL)
    , firstChild (NULL)
    , lastChild (NULL)
    , previous (NULL)
    , next (NULL)
{
    Link (parent);
}

CSearchPathTree::~CSearchPathTree()
{
    if (parent)
        DeLink();

    while (firstChild != NULL)
        delete firstChild;
}

// add a node for the given path and rev. to the tree

CSearchPathTree* CSearchPathTree::Insert ( const CDictionaryBasedTempPath& p
                                         , revision_t startrev)
{
    assert (startrev != NO_REVISION);

    // exact match (will happen on root node only)?

    if (this->path == p)
    {
        startRevision = startrev;
        return this;
    }

    // (partly or fully) overlap with an existing child?

    CDictionaryBasedPath cachedPath = p.GetBasePath();
    for (CSearchPathTree* child = firstChild; child != NULL; child = child->next)
    {
        CDictionaryBasedTempPath commonPath
            = child->path.GetCommonRoot (p);

        if (commonPath != this->path)
        {
            if (child->path == p)
            {
                // there is already a node for the exact same path
                // -> use it, if unused so far; append a new node otherwise

                if (child->startRevision == NO_REVISION)
                    child->startRevision = startrev;
                else
                    return new CSearchPathTree (p, startrev, this);
            }
            else
            {
                // the path is a (true) sub-node of the child

                return child->Insert (p, startrev);
            }
        }
    }

    // no overlap with any existing node
    // -> create a new child

    return new CSearchPathTree (p, startrev, this);
}

void CSearchPathTree::Remove()
{
    startRevision = revision_t (NO_REVISION);
    lastEntry = NULL;

    CSearchPathTree* node = this;
    while (node->IsEmpty() && (node->parent != NULL))
    {
        CSearchPathTree* temp = node;
        node = node->parent;

        delete temp;
    }
}

// there is a new revision entry for this path

void CSearchPathTree::ChainEntries (CFullGraphNode* entry)
{
    assert (entry != NULL);

    lastEntry = entry;
    startRevision = max (startRevision, entry->GetRevision());
}

// return true for active paths that don't have a revEntry for this revision

bool CSearchPathTree::YetToCover (revision_t revision) const
{
    return    IsActive()
           && ((lastEntry == NULL) || (lastEntry->GetRevision() < revision));
}

// return next node in pre-order

CSearchPathTree* CSearchPathTree::GetPreOrderNext (CSearchPathTree* lastNode)
{
    if (firstChild != NULL)
        return firstChild;

    // there is no sub-tree

    return GetSkipSubTreeNext (lastNode);
}

// return next node in pre-order but skip this sub-tree

CSearchPathTree* CSearchPathTree::GetSkipSubTreeNext (CSearchPathTree* lastNode)
{
    CSearchPathTree* result = this;
    while ((result != lastNode) && (result->next == NULL))
        result = result->parent;

    return result == lastNode
        ? result
        : result->next;
}

// find sub-tree of pathID
// (return NULL if there is no such node)

CSearchPathTree* CSearchPathTree::FindCommonParent (index_t pathID)
{
    index_t nodePathID = path.GetBasePath().GetIndex();

    // collect all path elements to find *below* this one

    index_t pathToFind[MAX_PATH];
    size_t index = 0;

    while ((pathID != NO_INDEX) && (pathID > nodePathID))
    {
        pathToFind[index] = pathID;
        ++index;
        assert (index < MAX_PATH);

        pathID = path.GetDictionary()->GetParent (pathID);
    }

    // start search at *this node

    CSearchPathTree* node = this;
    CSearchPathTree* oldNode = node;

    while (node != NULL)
    {
        // follow the desired path until it hits or passes the node

        while ((index != 0) && (nodePathID > pathID))
            pathID = pathToFind[--index];

        // scan sibling branches for a match, if this node wasn't one.
        // Since all are on the *same* level, either
        // * one must match
        // * nodePathID < pathID (i.e. node is a true child)
        // * path not found

        while ((nodePathID < pathID) && (node->next != NULL))
        {
            node = node->next;
            nodePathID = node->path.GetBasePath().GetIndex();
        }

        // end of search or not in this sub-tree?

        if ((index == 0) || (nodePathID != pathID))
            return node;

        // descend one level

        pathID = pathToFind[--index];

        oldNode = node;
        node = node->firstChild;
        if (node != NULL)
            nodePathID = node->path.GetBasePath().GetIndex();
    }

    // not found

    return oldNode;
}