package com.apython.python.pythonhost.data;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by Sebastian on 06.07.2017.
 */

public class BinaryTreeMap<Value> {
    private static final int DEFAULT_CAPACITY = 8;
    private int              size;
    private long[]           keys;
    private ArrayList<Value> values;
    
    public class Surrounding {
        private int index;
        public long lesserKey = -1, higherKey = -1;
        public Value lesserObject = null, higherObject = null;

        private Surrounding(int index) {
            this.index = index;
            if (index >= 0) {
                this.lesserKey = keys[index];
                this.lesserObject = values.get(index);
            }
            if (index < size - 1) {
                this.higherKey = keys[index + 1];
                this.higherObject = values.get(index + 1);
            }
        }
        
        public Surrounding getNext() {
            if (this.index >= size || this.higherKey == -1) return null;
            return new Surrounding(this.index + 1);
        }
        
        public Surrounding getPrev() {
            if (this.index <= 0 || this.lesserKey == -1) return null;
            return new Surrounding(this.index - 1);
        }
    }

    public BinaryTreeMap() {
        this(DEFAULT_CAPACITY);
    }
    
    public BinaryTreeMap(int capacity) {
        keys = new long[capacity];
        values = new ArrayList<>(capacity);
        size = 0;
    }
    
    public Surrounding getSurrounding(long key) {
        int index = Arrays.binarySearch(keys, 0, size, key);
        if (index >= 0) { // found key
            return new Surrounding(index);
        } else { // not found
            index = (index + 1) * -1;
            return new Surrounding(index - 1);
        }
    }
    
    public Value get(long key) {
        int index = Arrays.binarySearch(keys, 0, size, key);
        return index < 0 ? null : values.get(index);
    }
    
    public void put(long key, Value value) {
        int index = Arrays.binarySearch(keys, 0, size, key);
        if (index >= 0) { // found key
            values.set(index, value);
        } else { // not found
            index = (index + 1) * -1;
            if (size + 1 > keys.length) {
                long[] newKeys = new long[keys.length < DEFAULT_CAPACITY ?
                        DEFAULT_CAPACITY : (int) (keys.length * 1.5)];
                System.arraycopy(keys, 0, newKeys, 0, index);
                newKeys[index] = key;
                System.arraycopy(keys, index, newKeys, index + 1, size - index);
                keys = newKeys;
            } else {
                System.arraycopy(keys, index, keys, index + 1, size - index);
                keys[index] = key;
            }
            values.add(index, value);
            size++;
        }
    }
    
    public void clear() {
        size = 0;
        values.clear();
    }
    
    public Value remove(long key) {
        int index = Arrays.binarySearch(keys, 0, size, key);
        if (index < 0) throw new IllegalArgumentException("Key " + key + "does not exist");
        System.arraycopy(keys, index + 1, keys, index, size - (index + 1));
        size--;
        return values.remove(index);
    }
    
    public int size() {
        return size;
    }
}

@@ -231,43 +231,8 @@
  8;%0A
-    private int              size;%0A
     
@@ -720,20 +720,29 @@
 index %3C 
+values.
 size
+()
  - 1) %7B%0A
@@ -952,20 +952,29 @@
 ndex %3E= 
+values.
 size
+()
  %7C%7C this
@@ -1445,34 +1445,16 @@
 acity);%0A
-        size = 0;%0A
     %7D%0A  
@@ -1547,36 +1547,45 @@
 Search(keys, 0, 
+values.
 size
+()
 , key);%0A        
@@ -1868,36 +1868,45 @@
 Search(keys, 0, 
+values.
 size
+()
 , key);%0A        
@@ -2047,36 +2047,45 @@
 Search(keys, 0, 
+values.
 size
+()
 , key);%0A        
@@ -2237,20 +2237,29 @@
     if (
+values.
 size
+()
  + 1 %3E k
@@ -2576,36 +2576,45 @@
 eys, index + 1, 
+values.
 size
+()
  - index);%0A     
@@ -2724,20 +2724,29 @@
 ex + 1, 
+values.
 size
+()
  - index
@@ -2839,28 +2839,8 @@
 e);%0A
-            size++;%0A
     
@@ -2886,26 +2886,8 @@
 ) %7B%0A
-        size = 0;%0A
     
@@ -3002,20 +3002,29 @@
 eys, 0, 
+values.
 size
+()
 , key);%0A
@@ -3170,20 +3170,29 @@
  index, 
+values.
 size
+()
  - (inde
@@ -3204,24 +3204,8 @@
 ));%0A
-        size--;%0A
     
@@ -3287,20 +3287,29 @@
  return 
+values.
 size
+()
 ;%0A    %7D%0A

Improve BinaryTreeMap by using the size of the backend list