#include "tree.h"

#include <iostream>

class LongestInorderPositiveSequenceLen: public TernaryTree<int>::const_visitor
{
    unsigned int count;
    unsigned int max_count;
    
public:
    LongestInorderPositiveSequenceLen ():
        count (0),
        max_count (0)
        {
        }
    
    void visit_node (const TernaryTree<int> &tree)
        {
            if (tree.get_key () > 0)
            {
                if (++count > max_count)
                    max_count = count;
            }
            else
                count = 0;
        }
    
    unsigned int result () const { return max_count; }
};

template<typename T>
int longest_inorder_positive_sequence_len (const TernaryTree<T> &tree)
{
    LongestInorderPositiveSequenceLen visitor;
    
    tree.visit_inorder (visitor);
    return visitor.result ();
}

void print_spaces (unsigned int num)
{
    for (unsigned int i = 0; i < num; ++i)
        std::cout << "  ";
}

template<typename T>
void print_tree (const TernaryTree<T> &tree, unsigned int depth = 0)
{
    if (!tree)
        return;

    print_spaces (depth);
    std::cout << tree.get_key () << std::endl;

    ++depth;

    if (tree.left ())
    {
        print_tree (tree.left (), depth);
    }
    else if (tree.middle () || tree.right ())
    {
        print_spaces (depth);
        std::cout << "#" << std::endl;
    }
    
    if (tree.middle ())
    {
        print_tree (tree.middle (), depth);
    }
    else if (tree.right ())
    {
        print_spaces (depth);
        std::cout << "#" << std::endl;
    }
    
    print_tree (tree.right (), depth);    

}

template<typename T>
void print_tree_inorder (const TernaryTree<T> &tree)
{
    if (!tree) return;
    
    print_tree_inorder (tree.left ());    
    std::cout << tree.get_key() << std::endl;
    print_tree_inorder (tree.middle ());    
    print_tree_inorder (tree.right ());    
}

template<typename T>
void insert_random_node (TernaryTree<T> tree, const T &value)
{    
    if(!tree)
    {
        tree.add_root (value);
    }
    else
    {
        int d = random () % 3;
        
        while ((d == 0 && tree.left ()) || (d == 1 && tree.middle ()) || d == 2 && tree.right ())
        {
            if (d == 0) tree = tree.left ();
            else if (d == 1) tree = tree.middle ();
            else tree = tree.right ();

            d = random () % 3;
        }

        if (d == 0) tree.add_left (value);
        else if (d == 1) tree.add_middle (value);
        else tree.add_right (value);
    }

}

TernaryTree<int> random_tree ()
{
    srandom (time(0));
    
    unsigned int nodes_num = random () % 20 + 5;
    
    TernaryTree<int> tree;
    tree.add_root ((random () >> 5) % 200 - 100);
    
    for (unsigned int i = 1; i != nodes_num; ++i)
    {
        int value = (random () >> 5) % 200 - 100;
        insert_random_node (tree, value);
    }
    
    return tree;
}

int main (int argc, char **argv)
{
    typedef TernaryTree<int> tree_t;
    
    if (0) {
        tree_t tree;
        tree.add_root (1);   
        tree_t l = tree.add_left (2);
        tree_t m = tree.add_middle (3);
        tree_t r = tree.add_right (4);

        print_tree (tree.left ());
        
        print_tree (l);
        print_tree (m);
        print_tree (r);

        std::cout << std::endl;
        
        l.remove ();
        print_tree (tree);

        std::cout << std::endl; print_tree (tree.left ());

        tree.left ().set_key (15);
        std::cout << std::endl; print_tree (tree);
        
        return 0;
    }

    std::cerr << std::endl << std::endl;
    
    tree_t tree2 = random_tree ();
    
    print_tree (tree2);

    std::cout << std::endl << std::endl;
    print_tree_inorder (tree2);
    std::cout << std::endl << std::endl;
    
    std::cout << "A leghosszabb pozitiv sor hossza: " <<  longest_inorder_positive_sequence_len (tree2)
              << std::endl;
}