Create your repository: https://classroom.github.com/a/W1JDwUv9

  • Then clone the repository into your CodeAnywhere container using git clone YOUR_URL
    • (Click the green “Clone or Download” button to find your repository’s URL).
  • For this assignment you do NOT need to submit your source code files, just your README file.
  • Be sure to fill in your name in your readme file or you may lose points!

Due: Thursday 10/18 at 11:59PM.

Updates:

  • 10/13: Clarified requirements for 1.5

Objectives

  • To learn how Java uses objects to encapsulate data and methods
  • To understand how Java objects are stored in memory
  • To appreciate the differences between C and Java

Java Basics

Sick of “Hello World” yet?

public class Hello {

  public static void main (String[] argv)
  {
    String s = "Hello World!";
    System.out.println(s);
  }
}
  • Must be put in a file called “Hello.java”
    • Unlike C, file name is important and must match class name
  • Program start point: public static void main(...)

Compiling and Running Java

In Java, javac is used as the compiler. There are a few notable differences from C:

  • Standardized names:
    • The input code file must be named based on whatever public class is defined in it. A java code file can only define one public class (but it can have several non-public ones)
    • The output file always becomes <ClassName>.class
  • Each class gets its own compiled file (not just one executable like a.out)
  • A .class file is java bytecode—must be interpreted by the JVM
    • It is not platform specific assembly instructions/byte code like in C

To run a program we use the java command, followed by the name of the class we want to run.

cabox@codeanywhere$ ls
Hello.java
cabox@codeanywhere$ javac Hello.java
cabox@codeanywhere$ ls
Hello.class  Hello.java
cabox@codeanywhere$ java Hello
Hello World!

Compiling and Running in Repl.it

For this module you can do your java development on the Repl.it site instead of CodeAnywhere.

Here is a basic Java program editor that you can extend for each exercise in this module

A few notes:

  • Repl.it has a restriction on how files (and thus classes) are named. The site requires that your primary code file be named Main.java, which in turn means that your public class in that file must be named Main
  • Remember that Repl.it will lose your work if you leave the page, so you will need to copy your code into your GitHub readme to save it.

Data Types

We can define and work with variables in the same way as in C.

Type Domain
byte 8-bit integers: -128 to 127
short 16-bit integers: -32768 to 32767
int 32-bit integers: -2147483648 to 2147483647
long 64-bit integers: -9223372036854775808 to 9223372036854775807
float 32-bit floating point numbers: ± 1.4x10-45 to ± 3.4028235x10^38
double 64-bit floating point numbers: ± 4.39x10-322 to ± 1.7976931348623157x10308
boolean true or false
char 16-bit characters encoded using Unicode
  • Java has the same basic data types as C
    • short, int, long, float, double, char
    • No unsigned types
  • Plus two more
    • byte (8 byte number) and boolean (T or F)
  • All data types (except Boolean) have a precisely defined size on all platforms
    • Different from C where size depends on architecture: 16 vs 32 vs 64bit ints
  • All elements in an array are initialized to zero, false, or null. The compiler will produce an error for any other uninitialized variables.
  • Note that Java has a String type, but this is actually a class rather than a primitive data type as we will see later. The capital “S” in its name is a clue to that!
    • Java Strings are easier to use than C! You can easily do things like combine two strings together with the + operator.

Arrays can be created using [] notation. Unlike in C, an array must be instantiated using the new keyword, like:
int a[] = new int[size];.

  • Arrays can be dynamically sized (i.e., size does not need to be a constant like in C). This should give you a hint about where they will be located in memory.

Note, at this point we will assume that you have basic Java knowledge, such as working with variables, for/while loops, etc.

If you need a refresher, check Prof. Simha’s 1111 and 1112 modules.

Classes and Objects

In Java:

  • A class determines the type of an object
  • All objects have a class
  • Primitive data types (int, float, etc) and functions are not objects

Let’s use an example to think about why we want to use classes.

Consider the representation of points in the XY plane:

We could represent these points with a series of variables:

double x1 = 2;
double y1 = 3;
double x2 = 5;
double y2 = 3;
double x3 = 5;
double y3 = 7;

double d1 = Math.sqrt(x3*x3 + y3*y3);
System.out.println("d1 = " + d1);

