DesignPattern : Iterator

1. A simple mockup for ArrayList

package edu.xmu.designPattern.DesignPattern_Iterator;

public class ArrayList
{
	private Object[] objects = new Object[10];
	private int index = 0;

	public void add(Object o)
	{
		if (index == objects.length)
		{
			Object[] newObjects = new Object[objects.length * 2];
			System.arraycopy(objects, 0, newObjects, 0, objects.length);
			objects = newObjects;
		}
		objects[index] = obj;
		index++;
	}

	public int size()
	{
		return index;
	}
}

 

package edu.xmu.designPattern.DesignPattern_Iterator;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class ArrayListTest
{
	@Test
	public void test()
	{
		ArrayList list = new ArrayList();

		for (int i = 0; i < 15; i++)
		{
			list.add(new Object());
		}
		assertEquals(15, list.size());
	}
}

    Comments: The benefits of using ArrayList instead of using raw list is that we don't have to worry about the size of the list. It will expand automatically.

 

 

2. A simple mockup for LinkedList

package edu.xmu.designPattern.DesignPattern_Iterator;

public class Node
{
	private Object data;
	private Node next;

	public Node()
	{
		super();
	}

	public Node(Object currentObject, Node next)
	{
		super();
		this.data = currentObject;
		this.next = next;
	}

	public void add(Node node)
	{
		if (null == next)
		{
			next = node;
		} else
		{
			next.add(node);
		}
	}

	public Object getData()
	{
		return data;
	}

	public void setData(Object data)
	{
		this.data = data;
	}

	public Node getNext()
	{
		return next;
	}

	public void setNext(Node next)
	{
		this.next = next;
	}

}

 

package edu.xmu.designPattern.DesignPattern_Iterator;

public class LinkedList
{
	private Node header = null;
	private int size = 0;

	public void add(Object obj)
	{
		if (null == header)
		{
			header = new Node(obj, null);
		} else
		{
			header.add(new Node(obj, null));
		}
		size++;
	}

	public int size()
	{
		return size;
	}
}

 

package edu.xmu.designPattern.DesignPattern_Iterator;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class LinkedListTest
{
	@Test
	public void test()
	{
		LinkedList list = new LinkedList();

		for (int i = 0; i < 15; i++)
		{
			list.add(new Cat(i, "Cat" + i));
		}
		assertEquals(15, list.size());
	}
}

   Comments: This is a simple mockup for one-directional LinkedList.

 

 

3. Take container's replaceability into consideration.

    1) How can we switch the implementation of List from ArrayList to LinkedList without changing code of using them?

        Put it another way, how can we reduce the coupling between List and code that using this List?

        We can use Interface. And let ArrayList and LinkedList implements this Interface.

package edu.xmu.designPattern.DesignPattern_Iterator;

public interface Collection
{
	public void add(Object obj);
	public int size();
}

 

package edu.xmu.designPattern.DesignPattern_Iterator;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class LinkedListTest
{
	@Test
	public void test()
	{
		// Collection list = new ArrayList();
		Collection list = new LinkedList();
		for (int i = 0; i < 15; i++)
		{
			list.add(new Cat(i, "Cat" + i));
		}
		assertEquals(15, list.size());
	}
}

   Comments: Interface Oriented Programming.

 

 

4. Here is another important part of List fuction: Traversal --> This fuction is used quite often.

    How can we get every single Object from this List?

    1) The way we traverse an ArrayList:

package edu.xmu.designPattern.DesignPattern_Iterator;

import org.junit.Test;

public class ArrayListTest
{
	@Test
	public void test()
	{
		ArrayList list = new ArrayList();

		for (int i = 0; i < 15; i++)
		{
			list.add(new Cat(i, "Cat" + i));
		}
		
		for(int i = 0; i < list.size(); i++)
		{
			Cat cat = list.get(i);
		}
	}
}

 

   2) The way we traverse a LinkedList:

package edu.xmu.designPattern.DesignPattern_Iterator;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class LinkedListTest
{
	@Test
	public void test()
	{
		LinkedList list = new LinkedList();
		for (int i = 0; i < 15; i++)
		{
			list.add(new Cat(i, "Cat" + i));
		}
		
		Node currentNode = list.getHeader();
		while (null != currentNode)
		{
			Cat cat = (Cat) currentNode.getData();
			currentNode = currentNode.next();
		}
	}
}

   Comments:

        1)  Q: Why can't we define this in interface, like get(int index)?

             A: It's ok when using get(int index) for ArrayList because it's list inside which is convenient for random access.

                But when it comes to LinkedList when traversing using get(int index), it would have to find the element from head to tail.

                The time cost for traversal in ArrayList is O(n). The time cost for traversal in LinkedList is O(n^2) = (1 + 2 + 3 + 4 + ... + n);

                So we cannot using this to traverse all the list.

            E: And it may also possible for us to implements this Interface using the relization of Binary-Tree or some other techniques. Should we expose preorder/inorder/postorder traversal to the client?

       2)  Q: So, how can we figure out an easy way which have not only reduced the coupling between Implementation and Usage but also reduced the time cost for LinkedList?

            A: Think about Iterator Design Pattern as a solution.

       3) Now the problem is that different implementation may have different ways of traversal. How can we define a unified way to traversal them?

 

 5. A simple mockup for ArrayList Iterator

    1) Iterator interface

package edu.xmu.designPattern.DesignPattern_Iterator;

public interface Iterator
{
	public Object next();

	public boolean hasNext();
}

   2) ArrayList implementation

package edu.xmu.designPattern.DesignPattern_Iterator;

public class ArrayList implements Collection
{
	private Object[] objects = new Object[10];
	private int index = 0;

	public void add(Object obj)
	{
		if (index == objects.length)
		{
			Object[] newObjects = new Object[objects.length * 2];
			System.arraycopy(objects, 0, newObjects, 0, objects.length);
			objects = newObjects;
		}
		objects[index] = obj;
		index++;
	}

	public int size()
	{
		return index;
	}

	public Iterator iterator()
	{
		return new ArrayListIterator();
	}

	private class ArrayListIterator implements Iterator
	{
		private int currentIndex = 0;

		public Object next()
		{
			Object currentObject = objects[currentIndex];
			currentIndex++;
			return currentObject;
		}

		public boolean hasNext()
		{
			if (currentIndex > index || null == objects[currentIndex])
			{
				System.out.println("no next");
				return false;
			} else
			{
				System.out.println("has next");
				return true;
			}
		}
	}
}

   3) ArrayList test case

package edu.xmu.designPattern.DesignPattern_Iterator;

import org.junit.Test;

public class ArrayListTest
{
	@Test
	public void test()
	{
		Collection list = new ArrayList();

		for (int i = 0; i < 15; i++)
		{
			list.add(new Cat(i, "Cat" + i));
		}
		for (Iterator iter = list.iterator(); iter.hasNext();)
		{
			Cat cat = (Cat) iter.next();
			System.out.println(cat);
		}
	}
}

   4) Output is correct.

 

 6. A simple mockup for LinkedList Iterator

    1) The implementation for LinkedList Iterator

package edu.xmu.designPattern.DesignPattern_Iterator;

public class LinkedList implements Collection
{
	private Node header = null;
	private int size = 0;

	public void add(Object obj)
	{
		if (null == header)
		{
			header = new Node(obj, null);
		} else
		{
			header.add(new Node(obj, null));
		}
		size++;
	}

	public int size()
	{
		return size;
	}

	public Iterator iterator()
	{
		return new LinkedListIterator();
	}

	private class LinkedListIterator implements Iterator
	{
		private Node currentNode = header;

		public Object next()
		{
			if (currentNode == header)
			{
				Node temp = header;
				currentNode = header.getNext();
				return temp.getData();
			} else
			{
				Node temp = currentNode.getNext();
				currentNode = temp;
				return temp.getData();
			}
		}

		public boolean hasNext()
		{
			if (null != currentNode.getNext())
			{
				return true;
			} else
			{
				return false;
			}
		}
	}
}

   2) The test case

package edu.xmu.designPattern.DesignPattern_Iterator;

import org.junit.Test;

public class LinkedListTest
{
	@Test
	public void test()
	{
		LinkedList list = new LinkedList();
		for (int i = 0; i < 15; i++)
		{
			list.add(new Cat(i, "Cat" + i));
		}

		for (Iterator iter = list.iterator(); iter.hasNext();)
		{
			System.out.println((Cat) iter.next());
		}
	}
}

   3) The output is correct.