The goal of this lab period is to get you started on the current assignment. We'll go over a singly-linked list, private classes, Iterators, and how to create a generic container.

Documentation for Java 1.6 is located at: Java 1.6 SE API

---

Tasks

1. Create a new java file called LinkedList.java. Import java.util.*. Define the class as:

   public class LinkedList<T>

2. First, we need to create an inner container class that will hold a generic object and a next pointer. Make a private inner class called Node that has a Node field called next, and a T field with a name of your choice. The Node class should have the following methods.
   • public Node(T item) - a constructor that initialized next to null and the container field to item.
   • public T getContents() - returns the value of the container field.
   • public void setNext(Node n) - sets next to the given node.
   • public Node getNext() - returns the next node.
3. Create the fields for the LinkedList class to store the head of the list and the number of items in the list. Then make the following methods for the LinkedList class.
   • public LinkedList() - constructor that creates an empty list.
   • public void clear() - empties the list.
   • public int size() - returns the size of the list.
   • public void add(T item) - adds item to the head of the list.
4. To enable another program to loop through our list, we're going to implement the Iterable interface, which allows a programmer to use the foreach loop structure on our LinkedLists. First, change the class definition for LinkedList to be:

   public class LinkedList<T> implements Iterable<T>

   Then we need to create our own Iterator subclass that handles traversing the list. Create a new private class inside the LinkedList class with the following definition.

   private class LinkedListIterator implements Iterator<T>

   Give the class one field, which is of type Node, and which will hold the next node to be provided during a traversal. Then implement the following methods in the class.

   • public LinkedListIterator(Node head) - creates an LinkedListIterator given the head of a list.
   • public boolean hasNext() - returns true if there are still values to traverse (if the current node reference is not null).
   • public T next() - returns the next item in the list, which is the item contained in the current node. The method also needs to move the traversal along to the next node in the list.
   • public void remove() - does nothing. Implementing this function is optional for an Iterator.

   Finally, add the function iterator to your LinkedList class. It should return a new LinkedListIterator with head passed to the constructor.

   public Iterator<T> iterator()

5. Now copy the following main function to your LinkedList.java file and test out your Iterator.

   public static void main(String[] args) {
       LinkedList<Integer> list = new LinkedList<Integer>();
   
       list.add(5);
       list.add(10);
       list.add(20);
   
       System.out.printf("\nAfter setup %d\n", list.size());
       for(Integer item: list) {
           System.out.printf("thing %d\n", item);
       }
       list.clear();
   
       System.out.printf("\nAfter clearing %d\n", list.size());
       for(Integer item: list) {
           System.out.printf("thing %d\n", item);
       }
   
       for(int i=0;i<20;i+=2) {
           list.add(i);
       }
   
       System.out.printf("\nAfter setting %d\n", list.size());
       for(Integer item: list) {
           System.out.printf("thing %d\n", item);
       }
   }
   

6. Create two more methods for your LinkedList class. You can make use of the foreach structure in the first method.
   • public ArrayList<T> toArrayList() - returns an ArrayList of the list contents in order.
   • public ArrayList<T> toShuffledList() - returns an ArrayList of the list contents in shuffled order.

   Then add the following to the end of your main test function.

       ArrayList<Integer> array = list.toArrayList();
       System.out.printf("\nAfter copying %d\n", array.size());
       for(Integer item: array) {
           System.out.printf("thing %d\n", item);
       }						
   
       array = list.toShuffledList();
       System.out.printf("\nAfter copying %d\n", array.size());
       for(Integer item: array) {
           System.out.printf("thing %d\n", item);
       }
   

Agents on a Landscape

This week we'll continue to experiment with 2D agent-based simulations. You will also use the linked-list class from lab to maintain a list of agents in a Landscape.

Documentation for Java 1.6 is located at: Java 1.6 SE API

Setup

You can copy over your Cell.java and Landscape.java files from project 2. We'll be modifying, and in some cases simplifying them.

In general, a Landscape will no longer be a discrete thing with cells. Instead, each Cell will keep track of its own location, and that location will be a continous value. The Landscape will use the LinkedList class to keep track of agents on the Landscape.

Tasks

1. Simplify the Cell class so that it keeps track of only its location, and does so with two double fields: x and y. The Cell class should have only the following functions.
   • public Cell(double x, double y) - constructor that takes an x and y location.
   • public double getX() - returns the x location as a double.
   • public int getColumn() - returns the x location as the nearest integer.
   • public double getY() - returns the y location as a double
   • public int getRow() - returns the y location as the nearest integer.
   • public String toString() - returns a string containing a single period.
   • public void updateState(Landscape scape) - this function will update the Cell's state and status, but leave it blank for now. In fact, you may want to comment it out so you can run the test main function given below without having to compiled Landscape.
   • Create a test main function. Feel free to use the following.

   public static void main(String args[]) {
   	Cell cell1 = new Cell(4.4, 3.6 );
   	Cell cell2 = new Cell(2.1, 4.5 );
   
   	System.out.printf( "cell1: %.2f %.2f %d %d\n", 
   	cell1.getX(), cell1.getY(), 
   	cell1.getColumn(), cell1.getRow() );
   
   	System.out.printf( "cell2: %.2f %.2f %d %d\n", 
   	cell2.getX(), cell2.getY(), 
   	cell2.getColumn(), cell2.getRow() );
   }
   

