Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Need help in my "Custom Set" implementation

Okay I have a really annoying error. Its coming from my retainAll method. The problem is that I am outputting 1,3,5 in ints at the end, but I need 1,3,5,7,9. Here is the code below for the MySet and driver classes

public class MySetTester {

    public static void main(String[]args) {
        MySet<String> strings = new MySet<String>();
        strings.add("Hey!");
        strings.add("Hey!");
        strings.add("Hey!");
        strings.add("Hey!");
        strings.add("Hey!");
        strings.add("Listen!");
        strings.add("Listen!");
        strings.add("Sorry, I couldn't resist.");
        strings.add("Sorry, I couldn't resist.");
        strings.add("(you know you would if you could)");
        System.out.println("Testing add:\n");
        System.out.println("Your size: " + strings.size()
                        + ", contains(Sorry): " + strings.contains("Sorry, I couldn't resist."));
        System.out.println("Exp. size: 4, contains(Sorry): true\n");
        MySet<String> moreStrings = new MySet<String>();
        moreStrings.add("Sorry, I couldn't resist.");
        moreStrings.add("(you know you would if you could)");
        strings.removeAll(moreStrings);
        System.out.println("Testing remove and removeAll:\n");
        System.out.println("Your size: " + strings.size()
                           + ", contains(Sorry): "
                           + strings.contains("Sorry, I couldn't resist."));
        System.out.println("Exp. size: 2, contains(Sorry): false\n");


        MySet<Integer> ints = new MySet<Integer>();
        for (int i = 0; i < 100; i++) {
            ints.add(i);
        }

        System.out.println("Your size: " + ints.size());
        System.out.println("Exp. size: 100\n");

        for (int i = 0; i < 100; i += 2) {
            ints.remove(i);
        }

        System.out.println("Your size: " + ints.size());
        System.out.println("Exp. size: 50\n");
        MySet<Integer> zeroThroughNine = new MySet<Integer>();

        for (int i = 0; i < 10; i++) {
            zeroThroughNine.add(i);
        }
        ints.retainAll(zeroThroughNine);
        System.out.println("ints should now only retain odd numbers"
                            + " 0 through 10\n");

        System.out.println("Testing your iterator:\n");

        for (Integer i : ints) {
            System.out.println(i);
        }

        System.out.println("\nExpected: \n\n1 \n3 \n5 \n7 \n9\n");

        System.out.println("Yours:");
        for (String s : strings) {
            System.out.println(s);
        }
        System.out.println("\nExpected: \nHey! \nListen!");
        strings.clear();
        System.out.println("\nClearing your set...\n");
        System.out.println("Your set is empty: " + strings.isEmpty());
        System.out.println("Exp. set is empty: true");
    }
}

And here is the main code. But still read the top part because that's where my examples are.

import java.util.Set;
import java.util.Collection;
import java.lang.Iterable;
import java.util.Iterator;
import java.util.Arrays;
import java.lang.reflect.Array;
public class MySet<E> implements Set<E>, Iterable<E>
{
    // instance variables - replace the example below with your own
    private E[] backingArray;
    private int numElements;

