Last active
August 29, 2015 14:06
-
-
Save qcom/1e52aeaf03bb9526ecdc to your computer and use it in GitHub Desktop.
vector implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment