using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace Phone
{
    /// <summary>
    /// Interaktionslogik für MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        private DataCreator dataCreator = new DataCreator();
        public Dictionary<long, string> data = new Dictionary<long, string>();
        long[] keys = { 0L };
        private Tree MyTree;
        public int nodeCounter = 0;

        public MainWindow()
        {
            InitializeComponent();

            dataCreator.create();

            keys = dataCreator.data.Keys.ToArray();
            Array.Sort(keys);

            foreach(long key in keys)
            {
                data.Add(key, dataCreator.data[key]);
            }

            MyTree = createTree(data, keys);
            int i = nodeCounter;
            int j = 0;
        }

        private void _return_Click(object sender, RoutedEventArgs e)
        {
            long key = Convert.ToInt64(this._input.Text);
            string result = MyTree.search(key, MyTree.Root);
            this._result.Text = result;
        }

        private Tree createTree(Dictionary<long, string> items, long[] keys)
        {
            long key = keys[(int)(Math.Ceiling((double)((double)keys.Length / (double)2)))];
            List<long> keysForUse = keys.ToList();
            keysForUse.Remove(key);
            Node root = new Node(key, items[key]);
            Tree myTree = new Tree(root);

            int leftLength = (int)(Math.Floor((double)((double)keysForUse.Count / (double)2)));
            int rightLength = (int)(Math.Ceiling((double)((double)keysForUse.Count / (double)2)));

            long[] forLeft = new long[leftLength];
            long[] forRight = new long[rightLength];
            int counter = 0;
            int i = 0;

            for (i = 0; counter < (keysForUse.Count / 2); i++)
            {
                forLeft[i] = keys[counter++];
            }

            for (i = 0; counter < keysForUse.Count; i++)
            {
                forRight[i] = keys[counter++];
            }

            createLeft(forLeft[(int)(Math.Floor((double)((double)forLeft.Length / (double)2)))], items, myTree.Root, forLeft, myTree);
            createRight(forRight[(int)(Math.Floor((double)((double)forRight.Length / (double)2)))], items, myTree.Root, forRight, myTree);

            return myTree;
        }

        private void createLeft(long key, Dictionary<long, string> items, Node parent, long[] keysLeft, Tree tree)
        {
            List<long> keys = keysLeft.ToList();
            tree.add_node(key, items[key], tree.Root);
            nodeCounter++;
            keys.Remove(key);

            int leftLength = (int)(Math.Floor((double)((double)keys.Count / (double)2)));
            int rightLength = (int)(Math.Ceiling((double)((double)keys.Count / (double)2)));

            long[] forLeft = new long[leftLength];
            long[] forRight = new long[rightLength];
            long[] left = keys.ToArray();
            int counter = 0;
            int i = 0;

            for (i = 0; counter < (left.Length / 2); i++)
            {
                forLeft[i] = left[counter++];
            }

            for (i = 0; counter < left.Length; i++)
            {
                forRight[i] = left[counter++];
            }

            if (leftLength != 0)
            {
                createLeft(forLeft[(int)(Math.Floor((double)((double)forLeft.Length / (double)2)))], items, tree.Root, forLeft, tree);
            }
            if (rightLength != 0)
            {
                createRight(forRight[(int)(Math.Floor((double)((double)forRight.Length / (double)2)))], items, tree.Root, forRight, tree);
            }

        }

        private void createRight(long key, Dictionary<long, string> items, Node parent, long[] keysLeft, Tree tree)
        {
            List<long> keys = keysLeft.ToList();
            tree.add_node(key, items[key], tree.Root);
            nodeCounter++;
            keys.Remove(key);

            int leftLength = (int)(Math.Floor((double)((double)keys.Count / (double)2)));
            int rightLength = (int)(Math.Ceiling((double)((double)keys.Count / (double)2)));

            long[] forLeft = new long[leftLength];
            long[] forRight = new long[rightLength];
            long[] left = keys.ToArray();
            int counter = 0;
            int i = 0;

            for (i = 0; counter < (left.Length / 2); i++)
            {
                forLeft[i] = left[counter++];
            }

            for (i = 0; counter < left.Length; i++)
            {
                forRight[i] = left[counter++];
            }

            if (leftLength != 0)
            {
                createLeft(forLeft[(int)(Math.Floor((double)((double)forLeft.Length / (double)2)))], items, tree.Root, forLeft, tree);
            }
            if (rightLength != 0)
            {
                createRight(forRight[(int)(Math.Floor((double)((double)forRight.Length / (double)2)))], items, tree.Root, forRight, tree);
            }

        }
    }
}