#ifndef B_TREE_NODE_H
#define B_TREE_NODE_H

/*****************************************
 * UW User ID:  pagunnew
 * Submitted for ECE 250
 * Department of Electrical and Computer Engineering
 * University of Waterloo
 * Calender Term of Submission:  Winter 2011
 *
 * By submitting this file, I affirm that
 * I am the author of all modifications to
 * the provided code.
 *****************************************/

#include "ece250.h"
#include "Exception.h"

template <typename Object>
class B_tree;

template <typename Object>
class B_tree_node {
	private:
		const static int N;

		int          num_elements;
		bool         is_leaf;
		Object       elements[5];
		B_tree_node *subtrees[5];

		void insert_leaf_not_full(const Object &);
        B_tree_node *insert_leaf_full(const Object &);
		void insert_internal_not_full(const Object &);
		B_tree_node *insert_internal_full(const Object &);

		Object getMin();
		Object internal_update_elements();
		void insert_subtree(B_tree_node<Object> *);


	public:
		B_tree_node( bool = true );
		B_tree_node( B_tree_node *, B_tree_node * );
		~B_tree_node();

		Object        retrieve( int ) const;
		B_tree_node  *subtree( int ) const;
		int           size() const;
		bool          leaf() const;
		bool          empty() const;
		bool          full() const;
		int           count( Object const & ) const;

		void          draw( int = 0 ) const;
		static void   space( int = 0 );

		B_tree_node  *insert( Object const & );
};

template <typename Object>
const int B_tree_node<Object>::N = 5;

template <typename Object>
B_tree_node<Object>::B_tree_node( bool lf ):num_elements( 0 ), is_leaf( lf ) {
    // Constructor for a leaf node
    elements[0] = 0;
    elements[1] = 0;
    elements[2] = 0;
    elements[3] = 0;
    elements[4] = 0;
}

template <typename Object>
B_tree_node<Object>::B_tree_node( B_tree_node<Object> *first, B_tree_node<Object> *second ):num_elements( 2 ), is_leaf( false ) {
    // Constructor for an internal node
    // Updates subtree pointers and element values
    subtrees[0] = first;
    subtrees[1] = second;
    subtrees[2] = 0;
    subtrees[3] = 0;
    subtrees[4] = 0;

    elements[0] = 0;
    elements[1] = second->getMin();
    elements[2] = 0;
    elements[3] = 0;
    elements[4] = 0;

}

template <typename Object>
B_tree_node<Object>::~B_tree_node() {
    // Deconstructor
    // If its an internal node, delete all subtrees
    if(!leaf())
    {
        for(int i = 0; i < num_elements; i++)
        {
            delete subtrees[i];
        }
    }
}

template <typename Object>
bool B_tree_node<Object>::leaf() const {
    // Returns true if the node is a leaf node, false otherwise
    if (is_leaf)
        return true;
    else
        return false;
}

template <typename Object>
int B_tree_node<Object>::size() const {
    // Returns the number of items in the tree. If if is a leaf node, it returns the number of itmes in the node.
    // If it is any other node it sums all items in all leaf nodes descendant from the current node.
    if (is_leaf)
        return num_elements;
    else
    {
        int sum = 0;
        for(int i = 0; i < num_elements; i++)
        {
            sum += subtrees[i]->size();
        }
        return sum;
    }

}

template <typename Object>
bool B_tree_node<Object>::full() const {
    // Returns true if the node is full, false otherwise
    if (num_elements == 5)
        return true;
    else
        return false;
}

template <typename Object>
bool B_tree_node<Object>::empty() const {
    // Returns true if the node is empty, false otherwise
	if (num_elements == 0)
        return true;
    else
        return false;
}

