using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Exercises
{
    public class Node<T> : IComparable<Node<T>> where T : IComparable<T>
    {
        public T Value { get; set; }
        public Node<T> Left { get; set; }
        public Node<T> Right { get; set; }
        public Node<T> Parent { get; set; }
        void Insert(T value) {
            Node<T> node = this;
            Node<T> previous = null;
            bool searchLeft = false;
            while (node != null) {
                if (node.Value.Equals(value))
                    return;
                else {
                    //search left if value is smaller
                    if (value.CompareTo(node.Value) < 0)
                        searchLeft = true;
                    else
                        searchLeft = false;

                    if (searchLeft) {
                        previous = node;
                        node = node.Left; //search left
                    }
                    else {
                        previous = node;
                        node = node.Right; //search right
                    }
                }

            }//while
            if (searchLeft)
                previous.Left = new Node<T>(value, previous);
            else
                previous.Right = new Node<T>(value, previous);
        } //insert

        public Node<T> Find(T value, Node<T> test = null) { //returns null if not found
            Node<T> node = this;
            bool searchLeft = false;
            while (node != null) {
                if (node.Value.Equals(value))
                    return node;
                else {
                    //search left if value is smaller
                    if (value.CompareTo(node.Value) < 0)
                        searchLeft = true;
                    else
                        searchLeft = false;

                    if (searchLeft)
                        node = node.Left; //search left
                    else
                        node = node.Right; //search right
                }


            } //while
            return null;
        } //find


        // Constructor
        public Node(T value, Node<T> parent = null) { //if no second parameter, this will be the root of a new tree
            //throw new Exception();
            Value = value;
            Parent = parent;
            Left = null;
            Right = null;
        }

        public int CompareTo(Node<T> rhs) {
            return Value.CompareTo(rhs.Value);
        }

        public bool Equals(Node<T> rhs) {
            return this.Value.Equals(rhs.Value);
        }


        public override string ToString() {
            /*
             * Simply do print left, print self, print right
             */
            StringBuilder mystring = new StringBuilder("");
            if (this.Left != null)
                mystring.Append(this.Left.ToString());

            mystring.Append(this.Value);

            if (this.Right != null)
                mystring.Append(this.Right.ToString());

            return mystring.ToString();
        } //ToString

        public static Node<T> MakeTree(params T[] list) {
            Node<T> root = null;
            if (list.Length > 0) {
                root = new Node<T>(list[0]);
                for (int i = 1; i < list.Length; i++) {
                    root.Insert(list[i]);
                }
            }
            return root;
        } //MakeTree


        public Node<TOut> MapTree<TOut>(Converter<T, TOut> f) where TOut : IComparable<TOut> {
            Node<TOut> node;
            node = new Node<TOut>(f.Invoke(this.Value));
            if (this.Left != null) {
                node.Left = this.Left.MapTree<TOut>(new Converter<T, TOut>(f));
                node.Left.Parent = node;
            }
            if (this.Right != null) {
                node.Right = this.Right.MapTree<TOut>(new Converter<T, TOut>(f));
                node.Right.Parent = node;
            }
            return node;
        }

        public IEnumerable<T> Values() {
            if (this.Left != null)
                this.Left.Values();

            yield return this.Value;

            if (this.Right != null)
                this.Right.Values();

        }

    }

    class Program
    {
        public static void Pause() {
            Console.Write("Press any key to continue . . . ");
            Console.ReadKey(true);
        }

        public static int f(char c) {
            return (int)c;
        }

        static void Main(string[] args) {
            Node<char> testnode, testnode2;
            Node<int> testnode3;
            testnode = Node<char>.MakeTree('p', 'x', 's', 't', 'r', 'q', 'b', 'a');
            testnode2 = Node<char>.MakeTree('b', 'x', 'r', 't', 's', 'q', 'p', 'a');
            Console.WriteLine(testnode.ToString());
            Console.WriteLine(testnode2.ToString());

            testnode3 = testnode.MapTree<int>(new Converter<char, int>(f));
            Console.WriteLine(testnode3.ToString());
            //List<int> newlist = testnode3.Values();
            IEnumerable<int> yo = testnode3.Values();
            foreach (int item in yo)
                Console.WriteLine(item);

            Pause();
        }
    }
}