title: Algorithm to return unique values from unsorted input
body: <p>I need to create an efficient algorithm that returns unique values from an unsorted input. I don't know the length of the input.</p>
  
  <p>As the function that will call this algorithm can abort the reading at any time, I think that using a well defined <code>Iterable</code> implementation is the right way, so I will not waste extra processing power for the uneeded input.</p>
  
  <p>Today, I am using a <code>Set</code> 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.</p>
  
  <p>The code below is my today's working algorithm:</p>
  
  <pre><code>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
           */
      }
  }
  </code></pre>
  
  <p>Does it have any better algorithm to do this?</p>