teaching machines

CS 245 Lecture 21 – Linked List, Stack, and Queue

April 15, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• why are we here?
• finishing up linked list and Snake
• stacks and queues
• a postfix calculator
• an HTML validator

Program This

Program This

Code

HashSet.java

package lecture21;

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());
    }
  }
}

LinkedList.java

package lecture21;

import java.util.NoSuchElementException;

public class LinkedList<T> {
  private Node<T> head;
  private Node<T> tail;

  public LinkedList() {
    head = new Node<T>(null, null, null);
    tail = new Node<T>(null, null, null);
    head.next = tail;
    tail.prev = head;
  }

  /**
   * Adds the new item at the end of this list.
   * 
   * @param newItem
   * The item to add.
   */
  public void prepend(T newItem) {
    Node<T> newNode = new Node<T>(newItem, head.next, head);
    head.next = newNode;
    newNode.next.prev = newNode;
  }

  public void append(T newItem) {
    Node<T> newNode = new Node<T>(newItem, tail, tail.prev);
    tail.prev = newNode;
    newNode.prev.next = newNode;
  }

  public boolean isEmpty() {
    return head.next == tail;
  }

  public int size() {
    int count = 0;
    Node<T> thisNode = head;
    while (thisNode.next != tail) {
      ++count;
      thisNode = thisNode.next;
    }
    return count;
  }

  public T getFirst() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    return head.next.value;
  }

  public T getLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    return tail.prev.value;
  }

  public T removeFirst() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    T value = head.next.value;
    head.next = head.next.next;
    head.next.prev = head;
    return value;
  }

  public T removeLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    T value = tail.prev.value;
    tail.prev = tail.prev.prev;
    tail.prev.next = tail;
    return value;
  }

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

  public class Iterator {
    private Node<T> current;

    public Iterator() {
      current = head;
    }

    public boolean hasNext() {
      return current.next != tail;
    }

    public T next() {
      current = current.next;
      return current.value;
    }
  }

  public static class Node<T> {
    private T value;
    private Node<T> next;
    private Node<T> prev;

    public Node(T value,
                Node<T> next,
                Node<T> prev) {
      this.value = value;
      this.next = next;
      this.prev = prev;
    }
  }
}

SnakesOnAFrame.java

package lecture21;

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.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;
import lecture21.LinkedList.Iterator;

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 LinkedList<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 LinkedList<Point>();
    snake.append(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);
      LinkedList<Point>.Iterator iSnake = snake.getIterator();
      while (iSnake.hasNext()) {
        Point segment = iSnake.next();
        g.fillRoundRect(segment.x * TILE_WIDTH, segment.y * TILE_HEIGHT, TILE_WIDTH, TILE_HEIGHT, 20, 20);
      }
    }
  }

  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.getFirst());
    
    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;
    }

    // Insert the new head.
    snake.prepend(head);

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

    panel.repaint();
  }

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

Stack.java

package lecture21;

public class Stack<T> {
  private LinkedList<T> items;
  
  public Stack() {
    items = new LinkedList<T>();
  }
  
  public boolean isEmpty() {
    return items.isEmpty();
  }
  
  public void push(T item) {
    items.append(item);
  }
  
  public T pop() {
    return items.removeLast();
  }
  
  public T peek() {
    return items.getLast();
  }
}

Valhalla.java

package lecture21;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Valhalla {
  public static void main(String[] args) throws FileNotFoundException {
    Scanner in = new Scanner(new File("/Users/johnch/Desktop/foo.html"));
    in.useDelimiter("(\\A|>)[^<]*(\\Z|<)");

    Stack<String> opens = new Stack<String>();

    while (in.hasNext()) {
      String element = in.next();
      System.out.println(element);
      // if it's an opener
      // push it
      // else
      // if there's no top
      // stack underflow -- invalid
      // elsif it corresponds to the top
      // pop -- valid
      // else bad correspondence

      if (!element.startsWith("/")) {
        opens.push(element);
      } else if (opens.isEmpty()) {
        System.out.println("stack underflow");
        return;
      } else {
        if (opens.peek().startsWith(element.substring(1))) {
          opens.pop();
        } else {
          System.out.println("got a " + element + " but waiting for a " + opens.peek());
          return;
        }
      }
    }

    if (opens.isEmpty()) {
      System.out.println("wee!");
    } else {
      System.out.println("unclosed " + opens.peek());
    }
  }
}

Haiku