template <typename Object>
int B_tree_node<Object>::count( Object const &obj ) const {
    // If it is a leaf, go through each element and see if the object is there
    if ( leaf() )
    {
        for ( int i = 0; i < num_elements; i++ )
        {
            if ( elements[i] == obj )
            {
                return 1;

            }
        }
        // Went through all the elements and the object was not there
        return 0;
    }

    // Check to see if it would be in the first subtree
    if ( obj < elements[1] )
    {
        return subtrees[0] -> count(obj);
    }

    // Check to see if it would be in the rest of the subtrees except the last
    for ( int i = 1; i < num_elements; ++i )
    {
        if ( obj < elements[i] )
        {
            return subtrees[i - 1] -> count(obj);
        }

    }
    // It must be in the last subtree if it exists
    return subtrees[num_elements - 1] -> count( obj );
}

template <typename Object>
Object B_tree_node<Object>::retrieve( int n ) const {
    // Returns the element stored at position n
    if(n < num_elements)
    {
        return elements[n];
    }
    else
    {
        throw out_of_bounds();
    }
}

template <typename Object>
B_tree_node<Object> *B_tree_node<Object>::subtree( int n ) const {
    // Returns the nth sub-tree in the array of trees in this node, if it exists, and throws an out-of-range error otherwise.
    // The exception is always thrown if it is a leaf node.
	if(leaf())
	{
        throw underflow();
	}
	else
	{
        if(subtrees[n])
        {
            return subtrees[n];
        }
        else
        {
            throw underflow();
        }
	}
}

template <typename Object>
B_tree_node<Object> *B_tree_node<Object>::insert( const Object &obj ) {
    // Check wich insert case happens
    if(leaf() && full())
    {
        return insert_leaf_full(obj);
    }
	if(leaf() && !full())
	{
	   insert_leaf_not_full(obj);
	   return 0;
	}
	if(!leaf() && !full())
    {
        insert_internal_not_full(obj);
        return 0;
    }
    if(!leaf() && full())
    {
        return insert_internal_full(obj);
    }
}

template <typename Object>
void B_tree_node<Object>::insert_leaf_not_full(const Object &obj){

    // Find the correct position for the new object
    int i = 0;
    while(obj > elements[i] && i < size())
    {
        i++;
    }
    // Move existing elements to make spacefor new object
    if(!empty())
    {
        for(int j = size()-1; j>=i; j--)
        {
            elements[j+1] = elements[j];
        }
    }

    elements[i] = obj;
    num_elements++;
}

template <typename Object>
B_tree_node<Object> *B_tree_node<Object>::insert_leaf_full(const Object &obj){

    B_tree_node<Object> *new_node = new B_tree_node<Object>(true);
    // Insert the largest two elements from the full node into the new node
    new_node->insert(elements[3]);
    new_node->insert(elements[4]);
    // And remove those elements from the list
    elements[3] = 0;
    elements[4] = 0;
    num_elements = num_elements - 2;

    // Check if the middle element needs to be copeied over aswell
    if (elements[2] > obj)
    {
        new_node->insert(elements[2]);
        elements[2] = 0;
        num_elements = num_elements - 1;
        insert(obj);
    }
    // It doesn't, so the new element joins the new leaf
    else
    {
        new_node->insert(obj);
    }

    return new_node;
}

template <typename Object>
void B_tree_node<Object>::insert_internal_not_full(const Object &obj) {

    B_tree_node<Object> *ins_ptr;

    // Check if it should go into the first subtree
    if(obj < elements[1])
    {
        ins_ptr = subtrees[0]->insert(obj);
    }
    else
    {
        // Go through all the subtrees and find which one the object should go into
        int i = 1;
        while( obj > elements[i] && elements[i] != 0)
        {
            i++;
        }
        i--;
        ins_ptr = subtrees[i]->insert(obj);
    }

    // A new leaf was created
    // If so update the subtrees
    if(ins_ptr != 0)
    {
        // Find the correct position for the new leaf
        int i = 0;
        while(ins_ptr->getMin() > elements[i] && i < num_elements)
        {
            i++;
        }

        // Move existing elements to make space for new leafs
        for(int j = num_elements-1; j>=i; j--)
        {
            elements[j+1] = elements[j];
            subtrees[j+1] = subtrees[j];
        }

        // Update the internal node
        subtrees[i] = ins_ptr;
        elements[i] = ins_ptr->getMin();
        num_elements++;

        // Corrects an odd problem with negative numbers
        if(subtrees[0]->getMin() > subtrees[1]->getMin())
        {
            B_tree_node<Object> *tmp = subtrees[1];
            subtrees[1] = subtrees[0];
            subtrees[0] = tmp;
        }

        // Makes sure each subtree is attached to the right element
        internal_update_elements();
    }
}

