package com.company;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main
{

    public static void main(String[] args)
    {
        BTree<Integer, Integer> tree = new BTree<>(4);
        tree.add(1, 1);
        tree.add(2, 2);
        tree.add(3, 3);
        tree.add(4, 0);
        tree.add(5, 0);
        tree.add(6, 0);
        tree.add(7, 0);
        tree.add(8, 0);
        tree.add(9, 0);
        tree.add(10, 0);
        tree.add(11, 0);
        tree.add(12, 0);
        tree.add(13, 0);

        System.out.println(tree.lookupRange(1, 2));
    }
}

interface RangeMap<K, V>
{
    int size();

    boolean isEmpty();

    void add(K key, V value); // insert new item into the map

    boolean contains(K key); // check if a key is present

    V lookup(K key); // lookup a value by the key

    List<V> lookupRange(K from, K to); // lookup values for a range of keys

    // optional: remove an item from a map (+1% extra credit)
    Object remove(K key);
}

class BTree<K extends Comparable<K>, V extends Number> implements RangeMap<K, V>
{
    private BNode<K, V> root = null;

    public final int B;
    private int size = 0;

    static class BNode<K extends Comparable<K>, V extends Number>
    {
        private final BTree<K, V> tree;
        private final int B;
        private BNode<K, V> parent;
        private final List<Pair<K, V>> nodes;
        private final List<BNode<K, V>> children;

        public BNode(BNode<K, V> parent, BTree<K, V> tree)
        {
            this.tree = tree;
            this.B = tree.B;
            this.parent = parent;
            this.nodes = new ArrayList<>(B);
            this.children = new ArrayList<>(B + 1);
        }

        public void addKey(K newKey, V newValue)
        {
            if (children.size() == 0)
            {
                add(newKey, newValue);
            }
            else
            {
                //Most left node
                if (nodes.get(0).getKey().compareTo(newKey) >= 0)
                {
                    children.get(0).addKey(newKey, newValue);
                }

                //Most right node
                if (nodes.get(nodes.size() - 1).getKey().compareTo(newKey) < 0)
                {
                    children.get(children.size() - 1).addKey(newKey, newValue);
                }

                //nodes.size() <= B-1
                for (int i = 1; i < nodes.size(); i++)
                {
                    if (nodes.get(i - 1).getKey().compareTo(newKey) >= 0 && nodes.get(i).getKey().compareTo(newKey) < 0)
                    {
                        children.get(i).addKey(newKey, newValue);
                    }
                }
            }
        }

        private void add(K newKey, V newValue)
        {
            this.nodes.add(new Pair<>(newKey, newValue));
            nodes.sort(Comparator.comparing(Pair::getKey));

            if (this.nodes.size() == B)
                split();
        }

        private void split()
        {
            if (nodes.size() == B)
            {
                int index = B % 2 == 0 ? B / 2 - 1 : B / 2;
                Pair<K, V> medianNode = nodes.get(index);

                BNode<K, V> leftNode = new BNode<>(parent, tree);
                /// удаляем ноды слева от пивота и добавляем их группой к детям родителя
                for (int i = 0; i < index; i++)
                {
                    //перезаписываем ноды
                    leftNode.nodes.add(nodes.get(0));
                    nodes.remove(0);
                }

                // перезаписываем детей в leftNode
                if (children.size() != 0)
                {
                    for (int i = 0; i <= index; i++)
                    {
                        //перезаписываем детей
                        leftNode.children.add(children.get(0));
                        children.remove(0);
                    }
                }
                ///Нужно проверить куда он смещает элемент, который был на этом индекс
                if (parent == null)
                {
                    BNode<K, V> newParent = new BNode<>(null, tree);
                    parent = newParent;
                    leftNode.parent = newParent;
                    parent.children.add(this);
                    tree.root = newParent;
                }
                parent.children.add(parent.children.indexOf(this), leftNode);
                parent.nodes.add(medianNode);
                // pivot стал нулевым
                nodes.remove(0);
                parent.nodes.sort(Comparator.comparing(Pair::getKey));

                parent.split();
            }
        }

