Building Data abstraction for line segments using "type abstraction"

Question

Below is the given exercise:

Exercise 5: Segments

Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints)

It is taught in class that data abstraction is the methodology to create barrier between "how data values are used" and "how data values are represented". It is taught that, an abstract data type is some collection of selectors and constructors, together with some behaviour conditions (invariants).

It is compound data that needs data processing which actually enables to think about data abstraction because the user would like to use this compound data as single unit.

Below code is building "data abstraction" and "ADT" for "rational number" using Java "class".

Point

package math.point;

public class Point{

    /*
     *  Representation constitute constructor & selectors 
     *  Representation - starts
     */

    private float[] tuple = null;

    public Point(float x, float y){
        this.tuple = new float[2];
        tuple[0] = x;
        tuple[1] = y;
    }

    private float xCoordinate(){ //selector
        return this.tuple[0];
    }

    private float yCoordinate(){ //selector
        return this.tuple[1];
    }

    /* Representation - ends */

    /*
     * Use - starts
     * Implementation is done using only constructor and selectors of this class
     */
    public float getXCoordinate(){
        return this.xCoordinate();
    }

    public float getYCoordinate(){
        return this.yCoordinate();
    }

    @Override
    /*
     * All the 3 contracts are of hashCode() are satisfied
     * 
     */
    public int hashCode() {
        int result = 17;
        result = result * 31 + (int)this.xCoordinate();
        result = result * 31 + (int)this.yCoordinate();
        return result;
    }

    @Override
    /*
     * 
     * Implementing logical equality
     */
    public boolean equals(Object obj) {
        return ( (this.xCoordinate() == ((Point)obj).xCoordinate())   && 
                            (((Point)obj).yCoordinate()  == this.yCoordinate())  );
    }

    @Override
    public String toString() {
        return "(" + this.xCoordinate() + ", " + this.yCoordinate() + ")";
    }

    /* Use - ends*/
}

Segment

package math.segment;
import math.point.*;

public class Segment {

    /*
     *  Representation constitute constructor & selectors 
     *  Representation - starts
     */

    private Point startSegment; //composition
    private Point endSegment; //composition

    public Segment(Point p1, Point p2){
        startSegment = p1;
        endSegment = p2;
    }


    private Point startSegment(){ //selector
        return this.startSegment;
    }

    private Point endSegment(){ //selector
        return this.endSegment;
    }

    /* Representation - ends*/





    /*
     * Use - starts
     * Implementation is done using only constructor and selectors of this class
     */
    public Point midPointSegment(){
        return    new Point ( (this.startSegment().getXCoordinate() + this.endSegment().getXCoordinate()) / 2, 
                                        (this.startSegment().getYCoordinate() + this.endSegment().getYCoordinate()) / 2 );
    }

    @Override
    public int hashCode() {
        int result = 17;
        result = result * 31 + this.startSegment().hashCode();
        result = result * 31 + this.endSegment().hashCode();
        return result;
    }


    @Override
    /*
     * Logical equality
     */
    public boolean equals(Object obj) {
        return this.startSegment().equals( ((Segment)obj).startSegment() ) && 
                                    this.endSegment().equals( ((Segment)obj).endSegment() );
    }


    @Override
    public String toString() {
        return  "(" + this.startSegment().getXCoordinate() + ", " + this.startSegment().getYCoordinate() + ")" 
                                                    + "__________________" +
                "(" + this.endSegment().getXCoordinate()   + ", " + this.endSegment().getYCoordinate()   + ")";
    }

    /* Use - ends */
}

Dummy

import math.point.*;
import math.segment.*;

/*
 * Driver code
 */
public class Dummy {

    public static void main(String[] args) {
        Point p1 = new Point(1, 2);
        Point p2 = new Point(3, 4);
        Segment line = new Segment(p1, p2);
        Point midPoint = line.midPointSegment();
        System.out.println(line);
        System.out.println("mid point is: " + midPoint);
    }
}

In the above code, Constructor and selectors constitute ADT.

In the above two implementations:

1. There is an abstract data type that supports an invariant1:

   If we construct point p from x-coordinate a and y-coordinate b, then p.xCoordinate(), p.yCoordinate() must equal a, b

