Ordered Array Class

Arrays are static data structures, so their size is fixed when they are created. Array elements are contiguous in RAM. This means that if you want to slot a value into the middle of an array, you need to shift the other values first. Imagine trying to slot yourself in between two people in a crowded cinema.

2018-09-19_06-43

A good exercise is to code an OrderedArray class. This is a wrapper for an array of Integer object (use Integers not ints so that we can check for nulls) that has an insert method that slots new values in ascending order.

I would say that the complexity of this code is about as tough as it gets at SL. If you need some scaffolding, use the class template below. Otherwise just have a go at it yourself. In addition, code a constructor that allows you to set the size of the array.

class Main {
  // This main class is just for testing.
  public static void main(String[] args) {
    OrderedArray oArr = new OrderedArray(50);
    for (int i = 0; i < 30; i++) {
      java.util.Random r = new java.util.Random();
      oArr.insert(r.nextInt(100));
    }
    // You will need to code this method.
    // The numbers should be in order.
    oArr.print();
  }  
}

class OrderedArray {

  // What instance variables will you need?

  public OrderedArray(int size) {
  // Use the size parameter to set the size of the array.
  }

  void insert(int n) {
  // Insert the new number in the right place.
  // 1. Find out where it should go.
  // 2. Make room for it.
  }

  void print() {
  // Print the numbers to the console.
  }
}

 

Interfaces and functional interfaces

Java interfaces are not in the IB syllabus, but if you want to call yourself a higher level computer scientist you should at least have some idea about them.

An interface is like a class but it doesn’t have code in its methods. What is the point of that? Well imagine that I am on your team of programmers and you want me to do some coding for you. By creating an interface, you can specify what methods my classes should have, without actually coding them. This means you can go ahead and write code that calls those methods before I have even written them, and therefore we can both be programming at the same time, taking advantage of concurrency.

Some well-known Java interfaces are Serializable, Iterable and Comparable. Here I define an interface called Flickable. In order for a class to be Flickable, it should have a flick() method:

public class FunctionalInterfaceDemo {

    public static void main(String[] args) {
        Switch s = new Switch();
        s.flick();
        
        Flickable f = new Flickable () {
            public void flick() {
                System.out.println("Anonymous inner flickable class flicked.");
            }
        };
        f.flick();
    }
}

class Switch implements Flickable {
    // This class MUST implement a flick() method, otherwise
    // the code will not compile.
    public void flick() {
        System.out.println("Switch flicked.");
    }
}

interface Flickable {
    // This states that if you want to call yourself flickable,
    // you have to implement a flick() method.
    void flick();
}

This is a powerful aid to object-oriented programming because you can anticipate the behaviour of classes that claim to implement an interface safe in the knowledge that if they don’t implement the interface the compiler will already have detected the problem.

But there is a different problem. Suppose now I make a change to my Flickable interface and add a line void unflick();. I have now moved the goalposts and said that any class that claims to be flickable must implement not only a flick() method but an unflick() method. The upshot is that all code that implements the flickable interface is now broken and will no longer compile!

From Java 8 onwards, you can declare an interface to be a functional interface. The reason for this is well beyond the scope of this post, but has to do with Java’s push to incorporate more practices from a programming paradigm called functional programming. The good news is that with the @FunctionalInterface compile directive, we can tell the compiler that our interface cannot have more than one method. This substantially reduces the possibility of breaking code by making a change to an interface, because the compiler will prevent it.

interface Flickable {
    // This states that if you want to call yourself flickable,
    // you have to implement a flick() method.
    void flick();

    // If you uncomment the next line you will break
    // break all classes that implement Flickable:    

    // void otherMethod(); 
}

@FunctionalInterface
interface Proddable {
    void prod();

    // If you uncomment the next line you will get a
    // compile error. You can't have more than one method 
    // in a functional interface.
    
    // void otherMethod(); 
}

Referential versus structural equality

This came up in class the other day.

Expressions involving the comparison operator (==) and two object references return true if the operands point to the same object. If you want to make a more meaningful comparison you have to override the equals method that all objects inherit from java.lang.Object.

See the Java code below to see how to override the equals method.

ref

public class EqualityDemo {

    public static void main(String[] args) {
        Student s = new Student("Fred", 123);
        Student t = s;
        Student u = new Student("Fred", 123);
        System.out.println(s==t);
        System.out.println(s==u);
        System.out.println(s.equals(u));
    }
}

class Student {

    String name;
    int id;

    public Student(String name, int id) {
        this.name = name;
        this.id = id;
    }   

    @Override
    public boolean equals(Object object) {
        Student student = (Student)object;
        return this.id == student.id && this.name.equalsIgnoreCase(student.name);
    }
}
Output:
true
false
true

Passing code as a parameter: An example of Java 8’s lambda expressions

