The Myers Diff Algorithm and Kotlin Observable Properties — how to connect them to make a developer’s life easier

Adrian Defus
Feb 7 · 7 min read

Have a look at the animation below — it’s a group of multi-color elements moving between each other after the button is pressed. From the developer’s point of view they are placed inside the RecyclerView with proper Adapter and LayoutManager attached.

Smooth movement between elements

When the new list is generated it replaces the old one and then the Adapter is notified about changes. If we don’t know anything about differences between lists we can use the notifyDataSetChanged() function to perform this notification, or if we have any more information, we can use additional notify-functions, like e.g. notifyItemInserted(position: Int), notifyItemMoved(fromPosition: Int, toPosition: Int), etc.

Now let’s take a look at the version control like Git, where we always see numerous differences in the code — some lines are inserted, others are deleted, and others are modified. Do you see the similarity between this behavior and notifying our Adapter? Have you ever wondered how those edited lines are calculated to find the best matching difference between old and new versions of a content?

Modifications in a file tracked by a git version control

Myers’ Diff Algorithm

Let’s take two sequences of characters — the first of them will be the one already existing (old version), and the second one will be the “output” with some modifications made (new version).

S1 = C B A B AS2 = A C A B B

Our goal is to calculate the best “difference” between them, which means finding a sequence of edits that will convert string S1 into S2. We can achieve this by playing a simple game, so let’s draw a board.

First, we need to put our strings on the right places. String S1 will be at the top of the board, and S2 on the left side. If we draw vertical and horizontal lines, each starting between the characters of our strings, we will create our playground consisting of squares. Additionally, we need to mark each line with a number (starting from 0) to know our exact position during the game. For example, the point (2,4) tells us that we are at the intersection of the vertical line 2 (x-axis) and the horizontal line 4 (y-axis). In our case, the board will look like this:

Base Diff board

The next step is to create “special” squares with a diagonal line going from the top left to the bottom right. The “special” square is the one which has corresponding characters (the letters to the left and to the top of it are the same). Let’s draw all the diagonal lines on the board.

Diff board with ‘special’ squares

The main goal of our game is to find the shortest way from the top-left corner (0,0) to the bottom-right (5,5). In each round we are allowed to move only by one step along the edge of the squares. If we reach the “special” point where the square’s diagonal starts, we can use it for free in the same step. Let’s start with round 0:

Diff game (Round 0)

We place the point at (0,0). From there we are able to move to the right (1,0) or to the bottom (0,1) with the additional free step to (1,2). Let’s draw our path after the first round.

Diff game (Round 1)

In round 2, we can take the following paths:

  • From (1,0) to (1,1)
  • From (1,0) by (2,0) to (3,1)
  • From (1,2) by (1,3) to (2,4)
  • From (1,2) by (2,2), (3,3) to (4,4)

After round 2, the state on the board is as follows:

Diff game (Round 2)

Let’s now see the full visualization of all rounds. After reaching (5,5), the paths that connect it with (0,0) are marked in green — there are two of them, so we will have two correct diff results in our game.

Diff game (whole visualization)

After having the correct paths, we can now use them to mark the differences between our strings. These are the rules that we have to follow:

  • Every vertical move is considered inserting the corresponding character into the square we are moving towards from the ‘new’ string (S2) — e.g. moving between (0,0) and (0,1) means inserting the ‘A’ character from S2
  • Every horizontal move is considered deleting the corresponding character into the square we are moving towards from the ‘old’ string (S1) — e.g. moving between (0,0) and (1,0) means deleting the ‘C’ character from S1
  • Every diagonal move is considered leaving the corresponding character in the square we are moving towards (remember that diagonals are placed in squares with the same corresponding letters)

Let’s write the edit sequence for each of the correct paths (top green and bottom green).

As you can see, each Diff sequence consists of two insertions and two deletions, and both of them can be used to mark the right difference between our strings. Let’s skip the Myers algorithm implementation step (you can find it in countless sources on the internet), and let’s take a look at how to use it to improve Android applications written in the Kotlin language.

DiffUtil

DiffUtil is the Android utility class which is the implementation of the Myers Algorithm with an additional second run to detect whether specific items were moved. It automatically dispatches updates to the RecyclerView Adapter, so the list elements change smoothly according to the way they were actually updated.

Assuming that we have the RecyclerView.Adapter implementation with the list of SampleItem types, we can use the DiffUtil class to calculate the difference between the existing state of the list element and the one we’ve just received.

As you can see, there is no need to use any of the notify functions to update the view — we just have to specify the difference between the list elements by creating an object that implements the DiffUtil.Callback interface, dispatch the DiffResult to the adapter, and the DiffUtil will do all the work for us. Let’s create some modifications by using Kotlin-specific elements to receive the developer-friendly RecyclerView.Adapter tool.

Kotlin extension functions and Delegated properties

Kotlin provides the ability to extend a class with the new functionality without having to inherit from it — called the extension function. Let’s create a RecyclerView.Adapter extension function which will dispatch updates to the view for two lists passed as the function parameters (the old and the new one).

Note that this list type has to implement the DiffItem interface, so the developer is able to indicate which elements of his custom class are specific to perform update operations properly.

After having the RecyclerView.Adapter extension function implemented, we can use another Kotlin-specific element — observable property. Observable property is a property with the delegated listener attached which gets notified about any modifications of its value.

Attaching the Observable delegate to our property will allow us to be notified about any changes of its value in onChange() function, which contains both the old and new values. We can use our autoNotify() adapter extension function within it, so right after the list modification is performed, the view will automatically be updated.

Although we have created a more developer-friendly implementation of the DiffUtil class, we still have to write all of these complicated elements of the code in order to attach our observable delegate and extension function. Let’s create the last modification — our custom adapter-item delegate extension.

Having the property of type List<DiffItem>, we can easily use our newly created delegate, and stop worrying about any additional unnecessary notify-function calls with quite friendly usage.

And that’s it. You can download these extensions packed as an android library just by adding the line below to your build.gradle file. Happy coding!

Want to read more exciting tech articles? Visit skyrise.tech blog!

Skyrise

Our selected toughts about technology, business, innovation and more. Information about us on skyrise.tech. Any questions or ideas — say hi@skyrise.tech ;)

Adrian Defus

Written by

Android Developer at www.skyrise.tech, Kotlin enthusiast

Skyrise

Skyrise

Our selected toughts about technology, business, innovation and more. Information about us on skyrise.tech. Any questions or ideas — say hi@skyrise.tech ;)

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade