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 controlMyers’ Diff AlgorithmLet’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 BOur 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 boardThe 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’ squaresThe 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 S2Every 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 S1Every 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.
DiffUtilDiffUtil 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 propertiesKotlin 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!.