Algorithm to return unique values from unsorted input I need to create an efficient algorithm that returns unique values from an unsorted input. I don't know the length of the input.

As the function that will call this algorithm can abort the reading at any time, I think that using a well defined Iterable implementation is the right way, so I will not waste extra processing power for the uneeded input.

Today, I am using a Set to keep track of the values I've already read. But I don't know if this is the most efficient algorithm, as my input length can be huge.

The code below is my today's working algorithm:

import java.util.Iterator;
import java.util.HashSet;
import java.util.Set;
import java.util.NoSuchElementException;
import java.io.BufferedReader;
import java.io.StringReader;
import java.io.IOException;

public class UniqueValues implements Iterable&lt;String&gt; {
    private final Iterator&lt;String&gt; iterator;

    public UniqueValues(BufferedReader r) {
        this.iterator = new UniqueValuesIterator(r);
    }

    public Iterator&lt;String&gt; iterator() {
        return iterator;
    }

    static class UniqueValuesIterator implements Iterator&lt;String&gt; {
        private final BufferedReader r;

        private final Set&lt;String&gt; values = new HashSet&lt;&gt;();

        // When 'next' is null, need to get the next value
        private String next;

        public UniqueValuesIterator(BufferedReader r) {
            this.r = r;
        }

        public boolean hasNext() {
            // Good point from OldCurmudgeon
            if(next != null) return true;

            try {
                String line;
                while((line = r.readLine()) != null) {
                    if(values.add(line)) { // add() returns 'true' when it is not a duplicate value.
                        next = line;
                        return true;
                    }
                }
            } catch(IOException e) { }

            return false;
        }

        public String next() {
            if(next == null) {
                if(! hasNext() ) throw new NoSuchElementException();
            }

            final String temp = next;
            next = null;
            return temp;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    // For testing
    public static void main(String... args) {
        final StringReader r = new StringReader("value1\nvalue6\nvalue1\nvalue3\nvalue3\nvalue6\nvalue1\nvalue6");

        for(final String value : new UniqueValues(new BufferedReader(r)) ) {
            System.out.println(value);
        }

        /* Output is (order is not important):
         * 
         * line 1
         * line 6
         * line 3
         */
    }
}


Does it have any better algorithm to do this?
There are three significant issues I would address here...


Ratchet Freak is right about being concerned about the Iterator/FilteredReader... but I disagree with his suggestion. I think the problem is that your code is converting a BufferedReader in to an Iterator, and making the results unique at the same time. This is a class that is performing 2 functions... and you shoould have two classes instead. One that converts the BufferedReader to an interator, and the other that enforces uniqueness.
If your input data really is huge, then a Set may not be the right data structure because of it's memory footprint. I have found that custom implementations of memory-efficient structures can save a lot of space. I hesitate to recommend that you change from the Set though, it is the 'logical' choice, but, if, for example, your average String value is about 16 characters, then more than half of your memory will be in the Set overhead. I have, in the past, had reason to do similar things to you, and have written a memory-efficient class that can be seen in JDOM here (you will need to make changes to that code if you want to use it because it will need to have a mechanism for a true/false seen-it test).
I have a pattern I use for Iterators that is really effective, and makes the Iterator logic much simpler/readable. I'll give you an example....


First, part 1, a Reader-to-Iterator implementation:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.Reader;
import java.util.Iterator;
import java.util.NoSuchElementException;


@SuppressWarnings("javadoc")
public class ReaderLineIterator implements Iterator&lt;String&gt; {

    private final BufferedReader reader;
    private String nextval;

    public ReaderLineIterator(Reader reader) {
        this.reader = (reader instanceof BufferedReader) ? (BufferedReader)reader :
            new BufferedReader(reader);

        advance();

    }

    private void advance() {
        try {
            nextval = reader.readLine();
        } catch (IOException ioe) {
            throw new IllegalStateException("Unable to read from reader.", ioe);
        }
    }

    @Override
    public boolean hasNext() {
        return nextval != null;
    }

    @Override
    public String next() {
        if (nextval == null) {
            throw new NoSuchElementException();
        }
        try {
            return nextval;
        } finally {
            advance();
        }
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

}


Note how, in this class, I use a trick for the nextval, where it is advanced in the finally block of the next() call. This is a pattern I like because it makes the hasNext() method very light-weight, and it is always a step-ahead of the data.

So, that is a single-purpose class, it converts a Reader to a line-at-a-time Iterator.

Now, you need a unique Iterator... which can look something like:

import java.util.HashSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;


@SuppressWarnings("javadoc")
public class UniqueIterator implements Iterator&lt;String&gt; {

    private final Iterator&lt;String&gt; source;
    private String nextval = null;
    Set&lt;String&gt; seenit = new HashSet&lt;String&gt;();

    public UniqueIterator(Iterator&lt;String&gt; source) {
        this.source = source;
        advance();
    }

    private void advance() {
        while (source.hasNext()) {
            String nxt = source.next();
            if (seenit.add(nxt)) {
                // found a unique value....
                nextval = nxt;
                return;
            }
        }
        // no more unique values.
        nextval = null;

    }



    @Override
    public boolean hasNext() {
        return nextval != null;
    }

    @Override
    public String next() {
        if (nextval == null) {
            throw new NoSuchElementException();
        }
        try {
            return nextval;
        } finally {
            advance();
        }
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

}