I have created a HashSet class myself for my Tuple object.

I have troubles implementing an Iterator for my TupleHashSet class. The hashArr attribute stores the Hashsets for my Tuple (Pair) objects. The insert method inserts the Tuples according to the calculated HashCode.

The problem is that my iterator doesn't iterate through the entire HashArr if I insert something with the method.

My teacher told me a tip that my approach is wrong since the HashSet value aren't interested in order. However, I'm not sure what he means with that.

TupleHashSet

package pgdp.hashset;

import java.util.Iterator;
import java.util.NoSuchElementException;

import pgdp.pools.Tuple;

public class TupleHashSet<T, S> implements Iterable<Tuple<T, S>> {

    private final Tuple<T, S>[] hashArr;
    public static final int SIZE = 353;

    public TupleHashSet() {
        hashArr = new Tuple[SIZE];
    }

    @Override
    public java.util.Iterator<Tuple<T, S>> iterator() {
        return new Iterator(hashArr);
    }

    class Iterator implements java.util.Iterator<Tuple<T, S>> {
        private Tuple<T, S>[] array;
        private int index = 0;

        Iterator(Tuple<T, S>[] t) {
            this.array = t;
        }

    @Override
    public boolean hasNext() {
            for (int i = index; i < SIZE;   i) {
                if (array[i] != null) {
                    return true;
                }
            }
            return false;
        }

    @Override
    public Tuple<T, S> next() {
            for (int i = index; i < SIZE;   i) {
                if (hashArr[i] != null) {
                    index = i   1;
                    return hashArr[i];
                }
            }
            throw new NoSuchElementException();
        }

    }

    private int hash(Tuple<T, S> t, int i) {
        return Math.abs((t.hashCode()   i) % SIZE);
    }

    public boolean insert(Tuple<T, S> t) {
        int i = findPosition(t);
        if (i == -1) {
            return false;
        }

        hashArr[i] = t;

        return true;
    }

    public Tuple<T, S> find(T t, S s) {
        Tuple<T, S> testTuple = new Tuple<>(t, s);

        return find(testTuple);
    }

    public Tuple<T, S> find(Tuple<T, S> t) {
        int i = findPosition(t);
        return i == -1 ? null : hashArr[i];
    }

    private int findPosition(Tuple<T, S> t) {
        int i = 0;
        int hash = hash(t, i);
        int start = hash;

        while (hashArr[hash] != null && !hashArr[hash].equals(t)) {
            hash = hash(t,   i);
            if (hash == start) {
                return -1;
            }
        }

        return hash;
    }

    public boolean contains(Tuple<T, S> t) {
        return find(t) != null;
    }

    public int insertedTuples() {
        int res = 0;
        for (Tuple<T, S> t : hashArr) {
            if (t != null) {
                res  ;
            }
        }
        return res;
    }

    public Tuple<T, S> removeFirstElement() {

        Tuple<T, S> ret;

        for (int i = 0; i < SIZE; i  ) {

            if (hashArr[i] != null) {
                ret = hashArr[i];
                hashArr[i] = null;

                while (hashArr[(i   1) % SIZE] != null) {

                    int c = 0;
                    int hash = hash(hashArr[(i   1) % SIZE], c);

                    while (hashArr[hash] != null && hash != i   1) {
                        hash = hash(hashArr[(i   1) % SIZE],   c);
                    }

                    if (hash != i   1) {
                        hashArr[hash] = hashArr[(i   1) % SIZE];
                        hashArr[(i   1) % SIZE] = null;
                    }
                    i  ;
                }
                return ret;
            }
        }
        return null;
    }

}

Tuple

package pgdp.pools;

import java.util.Objects;

public class Tuple<T, S> {

    private T t;
    private S s;

    public Tuple(T t, S s) {
        this.t = t;
        this.s = s;
    }

    public boolean equals(Object other) {
        if (other == this) {
            return true;
        }
        if (other == null) {
            return false;
        }
        if (this.getClass() != other.getClass()) {
            return false;
        }

        Tuple<T, S> otherSub = (Tuple<T, S>) other;
        return otherSub.s.equals(this.s) && otherSub.t.equals(this.t);

    }

    public int hashCode() {
        return Objects.hash(t, s);
    }

    public T getT() {
        return this.t;
    }

    public S getS() {
        return this.s;
    }

}

CodePudding user response：

This answer addresses your question about the iterator not returning all items.

The array index is never incremented, so it will always return the item at index 1, which is index 1. index must be incremented in the call to next before returning so that the next call starts at the subsequent element in the backing array.

Also, the backing array is not dense (meaning there could be empty slots at arbitrary positions, and that's OK), so the next function has to find the next valid entry, not just give up if the next entry is empty (i.e. null).

Try this instead:

@Override
public Iterator<Tuple<T, S>> iterator() {
    Iterator<Tuple<T, S>> it = new Iterator<Tuple<T, S>>() {
        private int index = 0;

        @Override
        public boolean hasNext() {
            for (int i = index; i < SIZE;   i) {
                if (hashArr[i] != null) {
                    return true;
                }
            }
            return false;
        }

        @Override
        public Tuple<T, S> next() {
            for (int i = index; i < SIZE;   i) 
                if (hashArr[i] != null) {
                    index = i   1;
                    return hashArr[i];
                }
            }
            throw new NoSuchElementException();
        }

    };
    return it;
}

CodePudding user response：

Here's a possible solution.

public boolean hasNext() {
  for(; index < SIZE && hashArr[index] == null; index  );
  return index < SIZE;
}