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)

Learning Kotlin: Named Arguments

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

More Information

On to our third exercise and definitely, the difficulty curve has lowered again (or should it be steep) as we have a simple lesson - how to use named arguments.

Not only is an example for it provided for how named arguments work:

  1. fun usage() {
  2.     // named arguments
  3.     bar(1, b = false)
  4. }

We also get an example of default values for arguments

  1. fun bar(i: Int, s: String = "", b: Boolean = true) {}

The problem we need to solve itself is simple too,

Print out the collection contents surrounded by curly braces using the library function 'joinToString'. Specify only 'prefix' and 'postfix' arguments.

Which has this answer:

  1. fun task2(collection: Collection<Int>): String {
  2.     return collection.joinToString(prefix = "{", postfix = "}")
  3. }

Not much to add to this lesson unfortunately.

Learning Kotlin: Java To Kotlin Converter

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

More Information

The second Koan is meant as an exercise of the IDE and is targetted at those moving from Java, as such this was a mixed bag for me.

The goal is to get a Kotlin version of Java code by letting the IDE do the conversion, but I decided to tackle it myself.

Initially, I thought I needed to do the entire file and not just the task function. So, what does the entire code look like when changed?

Java
  1. package i_introduction._1_Java_To_Kotlin_Converter;
  2.  
  3. import util.JavaCode;
  4.  
  5. import java.util.Collection;
  6. import java.util.Iterator;
  7.  
  8. public class JavaCode1 extends JavaCode {
  9.     public String task1(Collection<Integer> collection) {
  10.         StringBuilder sb = new StringBuilder();
  11.         sb.append("{");
  12.         Iterator<Integer> iterator = collection.iterator();
  13.         while (iterator.hasNext()) {
  14.             Integer element = iterator.next();
  15.             sb.append(element);
  16.             if (iterator.hasNext()) {
  17.                 sb.append(", ");
  18.             }
  19.         }
  20.         sb.append("}");
  21.         return sb.toString();
  22.     }
  23. }
  24.                    
Kotlin
  1. package i_introduction._1_Java_To_Kotlin_Converter;
  2.  
  3. import util.JavaCode;
  4.  
  5. import kotlin.collections.Collection;
  6.  
  7.  class JavaCode1 : JavaCode() {
  8.     fun task1(collection : Collection<Int>) : String {
  9.         val sb = StringBuilder()
  10.         sb.append("{")
  11.         val iterator = collection.iterator()
  12.         while (iterator.hasNext()) {
  13.             val element = iterator.next()
  14.             sb.append(element)
  15.             if (iterator.hasNext()) {
  16.                 sb.append(", ")
  17.             }
  18.         }
  19.         sb.append("}")
  20.         return sb.toString()
  21.     }
  22.  }
  23.                        

The first thing you'll notice is that the java.util.Collection is gone since Kotlin has its' own implementation and it is imported by default.

Next is the lack of Visibility Modifiers in the code. This is because everything is public by default. In addition to public there are protected, private and internal which work the same as with .NETs modifiers.

The next change is the variables, you don't need to define the type before the variable... you just define val for read-only variables or var for mutable variables. This is similar to C#s var keyword.

The final change is the lack of semicolons. This doesn't mean Kotlin doesn't have them, it means they are optional. You can add them as if it was Java or C# with no issue, it is you don't need them unless you are doing something confusing for the compiler.

SFTPK: Red/Black Trees

Submitted by Robert MacLean on Tue, 06/12/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.

Building off of the Binary Search Tree, we get the red/black tree which aims to solve the problem that a BST can become unbalanced.

The short version of a red/black tree is that is a BST with a set of rules that help us keep it performing well.

Thinking back to the BST, when we are doing the inserts and deletes at some point we need to rebalance the tree to ensure we keep that sweet O(log n) performance for searching. When is the right time to do that rebalancing?

A red/black tree extends a BST by adding one bit of information to each node; for those keeping track, our node now has the data, a key and a flag.

The flag is either red/black and there are 7 rules a BST (there are 5 official ones that relate to the colours, the first 5 below, but there are two more for the BST itself):

  1. Each node is either red or black
  2. The root node is black
  3. All leaves are black. These leaves can be the null points off of a node or they can be explicit nodes.
  4. A red node can only have black children
  5. Any path from a node to the leaves contains the same number of black nodes
  6. New nodes added are always Red.
  7. If the depth of a path is more than twice that of the shorted path we need to do a rotation.