        public V lookup(K key)
        {
            int index = -1;
            for (int i = 0; i < nodes.size(); i++)
            {
                if (nodes.get(i).getKey() == key)
                    index = i;
            }

            V returnValue = null;

            if (index == -1)
            {
                if (children.size() > 0)
                {
                    V value;
                    if (nodes.get(0).getKey().compareTo(key) >= 0)
                    {
                        value = children.get(0).lookup(key);
                        if (value != null)
                            returnValue = value;
                    }

                    //Most right node
                    if (nodes.get(nodes.size() - 1).getKey().compareTo(key) < 0)
                    {
                        value = children.get(children.size() - 1).lookup(key);
                        if (value != null)
                            returnValue = value;
                    }

                    //nodes.size() <= B-1
                    for (int i = 1; i < nodes.size(); i++)
                    {
                        if (nodes.get(i - 1).getKey().compareTo(key) >= 0 && nodes.get(i).getKey().compareTo(key) < 0)
                        {
                            value = children.get(i).lookup(key);
                            if (value != null)
                                returnValue = value;
                        }
                    }
                }
            }
            else
                returnValue = nodes.get(index).getValue();


            return returnValue;
        }

        public List<V> lookupRange(K from, K to)
        {
            List<V> returnList = new ArrayList<>();

            for (int j = 0; j < nodes.size(); j++)
            {
                //Most left node
                if (nodes.get(0).getKey().compareTo(from) >= 0)
                {
                    returnList.add(nodes.get(0).getValue());

                    if (children.size() > 0)
                    {
                        List<V> t = children.get(0).lookupRange(from, to);
                        if (t != null)
                            returnList.addAll(t);
                    }
                }

                //Most right node
                if (nodes.get(nodes.size() - 1).getKey().compareTo(from) < 0)
                {
                    return null;
                }

                //nodes.size() <= B-1
                for (int i = 1; i < nodes.size(); i++)
                {
                    if (nodes.get(i - 1).getKey().compareTo(from) >= 0 && nodes.get(i).getKey().compareTo(from) < 0)
                    {
                        if (nodes.get(i - 1).getKey().compareTo(from) >= 0)
                            returnList.add(nodes.get(i - 1).getValue());

                        if (nodes.get(i).getKey().compareTo(from) >= 0)
                            returnList.add(nodes.get(i - 1).getValue());

                        if (children.size() > 0)
                        {
                            List<V> t = children.get(i).lookupRange(from, to);
                            if (t != null)
                                returnList.addAll(t);
                        }
                    }
                }

                if (nodes.get(0).getKey().compareTo(to) >= 0)
                {
                    return null;
                }

                //Most right node
                if (nodes.get(nodes.size() - 1).getKey().compareTo(to) < 0)
                {
                    returnList.add(nodes.get(nodes.size() - 1).getValue());
                    if (children.size() > 0)
                    {
                        List<V> t = children.get(0).lookupRange(from, to);
                        if (t != null)
                            returnList.addAll(t);
                    }
                }

                //nodes.size() <= B-1
                for (int i = 1; i < nodes.size(); i++)
                {
                    if (nodes.get(i - 1).getKey().compareTo(to) >= 0 && nodes.get(i).getKey().compareTo(to) < 0)
                    {
                        if (nodes.get(i - 1).getKey().compareTo(to) >= 0)
                            returnList.add(nodes.get(i - 1).getValue());

                        if (nodes.get(i).getKey().compareTo(to) >= 0)
                            returnList.add(nodes.get(i - 1).getValue());
                        if (children.size() > 0)
                        {
                            List<V> t = children.get(i).lookupRange(from, to);
                            if (t != null)
                                returnList.addAll(t);
                        }
                    }
                }
            }
            return null;
        }
    }

    public BTree(int B)
    {
        this.B = B;
    }

    @Override
    public int size()
    {
        return size;
    }

    @Override
    public boolean isEmpty()
    {
        return size() == 0;
    }

    @Override
    public void add(K key, V value)
    {
        size++;

        if (root == null)
            root = new BNode<>(null, this);

        root.addKey(key, value);

    }

    @Override
    public boolean contains(K key)
    {
        return lookup(key) != null;
    }

    @Override
    public V lookup(K key)
    {
        return root.lookup(key);
    }

    @Override
    public List<V> lookupRange(K from, K to)
    {
        return root.lookupRange(from, to);
    }

    @Override
    public Object remove(K key)
    {
        return null;
    }
}