LexoRanks — what are they and how to use them for efficient list sorting

Published in

Whisper Arts

9 min readSep 1, 2020

In this article, we will explain what LexoRank is and how we used them in our mobile app to effectively sort lists and drag and drop items.

Drag and drop is a popular feature in applications. However, by implementing this functionality, you should be aware of some nuances: a large number of elements, recalculation of the positions every time and some additional logic if you have different sections in the list.

In this article we’ll explain how to avoid troubles, reduce the number of calculations and how LexoRanks helped us in this.

Let’s denote the problem

So, you decided to add the drag and drop feature in your application. You have to sort the elements somehow, right? Otherwise, there’s no point in drag and drop.

What’s the first thing that comes to mind?

Positions

The most common solution is to use positions. Numbers from 1 to infinity. It is easy and convenient to work with them, the elements are sorted without problems. At a glance, everything seems fine.

Then what’s wrong with the numerical position?

The problem is in additional operations. For example, we need to move the first element and put it between the second and third elements.

So we need to update 3 records items in the database. If we have a list with 10 positions — we need to update all these 10 records in the list (if we move the item from the 1st to the last place in the list). So when we move one item we need to update all neighbours.

Data in our app is synchronised with the server. So another problematic operation is updating the data on the server. After updating the item order in the list in the app — you need to send updated information to the server. And the server needs to send this update to everyone who is “listening” to this list of tasks. The more users change the order of tasks in the list, the more data need to be sent to the server, and the more data the server need to send to clients.

So if we moved only one item, we need to update information about all its neighbours.

Conclusion: we want to use something more optimal.

We want to use a solution that needs to update only one element in the list — the one that we moved.

Solution 1 — to use big integer numbers for the positions

We will place all elements in some standard positions at equal intervals (steps).

The first element will have a position equal to 1, and the second element will have a position equal to 1000.
When the user wants to drag something between these two elements, we will calculate the average position — (1000 + 1) / 2 = 500.
And so on and so on for other elements.

I think you know what’s wrong with this solution. We are limited in the number of steps that can be taken. I mean, between 1 and 1,000 and 500. Between 1 and 500, 250. Then 125… and eventually there’s no numbers left. Increasing the number of steps doesn’t solve the problem.

Solution 2 — to use fractional numbers

Can we use fractional numbers?

No, fractional numbers don’t fix the problem, they just delay the moment it occurs.

Solution 3

After making a brainstorm and Googling, we found a video about LexoRanks and how they are used it in Jira.

Here is the video:

LeksoRanks based on three things:

Strings are easy to sort alphabetically.
Between two strings you can find the average (not always, and it is not so easy).
If there is no way to find the average — you can use the buckets (sounds weird, yeah)

Everything is clear about alphabetical ordering .

So let’s go straight to section 2. How to find the average?

There are letters in the English alphabet “a” and “c” and between them, obviously “b”. But how do you find that “b” mathematically?

We can represent the letter as a code. For the letter “a” the code is 141. For the letter “с” the code is 143. The difference between codes will be 2 (a-b=143–141=2).
And let’s divide the result in half. We got 1.
And now, if we add one to the code “a”, we will get the code of the letter “b”.

A combination of English letters is called LexoRanks.

And what if between two items there is no free space? So for this reason we will use buckets.

The bucket is a mark before the rank. Looks like this: “0|aaa”. Here 0 is the bucket number. When there is no space left, the elements are moved from one bucket to another, and the labels are placed anew while keeping the order. That’s all the magic!

How we used LexoRanks in our project

How do we find the average between the two strings?

Let’s take two strings: “aa” and “cc” and find the average between them.

After a symbolic subtraction (described above) we get the number 11.

But what do we do next? You may think that you just need to add the result to the line “aa”. You’ll really get the line “bb” between “aa” and “cc”, but the algorithm will be wrong and now we’ll see why.

Let’s think, what does it look like? “aa,” “cc,” “11.” It looks like some kind of notation. What kind of notation? Base-26 notation! Why is that? Because the English alphabet has 26 letters.

Now we need to translate the result “11” from the base-26 notation to the decimal notation.

The formula is pretty simple:

X = y(0) + y(1) * size + y(2) * size^2 … y(n) * size^(n-1)

where “size” is the base of the notation (in this case size = 26) and y(n) — n-th number on the right

Let’s remember this formula as, for example, Formula 1, we will get back to it later.

Let’s put our numbers in formula and we get: 2 + 2 * 26 = 54. Now we know how many characters there are between “aa” and “cc”. But we need to take the average between those two. We divide 54 by 2, we get 27. All we have to do now is add our result to “aa” codes correctly.

How do we do that? First, we find how much we need to add to the first (right) symbol. To do this, we will get the remainder of the division of 27 by 26. We’ll get 1. We add 1 to “a” — we get the letter “b”.

Now we have to find out by how many characters we need to move the second character.

The following formula will help us:

X = Y / size^(n-1) % size

Using this formula, we can find out how much we need to add to a certain place (the symbol is set with n).

When we put everything in there, we get

(n = 2): (27/ 26) % 26 = 1.

Let’s add it up. We get the final result “bb”.

Implementing an algorithm in a programming language is not so difficult when you know exactly how it works. Below I’ve added the implementation of the algorithm in Dart language (the application, in which this problem solved, written in Flutter).

