package data_structures;

import java.util.Iterator;
import java.util.Arrays;
import java.lang.*;

public class OrderedVector<E> implements Iterable<E> {
    private E[] arr;
    private int size;
    private static final int DEFAULT_MAX_CAPACITY = 2;
    private int iteratedOver;
    
    private void checkBounds(int i) {
        if (i > size - 1) throw new IndexOutOfBoundsException();
    }
       
    private int binarySearch(E[] arr, E obj, int lo, int hi, boolean findPlace) {
        if (lo > hi) return findPlace ? lo : -1;
        int mid = (lo + hi) / 2;
        int comp;
        try {
            comp = ((Comparable<E>) obj).compareTo(arr[mid]);
        } catch (NullPointerException e) {
            comp = -1;
        }
        if (comp == 0) return mid;
        return comp < 0 ? binarySearch(arr, obj, lo, mid - 1, findPlace) : binarySearch(arr, obj, mid + 1, hi, findPlace);
    }
    
    private int binSearchFindPlace(E obj) {
        return binarySearch(arr, obj, 0, arr.length - 1, true);
    }
    
    private int binSearch(E obj) {
        return binarySearch(arr, obj, 0, arr.length - 1, false);
    }
    
    private void removeFromArr(int index) {
        E[] newArr = (E[]) new Object[arr.length];
        boolean set = false;
        for (int i = 0; i < arr.length; i++) {
            if (i == index) set = true;
            else newArr[set ? i - 1 : i] = arr[i];
        }
        arr = newArr;
        size--;
    }
    
    public OrderedVector() {
        clear();
    }
    
    public void insert(E obj) {
        if (size + 1 == arr.length) {
            E[] longerArr = (E[]) new Object[arr.length * 2];
            for (int i = 0; i < arr.length - 1; i++) longerArr[i] = arr[i];
            arr = longerArr;
        }
        int position = binSearchFindPlace(obj);
        E[] newArr = (E[]) new Object[arr.length];
        boolean set = false;
        for (int i = 0; i < arr.length; i++) {
            if (i == position) {
                newArr[i] = obj;
                newArr[i + 1] = arr[i++];
                set = true;
            } else {
                newArr[i] = arr[set ? i - 1 : i];
            }
        }
        arr = newArr;
        size++;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public E get(int index) {
        checkBounds(index);
        return arr[index];
    }
    
    public E get(E obj) {
        int position = binSearch(obj);
        if (position == -1) return null;
        return arr[position];
    }

    public E remove(int index) {
        checkBounds(index);
        E found = arr[index];
        removeFromArr(index);
        return found;
    }
    
    public E remove(E obj) {
        int position = binSearch(obj);
        if (position == -1) return null;
        removeFromArr(position);
        return obj;
    }
    
    public void remove() {}
    
    public boolean contains(E obj) {
        int position = binSearch(obj);
        return position != -1;
    }
    
    public void clear() {
        arr = (E[]) new Object[DEFAULT_MAX_CAPACITY];
        size = 0;
        iteratedOver = 0;
    }
    
    public E[] retrieve() {
        return arr;
    }
    
    public boolean hasNext() {
        return iteratedOver < size;
    }
    
    public E next() {
        return arr[iteratedOver++];
    }
    //  Returns an Iterator of the values in the list, presented in the same order as the list.   
    public Iterator iterator() {
        // return this;
    }
}