Generic Iterator implementation in java
I'd say that Node.data
is a reference to an Instance
object? If that is the case, the compiler can't automatically change an Instance
to a T
, because even though T
is an Instance
object (T extends Instance
), any given Instance
might not be a T
.
The Java Generics tutorial explains it: http://docs.oracle.com/javase/tutorial/extra/generics/subtype.html
Also, in your List<T>
class, you should be specifying Iterator
and ListIterator
as generic using Iterator<T>
and ListIterator<T>
, or else the compiler won't be able to handle the generics properly. Your Node
reference also needs to be generic: Node<T>
Hence you should be using
private Node<T> current;
and
public T next() {
Node<T> temp=current;
current=current.next;
return temp.data;
}
The compiler will usually warn you when you're using a raw type for a generic class.
Writing a generic iterator in Java
Pass this
to the iterator constructor. The StateSpace has access to the instantiated T
type, and so it can implement methods to determine how to getNext()
and hasNext()
. It's not clear what iX
and iY
are about.
import java.util.Iterator;
public class StateSpace<T extends AbstractState> implements Iterable<T> {
List<T> types;
int pos;
public StateSpace() {
types = new ArrayList<>();
}
public void add(T type) {
types.add(type);
}
T getNext() {
return types.get(pos++);
}
boolean hasNext() {
return pos < types.size()-1;
}
@Override
public Iterator<T> iterator() {
return new StateIterator(this);
}
}
and
public class StateIterator<T extends AbstractState> implements Iterator<T> {
private Iterator<Coordinate> iX, iY;
private StateSpace<T> stateSpace;
StateIterator(StateSpace<T> stateSpace){
this.stateSpace = stateSpace;
iX = Main.GRID.iterator();
iY = Main.GRID.iterator();
}
@Override
public boolean hasNext() {
return iX.hasNext() || iY.hasNext();
}
@Override
public T next() {
return stateSpace.getNext(); // or whatever.
}
}
maybe helps.
Iterator? vs Iterator in java
Nope. Iterator<?>
iterates over ?
s (some type that derives from Object
), while Iterator
only provides Object
s. This is the generics support in Java.
What's a ?
type? Well, that's a great question.
Back in the bad old days before Java 5, you had untyped collections and untyped iterators. So you'd have Object
s in your collections and you'd have to cast them manually. For example:
List foo = new ArrayList();
foo.add("Foo!");
for(Iterator i = foo.iterator(); i.hasNext(); )
{
Object element = i.next();
System.out.println((String)element);
}
Notice that cast? That's because we're just stuffing Object
s into lists, and we have to do all that housekeeping ourselves. Not so bad with just a List
, but imagine a map that contains a map that contains a map that contains a ... well, you get the idea. You're in casting hell and you can pretty quickly not know whether you're looking at a map that goes from String
to Integer
or your other map that goes backwards from Integer
to String
.
In Java 5, you can use generics, so now you can say:
List<String> foo = new ArrayList();
foo.add("Foo!");
for(Iterator<String> i = foo.iterator(); i.hasNext(); )
{
String element = i.next();
System.out.println(element);
}
Note that the cast was unnecessary? When we use a List<String>
, we can use an Iterator<String>
and have some type safety.
This is really beneficial when you start doing things with more complex data structures, like:
Map<String, Map<String, Map<String, SomeRandomObject>>> complexMap;
Using generic iterators instead of specific list types
First, forget about IntoIterator
and other traits or types. The core iteration trait in Rust is Iterator
. Its trimmed down definition is as follows:
trait Iterator {
type Item; // type of elements returned by the iterator
fn next(&mut self) -> Option<Self::Item>;
}
As you probably know, you can think of an iterator as a cursor inside of some structure. next()
method advances this cursor forward, returning an element it pointed at previously. Naturally, if the collection is exhausted, there is nothing to return, and so next()
returns Option<Self::Item>
, not just Self::Item
.
Iterator
is a trait, and so it can be implemented by specific types. Note that Iterator
itself is not a proper type which you can use as a return value or a function argument - you have to use concrete types which implement this trait.
The above statement may sound too restrictive - how to use arbitrary iterator types then? - but because of generics this is not so. If you want a function to accept arbitrary iterators, just make it generic in the corresponding argument, adding an Iterator
bound over the corresponding type parameter:
fn iterate_bytes<I>(iter: I) where I: Iterator<Item=u8> { ... }
Returning iterators from functions may be difficult, but see below.
For example, there is a method on &[T]
, called iter()
, which returns an iterator which yields references into the slice. This iterator is an instance of this structure. You can see on that page how Iterator
is implemented for Iter
:
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> { ... }
...
}
This structure holds a reference to the original slice and some iteration state inside it. Its next()
method updates this state and returns the next value, if there is any.
Any value whose type implements Iterator
can be used in a for
loop (for
loop in fact works with IntoIterator
, but see below):
let s: &[u8] = b"hello";
for b in s.iter() {
println!("{}", b); // prints numerical value of each byte
}
Now, Iterator
trait is actually more complex than the above one. It also defines a lot of transformation methods which consume the iterator they are called on and return a new iterator which somehow transforms or filters values from the original iterator. For example, enumerate()
method returns an iterator which yields values from the original iterator together with the positional number of the element:
let s: &[u8] = b"hello";
for (i, b) in s.iter().enumerate() {
println!("{} at {}", b, i); // prints "x at 0", "y at 1", etc.
}
enumerate()
is defined like this:
trait Iterator {
type Item;
...
fn enumerate(self) -> Enumerate<Self> {
Enumerate {
iter: self,
count: 0
}
}
...
}
Enumerate
is just a struct which contains an iterator and a counter inside it and which implements Iterator<Item=(usize, I::Item)>
:
struct Enumerate<I> {
iter: I,
count: usize
}
impl<I> Iterator for Enumerate<I> where I: Iterator {
type Item = (usize, I::Item);
#[inline]
fn next(&mut self) -> Option<(usize, I::Item)> {
self.iter.next().map(|a| {
let ret = (self.count, a);
self.count += 1;
ret
})
}
}
And this is how most iterator transformations are implemented: each transformation is a wrapping struct which wraps the original iterator and implements Iterator
trait by delegating to the original iterator and transforming the resulting value somehow. For example, s.iter().enumerate()
from the example above returns a value of type Enumerate<Iter<'static, u8>>
.
Note that while enumerate()
is defined in Iterator
trait directly, it can be a standalone function as well:
fn enumerate<I>(iter: I) -> Enumerate<I> where I: Iterator {
Enumerate {
iter: iter,
count: 0
}
}
The method works very similarly - it just uses implicit Self
type parameter instead of an explicitly named one.
You may wonder what IntoIterator
trait is. Well, it is just a convenience conversion trait which can be implemented by any type which can be converted to an iterator:
pub trait IntoIterator where Self::IntoIter::Item == Self::Item {
type Item;
type IntoIter: Iterator;
fn into_iter(self) -> Self::IntoIter;
}
For example, &'a [T]
can be converted into Iter<'a, T>
, and so it has the following implementation:
impl<'a, T> IntoIterator for &'a [T] {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.iter() // just delegate to the existing method
}
}
This trait is implemented for most container types and references to these types. It is in fact used by for
loops - a value of any type which implements IntoIterator
can be used in in
clause:
let s: &[u8] = b"hello";
for b in s { ... }
This is very nice from learning and reading perspective because it has less noise (in form of iter()
-like methods). It even allows things like these:
let v: Vec<u8> = ...;
for i in &v { /* i is &u8 here, v is borrowed immutably */ }
for i in &mut v { /* i is &mut u8 here, v is borrowed mutably */ }
for i in v { /* i is just u8 here, v is consumed */ }
This is possible because IntoIterator
is implemented differently for &Vec<T>
, &mut Vec<T>
and just Vec<T>
.
Every Iterator
implements IntoIterator
which performs an identity conversion (into_iter()
just returns the iterator it is called on), so you can use Iterator
instances in for
loops as well.
Consequently, it makes sense to use IntoIterator
in generic functions because it will make the API more convenient for the user. For example, enumerate()
function from above could be rewritten as such:
fn enumerate<I>(source: I) -> Enumerate<I::IntoIter> where I: IntoIter {
Enumerate {
iter: source.into_iter(),
count: 0
}
}
Now you can see how generics can be used to implement transformations with static typing easily. Rust does not have anything like C#/Python yield
(but it is one of the most desired features, so one day it may appear in the language!), thus you need to wrap source iterators explicitly. For example, you can write something analogous to the above Enumerate
structure which does the task you want.
However, the most idiomatic way would be to use existing combinators to do the work for you. For example, your code may be written as follows:
let iter = ...; // iter implements Iterator<Item=i32>
let r = iter.filter(|&x| x % 2 == 0); // r implements Iterator<Item=i32>
for i in r {
println!("{}", i); // prints only even items from the iterator
}
However, using combinators may turn ugly when you want to write custom combinator functions because a lot of existing combinator functions accept closures (e.g. the filter()
one above), but closures in Rust are implemented as values of anonymous types, so there is just no way to write the signature of the function returning the iterator out:
fn filter_even<I>(source: I) -> ??? where I: IntoIter<Item=i32> {
source.into_iter().filter(|&x| x % 2 == 0)
}
There are several ways around this, one of them is using trait objects:
fn filter_even<'a, I>(source: I) -> Box<Iterator<Item=i32>+'a>
where I: IntoIterator<Item=i32>, I::IntoIter: 'a
{
Box::new(source.into_iter().filter(|&x| x % 2 == 0))
}
Here we hide the actual iterator type returned by filter()
behind a trait object. Note that in order to make the function fully generic I had to add a lifetime parameter and a corresponding bound to Box
trait object and I::IntoIter
associated type. This is necessary because I::IntoIter
may contain arbitrary lifetimes inside it (just like Iter<'a, T>
type above), and we have to specify them in the trait object type (otherwise the lifetime information would be lost).
Trait objects created from Iterator
trait implement Iterator
themselves, so you can continue using these iterators as usual:
let source = vec![1_i32, 2, 3, 4];
for i in filter_even(source) {
println!("{}", i); // prints 2 and 4
}
Generic iterator
Here are some articles you might find of interest
Giving STL Iterators a Base Class
Type Erasure for C++ Iterators
any_iterator Class Reference
How to iterate through two generic lists with different types one item after another in java?
I won't give the full solution (and judging by your effort you don't want it), but I will attempt to explain in a way that will let you find it yourself.
First of all an unrelated note: you're specifying a specific iteration order. I assume this is fine and I will not touch it.
Your professor gave you the hint of using bounded generics. Let's understand why they are needed (see also the tutorial here and/or here). If you were asked to write a single method that takes an argument of any of 2 unknown types, your solution would be to find and take their common superclass - Object
.
In generics the situation is similar - find the most common denominator, only the syntax is a bit more tricky. If you were to write the constructor
ZipIterator(Iterator<Object> f, Iterator<Object> s) {...}
and attempt the initialization
List<Integer> lst1 = new List<>();
List<String> lst2 = new List<>();
new ZipIterator(it1, it2);
you would get a compilation error (read it). That is because a List<String>
is not a List<Object>
, even though a String
is an Object
. The correct way to do this is
ZipIterator(Iterator<? extends Object> f, Iterator<? extends Object> s) {...}
where ? extends Object
means "any type that extends Object
" (which is all of them because Object
...).
So you have the constructor, and you would need to make changes to your class in order to accommodate it. You don't even need to implement the given Iterator<E>
, you just hold 2 of those like you already do. Lastly, the class itself need not have a generic type: since its next
method must be able to return any type, it always returns Object
.
If you have any questions during your future attempts at this problem, or you find that this solution doesn't fit the assignment's requirements, feel free to post a comment.
Generic iterator for an interface and its subclasses and its types and subtypes
You're close. Your iterator BSTIterator
must implement Iterator<SearchTree.Entry<K, V>>
instead of Iterator<BSTNode<K, V>>
. I think it is because the type of your returned iterator has to guarantee it is any Entry<K, V>
, not specifically BSTNode
.
public class BSTIterator<K extends Comparable<? super K>, V>
implements Iterator<SearchTree.Entry<K, V>> {
// ...
}
public class BST<K extends Comparable<? super K>, V>
implements SearchTree<K, V> {
@Override
public Iterator<SearchTree.Entry<K, V>> iterator() {
return new BSTIterator<>();
}
}
Java - Why Iterator need to be generic?
The iterator interface is designed as
public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}
Note the next
method. What return type would it have, if the interface weren't generic? It would be
Object next();
So without parameterization you would end up with code like this:
List<String> list = createSomeList();
String s = (String) list.iterator().next();
Note the necessary cast. The whole point of generics is to produce code without the need to cast; this is called type safety. With the current iterator interface you can do
List<String> list = createSomeList();
String s = list.iterator().next();
Generic IteratorE behaves differently when a Raw Type of Collection object is passed to method which accepts Generic parameter
Thats not the iterator issue but the System.out.println that breaks the code.
On runtime there are no type checkings in collections (lookup Type Erasure for generics for details)
Your code fails because in m1 you are calling in fact
System.out.println(Object ob)
so it all gets printed as every thing in your collection is an Object
but in the m2 calls System.out.println(String str)
and here is the type check performed, you cannot pass object other than String
to this method
Related Topics
Is the "One-Past-The-End" Pointer of a Non-Array Type a Valid Concept in C++
Random Number Generator That Produces a Power-Law Distribution
Understanding the Dangers of Sprintf(...)
Static Analysis Tool to Detect Abi Breaks in C++
Why Is Copy Constructor Called Instead of Conversion Constructor
C++ Convert Integer to String at Compile Time
Do I Need to Close a Std::Fstream
Why Does C++11 Have 'Make_Shared' But Not 'Make_Unique'
How to Print Utf-8 Strings to Std::Cout on Windows
How Do Take a Screenshot Correctly with Xlib
Translating Python Dictionary to C++
Erasing Using Backspace Control Character
What's the Difference Between the Win32 and _Win32 Defines in C++
C++ Polymorphism Without Pointers
Loop Until Integer Input Is in Required Range Fails to Work with Non-Digit Character Inputs