template <typename Object>
B_tree_node<Object> *B_tree_node<Object>::insert_internal_full(const Object &obj) {

    B_tree_node<Object> *ins_ptr;

    // Check if it should go into the last subtree
    if(obj > elements[4])
    {
        ins_ptr = subtrees[4]->insert(obj);
    }
    else
    {
        // Go through all the subtrees and find which one the object should go into
        int i = 4;
        while( obj < elements[i] && elements[i] != 0)
        {
            i--;
        }
        ins_ptr = subtrees[i]->insert(obj);
    }

    // A new leaf was created, we now have 6 leafs thus there needs to be a new internal node
    if(ins_ptr != 0)
    {
        // Copy over the two largest subtrees to the new internal node
        B_tree_node<Object> *new_internal_node = new B_tree_node<Object>(subtrees[3], subtrees[4]);
        // Delete them and update size
        subtrees[3] = 0;
        subtrees[4] = 0;
        num_elements = num_elements - 2;

        // Check if the middle subtree (subtrees[2]) should go to the new internal node
        // It should, put it in the new internal node, and ins_ptr in the old internal node
        if(elements[2] > ins_ptr->getMin())
        {
            new_internal_node->insert_subtree(subtrees[2]);  // Works
            insert_subtree(ins_ptr);  // Works
        }
        // subtrees[2] belongs in the old internal node so just put ins_ptr in the new internal node
        else
        {
            if(ins_ptr->getMin() > new_internal_node->subtrees[1]->getMin())
            {
                new_internal_node->subtrees[2] = ins_ptr;
            }
            else
            {
                new_internal_node->insert_subtree(ins_ptr);
            }
        }
        new_internal_node->num_elements++;

        // Make sure all the elements[] have the right values
        internal_update_elements();
        new_internal_node->internal_update_elements();

        return new_internal_node;
    }
    else
    {
        return 0;
    }
}

template <typename Object>
void B_tree_node<Object>::insert_subtree(B_tree_node<Object> *obj){
    // Find the correct position for the new object
    int i = 0;
    while(obj->getMin() > subtrees[i]->getMin() && i < num_elements)
    {
        i++;
    }
    // Move existing subtrees to make space for new object
    int j = num_elements-1;
    while(j>=i)
    {
        subtrees[j+1] = subtrees[j];
        j--;
    }

    subtrees[i] = obj;
}

template <typename Object>
Object B_tree_node<Object>::internal_update_elements(){
    // Updates the elements[] values of the node
    elements[0] = 0;
    int i = 1;
    while( i < num_elements)
    {
        elements[i] = subtrees[i]->getMin();
        i++;
    }
}

template <typename Object>
Object B_tree_node<Object>::getMin(){
    // Return the minimum element in a subtree / leaf.
    if( leaf() )
    {
        return elements[0];
    }
    else
    {
        return subtrees[0]->getMin();
    }
}

template <typename Object>
void B_tree_node<Object>::draw( int n ) const {
	if ( leaf() ) {
		space( n );
		std::cout << "(" << num_elements << ") ";

		for ( int i = 0; i < num_elements; ++i ) {
			std::cout << elements[i] << " ";
		}

		std::cout << std::endl;
	} else {
		space( n );
		std::cout << "(" << num_elements << ")" << std::endl;
		space( n );
		std::cout << "* -> " << std::endl;
		subtrees[0] -> draw( n + 1 );

		for ( int i = 1; i < num_elements; ++i ) {
			space( n );
			std::cout << elements[i] << "-> " << std::endl;
			subtrees[i] -> draw( n + 1 );
		}
	}
}

template <typename Object>
void B_tree_node<Object>::space( int n ) {
	for ( int i = 0; i < n; ++i ) {
		std::cout << "   ";
	}
}

#endif