but this is pretty awkward – whenever we add new points to our graph we would need to define new variables that would be added to the stack.

Alternatively we could store everything in a pair of arrays, one for x values and one for the Y values. Since arrays in Java can be dynamically sized, they must not be based on the stack. Instead, arrays are always stored on the Heap:

  • Note that the arrary variables x and y are like pointers in C, referring to memory allocated on the heap with the new command
  • d0 is a local int on the stack which could be used to calculate distances for the different points

This approach would let us grow our number of XY points, but it is still a pretty messy solution, and it wouldn’t help if we decide to later add more data such as a Z coordinate to each point.

Exercise 1.1: Write a java program that stores the XY points into arrays that will result in the same memory layout as shown above. Write a for loop that calculates the distance from the origin to each point. Paste your program into a code block in your README file AND paste its output.

Class Data

For a better solution, we want to encapsulate the data that forms a “point” into a class and then instantiate objects to represent the specific points in our program. This keeps the data together in one place so we can easily work with it.


class XYPoint {
  double x;
  double y;
}

public class Main {
  public static void main (String[] argv) {
    // Make a new instance of an XYPoint object
    XYPoint p = new XYPoint();
    // Assign values to its variables:
    p.x = 2;
    p.y = 3;
    // Access its variables:
    double d = Math.sqrt(p.x*p.x + p.y*p.y);
    System.out.println("Distance = " + d);
  }
}

Here:

  • We are defining two classes: XYPoint and Main. What must be the filename to store these classes?
  • Importantly, the XYPoint class example above does not use the static keyword, whereas Main contains only a single method and that method is marked static
    • We call XYPoint a dynamic class… and soon we will see why.
    • The main method must appear in a public class.
    • Whatever class is marked as public must match the overall filename, since this is the class that will be visible to the outside.
    • This means any given .java file can have several class declarations, but only one public class and only one public static void main method.

Let’s see how the two classes interact:

  • The entry point to any Java program will always be a static void main method.
  • A dynamic class is not usable until an instance is created with the new operator: 
    XYPoint p = new XYPoint();
  • Once it is declared, we create a chunk of memory on the heap for it
  • This is analogous to what we’ve done with arrays in Java and with using malloc in C

Then, once this variable p points to the space in memory to hold the object instance, we can access parts of the object using the dot operator:

p.x = 2;

Think of it this way:

  • The variable p points to a chunk of memory that is constructed in the template of the object XYPoint (just like a struct in C)
  • The object XYPoint has two double’s called x and y.
  • Think of x and y as components of the object pointed to by p.
  • To access these components, we use p.x and p.y
  • Recall that in C we had to distinguish between structs that were accessed with as a local variable (meaning they were on the stack) versus a pointer (which could have been to the stack or heap). Why doesn’t Java require two operators for accessing object fields like in C?

In memory, our current program looks like:

From this we see that Java has pointers! It isn’t just something to torture you in C!

  • BUT, the main difficulties in using pointers in C arise from the complete freedom it gives you in how you use them (casting them, doing pointer arithmetic, treating arrays as pointers, the differences between pointer and non-pointer structs, etc).
  • In Java, all objects are stored on the heap and accessed via pointers, but because the programming model is restricted, it is hard to make the same mistakes as you had in C. You’ll still get plenty of Null pointer exceptions though!
  • In Java we generally call these references instead of pointers.
  • The chunk of memory on the heap is a bit larger than the data in the class because, underneath the hood, there is bookkeeping info for a class, and other items not necessarily visible in the code.

Class Methods

Our solution thus far can be further improved by making the XYPoint class contain not only data, but also the methods that operate on that data. This is something we couldn’t have done with structs in C.

Suppose we want to add a function to compute the distance from the origin to a point. Where should we put this function?

  • We could put it into Main and have it take an XYPoint as an argument
  • We could put it inside XYPoint and have it operate on the x and y fields of the object itself

In this case, it is fairly clear that the second solution is better – we generally want to keep functions close to the data that they operate on, and here it makes sense that the XYPoint object itself should be responsible for calculating its own distance. What are some reasons why we want to keep the method close to the data?

Exercise 1.2: Add a distance function to the XYPoint class that returns a double with the geometric distance from the origin to the point. Paste your code and output in your README.

