1. Code Style

For all code that you write during this class (assignments, labs, etc.) you are expected to follow the Google Java Style Guide.

There are publicly available IDE configurations that you can use to import in your IDE. These configuration will attempt to format and style your Java code according to the Google Java Style Guide. The configuration files for Java, as well as other languages, can be found in the Google Styleguide repo on GitHub.

1.1. Eclipse

  1. Download the Eclipse specific configuration file.

    1. If Github is down download the file here.

  2. Start Eclipse on your machine.

  3. Go to your Eclipse Preferences menu.

    • On a Mac press Command+,.

    • On Windows go to Window and then Preferences.

  4. On the left-hand side pane navigate to JavaCode StyleFormatter.

  5. On the right-hand side pane click on Import…​; a file explorer window pops up.

  6. Navigate to the location that you used to save the downloaded file from step 1 above.

  7. Click OK.

    • If a pop up message comes up from Eclipse mentioning something about the file being created by an older or newer version of Eclipse, click ok.

  8. Click Apply.

  9. Go back to the left-hand side panel and navigate to JavaEditorSave Actions.

  10. On the right-hand side pane check the following check boxes

    1. Perform the selected actions on save.

    2. Format source code.

    3. Format all lines.

    4. Organize imports.

    5. Additional actions.

  11. Once you select Additional actions the button Configure…​ located close to the right-edge of the current window will be enabled. Click it. A new window appears with 5 tabs Code Organization,Code Style,Member Access,Missing Code and Unnecessary Code.

  12. Click on Code Organization and make sure you check the following checkboxes.

    1. Remove trailing whitespace.

    2. All lines.

    3. Correct indentation.

  13. Click on Code Style and make sure you check the following checkboxes.

    1. Use blocks in if/while/for/do statements.

    2. Always.

    3. Use parenthesis in expression.

    4. Always.

  14. Click on Member Access and make sure you check the following checkboxes.

    1. Use 'this' qualifier for field access.

    2. Always.

    3. Use declaring class as qualifier.

    4. Qualify field accesses.

    5. Qualify method accesses.

    6. Change all accesses through subtypes.

    7. Change all accesses through instances.

  15. Click on Missing Code and make sure all checkboxes are selected.

  16. Click on Unnecessary Code and make you check the following checkboxes.

    1. Remove unused imports.

  17. Click on OK located in the bottom right-hand corner of the current window. This should take you back to the Preference menu.

  18. Click on OK location in the bottom right-habnd corner of the current window.

1.2. IntelliJ

  1. Downlaod the IntelliJ specific configuration file.

  2. Follow these instructions to install the file in IntelliJ.

    The staff has not attempted these steps for IntelliJ. Try them out during the lab. If you face any issues we’ll try and help during the lab.

2. Recursion: Binary Trees

An Integer BinaryTree (IBT) comprises of a leaf or a node. Both a leaf and a node contain an integer value. A node however also contains two sub trees called the left and the right subtree.

Here are some examples of IBTs

Leaf example Node example Node example
treeexamples
node1
node2
Practise Exercises
  1. Design a Java class hierarchy that captures IBTs.

  2. Create examples of IBTs.

  3. Design the following operations on an IBT.

    1. Design an operation size that returns the total number of nodes and leafs in the IBT.

    2. Design an operation sum that returns the sum of all integers in the tree.

    3. Design an operation multiply that returns the product of all integers in the tree.

    4. Design an operation contains that takes as input an integer n and returns true if n is found in the IBT and false is n is not found in the IBT.

We would like to pretty print our IBTs using the following rules

  1. For a leaf print out the integer stored at that leaf.

  2. For a node.

    1. Print a left parenthesis first.

    2. Print its left-subtree.

    3. Print the integer stored at this node.

    4. Print the right subtree.

    5. Print a right parenthesis.

The table below shows how the IBTs from above get printed out

Pretty print Leaf example

Pretty print Node example

Pretty print Node example

3

(30320)

((1003(580))10(50204))