2. Update your Landscape class so that in contains fields for the width and height (in pixels) and a LinkedList of Cell objects. The Landscape should implement the following methods.
   • public Landscape(int rows, int columns) - initialize the three fields.
   • public void reset() - clear the Landscape of agents.
   • public void getRows() - return the height of the Landscape.
   • public void getColumns() - return the width of the Landscape.
   • public void addAgent(Cell agent) - add the agent a to the Landscape.
   • public ArrayList getAgents() - returns an ArrayList of the Cells on the Landscape.
   • public String toString() - returns a string representing the Landscape. You may want to, first, create an ArrayList (or a regular 2D array) of String objects that are all initially a single space, with a carriage return at the end of each row. Then go through your agents and ask each one for its row and column index. After making sure they are within the boundaries of the Landscape, update the appropriate String in the grid or array using the Cell's toString function. At the end, concatenate all of the Strings in the grid or ArrayList and return it.
   • public ArrayList getNeighbors(double x0, double y0, double radius) - return a list of the Cells within radius distance of the location x0, y0.
   • public void advance() - get a shuffled list of Cells and then go through each one and call its updateState method.
   • Use the following test function to test if you can create a Landscape.

     public static void main(String args[]) {
         int rows = 30;
         int columns = 70;
         int numberOfAgents = 300;
         Landscape scape = new Landscape(rows, columns);
         Random generator = new Random();
     
         System.out.println("Landscape:\n" + scape);
         for(int i=0;i<numberOfAgents;i++) {
             float xCoordinate = generator.nextFloat() * columns;
             float yCoordinate = generator.nextFloat() * rows;
             scape.addAgent(new Cell(xCoordinate, yCoordinate));
         }
     
         System.out.println("\nLandscape:\n" + scape);
     }
     

3. Now go back to the Cell class and write the updateState method. It should implement the following rules.

   If the cell has more than 3 neighbors, then 
       the cell should move +/- 5 with a 1% chance.
   else
       the cell should move +/- 5
   

   Note that the Cell's motion should be a continuous value between +5 and -5 in both X and Y. You can use nextFloat or nextDouble to get a random floating point value between 0 and 1.0.

Then add the following the end of the Landscape main method.

for(int i=0;i<10;i++) {
    scape.advance();
    System.out.println("Iteration " + i + ":");
    System.out.println(scape);
}

Run Landscape and see if you get clumping behavior.

4. Create a new class, CategorizedCell, that extends Cell.

   public class CategorizedCell extends Cell {

   The new class should have an integer field category and implement or override the following methods.

   • public CategorizedCell(double x, double y, int category) - call the parent constructor and set the category. (The parent's constructor can be called using: super(...) ).
   • public int getCategory() - return the category value.
   • public String toString() - return a single character string indicating the category.
   • public void updateState(Landscape scape) - implement the following rule.

     Identify how many neighbors have the same category and how many are different
     
     If there are more of the same category
        move +/- 5 with a 1% chance
     else
        move +/- 5 
     

5. Change your Landscape main test function to create CategorizedCell agents instead of Cell agents in the main test function. Better yet, design a system where which type of Cell is created is determined by a command line argument. Give the CategorizedCell agents the category 0 or 1, then run the simulation again. If you wish, try using more categories.
6. Make a new Simulation class that can do the following.
   1. Run either type of simulation
   2. Control how many iterations the simulation will run
   3. Control how often the simulation gets printed to the command line
   4. Control the width and height of the Landscape
   5. Control the number of agents on the Landscape
7. Create one other type of agent that extends the Cell class and has a different update rule. Show simulations for it. Explain what individual behavior you are trying to model with your new agent type. [Example: the original Cell class is modeling a preference for clumping, while the second Cell class is modeling the impact on group behavior of subtle individual preferences.]

---

Extensions

1. See if you can mix and match different agent types and what happens.
2. Try out additional Cell subclasses with different update rules.
3. Experiment with the effects of modifying some of the update rules. These should be compare and contrast. Try to avoid comparing simulations where more than one thing has been changed.
4. Use command line arguments to control simulation parameters.
5. See if you can figure out how to make pictures of your Simulation. You may try to look at the pgm or ppm format.

---

Handin

Before handing in your code, double check that it is well-styled:

• All variable names and function names use camelCase.
• All class names are in PascalCase.
• All public classes and methods use complete JavaDoc.
• All private class members (fields and methods) have their own descriptive comment (but not JavaDoc).
• Comments are added to explain complicated code blocks.
• All variable and function names are appropriately descriptive.
• All indenting and squigly-braces are properly placed.
• Each class should have a unit test (main method) that calls and tests all methods in the class.

Make your writeup for the project a wiki page in your personal space. If you have questions about making a wiki page, stop by my office or ask in lab.

Your writeup should have a simple format.

• A brief description of the overall task, in your own words.
• As explanation of your solution, focusing on the interesting bits and any extensions.
• Printouts, pictures, or results to show what you did. You can do screen captures of your terminal to show the initial and final landscapes.
• Other results to demonstrate extensions you undertook. If you tried different update rules, for example, show how those affected the overall simulation results.
• A brief conclusion and description of what you learned.

Once you have written up your assignment, give the page the label:

cs231f13project3

You can give any page a label when you're editing it using the label field at the bottom of the page.

Do not put code on your writeup page or anywhere it can be publicly accessed. To hand in code, upload it to the Courses server.