Extending An Iterator

Resources:

1. How to design a skip iterator
2. Java's Iterator reference
3. C#'s IEnumerator reference
4. Wikipedia article on iterators

Takeaways:

• Iterators allow us to traverse and access elements in collections without the use of indexing.
• Iterators expose a consistent way to traverse all types of data structures, making the code more resilient to change.
• Iterators can allow the underlying collection to be modified during traversal, unlike when using indexing to iterate over a collection (like using a for loop on an array). This can mean insertion/deletion of items during traversal.
• Iterators exist in many languages, in C# they are called enumerators.
• Time & Space complexity in the code comments

Below you will find a class that takes an enumerator in it's constructor and extends the basic functionality of an iterator with the addition of Skip(), Peek(), & Remove() operations:

	using System;
	using System.Collections.Generic;
	using System.Diagnostics;
	public class Program
	{
	public class Iterator
	{
	private IEnumerator<int> it;
	private Dictionary<int, int> count;
	private int nextItem;
	// O(k) time, where k is the number of elements to skip
	public Iterator(IEnumerator<int> input)
	{
	it = input;
	count = new Dictionary<int, int>();
	Advance();
	}
	// O(k) time, where k is the number of elements to skip
	public int Next()
	{
	if (!HasNext())
	{
	throw new IndexOutOfRangeException();
	}
	int item = nextItem;
	Advance();
	return item;
	}
	// O(1) time
	public bool HasNext()
	{
	return nextItem != int.MinValue;
	}
	// O(1) time
	public int Peek()
	{
	if (!HasNext())
	{
	throw new IndexOutOfRangeException();
	}
	return nextItem;
	}
	// O(n*k) time, where n is the number of elements & k is the number of elements to skip
	// O(n + k) space
	public void Remove()
	{
	if (!HasNext())
	{
	throw new IndexOutOfRangeException();
	}
	var newIt = new List<int>();
	while (HasNext())
	{
	if (count.ContainsKey(nextItem))
	{
	count[nextItem]--;
	if (count[nextItem] == 0)
	{
	count.Remove(nextItem);
	}
	Advance();
	continue;
	}
	Advance();
	break;
	}
	while (it.MoveNext())
	{
	newIt.Add(it.Current);
	}
	it = newIt.GetEnumerator();
	}
	// O(k) space, where k is the number of elements to skip
	public void Skip(int toSkip)
	{
	// O(1) time
	if (!HasNext())
	{
	throw new IndexOutOfRangeException();
	}
	// O(k) time
	if (nextItem == toSkip)
	{
	Advance();
	}
	// O(1) time
	else
	{
	if (count.ContainsKey(toSkip))
	{
	count[toSkip] += 1;
	}
	else
	{
	count.Add(toSkip, 1);
	}
	}
	}
	// O(k) time, where k is the number of elements to skip
	private void Advance()
	{
	nextItem = int.MinValue;
	// MoveNext() is sort of like calling HasNext() & Next() in Java
	while (nextItem == int.MinValue && it.MoveNext())
	{
	int item = it.Current;
	if (!count.ContainsKey(item))
	{
	nextItem = item;
	}
	else
	{
	count[item] -= 1;
	if (count[item] == 0)
	{
	count.Remove(item);
	}
	}
	}
	}
	}
	public static void Main()
	{
	var list = new List<int>
	{
	2,
	3,
	5,
	6,
	5,
	7,
	5,
	-1,
	5,
	10
	};
	var itr = new Iterator(list.GetEnumerator());
	Debug.Assert(itr.Peek() == 2);
	Debug.Assert(itr.Next() == 2);
	itr.Remove();
	Debug.Assert(itr.Peek() == 5);
	Debug.Assert(itr.Next() == 5);
	itr.Remove();
	itr.Remove();
	itr.Skip(7);
	itr.Skip(5);
	itr.Remove();
	Debug.Assert(itr.Next() == 5);
	itr = new Iterator(list.GetEnumerator());
	Debug.Assert(itr.HasNext());
	Debug.Assert(itr.Next() == 2);
	itr.Skip(5);
	Debug.Assert(itr.Next() == 3);
	Debug.Assert(itr.Next() == 6);
	Debug.Assert(itr.Peek() == 5);
	Debug.Assert(itr.Next() == 5);
	itr.Skip(5);
	itr.Skip(5);
	Debug.Assert(itr.Next() == 7);
	Debug.Assert(itr.Next() == -1);
	Debug.Assert(itr.Next() == 10);
	Debug.Assert(!itr.HasNext());
	}
	}

view raw Iterators.cs hosted with ❤ by GitHub

As always, if you found any errors in this post please let me know!