Lecture: 7
Date: Jan 23, 2008

Q: How was lab?
Tedious?  Repetitive?  Long?  Repetitive?

The lab was testing not only that you knew the material but that you
have mastered it and can rattle it off quickly.

===

Recall our shape data definitions, but let's use Circles today and
forget about Squares.  So we have:

           +----------+
           |  IShape  |
           +----------+
            / \     / \
            ---     ---
             |       |
  +-------------+  +------------+
  |   Circle    |  | Rectangle  |
  +-------------+  +------------+
+-| Point center|  | Posn nw    |-+
| | int radius  |  | int height | |
| +-------------+  | int width  | |
|                  +------------+ |
|                                 |
|  +-----------+                  |
+->|   Point   |<-----------------+
   +-----------+
   | int x     |
   | int y     |
   +-----------+


(The names may have changed slightly from last time).

Notice that I made my own Posn-like class.  We'll see why in a minute.


Develop a program for determining if a point falls within a shape.

We have a union and two variants.  We need an interface.  The header
goes in the interface.  Since the header is in the interface, both
variants must implement the method.  So we have:

interface IShape {
  // does this shape contain the given point?
  boolean contains(Posn p);
}

class Rectangle ... {
  ...
  // does this rectangle contain the given point?
  boolean contains(Point p) { ... }
}

class Circle ... {
  ...
  // does this circle contain the given point?
  boolean contains(Point p) { ... }
}

Notice the subtle differences in purpose statements.

Let's makes some examples:

Point pout = new Point(0,0);
IShape circ = new Circle(new Point(10,10),5);
IShape rect = new Rectangle(new Point(10,15),10,20);

Point pincirc = new Point(8,12);
Point pinrect = new Point(18,10);

Draws these on the board.

circ.contains(pincirc) -> true
circ.contains(pinrect) -> false ...

You should be able to write these in the style of check ... expect
expressions (we just use a convenient short hand in class, but you're
responsible for all the details).

Let's do the circle implementation first.

class Circle ... {
  ...
  // does this circle contain the given point?
  boolean contains(Posn p) {
  /* Template
  ... this.loc ...    Point
  ... this.radius ... int
  ... p ... Point
  ... p.x ...       Q: Should we include p.x, p.y?
  ... p.y ...
  */
  ... }
}

A: No.  Why?  Because that breaks an ABSTRACTION BOUNDARY.  Suppose
   Point is changed in the future and uses polar coordinates rather than
   Cartesian.  Then we have to change all of the places that we
   accessed the x and y fields.  As a rule of thumb, you should only
   access what is advertised in an interface.  Otherwise you tie
   yourself to the particulars of the implementations of the classes
   you use.

Rules are meant to be broken and we're going to break this one in a
minute.  But you need to be conscious of this and avoid it if you can.

Q: Informally, how do we decide if a point is within a circle?  A: If
   the distance from the center point to the given point is less than
   the radius, then the point is in the circle.

(You have to decide about the boundary case.  If the distance =
radius, what do you do?  There is no right answer).

Q: What does this informal description suggest?
A: Wish list: compute the distance between two points.

Q: OK, where should this be defined?
A: Point, clearly.

Q: Why did I make my own Posn-like class?
A: So we could add a distanceTo method.

Q: What is the header for distanceTo?

// compute the distance from this point to the given point.
??? distanceTo(Point that)

Q: What should ??? be? int, double, Point, IShape, ...?
A: double.

Suppose we have double distanceTo(Point) in the Point class.
Q: How do you write Circle's contains method?
A: Well first, you update the template by adding p.distanceTo(Point)
   and this.loc.distanceTo(Point).

class Circle ... {
  ...
  // does this circle contain the given point?
  boolean contains(Posn p) {
  /* Template
  ... this.loc ...    Point
  ... this.radius ... int
  ... this.loc.distanceTo(Point) ... double
  ... p ... Point
  ... p.distanceTo(Point) ... double
  */
    return p.distanceTo(this.loc) <= this.radius;
  }
}

Q: Could we have done return this.loc.distanceTo(p) <= this.radius?

Let's turn to distanceTo.

// compute the distance between this point and the given point.

Q: Why not: between two points?
Q: What does the above tell us about the method header?

double distanceTo(Point that) {
  /* Template
  ... this.x ... int
  ... this.y ... int
  ... that.x ... int  Q: Should we include that.x and that.y?
  ... that.y ... int
  */
}

A: Yes.
Q: But what about all that ABSTRACTION BARRIER stuff?
A: Well, we're not breaking any abstraction because we are IN the
   Point class and "that" is a Point.  We haven't broken anything.

Examples

