CSC152, Class 42: Vectors

Admin
* Visitors!
* Homework: Finish and "write up" yesterday's lab for next Monday.
* Quick quiz: What class number is it?

Overview:
* Vectors as ADT
* Vectors as compound ADT
* Questions
* Lab

/Questions on hashtables/

public class Silly
{
  public int hashCode()
  {
    return 1;
  } // int hashCode()
}

public class LessSilly {
  String contents;

  public LessSilly(String _contents)
  {
    this.contents = _contents;
  } // LessSilly(String)

  public int hashCode()
  {
    // One strategy: Get the first character, get the UNICODE value, return it
    // Reminder: Java converts between primitive types when it can; 
    // Each char can also be treated as an integer (which happens
    // to be its UNICODE v3 value)
    return this.contents.charAt(0);
  } // int hashCode()

  public String toString()
  {
    return this.contents;
  } // toString()

  public boolean equals(Object other)
  {
    return this.contents.equals(other.toString());
  } // equals(Object)
} // class LessSilly
 
 ht.put(new LessSilly("hello"));
 ht.put(new LessSilly("batman"));
 ht.put(new LessSilly("who"));
 ht.put(new LessSilly("is"));
 ht.put(new LessSilly("your"));
 ht.put(new LessSilly("partner"));
 ht.put(new LessSilly("today"));
 ht.dump(pen);

With "first letter"
  a and q map to same cell in a size 16
  b and r
  c and s
  d and t
  e and u
  f and v
  g and w
  h and x
  i and y BOOM

/Vectors/

Three key aspects of each ADT
* Purpose/Philosophy: A "growable" array of values.
* Methods (our theory):
  * void put(int index, Object putMePlease)
  * Object get(int index)
  * size()
  * toString() or dump()
  * remove(int index)
* Methods (Java practice):
  * put() might be expressed as add(Object), add(int index, Object addMe), and set(int index, Object setme)
  * get() might be expressed as get() or elementAt
  * capacity() or size() might work for size
  * toString() is there (it may or may not work)
  * remove() is there
* Applications: Why would this be a useful ADT or DS?
  * We have lots of applications of arrays
  * We regularly write programs in which arrays need to grow.
* Implementation: You've done it already with arrays

Three key aspects of each ADT
* Purpose/Philosophy: A "kitchen" sink of collections: You can do lots of different things.
* Methods:
  * Set methods (contains)
  * List methods (visit values in sequence)
  * Dictionary-like methods (indexOf)
* Applications
  * Even more!

Sam's questions:
* What's the difference between the capacity and the size?
  * size is how many things you've put in
  * capacity is how much total room there is
  * Example: If we create an array of size 10, but only use indices 0, 1, and 2: the capacity is 10, the size is 3
  * When size is about to exceed capacity, you must expand!
* Why do some basic ideas have two different methods to implement them?
  * E.g., get, elementAt (explicitly do the same thing) 
    * Different interfaces we're implementing have chosen different names
    * Smarter designers might have ensured similar/identical naming in the interfaces
  * add and set
    * Subtle differences in meaning

Lab!