Skip to content

Instantly share code, notes, and snippets.

@kardolus
Last active February 24, 2016 17:33
Show Gist options
  • Save kardolus/da8b2174920eca3efc79 to your computer and use it in GitHub Desktop.
Save kardolus/da8b2174920eca3efc79 to your computer and use it in GitHub Desktop.
Implementation of a Set with an array.
package us.kardol.datastructure;
/**
* Created by Guillermo Kardolus on 2/24/16.
*/
public class Set {
private int size = 0;
private int capacity = 4;
private Object[] elements = new Object[capacity];
public boolean isEmpty(){
return size == 0;
}
public void add(Object object){
if(this.contains(object)){
return;
}
if(size == capacity){
elements = copy();
}
elements[size] = object;
size++;
}
public void remove(Object object){
int index = indexOf(object);
if(index < 0){
return;
}
elements[index] = elements[size - 1];
elements[size - 1] = null;
size--;
}
public int getSize(){
return this.size;
}
public boolean contains(Object o){
return indexOf(o) > -1;
}
private Object[] copy(){
this.capacity = this.capacity * 2;
Object[] output = new Object[capacity];
for(int i = 0; i < elements.length; i++){
output[i] = elements[i];
}
return output;
}
private int indexOf(Object o){
for(int i = 0; i < size; i++){
if(elements[i].equals(o)){
return i;
}
}
return -1;
}
}
package us.kardol.datastructure;
import org.junit.Before;
import org.junit.Test;
import static org.junit.Assert.*;
/**
* Created by Guillermo Kardolus on 2/24/16.
*/
public class SetTest {
Set emptySet;
Set oneSet;
Set manySet;
@Before
public void setUp(){
emptySet = new Set();
oneSet = new Set();
manySet = new Set();
oneSet.add("1");
manySet.add("1");
manySet.add("2");
}
@Test
public void testIsEmptyWithoutElements() {
assertTrue(emptySet.isEmpty());
}
@Test
public void testIsEmptyOnNonEmptySet(){
assertFalse(oneSet.isEmpty());
}
@Test
public void testManySetSize(){
assertTrue(manySet.getSize() > 1);
}
@Test
public void testManySetContainsElement(){
assertTrue(manySet.contains("1"));
}
@Test
public void testAddTooMany(){
manySet.add("5");
manySet.add("3");
manySet.add("7");
}
@Test
public void testAddDuplicate(){
oneSet.add("1");
assertEquals(oneSet.getSize(), 1);
}
@Test
public void testRemoveElement(){
manySet.remove("1");
assertEquals(manySet.getSize(), 1);
assertFalse(manySet.contains("1"));
assertTrue(manySet.contains("2"));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment