teaching machines

CS 245 Lecture 11 – Set and Generics

October 8, 2013 by Chris Johnson. Filed under
Deprecated: Creation of dynamic property WP_Term::$cat_ID is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 378

Deprecated: Creation of dynamic property WP_Term::$category_count is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 379

Deprecated: Creation of dynamic property WP_Term::$category_description is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 380

Deprecated: Creation of dynamic property WP_Term::$cat_name is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 381

Deprecated: Creation of dynamic property WP_Term::$category_nicename is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 382

Deprecated: Creation of dynamic property WP_Term::$category_parent is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 383

Deprecated: Creation of dynamic property WP_Term::$cat_ID is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 378

Deprecated: Creation of dynamic property WP_Term::$category_count is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 379

Deprecated: Creation of dynamic property WP_Term::$category_description is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 380

Deprecated: Creation of dynamic property WP_Term::$cat_name is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 381

Deprecated: Creation of dynamic property WP_Term::$category_nicename is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 382

Deprecated: Creation of dynamic property WP_Term::$category_parent is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 383

Deprecated: Creation of dynamic property WP_Term::$cat_ID is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 378

Deprecated: Creation of dynamic property WP_Term::$category_count is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 379

Deprecated: Creation of dynamic property WP_Term::$category_description is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 380

Deprecated: Creation of dynamic property WP_Term::$cat_name is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 381

Deprecated: Creation of dynamic property WP_Term::$category_nicename is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 382

Deprecated: Creation of dynamic property WP_Term::$category_parent is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 383
cs245, fall 2013, lectures.

Agenda

• what ?s
• what does this do?
• writing a set data type
• generalizing code without a supertype

What Does This Do?

• public abstract class Foo {
    public String toString() {return "foofoofoo";}
  }
  ...
  System.out.println(new Foo());

• public class A {
    public int get() {return 5;}
  }
  public class B extends A {
    public int get() {return 7;}
  }
  ...
  A a = new B();
  System.out.println(a.get());

• public static boolean isEven(int i) {
    return isOdd(i - 1);
  }
  public static boolean isOdd(int i) {
    return isEven(i - 1);
  }
  ...
  System.out.println(isEven(9));

Code

VerdeganTest.java

package lecture11;

public class VerdeganTest {
  public static boolean isEven(int i) {
    return isOdd(i - 1);
  }

  public static boolean isOdd(int i) {
    if (i == 1) {
      return true;
    } else if (i == 0) {
      return false;
    }
    return /* i == 1 || */isEven(i - 1);
  }

  public static void main(String[] args) {
    System.out.println(isEven(2000000));
  }
}

Set.java

package lecture11;

public class Set<T> {
  private T[] items;
  private int nitems;

  public Set() {
    items = (T[]) new Object[100];
    nitems = 0;
  }
  
  public T get(int i) {
    return items[i];
  }

  public int size() {
    return nitems;
  }

  public boolean contains(T needle) {
    for (int i = 0; i < size(); ++i) {
      if (items[i].equals(needle)) {
        return true;
      }
    }
    return false;
  }

  public void add(T s) {
    if (!contains(s)) {
      items[nitems] = s;
      ++nitems;
    }
  }

  public static void main(String[] args) {
    Set<String> set = new Set<String>();
    System.out.println(set.size());
    set.add("blarp");
    System.out.println(set.contains("blarp"));
    
    String s = set.get(0);
  }
}

Haiku