SFTPK: Heap

Submitted by Robert MacLean on Mon, 07/02/2018 - 09:00

This post is one in a series of stuff formally trained programmers know – the rest of the series can be found in the series index.

Continuing on with more tree-based data structures, we get to the heap. If we look back at the BST and Red/Black those trees ended up with the most average/middle value at the root node so that nodes which were smaller were on the left and larger nodes were on the right, the heap changes that.

There are actually two heaps, a minimum and maximum value heap, but there are very similar. The key aspects to know about either heap are

  1. It is a binary tree. This is important for insertion and deletion and ensures the depth of the tree doesn't grow out too far from the root node.
  2. In a minimum heap, the root node is the SMALLEST value in the tree.
  3. In a minimum heap, any node should be smaller than all of its' children
  4. In a maximum heap, the root node is the LARGEST value in the tree
  5. In a maximum heap, any node should be larger than all of its children

The advantage of a heap is as an implementation of a Queue where you can control the order items appear in the queue rather than just relying on insertion order.

Let's have a look at what these will look like when we have the following dataset: 45, 42, 56, 78, 99, 30

Step Minimum Heap Maximum Heap
1 We add 45 as the root node We add 45 as the root node
2 We add 42 as the first child, but it is smaller, so we will swap it with the root node We add 42 add as the first child node
3 We add 56 as the second child node We add 56 as the second child node; it is larger than its parent so we swap them.
4 We add 78 as a child of 45 We add 78 as a child of 42, though it is larger so it must be swapped. 78 is now a child of 56, which still wrong so we need to swap them too.
5 We add 99 as a child of 45 We add 99 as a child of 56. 99 is larger, so we then swap 99 and 56. 99 is still larger than 78, so we need to swap those nodes too
6 Next we add 30 under 56. It is smaller than 56 so it must be swapped. Once swapped, its parent 42 is also larger so they need to swapped too. Last we add 30 to under 45.

Implementations

Java has a built-in implementation with the PriorityQueue and, unfortunately, .NET and JavaScript lacks an out of the box option.

Learning Kotlin: Object Expressions and SAM Conversions

Submitted by Robert MacLean on Thu, 06/28/2018 - 09:00

More Information

For the 11th post, we get something new to an old C# person - Object Expressions!

Object Expressions are very similar to Anonymous Classes in Java where you can declare a class inline rather than entirely separately in its own file.

In the first Koan we need to implement Comparator<Int> inline:

  1. fun task10(): List<Int> {
  2.     val arrayList = arrayListOf(1, 5, 2)
  3.     Collections.sort(arrayList, object : Comparator<Int> {
  4.         override fun compare(o1:Int, o2:Int):Int {
  5.             return o2 - o1;
  6.         }
  7.     })
  8.     return arrayList
  9. }

You can see on line 21, we define the new object with the object keyword and then use : Comparator<Int> to state it implements that interface. The Comparator has a single function which needs to be implemented which we do on line 22.

The second Koan takes this further and states if there is a single method in an abstract class or interface then we can use SAM, or Single Abstract Method, to avoid needing the class at all as we just need to implement the single function. To achieve this with the Koan, we use an anonymous function that handles the compare function of the Comparator:

  1. fun task11(): List<Int> {
  2.     val arrayList = arrayListOf(1, 5, 2)
  3.     Collections.sort(arrayList, { x, y -> y - x})
  4.     return arrayList
  5. }

and lastly, if we look back to previous post we can use the extension method to simply it further:

  1. fun task12(): List<Int> {
  2.     return arrayListOf(1, 5, 2).sortedDescending()
  3. }

These Koans have given me more thoughts about the language than probably any previous Koans:

  1. Why do classes which implement an interface use override?
    In C#, when you implement an interface you do not need to state that you are not overriding the functions (see this example). In C# only state that your are overriding when you inherit from a function and you actually override a function. The reason is that an interface in Kotlin is closer to an abstract class than in C#, to the point it can have functionality - yup, interfaces can have functions and logic!
  2. So why does Kotlin have interfaces and abstract classes?
    The key difference is an abstract class can have state while the logic in an interface needs to be stateless!
  3. Why bother having SAM?
    As I was working on the Koan, I was delighted by the SAM syntax... and then I wondered why I needed this at all? Why is Collections.sort taking a class as the second parameter? Why not just pass in a function, since that is all that is actually needed? Both C# and Kotlin supports passing functions so this is possible... but something I never knew about Java is that it doesn't support passing functions! You have to use Callable, a class, to pass functions.

Learning Kotlin: Extension Functions and Extensions On Collections

Submitted by Robert MacLean on Wed, 06/27/2018 - 09:00

More Information

This post is the first to cover multiple Koans in a single post.

The 10th in our series is very simple coming from C# because Extension Functions in Kotlin are identical as Extension Methods in C#, though they are much cleaner in their implementation.