Next let’s add a function to calculate the distance between two XYPoints. Where should we put this?

  • We could put it in Main since it is aware of all the different points.
  • We could put it in XYPoint since it could compare itself against a point passed as an argument.

Once again, the second solution is better since we think of distance as being a characteristic of the XYPoint itself, rather than being something controlled by the overall program.

  • Nevertheless, there may be cases where placing it in Main is better or it may be required if you don’t have access to edit the XYPoint source code.

Note: If we place a function in the Main class, it will need to be a static method because we never instantiate that class.

  • A static method like main can only call functions in a dynamic class that has been instantiated into an object, or other static methods.
  • The static keyword is similar in C and in Java: having a static variable in a C function meant that there was only a single version of that variable – unlike a normal local variable, we would not (dynamically) create a new version of that variable on the stack every time the function was called.
  • Static variables in Java act the same way – we will only have one version of them, rather than one version per object that gets created.

Exercise 1.3: Add distanceTo functions to both Main and XYPoint – you will need different arguments for each one. Instantiate two XYPoint variables in your main function and call both versions of your distance functions to compute the distance between them. Paste your code and output into your README.

Exercise 1.4: Consider a square with the lower left corner at the origin, and with length s. A point is considered within the square if it’s inside or on the one of the edges, as in this diagram:

Write a method inside the XYPoint class so that the following code in main() works:

public static void main (String[] argv) {
  XYPoint p = new XYPoint ();
  p.x = 2;    p.y = 3;
  boolean yes = p.isWithin (5);
  System.out.println (yes); // should be true

  XYPoint q = new XYPoint ();
  q.x = 5;    q.y = 7;
  yes = q.isWithin (5);
  System.out.println (yes); // should be false

  XYPoint z = new XYPoint ();
  z.x = 8;    z.y = 9;
  yes = z.isWithin (5);
  System.out.println (yes); // should be false
}

The method isWithin() takes in the length of the square’s side.

Arrays of Objects

One of the conveniences of using an array is the ability to write code that marches through the array performing the same computation. For example, we might want to walk through an array of our point objects and print their distance values.

Let’s now see how this can work with a group of objects in an array:

class XYPoint {

  double x;
  double y;

  public void printDistance () {
    double d = Math.sqrt (x*x + y*y);
    System.out.println (d);
  }

}

public class Main {

  public static void main (String[] argv) {
    // Make an instance of the object with the new operator:
    XYPoint[] p = new XYPoint [3];
    p[0] = new XYPoint ();            // First point.
    p[0].x = 2;   p[0].y = 3;
    p[1] = new XYPoint ();            // Second one.
    p[1].x = 5;   p[1].y = 7;
    p[2] = new XYPoint ();            // Third.
    p[2].x = 5;   p[2].y = 3;

    for (int i=0;  < p.length; i++) {
        p[i].printDistance ();
    }
  }
}

There are a few key points we need to undestand this. Let’s draw some memory pictures to illustrate.

First, the memory picture just after executing

	XYPoint[] p = new XYPoint [3];

  • The statement declares an array variable p.
  • Then, the new operator assigns a size-3 array of variables that will eventually point to chunks of XYPoint objects. At this point all of the entries in the array itself are null references.

Next, consider the execution up to:

  XYPoint[] p = new XYPoint [3];
  p[0] = new XYPoint ();   
  p[0].x = 2;   p[0].y = 3;
  • The second line makes the first location of the array point to an XYPoint object.
  • The third line assigns values using the “dot” operator.
  • Thus, in memory it looks like:

Finally, after the next two objects have been created

  XYPoint[] p = new XYPoint [3];
  p[0] = new XYPoint ();   
  p[0].x = 2;   p[0].y = 3;
  p[1] = new XYPoint ();            // Second one.
  p[1].x = 5;   p[1].y = 7;
  p[2] = new XYPoint ();            // Third.
  p[2].x = 5;   p[2].y = 3;

we will have:

A common error in Java programming is to only use new to allocate the array itself and to forget to also use new for each object in the array! What type of error will you get if you make this mistake?

Side Note: Java provides the Math.random() function which returns a random double value between 0 and 1 (specifically, the range includes 0 but will be strictly less than 1). You can scale this up to get larger random numbers:

int d6 = Math.Random() * 6; // random int between 0 and 5