So with these rules, insert & delete get more complex because you need to check these rules and, if the rules do not work you start to correct the issue. What is great with this is that because of the rules you become really efficient at correcting the problems.


So let's look at a really simple BST:

A simple BST

Next, let's make it a red/black tree following our rules above. I am also going to add the leave nodes in this image to help explain it but will take them out the remaining ones.

Our simple BST that is now painted red/black

Note:

  • that from the root node you need to go through 1 black node to reach a leaf node regardless of path.
  • All red nodes only have black children.
  • A black node can have black children.

Now we are going to add a node with value 11. It is added in the correct place and as a red node.

Addition of a new node

However 9 is red and has a red child, so we need to trigger a repaint of it to black. That causes a new issue, that from the root node to the leaves you may go through 1 black node by going left or 2 black nodes by going right, so we need to paint the parent of 9 (i.e. 7) to red. Lastly, since 7 is now red, 6 must be repainted to black. Finally, we have a correct red/black tree again.

A red/black tree after painting

Lastly let us add 10, which goes under 11. Immediately we note that the length from 5 to the leaf of 10 is 4 steps, while the shortest path (the left side) is 2. We know we need to do a rotation.

A red/black tree after painting

The rotation is easy, we take the child of the longer side (i.e. 7) and make it root and make the original root (i.e. 5) a child of it. Since 7 has two children already (5 and 9), it's original child 6 moves to under 5. Next, we just trigger a repaint, starting with the fact 7 needs to be black and you end up with the following:

A red/black tree after painting

This might seem really expensive to do, but since you are just changing pointers and only a few the performance of the insert becomes also O(log n).

Implementations

Unfortunately, neither Java, .NET nor JavaScript has out of the box implementations but there are plenty of ones available if you search for it.

Learning Kotlin: Hello World

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

More Information

So let's start with line one: package i_introduction._0_Hello_World

In Kotlin package is just the same as a package in Java or Namespaces in .NET. There is no link between package name and the filesystem.


Next up is imports:

  1. import util.TODO
  2. import util.doc0

Imports are the same as import in Java and Using in C#. Kotlin does import a number of packages by default:

  • kotlin.*
  • kotlin.annotation.*
  • kotlin.collections.*
  • kotlin.comparisons.* (since 1.1)
  • kotlin.io.*
  • kotlin.ranges.*
  • kotlin.sequences.*
  • kotlin.text.*

Next up is our first function defination fun todoTask0(): Nothing = ...

We use the fun keyword to state it is a function, followed by the function name todoTask0 and the parameters... in this case, that is empty.

The function returns Nothing though that isn't specifically required as the compiler can infer the return type.

This is a single statement function so it ends with an equal sign.

The next function is a little different

  1. fun task0(): String {
  2.     return todoTask0()
  3. }

The second function returns a String and is not a single statement function.


So how do we solve this Koan?

  1. fun task0(): String {
  2.     return "OK"
  3. }

Learning Kotlin: Introduction

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

I have recently decided to start to learn Kotlin, and have started with the Koans.

Koans are simple unit tests which help ease you into learning a new language.

The first step was setting this up, in Windows and VSCode... cause for some reason I hate myself that much.

Requirements

Using

So I am using VSCode as the editor and then the command line to run the unit tests.

Parts

Since this will be ongoing, I am going to break it into a number of parts, listed below (this list will be updated over time):

  1. Hello World
  2. Java To Kotlin Converter
  3. Named Arguments
  4. Default Arguments
  5. Lambdas
  6. String Templates
  7. Data Classes
  8. Nullable Types
  9. Smart Casting
  10. Extension Functions and Extensions On Collections
  11. Object Expressions and SAM Conversions
  12. Kotlin's Elvis Operator
  13. Return when
  14. The awesome that is the backtick
  15. Collections
  16. It is a thing
  17. Operators
  18. Operators don't need to mean one thing
  19. Destructuring
  20. For Loop
  21. Invoke
  22. Looking at the In Operator & Contains
  23. The .. operator
  24. Todo
  25. By
  26. The lazy delegate
  27. The Observable Delegate (with a slight detour on reference functions)
  28. The map delegate
  29. The vetoable delegate
  30. The notnull delegate and lateinit