set

Set implementation

Pinterest LinkedIn Tumblr

The set is a data structure that can store values without any order and do not contain duplicate elements. The set is a computer implementation of a finite set. It contains finite natural number of elements. The subset is a set build from master set and has few elements. Example, Set S={1, 2, 3, 4, 5}, Subset = { {1, 2, 3}, {2, 3}, {1}}. The set can be implemented using linked lists, vectors and hash tables. It can be static and dynamic. Static set cannot change the elements after constructing the elements. The dynamic set can add or remove the elements after construction. The static set contains build and ternate the elements from the set. But the dynamic set support add, remove operations too.

Multiset or bag is the generalization of the set which support multiple duplicate values. Multisets can naturally be implemented using the hash table or trees.

Write a program to implement the set operations.

Algorithm Explanation

The set is a data structure that store values without any order. Insert operation make sure no duplicate in the set
Static and dynamic set supports to iterate the elements from the set.
Set support contains, size and insert operations.
The insert increment the array when it reach the maximum size.

Source Code

package com.dsacode.DataStructre.set;
 
public class SetImpl {
 
    private String  arrayElement[];
 
    int size = 0;
 
    public SetImpl() {
        this.arrayElement = null;
    }
 
    public SetImpl(String [] element) {
        arrayElement = element;
        size = arrayElement.length;
    }
 
 
    public void addElement(String  element) {
        if (!contains(element)) {
            if (size == arrayElement.length) {
                incrementArray();
            }
            arrayElement[size++] = element;
        }
    }
 
     
 
    public boolean contains(String  elem) {
        if (elem == null) {
            for (int i = 0; i < size; i++)
                if (arrayElement[i] == null)
                    return true;
        } else {
            for (int i = 0; i < size; i++)
                if (elem.equals(arrayElement[i]))
                    return true;
        }
        return false;
    }
 
    public int size() {
        if (arrayElement != null) {
            return arrayElement.length;
        } else
            return 0;
    }
 
    public void clear() {
        arrayElement = null;
    }
 
    public String toString() {
 
        if (arrayElement == null || arrayElement.length == 0) {
            return "[EMPTY]";
        } else {
            String toStr = "[";
            for (int i = 0; i < arrayElement.length; i++) {
                toStr += arrayElement[i] + "”,";
            }
            toStr += "”]";
            return toStr;
        }
    }
 
    public boolean isEmpty() {
        if (arrayElement == null || arrayElement.length == 0)
            return true;
        else
            return false;
    }
 
    private void incrementArray() {
        String [] temparray = arrayElement;
        int tempsize = size + 5;
        arrayElement =  new String[tempsize];
        System.arraycopy(temparray, 0, arrayElement, 0, size);
    }
    public static void main(String[] args) {
        String []array={"One","two","Three","four","five"};
 
        SetImpl set = new SetImpl(array);
         
        System.out.println("Itmes in the set: "+ set.toString());
        System.out.println("Set size: "+ set.size());
         
        System.out.println("Does Set contains 'One' : "+ set.contains("One"));
        set.addElement("ten");
         
        System.out.println("Itmes in the set: "+ set.toString());
    }
 
}

Output

Itmes in the set: [One,two,Three,four,five,]
Set size: 5
Does Set contains 'One' : true
Itmes in the set: [One,two,Three,four,five,ten,null,null,null,null,]

Source Explanation

Pass the array of elements to the Set implementation.
Contractor read each element from an array and add to the local array.
Iterate all the element from Set and print the size of set.
Check the given string contains in the set. Print all the values from Set implementation.

Real Applications

  1. Syntax highlighter which highlight the source code
  2. Counting, finding, removing with duplicates allowed.
  3. Count the number of occurrences
  4. Subset and intersection
  5. Arrange items in the Supermarket

Reference

  1. https://en.wikipedia.org/wiki/Set_(abstract_data_type)
  2. https://msdn.microsoft.com/en-us/library/aa289153%28v=vs.71%29.aspx?f=255&MSPPError=-2147217396
  3. http://infolab.stanford.edu/~ullman/focs/ch07.pdf
  4. https://www.mathsisfun.com/sets/sets-introduction.html

Write A Comment