Exercise 1.5: Create an array of 10 XYPoints in your main function with random X,Y coordinates between 0 and 20. Add a distanceToAllPoints function that calculates the distance between each pair of points in the array and prints it to the console. You do not need to include the output of your program in your README file. Instead, explain why you created the function in the place that you did and why you chose those arguments.

Objects in Objects

One intuitive way to think about the variable x in XYPoint is that the variable x is inside the object and is accessed via the “dot” operator: p.x = 2;

  • One can draw an analogy thinking of the object as a box with compartments, one each for instance variable defined within it.

It is possible to put an object (which itself has components) inside another, as in this example:

Suppose we wish to represent a line segment between two points.

  • A line segment is therefore defined by its end points.
  • We’ll call one of them start and the other end.
class XYPoint {
  double x;
  double y;
}

class XYLine {

  XYPoint start;         // An object variable.
  XYPoint end;           // Another one.

  public void printSlope () {
    double s = (end.y - start.y) / (end.x - start.x);
    System.out.println ("Slope = " + s);
  }

}

public class Main {

  public static void main (String[] argv) {
    XYPoint p = new XYPoint ();
    p.x = 2;   p.y = 3;

    XYPoint q = new XYPoint ();
    q.x = 5;   q.y = 7;

    XYLine L = new XYLine ();
    L.start = p;      // Point to the same object as p, not a full copy!
    L.end = q;
    L.printSlope ();
  }

}

Let’s understand this from a memory point of view:

  • After the first two points are created in main() we have:

  • Then, right after the XYLine object is created with 
     XYLine L = new XYLine ();

  • Next, consider what happens after the assignments 
     L.start = p;       // Point to the same object as p, not a full copy!
 L.end = q;

  • Here we have entered some addresses to emphasize the copying of (pointer or address) values from variables p and q into L.start and L.end
  • Now let’s draw the same thing without addresses but with our conceptual arrows:

Class Constructors

Often we want to immediately fill in some instance variables when we create a new object. A class constructor allows us to easily do that:

class XYPoint {
  double x;
  double y;
  public XYPoint(double x, double y) {
    this.x = x;   // differentiate between parameter x and instance variable
    this.y = y;
  }
  public XYPoint() {
    x = Math.random() * 10;
    y = Math.random() * 10;
  }
}

public class Main {
  public static void main (String[] argv) {
    // Make a new instance of an XYPoint object
    XYPoint p = new XYPoint();
    XYPoint p2 = new XYPoint(5, 5);
    // Access its variables:
    double d = Math.sqrt(p.x*p.x + p.y*p.y);
    System.out.println(d);
    d = Math.sqrt(p2.x*p2.x + p2.y*p2.y);
    System.out.println(d);
  }
}

Note:

  • A class can have several different constructors with different parameters.
  • Here we are using the this keyword to distinguish between the x variable that arrives as a parameter to the constructor and the instance variable x which is part of “this” new object being created.

What are the benefits of using a constructor? What could go wrong if we didn’t have one?

Exercise 1.6: Create at least two different constructors for the XYPoint and XYLine classes. Add a function that calculates the length of a line. Create an array with 10 random lines and print the length of each one.

From C to Java

Consider this C code for a manually defined Linked List from C Module 4:

struct LNode {
  int data;
  LNode* next;
};
struct LList {
  LNode* head;
};

int main() {
 struct LList* list;
 struct LNode * a, * b, * c;
 list = NULL;
 a = NULL; b = NULL; c = NULL;
 list = malloc(sizeof(struct LList));
 a = malloc(sizeof(struct LNode));
 b = malloc(sizeof(struct LNode));
 c = malloc(sizeof(struct LNode));
 list->head = a;
 a->data = 45;
 a->next = b;
 b->data = 89;
 b->next = c;
 c->data = 52;
 c->next = NULL;
}

How do we convert this C code into Java code?

  • no structs!
    • Define a class for each data type
  • no malloc!
    • instantiate object with new
  • define constructor to initialize objects
  • don’t need to initialize references to null
  • don’t need to differentiate between local structs and struct pointers
    • in Java, everything is a pointer!
    • use . instead of ->

Exercise 1.7: Convert the above C linked list code into Java. Make the program print out the data for each node.

Home - Next
© 2003, Rahul Simha (revised 2017). Further revised by Tim Wood 2018.