Set is an abstract data structure used for storing elements. Since the structure reflects the mathematical term set, it does not guarantee any particular order of the stored elements and contains every value at most once (i.e. contains only unique values).
Similarly we can define multiset (bag) – a set, which may contain each value more than once. To implement a system of non-overlaping subsets, we use a data structure called disjoint set.
Implementation
To implement a set in the most straightforward way, we can use a list data structure and forget its ordering and check that it contains every value at most once. Although this approach is easy to implement, it is very ineffective, because almost every operation has to iterate over the underlying list (with asymptotic complexity). For this reason is the list based implementation used only very rarely. In practice set is usually implemented as a hash table (guarantees on average
complexity of both operations put and contains).
Code
/**
* Set implemented as a list (using ArrayList)
* @author Pavel Micka
* @param <ENTITY> Type parameter of the contained value
*/
public class Set<ENTITY> {
private List<ENTITY> list;
/**
* Constructor
* @param initialCapacity initial capacity of the underlying ArrayList
*/
public Set(int initialCapacity){
list = new ArrayList<ENTITY>(initialCapacity);
}
/**
* Inserts entity into the set
* @param e entity
* @return true - if was the insertion successful, false - if the set already contained this value
*/
public boolean put(ENTITY e) {
if (list.contains(e)) return false;
list.add(e);
return true;
}
/**
* Return (and remove) some element from the set
* @return element, null if the set is empty
*/
public ENTITY pick() {
if(list.size() == 0) return null;
return list.remove(list.size() - 1);
}
/**
* Remove given entity from the set
* @param e entity
* @return true - if the set contained the entity, false - otherwise
*/
public boolean remove(ENTITY e) {
return list.remove(e);
}
/**
* Query if the set set contains given entity
* @param e entity
* @return true - if the set contains the entity, false - otherwise
*/
public boolean contains(ENTITY e) {
return list.contains(e);
}
/**
* Size of the set
* @return number of stored entities
*/
public int size() {
return list.size();
}
}