2. There is an abstract data type that supports an invariant2:

   If we construct a line segment l from point p1 and point p2, then l.startSegment()______l.endSegment() must equal p1______p2

In the above implementation:

1. Parts of the program that use line segments to perform computation use midPointSegment, hashCode, equals, toString.

2. Parts of the program that implement midPointSegment, hashCode, equals, toString in impl-2 use constructor and selectors of it's own class and user api of class Point.

3. Parts of the program that create line segments use midPointSegment.

4. Parts of the program that implement constructor for line segment use two instances of class Point.

5. Parts of the program that implement selectors for line segments use two instances of class Point.

In the above code, class Segment and class Point is a "type abstraction" mechanism that builds Data abstraction.

Is my understanding correct on designing data abstraction and ADT for line segments?

Answer 1

Point

this.tuple[] doesn't really do much work. x and y are stored there, then pulled back out and never used again.

• Why not just store these as straight up fields?
• Or alternatively make self.tuple an ArrayList and simply use tuple.hashCode() for a point's hash? (ArrayList inherits hashCode from List.)

Given the nature of floating point numbers and their arithmatic, it might be a good idea to have a method that compares to points and determines if they are close enough to be considered equal. The tolerance for "equality" could be passed as a parameter or hard coded depending on the application.

Segments

Geometrically, "start" and "end" are ambiguous: the line segment [(0,0), (0,1)] the same as [(0,1), (0,0)].

This suggests standardizing the order of points based on their geometric properties (and therefore a comparison method in the Point class). For example:

 if x1 < x2 then point(x1, y1) < point(x2, y2)
 if x1 = x2 and y1 < y2 then point(x1, y1) < point(x2, y2)
 Invariant:
    for lineSegment(p1, p2)
        p1 < p2

Ordering points makes ordering line segments easier:

   if p0 < p2 then lineSegment(p0, p1) < lineSegment(p2, p3)
   if p0 = p2 and p1 < p3 then lineSegment(p0, p1) < lineSegment(p2, p3)

Having ordered line segments makes some geometric operations (eg. Bentley-Ottmann) involving line segments substantially easier as well.

Answer 2

• About the Point class:

  1. I do not see any reason to store coordinates in an array. This way is much clear, in my opinion:

     public class Point {
     
         private final float x;
         private final float y;
     
         ...
     }
     

  2. Having two pairs of getters(xCoordinate and getXCoordinate and the same for y) which do exactly the same thing looks strange. I would get rid of the private ones. Moreover, I'd recommend accessing x and y directly inside this class's methods. It doesn't break encapsulation(the clients can still access them only using the public API) and it reduces the amount of code repetition. One may argue that it reduces flexibility, but in this case I do not see any other reasonable ways to represent a point in a 2-D space.

  3. The equals implementation is broken. If obj is null or it is not an instance of the Point class, your code throws an exception. But it should just return false. Here is my version:

     @Override
     public boolean equals(Object o) {
         if (this == o) {
             return true;
         }
         if (!(o instanceof Point)) {
             return false;
         }
         Point p = (Point) o;
         return x == p.x && y == p.y;
     }
     

     (there is another subtle issue here: comparing floats with == operator may do not we want it do because of rounding errors(if x and y are results of some computations), so we may want to compare them with some tolerance).

  4. The quality of the comments is pretty low. Most of the comments are useless, while there are no detailed comments for public methods. That's, I'd recommend removing comments like //selector and similar but add a detailed description of each public method and the class itself. It should be clear how to use the public API of your class without reading its source code(as of now, it is not possible to understand what toString returns without looking at it, for instance).

• About the Segment class.

  1. I'd question the necessity of having private getters. It seems to me that if a Segment is defined as a pair of points, its representation is unlikely to change in the future.

  2. Immutability is good, you can make it more explicit by making the startSegment and endSegment final.

  3. Again, eqauls is broken.

  4. And again, I'd recommend writing better comments for public methods.

• The Dummy class:

  If it is a demo, it is fine. But if it is used to test your code, I'd strongly recommend to start testing your code in a systematic manner using unit tests.

• About the ADT: it is not constructors and selectors that constitute the ADT. The entire class represents an abstract data type.