Skip to main content

Introduction

This resource is presented as list of topics, functions, and patterns that we’ve encountered so far in CIS 110. It is reference material, and not a definitive textbook.

Please note that this resource is not…

Here are a handful of good ways to use this document:

You might notice that some text looks like this. When something is written in this way, it’s information that you might be interested to learn but that you’re not required to know.

Note: We leave the table of contents in full, but will not fill in the relevant information until it has been taught in lecture.

Table of Contents:

Incomplete List of Functions & Operations We Have Used

Basics of a Java Program

Writing & Running Code

The main Method & args

This is the entry point to a program. That is, when you run java Apples fuji macintosh pink-lady, you’re doing the following:

Code Blocks

Java programs are essentially sequences of nested code blocks. Code blocks are groups of lines of code that live between an open brace (this character: { ) and its corresponding close brace (this character: }). Note that a block of code does not necessarily end at the first } character following a { character in the case of nested code.
An illustration follows, with each comment specifying which code block that line would belong to. Note the fact that code blocks can nest, and how this is represented here with the decimal notation (block 1.2.1 is the first block inside the second block inside the first block, for example).

public class CodeBlockExample {
  // BLOCK 1
  public static void main(String[] args) {
    // BLOCK 1.1
    for (...) {
      // BLOCK 1.1.1
    }
    // BLOCK 1.1
    while (...) {
      // BLOCK 1.1.2
    }
    // BLOCK 1.1
  }
  // BLOCK 1

  public static int tester() {
    // BLOCK 1.2
    for (...) {
      // BLOCK 1.2.1
    }
    return 0; // BLOCK 1.2
    // BLOCK 1.2
  }
}

Drawing

A complete reference to drawing with PennDraw is already available on the course site. Some key points:

Variables

What A Variable Is

Variables are just names for individual pieces of data in Java. You provide the name and type of a variable to Java, and Java will keep track of that name for you. You can then assign (and reassign) data to the variable for later use. Variables in Java are mutable, meaning that you are able to change the values that the variables contain. This is the big reason why they are so useful!

Declaring a Variable

The syntax for declaring a variable is a two part statement: type name, where type is the data type of the variable and name is the name of the variable. When a variable is declared without having a value assigned to it, the variable will have a default value. The default value depends on the data type that variable, but the result is that whenever you reference the variable after it is declared, it will have some (potentially null value). Once a variable has been declared, it is not possible to declare a variable of the same name in the same scope.
Some examples:

int x;
double y;
String lastName;
char middleInitial;
boolean isFinished;

Assigning a Value to a Variable

This is done with the use of the assignment operator, =. The syntax for assigning a value to a variable is: providing the name of the variable, followed by the assignment operator, followed by an expression that will be the new value of the variable (examples to follow). It is possible to assign a value to a variable at the moment it is declared, although this is not required. This means that it is possible to assign to a variable when or after it is declared, but it is not possible to assign a value to a name of a variable that has never been declared. Variables can also be assigned in terms of themselves, and this is a powerful asset in the case of trying to count or store intermediate results of computation.
Some examples:

int age = 53;
double y;
y = age * 2.5;
String lastName;
lastName = "Fouh";
middleInitial = (char) (middleInitial + 2);
boolean isFinished;
isFinished = !isFinished;

Variable Scopes

The scope of a variable is the set of lines in the Java program where Java will recognize the name of that variable. A variable is generally in scope for the entire code block in which it is defined following its definition, and it is also in scope for all code blocks nested inside after its definition.

public static void main(String[] args) {
  // x is not in scope
  System.out.println("not yet");
  boolean x = true; // x begins scope here
  while (x) {
    // this is a nested code block within the previous one
    x = false; // x is in scope here
    System.out.println("Just once.");
  }
  // we're back in the original block; x is in scope
  System.out.println(x);
} // x's original code block ends.
// x is not in scope here

public static int tester() {
  // x is not in scope here
}

Data Types

What a Data Type Is

In Java, every expression that stores or calculates to a value has a data type. A data type is a formal classification for how Java represents and handles any piece of information. This is a broad and almost philosophical definition. A more practical one looks like this: a data type in Java is a definition of the range that a particular value can belong to, and what operations are valid to perform on that value. Operators and functions in Java specify what data types they can work with. If you are not careful with tracking the data types of the inputs to different functions and operators, you can end up with code that won’t compile.

Primitive Data Types in Java

There are a number of primitive Data Types available in Java. To say that a data type is primitive means that the type is predefined by Java to be included in the language. In this class we focus on studying four primitive data types: boolean, char, int, and double. In addition, we are also heavily interested in the String Data Type which, while not technically a primitive one, can be used in many similar ways to the primitive data types.

Table of Primitives

Data Type Range Default Usage Key Operations (not exhaustive)
int [-32,768, 32,767] 0 integers +,-,*,/,%,>,<,<=,=>,==,!=
double a very negative number up to a very positive number 0.0 numbers, including fractional parts +,-,*,/,%,>,<,<=,=>,==,!=
boolean {true, false} false truth values ==, !=, !, && , ||
char [0, 65535] 0, or '\u0000' single characters of text (letters, numbers, punctuation, spaces) represented as small integers similar to int

Strings

Strings are effectively sequences of chars. The default value of a String is null (more on this later). Strings are how we represent text and language in Java. The operations defined on Strings are numerous, but an important basic one is the + operator, which represents concatenation when applied to one or more Strings.

Strings are immutable in Java, meaning that when you perform some operation on a String, an entirely new String will be returned.

String first = "Maya";
String second = first.toUpperCase(); // Capitalize all letters in string

System.out.println("first is still " + first);
System.out.println("second is " + second);

Running the above code demonstrates that String first was unchanged after the call to toUpperCase():

> first is still Maya
> second is MAYA

Some Important Operators & Tools

Many of the operators available for each data type will prove useful at some point. This section represents a brief overview of some of these, as well as other function tools. For a more complete overview of the behaviors of operations among different types, make sure to look at the exercises at the end of this presentation.

Relational Operators

All of >,<,<=,=>,==,!= are operators that accept two values of primitive data types and return a boolean result. These comparison tools are often essential for defining the control flow of your programs in if statements and in loops.

The multifaceted +

Mod (%)

Another name for mod would be “remainder after division”. Major uses for this operation include constraining ints to wrap around within a certain range, testing for whether a number is even or odd, or checking to see if a number is a multiple of another. Remember that % with one negative argument leads to a negative result.

Casting

Casting is the process of interpreting a value of some data type as a different data type. In this course, when we refer to casting we are referring to the manual process of converting from a type with a wider range of values into a type with a smaller range of values.

int justTheInt = (int) 51.564;
char asLetter = (char) justTheInt;

Although we usually refer to it as “type promotion” in CIS 110, some sources will refer to conversions going in the other direction as casting, too. This is the automatic process of converting a char into an int or an int into a double that Java will do for you. This works automatically when the original type is “smaller” than the new, “larger” type.

Parsing

Parsing is the process of interpreting the value of a String as a representation of a value in some other data type. The primary ways that we use parsing with respect to data types are with the following two examples:

int fromString42 = Integer.parseInt("42");
double fromStringThreePointOneFour = Double.parseDouble("3.14159265");

Math

The basic arithmetic operators represent only a small fraction of the math that you can do in Java. Using the Math library, operations like abs, min, max, trigonometric functions, exponentiation, round, and random are available. There’s a good listing of these at the end of this presentation.

Conditionals

Conditionals are the simplest means we have to influence control flow in our programs. By default, Java programs execute sequentially, with each line being run in the order it’s written. When you add conditionals to your program, you decide among several options for which lines of code to be run next based on the state of some specified values.

When to use a Conditional

if, else if, and else

Control flow can be influenced using if, else if, and else statements.

if (x > y || a == c) {
  System.out.println("Hello");
} else if (x == y) {
  System.out.println("Goodbye");
} else if (x < y) {
  System.out.println("So long");
} else {
  System.out.println("Farewell");
}

// These next if statements are unrelated to the first chain and to each other.
// Either of them will be run when their conditions are true, independent of prior conditionals.
if (u && i) {
  return 10;
}
if (me && u) {
  return 20;
}

Switch Statements

Switch statements are conditionals designed for the purpose of checking the value of some variable or expression against several enumerated outcomes. We do not require you to use a switch statement in this class, although you are certainly welcome to. An example that demonstrates the complete syntax of a switch statement is presented here.

switch (name) {
  case "Harry": case "Eric":
    title = "Professor";
    break;
  case "Jules": case "Michael": case "Gian": case "Ben":
    title = "Head TA";
    break;
  default:
    System.out.println("Name not matched, default case used");
    title = "TA";
    break;
}

This example checks to see if name is the name of a professor, a head TA, or a TA.

Loops

Loops are the way that we implement iteration in Java. They are the tools by which we are able to write programs that perform one task many, many times. It is from this ability to write in repetition (with controlled variation) that the power of computation emerges.

Rules of Iteration in Java

Any loop that we use in Java is controlled by three components:

  1. An initialization of a loop control variable (or perhaps several variables).
  2. A termination condition defined over the control variable(s). When the loop control variable reaches a particular value or state, the termination condition will evaluate to false and the iteration of the loop will stop.
  3. A modification of the loop control variable(s). By modifying the control variable(s), we can eventually reach the state outlined in the termination condition, indicating that the loop should cease repeating.

The While Loop

As outlined in the previous section, a while loop must include an initialization component, a termination condition, and a modification step.

int i = 40; // initialization (i is the loop control variable)
while (i > 0) { // termination condition
  System.out.println(i);
  i--; // modification step
}

boolean hasPressed = false; // initialization (hasPressed is the loop control variable)
while (!hasPressed) { // termination condition
  PennDraw.filledRectangle(...);
  if (PennDraw.mousePressed()) {
    hasPressed = true; // modification
  }
}

Some takeaways from these two examples:

The termination condition is checked before every iteration of the loop, including before the (potential) first iteration.

The For Loop

A for loop must again include an initialization step, a termination condition, and a modification. Unlike a while loop, though, a for loop has space for these steps built into its very syntax.

//  |INITIALIZATION   | TERMINATION COND. | MODIFICATION|
for (String line = "."; line.length() < 10; line += '.') {
  System.out.println(line);
}

//  |INIT.         | TERM. |  MODIF.|
for (double k = 100; k == 1; k /= 10) {
  System.out.println(k);
}

//  |INIT.    | TERM.          | MOD|
for (int i = 0; i < args.length; i++) {
  System.out.println(args[i]);
}

A variable initialized during the intialization step is in scope only in the body of the loop. The termination condition is checked before every iteration of the loop, including before the (potential) first iteration. The modification step is performed after each iteration.

Your Loop of Choice

It is possible to convert a loop of one variety into an equivalent loop of the other variety. This is always true, although it usually is somewhat more natural to use one type in certain circumstances.

It’s often more natural to write a while loop when:

It’s often more natural to write a for loop when:

Perhaps the most salient point here: if your problem can be phrased as “examine every x in y” or “for every element of this array/this string, do something”, this is a good sign that a for loop would fit nicely. These are just general guidelines, and you should keep in mind that you can always make either loop work.

Break and Continue

break is a statement that, when executed in the body of a loop, causes that loop to immediately stop executing. The current iteration is halted, and no further iterations are executed. The control of the program resumes immediately after the body of the loop.

continue is a statement that, when executed in the body of a loop, causes that iteration of the loop to immediately cease. In the case of the for loop, this causes the modification step to be applied. As long as the termination condition has not been met, the next iteration of the loop will commence.

break exits a loop entirely, continue skips to the next iteration.

Arrays

What is an Array?

In Java, an array is an fixed-length, indexed sequence of values that are all of the same type. Each value in this sequence can be modified and overwritten. An array is a data type of its own, and the type of an array is different from the type of the elements it contains. In particular, int x = 4; defines a variable of type int, whereas int[] xs = {3, 4, 5}; defines a variable of type int[] (note the difference in brackets).

int[] ages = new int[320]; // an array of 320 ints
ages = new int[60]; // a new array of 60 ints. It is valid to store a new array in ages.

double[] xPositions = new double[10];

String[] suits = {"spades", "hearts", "diamonds", "clubs"};

Arrays Are Fixed-Length

When you create an array, you must also specify its length. This can be done with implicit initialization (e.g. new char[4]) or explicit (e.g. {4, 3, 2, 1}). In both of these example cases, the arrays have a length of 4. It is not possible to add another element to this array without first creating a new, larger array.

Arrays Are Indexed

Arrays in Java are 0-indexed, meaning that we refer to the first element of an array as being at index 0. Using .length on the end of the array, we have an expression for the length of an array. If we have some array arr, and we say that n is equal to arr.length, then each integer between 0 and n (but not including n) is a valid index for that array.

The syntax for indexing into arrays in Java is to append [index] to the end of a variable containing an array. Taking our example from above with suits:

String[] suits = {"spades", "hearts", "diamonds", "clubs"};

Then the following table represents the indices of suits:

Index Value
suits[0] "spades"
suits[1] "hearts"
suits[2] "diamonds"
suits[3] "clubs"
suits[4], suits[5], … Leads to ArrayIndexOutOfBoundsException
suits[-1], suits[-2], … Leads to ArrayIndexOutOfBoundsException

Arrays Contain Values Of One Type Only

When an array is initialized without explicit values, we use the syntax new type[length], where type represents some valid data type (String, boolean, etc). The array that is created thus has the data type type[], which reads in English as “an array of types” or a “type array”. This new array can only contain values of data type type from now on.
This also means that when initializing arrays with explicit values, those explicit values must all be of the same type.
When declaring a variable that will contain an array, you must declare the variable of the correct type. Refer the previous examples under “What is an Array?”.

Manipulating Arrays

Presented here are a few examples of how to manipulate arrays. These are taken directly from the website of the course’s textbook. All credit to Sedgewick and Wayne. Refer to the booksite’s section on arrays for a fuller listing of patterns related to using arrays.

Initializing entries of an array to random values

int n = 5;
double[] a = new double[n];
for (int i = 0; i < n; i++) {
    a[i] = Math.random();
}

Printing the values of an array

Assumes the existence of some array a, like the one from the first example.

System.out.println("a[]");
System.out.println("-------------------");
for (int i = 0; i < n; i++) {
    System.out.println(a[i]);
}
System.out.println();
System.out.println("a = " + a);
System.out.println();

Finding the maximum value in an array

Assumes the existence of some array a, like the one from the first example.

double max = Double.NEGATIVE_INFINITY;
for (int i = 0; i < n; i++) {
    if (a[i] > max) max = a[i];
}
System.out.println("max = " + max);

Finding the sum & mean of an array of doubles

Assumes the existence of some array a, like the one from the first example.

double sum = 0.0;
for (int i = 0; i < n; i++) {
    sum += a[i];
}
System.out.println("average = " + sum / n);

Functions

Functions (or methods) are the basic building blocks of Java programs. main is a function, Math.abs is a function, PennDraw.filledRectangle is a function, and you can write your own functions. In CIS 110, we use the terms “function” and “method” to refer to the same thing. Both the term “function” and the term “method” have broader and diverging meanings outside of the scope of the course, but in CIS 110 we can use them interchangably.

In JavaScript, it’s not the case that every function is a method although the reverse is basically true. Going by the definitions outlined in, say, Cornell’s CS1130 Course, Java has it so that not every method is a function even though every function is indeed a method. This is vague notation.

Functions in Java are similar to functions in mathematics. Fundamentally, functions are tools that take some inputs, do some work based on the inputs, and produce some output.

Anatomy of a Function

A function has…

  1. a header. A header consists of several pieces:
    1. One or more optional modifiers, like public and static. You should continue to include these words at the beginning of your functions, even though we haven’t covered their meanings yet.
    2. A return type. This specifies the data type that the function is guaranteed to output.
      1. If a function has a return type of int, for example, the function is guaranteed to return an int.
      2. It is possible for a function to have a return type of void, which is a guarantee that the function will not return any data at all.
    3. A name. This specifies how you can refer to this function and use it later.
    4. A list of arguments type & name pairs
      1. Each argument must have its type specified first
      2. The name of the argument in the header puts variables with these names in scope in the body of the function.
  2. a body. The body of a function is a just another block of code where execution starts at the top.
  3. one or more return statements.
    1. return is a keyword in Java that indicates that the function should stop executing.
    2. return is coupled with a value. For example, a full return statement might look like return true;, return x + 4;, or return str.toUpperCase(). In each case, the type of the value being returned must match the return type of the function.
    3. A function with a non-void return type must end with a return. Reaching the end of a function without hitting return will result in an error.
    4. The only exception to these rules are in the case of a function with return type void. In this case, return cannot be paired with a value, since void indicates that no data is returned. In functions with return type void, it is possible to use no return statements at all, and when Java reaches the end of the function body, Java will return implicitly.

To illustrate these rules, we examine a searching function:

/**
 * indexOfValue attempts to find value in an array of chars
 * called list. If we find value, return its index. If we
 * don't find value, return -1 to indicate that value is 
 * not in list.
 */
public static int indexOfValue(char value, char[] list) {
  for (int i = 0; i < list.length; i++) {
    if (list[i] == value) {
      return i;
    }
  }
  return -1
}

Functions and Control Flow

Java programs start executing at main when run from the command line, as we do in CIS 110. Control is passed between functions with function calls, which happen where we write the name of the function followed by a list of input argument values in parentheses.

Considering the example below, we have a function public static int addTwo(int x). We can call addTwo like so: addTwo(4). In this case, 4 is the value that will be bound to the variable x at the start of addTwo’s body.

The execution of the most recent function call must be completed before control is passed back to the point where that call was made. This results in a call stack.

public class Functions {
    public static void main(String[] args) {
        System.out.println("Starting main.");
        int six = addTwo(4);
        System.out.println("four plus two is " + six);
        int eight = addThree(5);
        System.out.println("five plus three is " + eight);
        System.out.println("Leaving main");
    }

    public static int addTwo(int x) {
        System.out.println("Starting addTwo with input " + x);
        System.out.println("Leaving addTwo");
        return x + 2;
    }

    public static int addThree(int x) {
        System.out.println("Starting addThree with input " + x);
        int temp = addTwo(x);
        System.out.println("Leaving addThree");
        return temp + 1;
    }
}

The output:

$ java Functions
Starting main.
Starting addTwo with input 4
Leaving addTwo
four plus two is 6
Starting addThree with input 5
Starting addTwo with input 5
Leaving addTwo
Leaving addThree
five plus three is 8
Leaving main

Observe how this output illustrates the call stack. main is called first. From main, we call addTwo, which returns 6 without calling another function. Then from main, we call addThree, which in turn calls addTwo. addThree’s call to addTwo is resolved before addThree returns the result back to main. Then, main finishes execution without a return statement, which is acceptable because main always has return type void.

Functions and Variable Scope

When a function is called and its body is executed, Java creates a new scope. Generally speaking, the only variables that will be in scope at the start of the function execution will be the input arguments to that function.

public class Scope {
  public static void main(String[] args) {
        int a = 50;
        int b = 100;
        int c = 200;
        System.out.println("before newScope, main's c = " + c);
        newScope(a, b);
        // the variable c declared in newScope is out of scope
        // back here in main.
        System.out.println("after newScope, main's c = " + c);
    }

    public static void newScope(int x, int y) {
        System.out.println("STARTING newScope");
        // x and y are in scope
        System.out.println("x = " + x);
        System.out.println("y = " + y);

        // a, b, and c are not in scope here.
        // we can declare a variable c here
        int c = 40;
        System.out.println("newScope's c = " + c);
        System.out.println("ENDING newScope");
    }
}

Output:

$ java Scope
before newScope, main's c = 200
STARTING newScope
x = 50
y = 100
newScope's c = 40
ENDING newScope
after newScope, main's c = 200

Recursion

Recursion is a strategy of programming that uses a solution that’s determined in terms of itself. The recursive answer to the question of how long a given String is might be “one character longer than the length of this String without its first character.” This might seem like an unhelpful answer, but if we combine it with the knowledge that an empty String has a length of 0, then we’re actually approaching a solution. How long is "Java"? Well, it’s one character longer than "ava", which itself is one character longer than "va", which itself is one character longer than "a", which itself is one character longer than "", which has a length of 0 characters. All together, that means that "Java" is 1 + 1 + 1 + 1 + 0, or 4 characters long.

Here’s a look at the above algorithm written in Java.

public static int myLength(String s) {
  if (s.equals("")) { //base case
    return 0;
  }
  return 1 + myLength(s.substring(1)); //recursive case
}

Essential Components of a Recursive Algorithm

Tracing Recursion

Any time a recursive call is made, that call must be fully evaluated before the rest of the function can evaluate. This holds true for the successive recursive calls too, leading to multiple calls awaiting execution on a “call stack” that Java manages for us.

You can explore the execution of a recursive fibonacci function here.

Unit Testing

Unit testing is an essential practice for efficient and correct programming. It is useful for helping to define expected behaviors and it allows a programmer to check for correctness in the work that they’ve done.

In order to write unit tests in Java, we make use of JUnit.

Essentials of a Test Case

A test case is a way of testing the behavior of a small unit of code, typically a function, when run with a particular input (or set of inputs). Thus, the essential components for defining any test at a high level are:

  1. Inputs. These are the pieces of data that you’d like to see how your code handles. If you’re unit testing a search function, your input would be some particular array of Strings and a target String.
  2. Expected Output. This defines the value that your unit of code should evaluate to or return after being run on your chosen inputs. If your inputs to search were String[] arr = {"Harry", "Jules", "Michael"} and String target = "Jules", then the expected output of search(arr, target) would be 1, which is the index at which "Jules" can be found in the input array. You determine the expected output for a test by manually examining the inputs and the desired behavior of the function; you do not actually run the unit of code to generate this value!
  3. Actual Output. This is the actual value that your unit of code returned after being run on your chosen inputs. The actual output is evaluated by running the unit of code you’re testing on the inputs that you chose. That is, int actual = search(array, target) in this case.
  4. Assertion Statement. The assertion statement is the part of the JUnit test case that checks to see if the expected output matches the actual output. There are actually very many assertion statements one can use, but we mostly focus on assertEquals. That is, the assertion statement for the searching example might then look like assertEquals(expected, actual). In fact, you should usually provide a String as well that explains the purpose of the test case. That is: assertEquals("searching for Jules in array {Harry, Jules, Michael}", expected, actual).

Anatomy of a JUnit Test File

import static org.junit.Assert.*;
import org.junit.*;

public class SearchingTest {
    @Test
    public void TestSearchJulesInArrayWithJulesOutputs1() {
        String target = "Jules";
        String[] array = {"Harry", "Jules", "Michael"};
        int expected = 1;
        int actual = Searching.search(array, target);
        assertEquals("searching for Jules in array {Harry, Jules, Michael}", expected, actual);
    }
}

Of note:

Passing and Failing Tests

If a test is shown to pass, that means the expected output matched the actual output. Note that this doesn’t necessarily mean that your code is absolutely correct! You could have written the test incorrectly, or you could have chosen an input that works while most other inputs would cause the test to fail.

If a test is shown to fail, that means the expected output did not match the actual output. This might mean that there’s a bug in the unit of code you’re testing, or it might mean that you made a mistake when writing your test.

Testing helps you sniff out when your code isn’t working properly, but without a careful eye and a broad set of tests, it’s possible to miss what you’re looking for. Test carefully, and test widely.

Object Oriented Programming

Object Oriented Programming is a paradigm that views programs as collections of entities called objects that are comprised of and interact with each other.

Contrast this with our previous notion of programming, which is called procedural programming. This just views programs as lines of code to be run, one after the other, with functions representing procedures that implement a specific task. Procedural programming is actually an effective way of thinking about drawing as we did it in the early parts of the semester: it’s not not necessary to view a program that sketches a scene as one made of many objects interacting with each other. Sometimes code is, after all, just a list of instructions.

Objects vs Classes

Objects in Java are representations of real-world entities. Objects have state and behavior, and these are defined by classes. We say that objects are individual instances of a class. Therefore, a class is a blueprint for how to create objects of that underlying type.

Here we have a class called Soda.

public class Soda {
  private String container;
  private String flavor;

  public Soda(String container, String flavor) {
    this.container = container;
    this.flavor = flavor;
  }

  // rest of class omitted for space
}

In another program, SodaFountain.java, we might have the following lines:

Soda sprite = new Soda("glass bottle", "lemon-lime");
Soda coke = new Soda("can", "hard to describe");

In this case, we say that sprite and coke are objects, and that Soda is the class from which they have been instantiated.

Writing Classes to Define Object State & Behavior

Now that we have the difference between a class and an object, it’s time to think about how classes are written. Classes are made up of fields, methods, and (optionally) constructors.

Fields

A class’ fields represent the data that an instance of the class can store. These are effectively variables that belong to instances (objects) of this class. To that end, we sometimes refer to them as instance variables. Fields belong at the top of a class by convention.

public class Tree {
  public int age;
  private String species;
  private double height;
  private double width;

  // rest of class omitted for space
}

In this class Tree, we have four fields. These are: age, species, height, and width. Observe that they have a type associated with them just like any other variable. Additionally, they have a privacy modifier (in this case, all but age are private). By convention, fields will normally be private, and this is explained further in the section on Encapsulation.

A field can be accessed inside of a class definition using its name alone, or with this as a way to specify that you’re referring to the field in the case that multiple variables in the same scope share the same name (this is called shadowing).

age = age + 34;
// if the RHS variable height shadows the field named 
// height, this example stores the value of the local
// variable height in the field called height.
this.height = height

Outside of the object’s class, only its public fields are directly accessible without the use of getter methods. Imagining we have some function generateTree that returns some Tree object, consider the following:

Tree t = generateTree();
System.out.println(t.age); // this compiles
System.out.println(t.width); // this does not

Methods

Methods are the functions of a class and they represent what the object can do and how it can change. These follow the rules of functions as we have discussed before. When viewing methods from the object oriented approach, it’s important to recall that the methods in a class have access to that class’ fields. Continuing our Tree example from before:

public class Tree {
  // ... same field definitions from above

  // estimate volume of trunk using cylinder formula.
  public double estimateTrunkVolume() {
    return Math.PI * (width / 2) * (width / 2) * height;
  }
}

Observe that the estimateTrunkVolume method of a Tree has access to the width and height fields of the Tree class. These variables are accessible in the body of the method without being passed in as input arguments.

Methods will be, in the context of this class, either public or private. Like with fields, private methods are only accessible inside the class itself whereas public methods are available from any instance of the class in another file.

If a method is public, it can be called from any instance of the class:

Tree narrow = generateTree();
double volume = narrow.estimateTrunkVolume();

Methods with private designation are generally helper methods. For better understanding of public vs. private in methods, refer to notes on Encapsulation.

Constructor

Constructors are the tools that we use to actually instantiate an object from a class. Constructors are essentially special methods that take the name of the class itself. When a constructor is called with the new keyword, Java will provide the space in memory to create a new instance of the desired class and it will use the constructor to set up the new instance in the specified manner.

Let’s return once more to our Tree example:

public class Tree {
  public int age;
  private String species;
  private double height;
  private double width;

  public Tree(int age, String species, double height, double width) {
    this.age = age;
    this.species = species;
    this.height = height;
    this.width = width;
  }
}

Our constuctor is written right beneath the class’ fields (this is conventional). Note that it looks like a method named Tree without a specified return type. This is what indicates to Java that this thing is a constructor: no return type and sharing its name with the class itself. Notice how the input arguments to the constructor match the fields of the class: this is a typical pattern, where we have a constructor that assigns each of its inputs to the corresponding fields of the new object. A constructor can take fewer input arguments than fields in the class or vice versa. A constructor does not need a return statement.

Principles of Object Oriented Programming

Encapsulation

Encapsulation is the principle that an object should hide the details of how they work by providing a barrier between the interface of the object (what it can do) and its implementation (how it does what it does). The concept of separating implementation from interface is central to the notion of Abstraction as well, but Encapsulation focuses primarily on the tools that we use to hide the machinery of an object from the client that uses it.

Encapsulation is achieved in Java by use of Access Control, which itself is defined with visibility modifiers public and private. When a field or method is tagged with private, that field or method will only be accessible from within the file where it is defined. public fields and methods are, by contrast, available in any other file.

The public interface of a class is therefore the set of fields and methods available in the class that are defined as public. These are the methods that a user can call at will. If any fields are part of the public interface, then a user can access & modify these directly.

public class Person {
  public int age;

  public Person(int age) {
    this.age = age;
  }
}

In this class Person, the field age would be considered part of the public interface. This is concerning, though, because a client using Person objects could do the following:

Person harry = new Person(24);
harry.age = -20;

It doesn’t make sense for a Person to have a negative age, so a Person object shouldn’t be able to have their age be 0 or less. Leaving age as public allows anyone with access to a Person object to put that object into a nonsensical state. Thus, it makes better sense to do the following:

public class Person {
  private int age;

  public Person(int age) {
    this.age = Math.max(0, age);
  }

  public int getAge() {
    return this.age;
  }

  public void ageOneYear() {
    this.age += 1;
  }
}

By keeping age private, modifying the constructor, and adding methods getAge and ageOneYear to the public interface, we keep age as a field that’s just part of the implementation. If a user wants to see a Person’s age, they can use the getAge method (a getter) to see it. If they want to change it, we are specifying with ageOneYear that a Person can only age one year at a time, and our constructor makes it so that making a Person with a negative age is impossible.

Getters and Setters

Getters and setters are special types of methods that help implement Encapsulation in a class. A getter is a method that returns the value of some data stored by an instance of the class. Note that this could be returning a field directly, or it could return some piece of data stored implicitly by an instance.

public class Circle {
  private double radius;

  // Constructor omitted for space...

  public double getRadius() {
    return this.radius;
  }

  public double getDiameter() {
    return this.radius * 2;
  }

  public double getArea() {
    return Math.PI * this.radius * this.radius;
  }
}

In this Circle example, we have defined three getters: getRadius, getDiameter, and getArea. Notice that the only field of the class, radius, is private. The only way to access this data is therefore using getRadius. There are no fields for the diameter or the area of the shape, but we might also call getDiameter and getArea getters for their corresponding data anyway.

Setters work similarly, but they provide controlled means of updating the values of data stored in an object.

public class Circle {
  private double radius;

  // Constructor & getters omitted for space...

  public void setRadius(double radius) {
    radius = Math.abs(radius);
    this.radius = radius;
  }
}

In this example, setRadius is a setter for the radius field that allows us to update that piece of data without risking the client filling the field with a negative (nonsensical) value.

Careful choices for public and private on the fields and methods of a class combined with getters and setters for private fields allow you to define an interface that hides and protects the implementation that you’ve chosen.

Abstraction

Abstraction is the process of representing real-world entities with properties relevant to the client that will be using it. The properties that we choose to represent an entity become the fields of the object. These chosen properties, along with our view of the stakeholder’s desired use of the object, then help to define the interface that will be available to users of the object.

Abstraction is fundamental to solving interesting problems with Computer Science: it is not possible to directly manipulate a Movie, a Movie Ticket, or a Movie Theater with Java code, but we can keep track of abstract instances of these things to solve problems about them (selling and tracking tickets for film screenings, for example).

When designing a class, we use abstraction to make conscientious choices about how a class will represent an entity.

State

Classes are defined with fields. When we talk about fields in the context of instantiated objects, we often refer to them as instance variables. These instance variables, like all variables we’ve been working with so far, store values and can change through time (unless they’re constants). Looking at the values of all of the instance variables in a particular object at a particular time defines its state. In most cases, classes are written so that the objects defined from them can change through time, representing different states of the entities that the objects are designed to represent.

public class Person {
  private String name;
  private String address;

  // constructors, getters, setters, & more omitted
}

A Person class might have fields for a name and an address. The state of any particular instance of Person, perhaps harry, would then be that Person’s name and address. At the time of this writing, harry’s address would be in Philadelphia, but when harry moves in a couple of years, we could call some method harry.moveTo("New York City"). Then, we’ve updated harry’s state to reflect his new location.

Mutability and Immutability

Variables (and thus fields) are mutable, or changeable, by default in Java. This means that any user with access to an object’s fields will generally have the ability to change the state of that object. We have already addressed this to a limited extent in our discussion of encapsulation: using privacy modifiers and carefully chosen getters, setters, and other methods, we can limit the access that a user has to the state of an object. But limited access is not the same thing as immutability; indeed, the presence of any setter or other public method that modifies the instance variables of an object implies that the object is mutable from the perspective of the end user.

Consider, then, the example of the String data type in Java. Strings are objects, and we consider them to be immutable. Now we can understand that this is because users of the String class have no ability to change the fields of any String object: there are no getters and setters for the class, and all of the methods that manipulate a String return a new version of the String.

String bookTitle = "In The Dream House"
System.out.println(bookTitle.toUpperCase());
System.out.println(bookTitle);

This results in:

"IN THE DREAM HOUSE"
"In The Dream House"

Even the methods available in String that manipulate some instance of a String do not modify the original String: calling .toUpperCase() left bookTitle the same for when we printed it out again afterwards. In this way, the String class achieves immutability.

public class Receipt {
  private String recipient;
  private double[] amounts;
  private String[] items;

  public Receipt(String recipient, double[] amounts, String []) {...}

  public double computeSubtotal() {...}

  public double computeGrandTotal(double taxRate) {...}

  public void printReceipt() {...}
}

The above class for Receipt (with method implementations left implied for space) describes another immutable object. A Receipt object, once instantiated, cannot be modified. A user can only tally up the Receipt or print a nice, readable version of it, but neither of these actions change the state of the Receipt.

Abstract Data Types

In many cases, it’s not very important how some object works, as long as it does what we expect it to do. This is true in real life: when it comes to a car, you know that it can accelerate, brake, park, get in and out without worrying too much about what’s under the hood (literally). Abstract Data Types (ADTs) are ways that we can employ this principle in programming.

In Java, we write ADTs using interfaces. If a class implements an interface, we say that the class is a subtype of the ADT’s interface or that the ADT is a supertype of the class.

Interfaces look like classes, but instead of fields and methods, interfaces are comprised of:

  1. abstract methods, or method signatures without bodies
  2. constants, or variables declared with keywords static and final that cannot be changed after they are declared.

The abstract methods are doing the heavy lifting here. These method signatures without bodies to the functions define exactly what an object of this ADT must be able to do, but they don’t specify how it happens.

public interface Car {
  public static final KM_PER_MILE = 1.609;

  void enter(String passenger);
  void accelerateTo(double targetSpeed);
  void brake(double targetSpeed);
}

Here’s a basic example of a Car ADT. This tells us that any object of type Car can do these things: you can enter a car, you can speed upp, and you can slow down. Any object of type Car will also have access to the constant KM_PER_MILE, which might be useful in dealing with speeds for cars in different parts of the world.

It’s important to recognize that we can’t instantiate a Car directly: there’s no constructor in this interface, and we couldn’t write one even if we wanted to. Instead, we can only instantiate objects of types that implement the Car interface. The following snippet is the beginning of a StationWagon interface.

A note from Harry: A station wagon is not a particularly stylish variety of car. It has a boxy shape, a sluggish disposition, and plenty of trunk space. I note all of this with pride and nostalgia: my first car was a ‘98 Volvo station wagon.

public class StationWagon implements Car {
  private String manufacturer;
  private double topSpeedMPH;
  private double currentSpeedMPH = 0;
  private int numDoors;
  private int numPassengers = 0;
  private String[] passengers = new String[6];

  public StationWagon(String manufacturer, double topSpeed, int numDoors) {
    // implemented but omitted for length
  }

  @Override
  public void enter(String passenger) {
    if (numPassengers < passengers.length) {
      passengers[numPassengers] = [passenger];
      numPassengers++;
    } else {
      System.out.println("Car's full!");
    }
  }

  @Override
  public void accelerateTo(double targetSpeed) {
    // implemented but omitted for length
  }

  @Override
  public void brake(double targetSpeed) {
    // implemented but omitted for length
  }

  public double getSpeedMPH() {
    return currentSpeedMPH;
  }
  
  public double getSpeedKMPH() {
    return currentSpeedMPH * KM_PER_MILE;
  }
}

Some important things to highlight here about how StationWagon implements Car.

Thus, the StationWagon class can instantiate any number of different StationWagon objects that represent different vehicles. Importantly, all StationWagons are also all Cars—this is an example of the subtype-supertype relationship.

Car harrysVolvo = new StationWagon("Volvo", 85, 4);
StationWagon otherCar = new StationWagon("Volkswagen", 99, 4);

In the above snippet, we instantiate two new objects. In both lines, we call the StationWagon constructor. For harrysVolvo, we store the resulting object we create in a variable of type Car. This works because a StationWagon is indeed a Car. For otherCar, we store the StationWagon in a variable of type StationWagon. This is also acceptable, and it means that otherCar can be used as a StationWagon more specifically than as a Car.

References in Java

Some brief defenitions for reference, then:

Java is a pass-by-value language. When you call a function in Java and give it an argument, the value of that argument is copied and handed along to the body of the function that’s being called. When dealing with reference variables in Java, or variables that themselves contain a reference to some object’s location in memory, a copy of this reference is passed into the function being called. Thus, the input parameter to the function call and the local variable available in the body of the function are aliases for each other.

LinkNodes, Linked Lists, & Array Lists

Lists in Java are covered quite thoroughly in our interactive Codio course. Please explore them there!

Typical List Interface

A brief overview of a typical List interface, defined over some arbitrary example object called Item:

  1. add, which can be implemented in multiple ways:
    1. void add(Item i, int index) adds Item i to the list at position index.
    2. boolean add(Item i) simply adds Item i to the end of the list and returns true, or returns false if there is no room.
  2. boolean remove(Item i) removes Item i from the list and returns true, or returns false if there is no such item. If there are duplicates of i in the list, the behavior may vary. Typically this results in removing the first matching Item, although this depends on the specifications.
  3. boolean contains(Item i) returns true if Item i appears in the list, and false otherwise.
  4. boolean isEmpty() returns true if the list is empty and false otherwise.
  5. int size() returns the number of items in the list as an int.
  6. int get(Item i) returns the index of Item i in the list. If there are duplicates of i in the list, the behavior may vary. Typically this results in finding the index of the first matching Item, although this depends on the specifications.

Number Systems

Some quick definitions:

Decimal vs. Binary

Decimal, also referred to as base-10, is our typical way of dealing with numbers. The decimal number system consists of digits 0-9. For an integer (we won’t handle fractional numbers in other systems in CIS 110), we might call the position of the least significant digit (the right-most digit) the “ones place”, then moving to the left we get the “tens place” and the “hundreds place” and so on. This reflects how we read numbers in decimal: 5,839 is equivalent 5*1000 + 8*100 + 3*10 + 9*1.

Binary is the base-2 number system, where our only digits are 0 and 1. These “binary digits” are also called bits. Counting in binary proceeds as follows: 0, 1, 10, 11, 100, 101, 110, 111, 1000, and so on. Instead of a “tens place” and a “hundreds place” as in decimal numbers, we have a “twos place” and a “fours place”. That is, if we want to convert the binary number 1011 into a decimal interpretation, we view it in the following way: 1101 in binary is 1*8 + 1*4 + 0*2 + 1*1 = 13 in decimal.

Converting from Binary to Decimal

As discussed right above, it’s simple to convert from binary to decimal by considering the binary number to be a sum of powers of two.

The algorithm for converting is as follows:

110101 becomes, then 1*2^0 + 0*2^1 + 1*2^2 + 0*2^3 + 1*2^4 + 1*2^5, which is 1 + 4 + 16 + 32 = 53.

Converting from Decimal to Binary

Going in this direction, we recommend the following algorithm: starting with the decimal number to convert, and while the quotient is greater than 0, perform integer division, keeping track of the remainder. This is perhaps better explained through example (see the slides for an image version):

  1. Start at 157. Divide this by 2 to get 78 remainder 1.
  2. Divide 78 by 2 to get 39 remainder 0.
  3. Divide 39 by 2 to get 19 remainder 1.
  4. Divide 19 by 2 to get 9 remainder 1.
  5. Divide 9 by 2 to get 4 remainder 1.
  6. Divide 4 by 2 to get 2 remainder 0.
  7. Divide 2 by 2 to get 1 remainder 0.
  8. Divide 1 by 2 to get 0 remainder 1, and we’re done dividing.
  9. Read the remainders in reverse: 10011101.

We can verify that this is correct: 10011101 (binary) = 1 + 4 + 8 + 16 + 128 = 157 (decimal).

Encryption & XOR

We can interpret any piece of data as a sequence of bits. Thus, data of all types (ints, doubles, Strings, images, text files, videos, PDFs, etc) are interpretable as binary numbers! We can leverage this interpretation to carefully encrypt the data.

Supposing we have some message m that is the binary representation of some String. We can use the bitwise XOR operation, written in Java as ^, to encrypt m using some secret key k of the same length as m.

Here is the truth table for XOR:

x y x^y (result)
0 0 0
0 1 1
1 0 1
1 1 0

Say that m = 10111010, and k is a randomly generated bit String of the same length 11011010:

String name                
m (message) 1 0 1 1 1 0 1 0
k (random key) 1 1 0 1 1 0 1 0
m ^ k 0 1 1 0 0 0 0 0

Crucially, this process is reversible using the same key for encryption and decryption:

String name                
m ^ k 0 1 1 0 0 0 0 0
k (random key) 1 1 0 1 1 0 1 0
m ^ k ^ k = m (message) 1 0 1 1 1 0 1 0

2D Arrays

Declaring and Initializing

Put simply, 2D arrays are arrays of arrays. The syntax for declaring a variable for a 2D array of ints is as follows:

int[][] ages;

2D arrays can be initialized implicitly or explicitly, just like how we’ve used arrays previously:

int[][] ages = new int[3][5];

This is implicit initialization, and it results in ages being an array containing 3 other arrays, each of which has 5 elements. The result is a 2D array that looks like this:

         
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

We can use explicit initialization instead:

int[][] ages = { 
                 {3, 4, 6},
                 {1, 2},
                 {0},
                 {5, 6, 7}
                };

This results in a jagged array, where not all rows are of the same length. This works perfectly well!

     
3 4 6
1 2  
0    
5 6 7

Indexing

By convention in this class, we refer to 2D arrays in row-major order, where the first index of the array refers to the “row” number and the second index to the “column”. Further, the first row is the top one in the visualizations we’ve given before. For example, let’s visualize the following 2D array:

 String[][] seatingChart = {
                              {"Harry", "Eric", "Jules"}, 
                              {"Gian", "Ben", "Michael"}
                           };

For the purposes of this class, we’ll view seatingChart like this:

     
“Harry” “Eric” “Jules”
“Gian” “Ben” “Michael”

Independent of how we view the 2D array in text, we have that seatingChart[0][0] evaluates to "Harry" and seatingChart[1][2] evaluates to "Michael".

If you are working in a context where the 2D space analogy of rows and columns is not useful, or if this notation is confusion, recall that 2D arrays are just arrays of arrays, and so the following table holds for double[][] prices:

expression expression data type data type interpretation 2D analogy interpretation
prices double[][] array with elements of type double[] 2D array / matrix
prices[i] double[] array with elements of type double row i
prices[i][j] double a single double a single entry at row i, column j

Iteration through 2D Arrays

2D arrays are (I’ll write it again!) arrays of arrays, so it makes sense to use nested loops to iterate through them. Presented below is a snippet that’s safe to use on both jagged and rectangular 2D arrays. The purpose of the snippet is to go through and print out every entry of the 2D array, although it can easily be adapted for other purposes:

Item[][] itemArr = generateItemArray();

for (int i = 0; i < itemArr.length; i++) {
  for (int j = 0; j < itemArr[i].length; j++) {
    System.out.println(itemArr[i][j]);
  }
}

Observe that the inner loop iterates from 0 up to the length of the current row, so jagged arrays are handled automatically without throwing ArrayIndexOutOfBoundsException.

Comparing Objects

When you write a class for a data type, it’s possible that the instances of that class can be compared to one another in some reasonable way. One Student might be compared to another Student based on their first names: Student ruth comes alphabetically after Student prabh but before Student xianHan.

To make it so an object is automatically comparable for the purposes of several built-in Java methods, you must first specify that the class implements Comparable.

Specifically, you must have:

public ClassName implements Comparable<ClassName>

as the first line of the class definition. Note that because Comparable is a generic type, you need to append the <ClassName> to the end of it. The reasons why are beyond the scope of the course, you just need to remember that you have to include it for now.

Secondly, now that you’ve committed to implementing the Comparable interface, you need to make sure that your class implements the methods included in Comparable. Fortunately, there’s only one: int compareTo(ClassName other).

compareTo should return:

Now you can use the .sort methods of Arrays or Lists of ClassName objects to have Java automatically handle the sorting of those collections!