/* Katie Lewis
 * April 2004
 * Note: In codeing this referred to code examples from Professor Kuenning 
 * and Matt Gnaizda.
 *
 */

#include <cstdlib>
#include "node.hh"
#include <cassert>

const int START_SIZE = 10;
const int LEAF_SIZE = 1;

/*------------------------------------------------------------------------*/

Node::Node()
    : loc(),
      numLinks(0),
      sizeLinksArray(0),
      links(NULL),
      isLeaf(false),
      leafLength(0),
      leafAngle(0)
    {
    }

Node::Node(const Location& loc_)
    : loc(loc_),
      numLinks(0),
      sizeLinksArray(0),
      links(NULL),
      isLeaf(false),
      leafLength(0),
      leafAngle(0)
    {
    }

Node::Node(const Location& loc_, int numLinksArray_)
    : loc(loc_),
      numLinks(0),
      sizeLinksArray(numLinksArray_),
      isLeaf(false),
      leafLength(0),
      leafAngle(0)
    {
    links = new Node*[sizeLinksArray];
    for (int i = 0; i<sizeLinksArray; ++i)
        {
        links[i] = NULL;
        }
    }

Node::Node(bool leaf_)
    : loc(),
      numLinks(0),
      sizeLinksArray(0),
      links(NULL),
      isLeaf(leaf_),
      leafLength(LEAF_SIZE),
      leafAngle(0)
    {
    }

Node::~Node()
    {
    delete[] links;
    }

/* Assignment Operator */
Node& Node::operator=(const Node& input)
    {
    loc = input.loc;

    Node** newLinks = new Node*[sizeLinksArray];

    for (int i = 0; i < input.sizeLinksArray; ++i)
        {
        newLinks[i] = input.links[i];
        }

    delete[] links;
    links = newLinks;
    numLinks = input.numLinks;
    sizeLinksArray = input.sizeLinksArray;
    isLeaf = input.isLeaf;    
    leafLength = input.leafLength;
    leafAngle = input.leafAngle;

    return *this;
    } 

/* Copy Constructor */
Node::Node(const Node& input)
    : loc(input.loc)
    {
    Node** newLinks = new Node*[input.sizeLinksArray];

    for (int i = 0; i < input.sizeLinksArray; ++i)
        {
        newLinks[i] = input.links[i];
        }

    links = newLinks;
    numLinks = input.numLinks;
    sizeLinksArray = input.sizeLinksArray;
    isLeaf = input.isLeaf;
    leafLength = input. leafLength;
    leafAngle = input.leafAngle;
    }


bool Node::add(Node* bpoint, const int& maxBranching)
    {
    if (isLeaf)
        return false;

    if (links == NULL)
        {
        int newSize;
        if (START_SIZE > maxBranching)
            newSize = maxBranching;
        else
            newSize = START_SIZE;
        links = new Node*[newSize];
        for (int i = 0; i < newSize; ++i)
             links[i] = NULL;
        links[0] = bpoint;
        ++numLinks;
        return true;        
        }

    if (maxBranching > sizeLinksArray && numLinks+1 > sizeLinksArray)
        expandLinks(maxBranching);
    assert(sizeLinksArray >= numLinks+1);

    bool success = false;
    int freespot = 0;
    
    for (int i = sizeLinksArray; i >=0; --i)
         {
         if (links[i] == NULL)
             {
	     success = true;
             freespot = i;
             }
         else if (links[i]->loc == bpoint->loc)
             return false; 
         }

    if (success)
        {  
        links[freespot] = bpoint;    
        ++numLinks;
        }

    return success;
    }


bool Node::addBetween(Node* insertee, const Location& child, 
                      const int& maxBranching)
    {
    if (isLeaf)                    //can't insert a node into a leaf
        return false;

    for (int i = 0; i < sizeLinksArray; ++i)
        {
        if (links[i]->loc == child)
            {
            bool success = insertee->add(links[i], maxBranching);
            links[i] = insertee; 
            return success;
            }
        }
    return false;
    }


void Node::expandLinks(const int& maxBranching)
    {
    assert(!isLeaf);
    assert(numLinks+1 > sizeLinksArray && maxBranching <= sizeLinksArray);
    assert(links != NULL);

    int newSize = 2*sizeLinksArray;
    if (newSize > maxBranching)
        newSize = maxBranching;

    Node** newLinks = new Node*[newSize];

    for (int i = 0; i < sizeLinksArray; ++i)
         {
         newLinks[i] = links[i];
         }

    for (int i = sizeLinksArray; i < newSize; ++i)
         {
         newLinks[i] = NULL;
         }

    links = newLinks;
    sizeLinksArray = newSize;
    }

void Node::retractLinks()
    {
    int newSize = (int)(0.3*sizeLinksArray);

    assert(numLinks < newSize);
            
    Node** newLinks = new Node*[newSize];

    int j =0;
    for (int i = 0; i < sizeLinksArray; ++i)
         {
         if (links[i] != NULL)
             {
             newLinks[j] = links[i];
             ++j;
             }
         }

    links = newLinks;
    sizeLinksArray = newSize;
    }









/*------------------------------------------------------------------------*/