import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;

public class Program
{

    public static void main(String[] args)
    {
        BTree<Integer, Integer> tree = new BTree<>(3);
        Integer number;
        SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd");

        for (int i = 1; i <= 6; i++)
        {
            tree.add(i, i);
        }
        tree.add(10, 10);

    }
}

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);
                }

                if (nodes.size() > 0)
                {
                    //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 left, K right)
        {
            List<V> answer = new ArrayList<V>();

            if (children.size() != 0)
            {
                /// these nodes do NOT contain keys in range
                //most left case
                if (nodes.get(0).getKey().compareTo(right) > 0)
                    answer.addAll(children.get(0).lookupRange(left, right));
                    // most right case
                else if (nodes.get(nodes.size() - 1).getKey().compareTo(left) < 0)
                    answer.addAll(children.get(children.size() - 1).lookupRange(left, right));
                    ///

                else
                {
                    /// these nodes contain keys in range
                    if (nodes.get(0).getKey().compareTo(left) >= 0) {
                        answer.addAll(children.get(0).lookupRange(left, right));
                        if (nodes.get(0).getKey().compareTo(right) <= 0)
                            answer.add(nodes.get(0).getValue());
                    }

                    for (int i = 0; i < nodes.size(); i++)
                    {
                        // go to left
                        if (nodes.get(i).getKey().compareTo(left) >= 0 && nodes.get(i).getKey().compareTo(right) <= 0)
                        {
                            answer.addAll(children.get(i).lookupRange(left, right));
                            if (nodes.get(i).getKey().compareTo(right) <= 0)
                                answer.add(nodes.get(i).getValue());
                        }
                    }
                    //most right
                    if ((nodes.get(nodes.size() - 1).getKey().compareTo(right) < 0))
                    {
                        // answer.add(nodes.get(nodes.size() - 1).getValue());
                        answer.addAll(children.get(nodes.size()).lookupRange(left, right));
                    }
                }
            }
            else
            {
                if (nodes.get(0).getKey().compareTo(right) < 0 && nodes.get(0).getKey().compareTo(left) > 0)
                // добавляем в лист элементы нода без проверки детей
                for (int i = 0; i < nodes.size(); i++)
                {
                    if (nodes.get(i).getKey().compareTo(left) >= 0 && nodes.get(i -1).getKey().compareTo(right) <= 0)
                        answer.add(nodes.get(i).getValue());
                }
            }

            return answer;
        }
    }

    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)
    {
        if (root == null)
            return null;
        return root.lookupRange(from, to);
    }

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

class Pair<K, V>
{
    private K key;

    public K getKey()
    {
        return key;
    }

    private V value;

    public V getValue()
    {
        return value;
    }

    public Pair(K key, V value)
    {
        this.key = key;
        this.value = value;
    }

    @Override
    public String toString()
    {
        return key + "=" + value;
    }
}