Practise Exercises
  1. Design the operation prettyprint for IBTs that implements pretty printing as described above.

The IBTs as described thus far create nodes that must have 2 subtrees. We would like to extend out IBTs to allow for two new kinds of nodes

  1. A left only node contains an integer and a left subtree only.

  2. A right only node contains an integer and a right subtree only.

Practise Exercises
  1. Extend your existing design to accommodate for the left only nodes and right only nodes

  2. Ensure that you update your program so that the function we have written thus far take left only and right only nodes into account.

3. ADTs

We would like to design a program that implements an Association List (AList). An AList contains pairs as elements. We will use {< >} to represent an empty AList and (k,v) to represent a pair.

  • The first element of the pair k is called a key.

  • the second element of the pair v is called a value.

So an AList holds key-value pairs. We would like to create an AList that has Point s (from Lab2) as keys and Shape s (from Lab2) as values.

Here is a table of the operations along with their specifications and comments.

Operation Specification Comments

Empty() : AList

Empty() = {< >}

  • Creates an empty AList.

isEmpty: Boolean

{<>}.isEmpty()                    = true

{<(k,v), (k1,v1), ...>}.isEmpty() = false
  • returns true if the AList is empty

  • returns false if the AList is non-empty

size() : Integer

{<>}.size()                    = 0

{<(k,v), (k1,v1), ...>}.size() =
    1 + {<{k1,v1,...>}.size()
  • returns 0 if the AList is empty

  • returns the number of pairs in the AList

add(a,b): AList

{<>}.add(a,b)                    = {<(a,b)>}

{<(k,v), (k1,v1), ...>}.add(a,b) =
    {<(a,b), (k,v), (k1,v1),...>}
  • if the AList is empty returns a new AList with one pair (a,b)

  • if the AList is non-empty returns a new AList that has the same pairs in the same order as the original non-empty AList but with the pair (a,b) prepended

replace(a,b) : AList

{<>}.replace(a,b)                    = {<>}

{<(a,c), (k1,v1), ...>}.replace(a,b) =
    {<(a,b),(k1,v1),...>}

{<(x,c), (k1,v1), ...>}.replace(a,b) =
    {(k1,v1),...>}.replace(a,b).add(x,c)
  • if the AList is empty replace returns the empty AList

  • if the first pair of the AList has the same key as the key provided as argument, a then replace the value of the pair in the AList with the second argument b

delete(x) : AList

{<>}.delete(x)                    = {<>}

{<(x,v), (k1,v1), ...>}.delete(x) =
    {<(k1,v1), ...>}

{<(y,v), (k1,v1), ...>}.delete(x) =
    {<(k1,v1), ...>}.delete(x).add(y,v)
  • if the AList is empty delete returns the empty AList

  • if the first pair of the AList has the same key as the key provided as argument, a then remove the first pair and return the remaining AList unaffected.

  • if the first pair of the AList is not the same key as the key provided as argument, a then proceed to the rest of the pairs and keep the first pair as the first pair.

has(x): Boolean

{<>}.has(x)                    = false

{<(x,v), (k1,v1), ...>}.has(x) = true

{<(y,v), (k1,v1), ...>}.has(x) =
    {<(k1,v1), ...>}.has(x)
  • if the AList is empty return false

  • return true only if you find a pair in the AList that has the same key value as the argument x

get(x) : Shape

{<>}.get(x)                    = ERROR

{<(x,v), (k1,v1), ...>}.get(x) = v

{<(y,v), (k1,v1), ...>}.get(x) =
    {<(k1,v1), ...>}.get(x)
  • if the AList is empty then throw an error

  • else keep looking at each pair in the AList, the first pair whose key is the same as the argument x return the value from that pair

Practise Exercises
  1. Design a Java program that implements the AList ADT.

  2. The clients changed their minds about of operations of AList. They would like you to update your design to reflect these alterations.

    1. Calling replace on an empty AList should throw an error.

    2. Calling delete on an emptyu AList should throw an error.