String getRankBetween({@required String firstRank, @required String secondRank}) {assert(firstRank.compareTo(secondRank) < 0, "First position must be lower than second. Got firstRank $firstRank and second rank $secondRank");/// Make positions equal
while (firstRank.length != secondRank.length) {
  if (firstRank.length > secondRank.length)
    secondRank += "a";
  else
    firstRank += "a";
}var firstPositionCodes = [];
firstPositionCodes.addAll(firstRank.codeUnits);var secondPositionCodes = [];
secondPositionCodes.addAll(secondRank.codeUnits);var difference = 0;for (int index = firstPositionCodes.length - 1; index >= 0; index--) {
  /// Codes of the elements of positions
  var firstCode = firstPositionCodes[index];
  var secondCode = secondPositionCodes[index];  /// i.e. ' a < b '
  if (secondCode < firstCode) {
    /// ALPHABET_SIZE = 26 for now
    secondCode += ALPHABET_SIZE;
    secondPositionCodes[index - 1] -= 1;
  }  /// formula: x = a * size^0 + b * size^1 + c * size^2
  final powRes = pow(ALPHABET_SIZE, firstRank.length - index - 1);
  difference += (secondCode - firstCode) * powRes;
}var newElement = "";
if (difference <= 1) {
  /// add middle char from alphabet
  newElement = firstRank +
     String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
  } else {
    difference ~/= 2;    var offset = 0;
    for (int index = 0; index < firstRank.length; index++) {
      /// formula: x = difference / (size^place - 1) % size;
      /// i.e. difference = 110, size = 10, we want place 2 (middle),
     /// then x = 100 / 10^(2 - 1) % 10 = 100 / 10 % 10 = 11 % 10 = 1
     final diffInSymbols = difference ~/ pow(ALPHABET_SIZE, index) % (ALPHABET_SIZE);     var newElementCode = firstRank.codeUnitAt(
        secondRank.length - index - 1) + diffInSymbols + offset;
     offset = 0;     /// if newElement is greater then 'z'
     if (newElementCode > 'z'.codeUnits.first) {
       offset++;
       newElementCode -= ALPHABET_SIZE;
     }
     
     newElement += String.fromCharCode(newElementCode);
  }  newElement = newElement
  .split('')
  .reversed
  .join();
 }return newElement;
}

But that’s not all

Anyway, that wasn’t the end for us. We were adding this feature to an already released application, so we needed to migrate user data. Writing a migration for SQL is not a problem, but it is not so easy to calculate the standard ranks. But knowing how to find average it becomes easy to do. The algorithm is the following:

set the beginning and end of the gap (we have “aaa” and “zzz” respectively)
consider how many combinations of different characters between strings Formula 1 can help us.
now divide what we’ve got by the maximum number of items on the list.
so, we have a step, we have an initial position, we just have to add a step to the initial position, get a rank, then add a step to that rank, get a new rank, then add a step again and so on.

The parameter forNumOfTasks is responsible for how many positions you get. If you put positions for the list with only 3 items, it makes no sense to calculate positions for the entire list (50, 100, or something else).

Our implementation of finding ‘default’ ranks

/// modify field forNumOfTasks to get certain number of positions
List<String> getDefaultRank({int forNumOfTasks = TASK_FOR_PROJECT_LIMIT_TOTAL}) {
final startPos = START_POSITION;
final endPos = END_POSITION;final startCode = startPos.codeUnits.first;
final endCode = endPos.codeUnits.first;
final diffInOneSymb = endCode - startCode;/// x = a + b * size + c * size^2
final totalDiff = diffInOneSymb + diffInOneSymb * ALPHABET_SIZE + diffInOneSymb * ALPHABET_SIZE * ALPHABET_SIZE;/// '~/' – div without remainder
final diffForOneItem = totalDiff ~/ (TASK_FOR_PROJECT_LIMIT_TOTAL + 1);/// x = difference / size^(place - 1) % size
final List<int> diffForSymbols = [
diffForOneItem % ALPHABET_SIZE,
diffForOneItem ~/ ALPHABET_SIZE % ALPHABET_SIZE,
diffForOneItem ~/ (pow(ALPHABET_SIZE, 2)) % ALPHABET_SIZE
];List<String> positions = [];
var lastAddedElement = startPos;
for (int ind = 0; ind < forNumOfTasks; ind++) {
var offset = 0;
var newElement = "";
for (int index = 0; index < 3; index++) {
final diffInSymbols = diffForSymbols[index];var newElementCode = lastAddedElement.codeUnitAt(2 - index) + diffInSymbols;
if (offset != 0) {
newElementCode += 1;
offset = 0;
}/// 'z' code is 122 if 'll be needed
if (newElementCode > 'z'.codeUnitAt(0)) {
offset += 1;
newElementCode -= ALPHABET_SIZE;
}final symbol = String.fromCharCode(newElementCode);
newElement += symbol;
}/// reverse element cuz we are calculating from the end
newElement = newElement.split('').reversed.join();
positions.add(newElement);
lastAddedElement = newElement;
}positions.sort();
return positions;
}

Ewww, are you tired? The hardest part is behind, just a little bit left!

We didn’t really like the bucket idea. Objectively, it’s good. But we didn’t like the idea of having a “recovery” algorithm: if the positions are over — recover with buckets! So we say no to buckets. However, the ranks are not infinite, so we have to think of something else.

And we’ve come up with

If there is no space left between the lines, we decided to simply add the middle letter of the English alphabet (“n”) to the lower boundary. If we want to insert an element between “aa” and “ab”, we get “aa”, “aan” and “ab”. Due to the fact that strings are sorted element by element from left to right, line prolongation will not spoil the sorting. But we have space for new elements without any recovery algorithms.

This piece of code can also be found in our algorithm.

if (difference <= 1) {
  /// add middle char from alphabet
  newElement = firstRank +
    String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
}

Results

For us LexoRanks seems to be a great indexing tool, the use of which optimizes the work with the database and the server: when moving the task in list, you need to update only one modified item.

And for all readers of our blog, we offer to try the result that we have achieved. Get the list from our app and try to sort it out by drag and drop items.

And now I want to share with you my list of 10 best movies that you can to watch with your kids.