In their example for the Koan we add a lastChar and lastChar1 function to the String class.

  1. fun String.lastChar() = this.get(this.length - 1)
  2.  
  3.  
  4. // 'this' refers to the receiver (String) and can be omitted
  5. fun String.lastChar1() = get(length - 1)

For the Koan itself, we need to an r function to Int and Pair<int, int> which returns an instance of RationalNumber, which we do as follows:

  1. fun Int.r(): RationalNumber = RationalNumber(this, 1)
  2. fun Pair<Int, Int>.r(): RationalNumber = RationalNumber(first, second)

An additional learning on this, was the Pair<A, B> class which is similar to the Tuple class from C#.

When we get into the second Koan, we get exposed to some of the built-in extension's functions in Kotlin which ship out of the box; in this case, we use sortedDescending extension method with the Java collection. It is a great example of mixing Java and Kotlin too:

  1. fun task12(): List<Int> {
  2.     return arrayListOf(1, 5, 2).sortedDescending()
  3. }

Learning Kotlin: Smart Casts

Submitted by Robert MacLean on Tue, 06/26/2018 - 09:00

More Information

The goal of this Koan is to show how smart the Kotlin compiler is; in that when you use something like the is keyword to handle type checking the compiler will then know the type later on and be able to use it intelligently.

So if we want to check types in Java we would use something like this where we would use instanceof to check the type and then cast it to the right type.

  1. public class JavaCode8 extends JavaCode {
  2.     public int eval(Expr expr) {
  3.         if (expr instanceof Num) {
  4.             return ((Num) expr).getValue();
  5.         }
  6.         if (expr instanceof Sum) {
  7.             Sum sum = (Sum) expr;
  8.             return eval(sum.getLeft()) + eval(sum.getRight());
  9.         }
  10.         throw new IllegalArgumentException("Unknown expression");
  11.     }
  12. }

In Kotlin we, by checking the type the compiler handles the casting for us, but before we get to that we also got to learn about the when which is the Kotlin form of the Switch keyword in C# or Java and it offers similar functionality, as shown in this example:

  1. when (x) {
  2.     1 -> print("x == 1")
  3.     2 -> print("x == 2")
  4.     else -> { // Note the block
  5.         print("x is neither 1 nor 2")
  6.     }
  7. }

and it supports multiple values on the same branch

  1. when (x) {
  2.     0, 1 -> print("x == 0 or x == 1")
  3.     else -> print("otherwise")
  4. }

Where it gets awesome, is the extra actions it supports; for example when values can be functions, not just constants:

  1. when (x) {
  2.     parseInt(s) -> print("s encodes x")
  3.     else -> print("s does not encode x")
  4. }

You can also use in or !in to check values in a range/collection:

  1. when (x) {
  2.     in 1..10 -> print("x is in the range")
  3.     in validNumbers -> print("x is valid")
  4.     !in 10..20 -> print("x is outside the range")
  5.     else -> print("none of the above")
  6. }

It really is very cool, so let us see how we use Smart Casts and when together and how it compares with the Java code above:

  1. fun eval(e: Expr): Int =
  2.     when (e) {
  3.         is Num -> e.value
  4.         is Sum -> eval(e.left) + eval(e.right)
  5.    }

Really nice and, I think, more readable than the Java code.

Learning Kotlin: Nullable Types

Submitted by Robert MacLean on Mon, 06/25/2018 - 09:00

More Information

The next Koan looks at how Kotlin handles nulls, and it does it wonderfully; Null is explicitly opt-in. For example, in C# you can assign null to a string variable but in Kotlin unless you say you want to support nulls, which you do by adding a trailing question mark to the class, you cannot.

Their example in this Koan is a nice example:

  1. fun test() {
  2.     val s: String = "this variable cannot store null references"
  3.     val q: String? = null
  4.  
  5.     if (q != null) q.length      // you have to check to dereference
  6.     val i: Int? = q?.length      // null
  7.     val j: Int = q?.length ?: 0  // 0
  8. }

Let us dig into the Koan, where we get given the following Java code:

  1. public void sendMessageToClient(@Nullable Client client, @Nullable String message, @NotNull Mailer mailer) {
  2.     if (client == null || message == null) return;
  3.  
  4.     PersonalInfo personalInfo = client.getPersonalInfo();
  5.     if (personalInfo == null) return;
  6.  
  7.     String email = personalInfo.getEmail();
  8.     if (email == null) return;
  9.  
  10.     mailer.sendMessage(email, message);
  11. }

and we need are going to rewrite it using the Nullable language features of Kotlin, which looks like:

  1. fun sendMessageToClient(client: Client?, message: String?, mailer: Mailer) {
  2.     val email = client?.personalInfo?.email
  3.     if (email == null || message == null) return
  4.  
  5.     mailer.sendMessage(email, message)
  6. }

The big changes from Java:

  1. The @NotNull attribute for mailer is no longer needed
  2. The @Null attribute for the other parameters becomes the question mark
  3. We do not need to pre-check client before calling the parameter, as you can use the null safe operator ?. to ensure you only check before we call the method.
  4. Unfortunately, the null safe operator in Kotlin doesn't support calling methods on null objects as C# currently does with its Elvis operator