    /**
     * Constructor for objects of class MySet
     */
    public MySet()
    {   
        backingArray=(E[]) new Object[5];
        numElements=0;
    }
    public boolean add(E e){

        for(Object elem:backingArray){
            if (elem==null ? e==null : elem.equals(e)){
                return false;
            }
        }
        if(numElements==backingArray.length){
            E[] newArray=Arrays.copyOf(backingArray,backingArray.length*2);
            newArray[numElements]=e;
            numElements=numElements+1;
            backingArray=newArray;
            return true;
        }
        else{
          backingArray[numElements]=e;
          numElements=numElements+1;
          return true;
        }
    }
    public boolean addAll(Collection<? extends E> c){
        for(E elem:c){
            this.add(elem);
        }
        return true;
    }
    public void clear(){
        E[] newArray=(E[])new Object[backingArray.length];
        numElements=0;
        backingArray=newArray;
    }
    public boolean equals(Object o){
        if(o instanceof Set &&(((Set)o).size()==numElements)){
            for(E elem:(Set<E>)o){
               if (this.contains(o)==false){
                 return false;  
            }
            return true;
           }
        }
        return false;
    }
    public boolean contains(Object o){
        for(E backingElem:backingArray){
                   if (o!=null && o.equals(backingElem)){
                       return true;
                    }
               }
        return false;
    }
    public boolean containsAll(Collection<?> c){
        for(E elem:(Set<E>)c){
            if(!(this.contains(elem))){
                return false;
            }
        }
        return true;
    }
    public int hashCode(){
      int sum=0;
      for(E elem:backingArray){
          if(elem!=null){
             sum=sum+elem.hashCode();
      }
    }
      return sum;
    }
    public boolean isEmpty(){
        if(numElements==0){
            return true;
        }
        else{
           return false;
        }
    }
    public boolean remove(Object o){
        int i=0;
        for(Object elem:backingArray){
             if(o!=null && o.equals(elem)){
               backingArray[i]=null;
               numElements=numElements-1;
               E[] newArray=Arrays.copyOf(backingArray,backingArray.length-1);
               return true;            
            }
            i=i+1;
        }
        return false;
    }
    public boolean removeAll(Collection<?> c){
        for(Object elem:c){
            this.remove(elem);
        }
        return true;

    }
    public boolean retainAll(Collection<?> c){
        MySet<E> removalArray=new MySet<E>();
        for(E arrayElem:backingArray){
            if(arrayElem!= null && !(c.contains(arrayElem))){
                this.remove(arrayElem);
            }
    }
    return false;
}
    public int size(){
        return numElements;
    }
    public  <T> T[] toArray(T[] a) throws ArrayStoreException,NullPointerException{
        for(int i=0;i<numElements;i++){
           a[i]=(T)backingArray[i];
        }
        for(int j=numElements;j<a.length;j++){
           a[j]=null;
        }
        return a;
    }
    public Object[] toArray(){
       Object[] newArray=new Object[numElements];
       for(int i=0;i<numElements;i++){
           newArray[i]=backingArray[i];
       }
       return newArray;
    }
    public Iterator<E> iterator(){
        setIterator iterator=new setIterator();
        return iterator;
    }
    private class setIterator implements Iterator<E>{
        private int currIndex;
        private E lastElement;
        public setIterator(){
            currIndex=0;
            lastElement=null;
        }
        public boolean hasNext(){
            while(currIndex<=numElements && backingArray[currIndex]==null){
                currIndex=currIndex+1;
            }
            if (currIndex<=numElements){
                return true;
            }
            return false;
        }
        public E next(){
           E element=backingArray[currIndex];
           currIndex=currIndex+1;
           lastElement=element;
           return element;
        }
        public void remove() throws UnsupportedOperationException,IllegalStateException{
            if(lastElement!=null){
               MySet.this.remove((Object)lastElement);
               numElements=numElements-1;
            }
            else{
             throw new IllegalStateException();
        }
    }
}
}

I've been able to reduce the problems, but otherwise this thing is still causing problems.

like image 509
georgetheevilman Avatar asked Oct 02 '22 13:10

georgetheevilman


1 Answers

Bug in the remove method. I added my implementation this method:

public boolean remove(Object o) {
    int i = 0;
    for (Object elem : backingArray) {
        if (o != null && o.equals(elem)) {
            System.arraycopy(backingArray, i+1, backingArray, i, numElements-i-1);
            backingArray[numElements-1] = null;
            numElements = numElements - 1;
            return true;
        }
        i = i + 1;
    }
    return false;
}

and another bug in method retainAll. I added my implementation this method:

public boolean retainAll(Collection<?> c) {
    int index = 0;
    boolean result = false;
    if (this.containsAll(c)){
        result = true;
    }

    while(index < numElements) {
        E e = backingArray[index];
        if (e != null && !(c.contains(e))) {
            this.remove(e);
        } else {
            index++;
        }
    }
    return result;
}
like image 70
Sergey Morozov Avatar answered Oct 07 '22 18:10

Sergey Morozov