Last active
February 24, 2016 17:33
-
-
Save kardolus/da8b2174920eca3efc79 to your computer and use it in GitHub Desktop.
Implementation of a Set with an array.
This file contains hidden or 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 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; | |
} | |
} |
This file contains hidden or 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 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