Skip to content

Instantly share code, notes, and snippets.

@francbreno

francbreno/Array.java

Created August 8, 2019 18:09
Show Gist options
  • Save francbreno/0a906fa637f89d983ed15cc52e0105fc to your computer and use it in GitHub Desktop.
Save francbreno/0a906fa637f89d983ed15cc52e0105fc to your computer and use it in GitHub Desktop.
Download ZIP
Array & DynamicArray in Java
Raw
Array.java
package easy.datastructures.array;
import java.util.Arrays;
import java.util.Iterator;
@SuppressWarnings("unchecked")
public class Array<T> implements Iterable<T>, ArrayBehaviors<T> {
protected T[] array; // Internal structure. FIXED length
protected int len; // the number of elements added to the array
protected int capacity; // max number of elements that can be added without creating another internal container
public Array() {
this(16);
}
public Array(int initialCapacity) {
if(initialCapacity < 0) throw new IllegalArgumentException("Initial capacity must be > 0");
this.capacity = initialCapacity;
this.array = (T[]) new Object[initialCapacity];
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
private int currentIndex = 0;
@Override
public boolean hasNext() {
return currentIndex < Array.this.size();
}
@Override
public T next() {
return Array.this.array[this.currentIndex++];
}
};
}
@Override
public int size() {
return this.len;
}
@Override
public boolean isEmpty() {
return this.size() == 0;
}
@Override
public void set(int i, T value) {
this.array[i] = value;
this.len++;
}
@Override
public T get(int i) {
return this.array[i];
}
@Override
public void clear() {
// this.array = Arrays
// .stream(this.array)
// .map(e -> null)
// .collect(Collectors.toList())
// .toArray(this.array);
Arrays.fill(this.array, null);
this.len = 0;
}
@Override
public int indexOf(T value) {
for(int i = 0; i< this.capacity; i++ ) {
if(this.array[i] != null && this.array[i].equals(value)) {
return i;
}
}
return -1;
}
@Override
public boolean contains(T value) {
return this.indexOf(value) > -1;
}
@Override
public String toString() {
return "Array [elements=" + Arrays.toString(array) + ", currentLen=" + len + ", maxSize=" + capacity + "]";
}
}
Raw
ArrayBehaviors.java
package easy.datastructures.array;
public interface ArrayBehaviors<T> {
public int size();
public boolean isEmpty();
public void set(int i, T value);
public T get(int i);
public void clear();
public int indexOf(T value);
public boolean contains(T value);
}
Raw
ArrayTest.java
package easy.datastructures.array;
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.CoreMatchers.not;
import static org.junit.Assert.assertThat;
import java.util.Iterator;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
class ArrayTest {
private Array<String> array;
@BeforeEach
public void setUp() {
this.array = new Array<>();
}
@Test
void testIterator() {
Iterator<String> iterator = this.array.iterator();
assertThat(iterator, not(equals(null)));
this.array.set(0, "A");
assertThat(iterator.next(), is("A"));
}
@Test
void testSize() {
assertThat(array.size(), is(0));
array.set(3, "Testing");
assertThat(array.size(), is(1));
}
@Test
void testIsEmpty() {
assertThat(this.array.isEmpty(), is(true));
array.set(3, "Testing");
assertThat(array.isEmpty(), is(false));
}
@Test
void testSet() {
assertThat(this.array.get(3), is((String) null));
array.set(3, "Testing");
assertThat(this.array.get(3), is("Testing"));
}
@Test
void testGet() {
assertThat(this.array.get(5), is((String) null));
array.set(3, "Testing");
assertThat(this.array.get(3), is("Testing"));
}
@Test
void testClear() {
array.set(3, "Testing");
array.set(1, "Testing");
array.set(15, "Testing");
array.set(0, "Testing");
this.array.clear();
assertThat(this.array.isEmpty(), is(true));
}
@Test
void testIndexOf() {
array.set(3, "Testing");
assertThat(this.array.indexOf("Testing"), is(3));
assertThat(this.array.indexOf("Inexisting Value"), is(-1));
}
@Test
void testContains() {
array.set(3, "Testing");
assertThat(this.array.contains("Testing"), is(true));
assertThat(this.array.contains("Inexisting Value"), is(false));
}
}
Raw
DynamicArray.java
package easy.datastructures.array;
import java.util.Arrays;
@SuppressWarnings("unchecked")
public class DynamicArray<T> extends Array<T> implements DynamicArrayBehaviors<T> {
public DynamicArray() {
super(16);
}
public DynamicArray(int initialCapacity) {
super(initialCapacity);
}
@Override
public void set(int i, T value) {
this.array[i] = value;
}
@Override
public void add(T value) {
if(capacity > size()) { // ok, there's space for at least one more element
this.array[this.len] = value;
} else { // we need to resize the internal array to double it's current size
if(size() == 0) this.capacity = 1;
else this.capacity = this.capacity * 2;
this.array = Arrays.copyOf(this.array, this.capacity);
}
this.len++;
}
@Override
public T removeAt(int index) {
if(index >= this.size() || index < 0) throw new IndexOutOfBoundsException();
T removedValue = this.array[index];
T[] new_array = (T[]) new Object[this.size() - 1];
// i iterate over all values, j backs position when i == index to hold the empty space
for(int i = 0, j = 0; i < this.size(); i++, j++) {
if(i == index) j--; // back j one position
else new_array[j] = array[i];
}
this.array = new_array;
this.capacity = --this.len;
return removedValue;
}
@Override
public boolean remove(T value) {
assert value != null;
for(int i = 0; i< this.size(); i++ ) {
if(value.equals(this.array[i])) {
removeAt(i);
return true;
}
}
return false;
}
}
Raw
DynamicArrayBehaviors.java
package easy.datastructures.array;
public interface DynamicArrayBehaviors<T> extends ArrayBehaviors<T> {
public void add(T value);
public T removeAt(int index);
public boolean remove(T value);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment