CODEWITHSUNDEEP
java
Zach Thompson
Zach Thompson

Reputation: 39

Java - Creating a method which returns an iterator

I'm currently creating a class called ArraySet that implements the Set interface. I'm supposed to create an iterator method that returns the values in natural order, where the time complexities are iterator(): O(1); hasNext(): O(1); next(): O(1); required space: O(1). The method is supposed to return an Iterator that does this. I'm confused by the way this method works and what is exactly wanted from me. Because it's a method I shouldn't be able to create hasNext(), or next() methods inside of it, and what Iterator am I trying to return? I tried just returning an Iterator but it's abstract and cannot be instantiated. I can understand making a new iterator class, but am having trouble understanding how this works in method form. Basically, what the method looks like at the moment is this, but like I've said I don't know what to even put inside of it. Also, if it helps there are two fields in the ArraySet class, int size (the number of elements in the Array), and T[] elements (the array where the elements are stored, strictly in natural order though I'm not even sure how to enforce natural order)

public Iterator<T> iterator() {
  return null;
}

Upvotes: 0

Views: 3043

Answers (2)

idelvall
idelvall

Reputation: 1661

This case is perfect for an anonymous class.

Anonymous classes enable you to make your code more concise. They enable you to declare and instantiate a class at the same time. They are like local classes except that they do not have a name. Use them if you need to use a local class only once.

@Override
public Iterator<T> iterator() {
    return new Iterator<T>() {
        @Override
        public boolean hasNext() {
            // ...
        }

        @Override
        public T next() {
            //..
        }

        @Override
        public void remove() {
            //..
        }
    };
}

On the other hand, by natural order they mean that the elements of your structure must implement Comparable, and given the O(1) requeriments, the internal array holding the data should be already ordered according this natural order. A more flexible approach (used in standard java collections) is don't require the elements to be comparable, and instead support an optional comparator to be passed in the constructor.

As an additional note: Make your iterator a fail fast iterator, i.e, aware of concurrent modifications using counters for each modification operation, that will give you some points. The idea is use a counter in the your ArraySet instance to count how many writing operations has been made (adding, removing). Then, when you create the iterator you record the current value of the counter (inside the iterator instance, or as a final variable in the iterator() method), and each time a method of the iterator instance is invoked you validate that the current value of the counter of the data structure is the same as the one recorded, meaning that not modification has been performed during the life of the iterator. Otherwise a ConcurrentModificationException is thrown.

Take a look at the source of some standard implementations for good examples.

Upvotes: 0

Matt Ball
Matt Ball

Reputation: 359826

Because it's a method I shouldn't be able to create hasNext(), or next() methods inside of it, and what Iterator am I trying to return?

No, methods cannot define other methods in Java. Are you perhaps thinking of defining an anonymous subclass of Iterator? That could work.

You need to create a concrete Iterator implementation. The iterator() method in your class will then instantiate and return a new instance of this implementation.

For clarity, here's what the skeleton of the thing might look like. It's up to you to implement the hasNext() and next() methods!

public class ArraySet<T> implements Iterable<T> {

  // snip...

  @Override
  public Iterator<T> iterator() {
    return new MyIterator();
  }

  private class MyIterator implements Iterator<T> {

    @Override
    public boolean hasNext() {
      // your logic here
    }

    @Override
    public T next() {
      // your logic here
    }
  }
}

Upvotes: 2

Related Questions