Point p2 = new Point(3,4);
pout.distanceTo(p2) ~> 5.0

Q: Why not 5?

Q: How do you compute the distance between points?
A: sqrt((x1-x2)2 + (y1-y2)2)

Q: How do you compute square roots in Java?
A: I don't know.  Ask the math expert: Math.

return Math.sqrt((this.x - that.x) * (this.x - that.x)
               + (this.y - that.y) * (this.y - that.y));

Look at the Help Desk documentation for ProfJ beginner.  Look at the
grammar of programs.  Look at EXPRESSION, then:

check EXPRESSION expect EXPRESSION

We know this one, but what about:

check EXPRESSION expect EXPRESSION within EXPRESSION

Q: What is this for?
A: Testing floating point numbers.

For example,

check pout.distanceTo(p2) expect 5.0 within 0.000001

Let's now do Rectangle's contains.

class Rectangle ... {
  ...
  // does this rectangle contain the given point?
  boolean contains(Point p) {
  /* Template
  ... this.loc ... Point
  ... this.height ... int
  ... this.width ... int
  ... this.loc.distanceTo(Point) ... double
  ... p ... Point
  ... p.distanceTo(Point) ... Point
  */
}

Q: Informally, how do we determine if a point is within a rectangle.

Think about intervals.  If the given point's x coordinate is within
[this.x,this.x+this.width] AND if the given point's y coordinate is
within [this.y,this.y+this.width], then the given point is inside this
rectangle, otherwise it is not.

Q: What does this suggest?
A: Wish list: boolean inInterval(int left, int n, int size)

// Determine if given n is in the interval [left,left+size].

Q: Where's the "this"?
A: Nowhere, so this method doesn't really depend on the rectangle that
   invokes the method.

Q: But where do we put the definition?
A: In Rectangle, because it is a helper for a Rectangle method.

Suppose we had boolean inInterval(int left, int n, int size).
Q: How do you write Rectangle's contains method?
A: Well first, you update the template by adding
   this.inInterval(int,int,int).

Then you'd say

  return this.inInterval(this.loc.x, p.x, this.width) &&
         this.inInterval(this.loc.y, p.y, this.height);

Q: WAIT A MINUTE.  Where did you get p.x and p.y?  Those aren't in the
   template.
A: Ah, you're right.  We've broken an ABSTRACTION BARRIER.  But we've
   done it intentionally.

See, I told you this would happen.  Did you think I was lying?

Q: How would you design inInterval?

// Determine if given n is in the given interval [left,left+size].
boolean inInterval(int left, int n, int size) {
  return left <= n && n <= left+size;
}

OK, let's do something more complicated:

  +----------------------+
  | +----------------+   |
  V V                |   |
A BST is one of      |   |
- (make-leaf)        |   |
- (make-node Number BST BST)

(define-struct leaf ())
(define-struct node (value left right))

Draw the class diagrams.

Q: What is the principle property of BSTs that we've left out here?
A: For any node, the numbers in the left subtree are smaller than the
   value in this node, and the numbers in the right subtree are greater
   than (or equal to?) the value in this node.

Q: What about repetitions?

Q: How do you insert a new value into a BST?

;; insert : BST Number -> BST
(define (insert b n)
  (cond [(leaf? b) ...]
        [(node? b) ... (node-value b)
                   ... (insert (node-left b) n)
                   ... (insert (node-right b) n)]))

(insert (make-leaf) 5) => (make-node 5 (make-leaf) (make-leaf))
(insert (make-node 7 (make-leaf) (make-leaf)) 5)
=>
(make-node 7 (make-node 5 (make-leaf) (make-leaf)) (make-leaf))

Q: Informally, how do we insert a value into a tree?

Well, if it's a leaf, you make a new node with the value and put
leaves in the subtrees.

If it's a node, you have to compare the value with the number in the
node.  If the given number is smaller, insert into the left
subtree. Otherwise, insert into the right.

Q: And...?
A: Oh yeah, let me revise:

If it's a node, you have to compare the value with the number in the
node.  If the given number is smaller, make a new node holding the
value of the current node, in the left subtree insert the given value
into the left subtree of the current node, in the right, just use the
right subtree of the current node.  Likewise, but reversed for the
right.

Code it.

;; insert : BST Number -> BST
(define (insert b n)
  (cond [(leaf? b) (make-node n (make-leaf) (make-leaf))]
        [(node? b)
         (if (> (node-value b) n)
             (make-node (node-value b)
                        (insert (node-left b) n)
                        (node-right b))
             (make-node (node-value b)
                        (node-left b)
                        (insert (node-right b) n)))]))

Think about how to do this in Java.