In languages like Python and Javascript, functions are “first class objects”. This means that they can be assigned to variables and passed as parameters. In Java, if you want this functionality, you have to use an anonymous class or a lambda expression. Below are examples of the old-fashioned anonymous class technique, the new Lambda expression technique and, for comparison, the same code in Python and Javascript. EDIT: I’ve now also included Kotlin, a new language I’m quite interested in that compiles to Java bytecode and runs on the JVM.

Note the in the Lambda expression example there is no body provided for the execute() method. The fact that the Executable interface has a single method, and that the code passed in is interpreted as an Executable object, is sufficient for the compiler to know that the code passed in should be run when the execute() method is invoked.

Java

package lambdaexample;

public class Main {

    public static void main(String[] args) {
        doAnonymousClassExample();
        doLambdaExample();
    }

    // This method not required by Lambda example
    static void doAnonymousClassExample() {
        CodeRunner c = new CodeRunner();
        c.run(new Executable() {
            public void execute() {
                System.out.println("The code is running.");
            }
        });
    }

    // This method not required by anonymous class example
    static void doLambdaExample() {
        CodeRunner runner = new CodeRunner();
        runner.run(() -> System.out.println("The code is running."));
    }
}

interface Executable {
    void execute();
}

class CodeRunner {
    void run(Executable code) {
        System.out.println("About to run the code...");
        code.execute();
    }
}

Javascript

var foo = function() {
  console.log("The code is running.");
}

function codeExecuter(code) {
  console.log("About to run code...");
  code();
}

codeExecuter(foo);

Python

def codeexecuter(code):
    print("About to run code...")
    code()

foo = lambda : print("The code is running.")
codeexecuter(foo)

Kotlin

fun main (args: Array) {
    val foo: () -> Unit = { println("The code is running...") }
    codeExecuter(foo)
}

fun codeExecuter(code: () -> Unit) {
    println("About to run code...")
    code.invoke()
}

Java Multithreading Example

This is not on the IB Computer Science syllabus, but it’s useful for IAs and Grade 10 projects. One of the key reasons you might decide to run some code in its own thread is so that your GUI can remain responsive to user-generated events like button clicks. Imagine you have a sudoku game that displays a timer. You would need to run the timer in its own thread so that the game remained responsive to the user entering answers in the sudoku grid.

public class MultiThreadingExample {

    public static void main(String[] args) {
        /* Create five new tasks and set them running in their
         * own threads.
         */
        for (int i = 0; i < 5; i++) {
            /* Notice that because we don't re-use the task 
             * or thread objects, there is no need to assign
             * them to variables. This code is equivalent to
             *
             * Task task = new Task();
             * Thread thread = new Thread(task);
             * thread.start()
             */
            (new Thread(new Task())).start();
        }
    }
}

class Task implements Runnable {
     
    private static int nextId;
    private int id;
    
    public Task() {
        init();
    }
    
    private synchronized void init() {
        /* The synchronized keyword ensures that any thread
         * that runs this method runs the whole method before
         * yielding to another thread. This is necessary here
         * to prevent two threads from executing id = nextId
         * consecutively (in which case they will both get the
         * same id).
         */
        id = nextId;
        nextId = nextId + 1;        
    }
    
    public void run() {
        /* Each thread just counts up to 10 and prints out its
         * id and the number it has reached.
         */
        for(int i = 0; i < 10; i++) {
            System.out.println(id + ": " + i);
        }
    }
}

Confusion with lists in the IB Computer Science syllabus

There are three key mentions of the word list in the IB syllabus and they are all HL only:

  • Linked lists in Topic 5
  • ADT list in Option D
  • ArrayList and LinkedList in Option D

Topic 5 Linked Lists

This reference is all about how linked list objects work with references to the next node. You need to be able draw or construct simple code to show the changes that the list undergoes with insertion or deletion of a node. You should also certainly know the basic algorithm for traversing the list, e.g searching for an item within it.

Types of lists are singly-linked, doubly-linked, circular, etc, and a key point is that they only support serial access and, unlike arrays, don’t support direct access.

ADT list in Option D (D4.7)

ADT stands for Abstract Data Type. The “abstract” is there because we are not worrying at all about implementation, just what operations a list might support. What the IB wants you to understand here is that we can still talk about adding, removing, getting the next value, etc, without specifying exactly how the data is stored. In the past there have been questions that invent a list, along with the operations it supports, there and then on the question paper, and students are expected to construct code using the list.

You can look at abstract lists in Java using the two links below. You are certainly not expected to know the details of these classes/interfaces, you just need the general concepts mentioned above.

java.util.AbstractList
java.util.List

ArrayList and LinkedList (D4.11)

The syllabus says you should have a “broad understanding of the operation of these lists and their interface (methods)”. Oddly you are not expected to know the implementation, but it seems to me a key fact that the underlying data structure in an ArrayList is an array, and the underlying data structure in a LinkedList is, well, a linked list. This has great implications for the decision as to which to select. Anyway, have a brief look at the Javadoc pages linked above, and also looked at the new slide put into the Option D presentation showing techniques for iteration through each of these list types.