# teaching machines

## CS 245 Lecture 19 – Snake

### Agenda

• what ?s
• Snake with ArrayList
• linked structures

### TODO

• I’ve reduced the grading scale by a couple of points. There are still 18 Blugolds available.

### Code

#### HashSet.java

package lecture19;

import java.util.ArrayList;

public class HashSet<T> {
private ArrayList<T>[] items;

public HashSet() {
items = new ArrayList[5];
}

public void add(T item) {
int i = Math.abs(item.hashCode()) % items.length;
if (items[i] == null) {
items[i] = new ArrayList<T>();
}
if (!items[i].contains(item)) {
items[i].add(item);
}
}

public void remove(T item) {
int i = Math.abs(item.hashCode()) % items.length;
if (items[i] != null) {
items[i].remove(item);
}
}

public boolean contains(T item) {
int i = Math.abs(item.hashCode()) % items.length;
return items[i] != null && items[i].contains(item);
}

public Iterator getIterator() {
return new Iterator();
}

public class Iterator {
private int hashIndexOfItemToRetrieve;
private int listIndexOfItemToRetrieve;

public Iterator() {
hashIndexOfItemToRetrieve = 0;
listIndexOfItemToRetrieve = -1;
advanceToNextItemToRetrieve();
}

public boolean hasNext() {
return hashIndexOfItemToRetrieve < items.length;
}

public T next() {
T item = items[hashIndexOfItemToRetrieve].get(listIndexOfItemToRetrieve);
advanceToNextItemToRetrieve();
return item;
}

private void advanceToNextItemToRetrieve() {
++listIndexOfItemToRetrieve;

while (hashIndexOfItemToRetrieve < items.length &&
(items[hashIndexOfItemToRetrieve] == null ||
listIndexOfItemToRetrieve >= items[hashIndexOfItemToRetrieve].size())) {
listIndexOfItemToRetrieve = 0;
++hashIndexOfItemToRetrieve;
}
}
}

public static void main(String[] args) {
HashSet<String> set = new HashSet<String>();
set.add("a");
System.out.println(set.contains("a"));
set.remove("a");
System.out.println(set.contains("a"));

set.add("a");
set.add("b");
set.add("c");
set.add("d");
set.add("e");
set.add("f");
set.add("g");
set.add("z");
set.add("z");
set.add("ifrim");
set.add("racecar");

System.out.println(set.contains("racecar"));
System.out.println(set.contains("tacocat"));

HashSet<String>.Iterator i = set.getIterator();
while (i.hasNext()) {
System.out.println(i.next());
}
}
}

#### SnakesOnAFrame.java

package lecture19;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.util.ArrayList;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class SnakesOnAFrame extends JFrame implements KeyListener {
private static final int TILE_WIDTH = 25;
private static final int TILE_HEIGHT = 25;
private int heightInTiles;
private int widthInTiles;
private SnakesPanel panel;
private ArrayList<Point> snake;

private HashSet<Point> eggs;

public SnakesOnAFrame() {
eggs = new HashSet<Point>();

panel = new SnakesPanel();
add(panel);

setFocusable(true);
requestFocusInWindow();
addKeyListener(this);

setSize(1024, 600);

heightInTiles = (int) (getSize().getHeight() / TILE_HEIGHT);
widthInTiles = (int) (getSize().getWidth() / TILE_WIDTH);

generateEggs();
snake = new ArrayList<Point>();
snake.add(new Point(6, 9));

setDefaultCloseOperation(EXIT_ON_CLOSE);
setVisible(true);
}

private void generateEggs() {
Random g = new Random();
for (int i = 0; i < 20; ++i) {
int y = g.nextInt(heightInTiles);
int x = g.nextInt(widthInTiles);
eggs.add(new Point(x, y));
}
}

class SnakesPanel extends JPanel {
public void paintComponent(Graphics g) {
super.paintComponent(g);

// draw eggs
g.setColor(Color.ORANGE);
HashSet<Point>.Iterator i = eggs.getIterator();
while (i.hasNext()) {
Point egg = i.next();
g.fillOval(egg.x * TILE_WIDTH, egg.y * TILE_HEIGHT, TILE_WIDTH, TILE_HEIGHT);
}

g.setColor(Color.GREEN);
for (Point segment : snake) {
g.fillRoundRect(segment.x * TILE_WIDTH, segment.y * TILE_HEIGHT, TILE_WIDTH, TILE_HEIGHT, 5, 5);
}
}
}

public static void main(String[] args) {
new SnakesOnAFrame();
}

@Override
public void keyPressed(KeyEvent arg0) {
}

@Override
public void keyReleased(KeyEvent event) {
Point head = new Point(snake.get(0));
switch (event.getKeyCode()) {
case KeyEvent.VK_UP:
--head.y;
break;
case KeyEvent.VK_DOWN:
++head.y;
break;
case KeyEvent.VK_LEFT:
--head.x;
break;
case KeyEvent.VK_RIGHT:
++head.x;
break;
}

snake.add(0, head);

// Is there an egg under the head?
if (!eggs.contains(head)) {
snake.remove(snake.size() - 1);
} else {
eggs.remove(head);
}

panel.repaint();
}

@Override
public void keyTyped(KeyEvent arg0) {
}
}

### Haiku

An ID crisis
Am I male? What is a train?
Array or linked list?