SFTPK: Stack & Queue

Submitted by Robert MacLean on Fri, 06/22/2018 - 09:00

This post is one in a series of stuff formally trained programmers know – the rest of the series can be found in the series index.

In this post, we will look at two related and simple data structures, the Stack and the Queue. The stack is a structure which can be implemented with either an Array or Linked List.

An important term for understanding a stack is that it is LIFO, last-in-first-out, system; namely, the last item you add (or push or bury) is the first item you take out when you retrieve an item (or peek or unbury).

Let's have a look at what a stack would look like:
What a stack looks like

In this, we added 1, 2, 3, 4, and then 5 and when we read from the stack we read in the reverse order.

Implementations


Next is the queue, which is very similar to the stack, except where the stack was LIFO; a queue is FIFO, first-in-first-out; so if we put in 1, 2, 3, 4, & 5 into the queue, then we would read them in the same order, i.e. 1, 2, 3, 4, 5.

Implementations

C# has a queue implementation and the JavaScript array can act as a queue, when you use unshift to add to the beginning of the array (also known as the head) and pop to remove from the end of the array (also known as the tail).

Learning Kotlin: Data Classes

Submitted by Robert MacLean on Thu, 06/21/2018 - 09:00

More Information

WOW! Data Classes are awesome! I really like a lot of how classes are handled in Kotlin, but Data Classes are the pinnacle of that work. The effort for this Koan is to convert this Java class to Kotlin:

  1. package i_introduction._6_Data_Classes;
  2.  
  3. import util.JavaCode;
  4.  
  5. public class JavaCode6 extends JavaCode {
  6.  
  7.     public static class Person {
  8.         private final String name;
  9.         private final int age;
  10.  
  11.         public Person(String name, int age) {
  12.             this.name = name;
  13.             this.age = age;
  14.         }
  15.  
  16.         public String getName() {
  17.             return name;
  18.         }
  19.  
  20.         public int getAge() {
  21.             return age;
  22.         }
  23.     }
  24. }

and what does that look like in Kotlin?

  1. data class Person(val name: String, val age: Int)

Yup, a single line. The data annotation adds a number of important functions (like ToString and copy). We then declare the class with a constructor which takes two parameters which both become properties.

Another important aspect I learnt with this one is that Kotlin has both a val and var keyword for variables. We have seen var already and val is for read-only variables.

Learning Kotlin: String Templates

Submitted by Robert MacLean on Wed, 06/20/2018 - 09:00

More Information

The purpose of this lesson is to show off string templating and the Koan starts with some interesting examples

  1. fun example1(a: Any, b: Any) =
  2.         "This is some text in which variables ($a, $b) appear."
  3.  
  4. fun example2(a: Any, b: Any) =
  5.         "You can write it in a Java way as well. Like this: " + a + ", " + b + "!"
  6.  
  7. fun example3(c: Boolean, x: Int, y: Int) = "Any expression can be used: ${if (c) x else y}"

If you are used to string templates from C# and JavaScript this should be fairly simple to understand.

The fourth example is interesting

  1. fun example4() =
  2.         """
  3. You can use raw strings to write multiline text.
  4. There is no escaping here, so raw strings are useful for writing regex patterns,
  5. you don't need to escape a backslash by a backslash.
  6. String template entries (${42}) are allowed here.
  7. """

This brought up something I've never heard of, raw strings. Raw strings seem to be the Python way of saying a Verbatim string... which I didn't know was the official term.

The actual Koan here is about converting this fun getPattern() = """\d{2}\.\d{2}\.\d{4}""" to a different regular expression, using a string template:

  1. fun task5(): String = """\d{2}\s$month\s\d{4}"""

It isn't that interesting and really, if you don't know regular expressions this could be tougher than it needs be.

Learning Kotlin: Lambdas

Submitted by Robert MacLean on Tue, 06/19/2018 - 09:00

More Information

So following C#, Kotlin has Lambda support with the change if => becoming -> and the Koan starts with some nice examples at the start:

  1. fun example() {
  2.  
  3.     val sum = { x: Int, y: Int -> x + y }
  4.     val square: (Int) -> Int = { x -> x * x }
  5.  
  6.     sum(1, square(2)) == 5
  7. }

Basically, though, the code that needs to be done is to check a collection if all items are even, which is easily done with:

  1. fun task4(collection: Collection<Int>): Boolean = collection.any({item -> item % 2 == 0})

Learning Kotlin: Default values

Submitted by Robert MacLean on Mon, 06/18/2018 - 09:00

More Information

Previously we covered Named Arguments and this is a small continuation from it, we start with a simple function fun foo(name: String): String = todoTask3() and we need to have it call a single Java function and to provide it with default values which ultimately looks like this:

  1. fun foo(name: String, number: Int = 42, toUpperCase: Boolean = false): String = JavaCode3().foo(name, number, toUpperCase)