How to Sort Large Draggable Lists in Your Database

Lexicographical Sorting of Indeterminate List Lengths

Feb 2 · 25 min read

If you are trying to build an extensive list of sortable items, you are probably familiar with issues related to database storage. Having a number indicating an item's place in the list runs into pretty significant efficiency issues as these algorithms are O(n) where n is the number of database updates. Many solutions online use a large number to represent the order due to the in-between spaces. For example, the first position may be 1000, then 2000, etc. This certainly has initial advantages as inserting an item between two existing ones can be done in only a few steps. Unfortunately, this can eventually also lead to O(n) when we consider that a user may eventually get to a state where all of the items in the list are sequential. When considering this problem, there are solutions that allow for finding a midpoint between two existing items without resorting to O(n). The first is using a decimal, as shown in the example here:

1
2
3
4
5
6
7
8
9
10
const midPoint = (previous, next) => ((next - previous) / 2) + previous;

export default (previous, next) => {
if (!next && !previous) return 0.5;
if (!next) return midPoint(previous, 1);

if (!previous) return midPoint(0, next);

return midPoint(previous, next);
};

We could start with values between 0 and 1 and implement an algorithm to create an order sequence with O(1). Unfortunately, this is where the good news for this solution ends. The number of decimal places required increases with every three insertions as the midpoint will require adding an extra decimal place. These long decimals can cause issues when preserving order when moving between systems that handle decimals differently, as precision might be lost.

The second solution is a lexicographical order value. This solution is much longer than the decimal one, has more edge cases to account for, but has none of the precision issues. This allows for a more robust solution with more flexibility for handling insertions. Lexicographical order uses strings and ASCII values to replace numbers in data sorting. For a recent solution, we used all letters in capital and lowercase as well as numbers for the lexicographical order. In a similar fashion to the decimal solution, this algorithm begins by recognizing that there are four initial statuses that the insertion may encounter for any order strings previous and next.

  • Empty list: There is no previous value and no next value.

  • Inserting at the end: There is no next value.

  • Inserting at the beginning: There is no previous value.

  • Inserting in between two existing values: previous and next order values exist.

1
2
3
4
5
6
7
8
9
10
11
export default ({ previous, next }) => {
 if (!next && !previous) return 'UUUUU';
 if (!next) return incrementBy(previous, 2);
 if (!previous) return decrementBy(next, 2);
 
const midValue = getMidPoint({ previous, next });
 if (midValue > previous && midValue < next) return midValue;
 if (previous.length > next.length) return handleIncrement(previous);
 if (next.length > previous.length) return decrement(next, false);
 return `${previous}U`;
};

In the above example, the first few lines are fairly self-explanatory. If given no previous or next values, return a string that can be considered a midpoint in the ASCII characters list. If presented with no next value, we increment from the previous position as there are no items after to worry about. If provided with no next, we assume we are adding to the end. In the case of no previous, we can do the same as the prior case by using decrementing instead. The functions of decrementBy and incrementBy will be explained below. The fourth case is the more complicated one. We want to grab the midpoint between previous and next to place the new item. The function for this will also be explained below.

As you can see from the example, this will not always work. There are sets of strings that have no midpoint between them. An example of this might be the string ‘aaaa’ and ‘aaab’. As there is no character between these two strings. We will try incrementing the previous to see if this would return a valid position between the two. In this case, it would not and we would need to try to decrement next. Because they are adjacent and neither incrementing nor decrementing work, the final step of adding a ‘U’ after the previous will return a valid result. The only time adding a U to the end of previous would not work is covered by decrement.

We can now break down increment, handleIncrement and incrementBy. IncrementBy is simply a function that uses increment on a string, jumping x number of characters from the right so as to leave some space in between. The function handleIncrement accounts for some edge cases and the removal of hanging zeros which we will discuss below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 const increment = (stringReplace, allowHangingZeros) => {
 const previousLastChar = stringReplace.slice(-1);
 const plcIndex = characters.indexOf(previousLastChar);
 if (stringReplace.length === 1 && plcIndex === characters.length - 1) {
   return null;
 }
 if (plcIndex === characters.length - 1) {
   const prevValue = increment(stringReplace.slice(0, -1), true);
   let nextChar = characters[0];
   if (prevValue === null) return null;
   if (!allowHangingZeros) {
     nextChar = '1';
     return `${stringReplace}${nextChar}`;
   }
   return `${increment(stringReplace.slice(0, -1), true)}${nextChar}`;
 }
 return `${stringReplace.slice(0, -1)}${characters[plcIndex + 1]}`;
};
 
const handleIncrement = (stringReplace) => {
 const incrementResult = increment(stringReplace, false);
 return incrementResult || `${stringReplace}1`;
};
 
const incrementBy = (stringToIncrement, columnsFromRightToIncrement) => {
 if (stringToIncrement.length <= columnsFromRightToIncrement) {
   return handleIncrement(stringToIncrement);
 }
 const savedChars = stringToIncrement.slice(-columnsFromRightToIncrement);
 const prefixToIncrement = stringToIncrement.slice(0, -columnsFromRightToIncrement);
 const incremented = increment(prefixToIncrement, true);
 let prefix = incremented;
 if (!incremented) {
   prefix = prefixToIncrement;
 }
 return `${prefix}${savedChars}${incremented ? '' : '1'}`;
};

Increment is a relatively simple recursive function that finds the character on the end of a string and replaces it with the character next in the sequence. There are some edge cases that handleIncrement and increment itself use. If the string is at the end of our ASCII sequence, we need to handle an overflow. Similarly to counting, when we reach the end of our characters, 9, we need to handle the overflow to 10. In this case, a recursion would occur. Think of the example ‘az.’ After incrementing this string, we will need the string ‘b0’; thus, we recursively call increment on the string ‘a’ because of the overflow. Now you may notice a conditional statement that will not allow ‘b0’ to be returned as a string. This is because of a problem with how there can be no space between two strings when using a hanging zero. Consider the example: ‘aa’ and ‘aa0’. It is impossible to insert a string between as any incrementation or appending to ‘aa’ will be after ‘aa0’ and the same issue occurs with decrementing from the latter. As such, a boolean that prevents zeros from being on the end is set. HandleIncrement turns this boolean on for the first call, but all subsequent recursive calls may safely ignore this constraint. The next edge case is for if we try to increment, and all characters overflow, such as in ‘zzz.’ In this case, a null response from increment will result in simply adding characters to the end of the provided string to increment from, resulting in the string ‘zzz1’, again avoiding the hanging zero.

The next major function group is decrement and decrementBy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const getMidPoint = ({ previous, next }) => {
 let midPoint = '';
 const length = previous.length > next.length ? previous.length : next.length;
 for (let i = 0; i < length; i += 1) {
   let prevIndex = characters.indexOf(previous[i]);
   let nextIndex = characters.indexOf(next[i]);
   if (prevIndex < 0) prevIndex = 0;
   if (nextIndex < 0) nextIndex = 0;
   if (prevIndex === nextIndex) {
     midPoint = `${midPoint}${previous[i]}`;
   } else if (prevIndex < nextIndex) {
     const midCharIndex = Math.ceil(((nextIndex - prevIndex) / 2) + prevIndex);
     midPoint = `${midPoint}${characters[midCharIndex]}`;
   } else {
     const midCharIndex = (((((characters.length - 1) - prevIndex) + nextIndex) / 2)
       + prevIndex) % (characters.length - 1);
     midPoint = `${midPoint}${characters[midCharIndex]}`;
   }
 }
 const lastChar = midPoint.slice(-1);
 if (lastChar === '0') {
   return `${midPoint}0U`;
 }
 return midPoint;
};

These functions work in much the same way as their increment counterparts with two small distinctions. First is the direction; they decrement their way around the ASCII values. Secondly, null is returned in the infrequent occurrence that a string provided is ‘0000000.’ This indicates that a string that can not be decremented passed into the algorithm. This is an invalid state and can not be processed. It probably indicates that the present order values should be cleaned up and given new strings. Note this algorithm itself will never produce an order value similar to the one above, but it handles this case all the same.

The final function is the midpoint calculator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const getMidPoint = ({ previous, next }) => {
 let midPoint = '';
 const length = previous.length > next.length ? previous.length : next.length;
 for (let i = 0; i < length; i += 1) {
   let prevIndex = characters.indexOf(previous[i]);
   let nextIndex = characters.indexOf(next[i]);
   if (prevIndex < 0) prevIndex = 0;
   if (nextIndex < 0) nextIndex = 0;
   if (prevIndex === nextIndex) {
     midPoint = `${midPoint}${previous[i]}`;
   } else if (prevIndex < nextIndex) {
     const midCharIndex = Math.ceil(((nextIndex - prevIndex) / 2) + prevIndex);
     midPoint = `${midPoint}${characters[midCharIndex]}`;
   } else {
     const midCharIndex = (((((characters.length - 1) - prevIndex) + nextIndex) / 2)
       + prevIndex) % (characters.length - 1);
     midPoint = `${midPoint}${characters[midCharIndex]}`;
   }
 }
 const lastChar = midPoint.slice(-1);
 if (lastChar === '0') {
   return `${midPoint}0U`;
 }
 return midPoint;
};

Here, we simply go along through both strings and, if the strings are the same character at an index, then we simply add that string to that same index in the output, midpoint. If the characters are different, then we find the midpoint between them in our array of ASCII-ordered characters. Again to prevent any midpoint string from ending in a zero we perform a check to add a character at the end if that occurs. And that is it, an algorithm to create your large reorderable arrays for your database. The algorithm is now O(3m) where m is the length of the order string. Far higher efficiency than the database updates required for other solutions. See below for the complete, commented solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
// List of approved characters in their correct order so they can be used in
// sorting for order calculations. Note that 'U' is used as a middle point character
// from this list.
const characters = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
 
// **************
// To prevent states where we have no positions between to order values
// the first call of increment (calls that are not recursive calls) must
// set allow hanging zeros to false.
const increment = (stringReplace, allowHangingZeros) => {
 const previousLastChar = stringReplace.slice(-1);
 const plcIndex = characters.indexOf(previousLastChar);
 
 // In the exceptionally rare case that we reach an order value such as
 // 'zzzzz', then we need to indicate that array should increment by adding
 // a character at the end since 'Uzzzzz' < 'zzzzz'. The wrapping function MUST turn
 // this order value to 'zzzzzU' as this will order it correctly.
 if (stringReplace.length === 1 && plcIndex === characters.length - 1) {
   return null;
 }
 
 // This case is for when a character reaches '0000z' and a carry over is
 // required. In the case that a null is reached, indicating that a character
 // needs to be added to the end, it is preserved through the recursion and
 // passed up. in any other case it simply increments recursively increments
 // the string.
 if (plcIndex === characters.length - 1) {
   const prevValue = increment(stringReplace.slice(0, -1), true);
   let nextChar = characters[0];
 
   if (prevValue === null) return null;
 
   if (!allowHangingZeros) {
     nextChar = '1';
     return `${stringReplace}${nextChar}`;
   }
 
   return `${increment(stringReplace.slice(0, -1), true)}${nextChar}`;
 }
 
 // Default case where the character can simply be incremented through
 // the list of characters.
 return `${stringReplace.slice(0, -1)}${characters[plcIndex + 1]}`;
};
 
// **************
// To prevent states where we have no positions between to order values
// the first call of decrement (calls that are not recursive calls) must
// set allow hanging zeros to false.
const decrement = (stringReplace, allowHangingZeros) => {
 const previousLastChar = stringReplace.slice(-1);
 const plcIndex = characters.indexOf(previousLastChar);
 
 // In this case we need to trigger a shift for all of the values above
 // to give some room at the bottom. This is fairly rare as an occurence
 // seeing as how the users would have to move an item to the first position
 // thousands of times from a default standard value. The returning of null
 // for a new index MUST trigger a shift for all order values associated with
 // the dataset and not be placed as the new order value.
 if (stringReplace.length === 1 && plcIndex === 0) {
   return null;
 }
 
 // This case is for when the list decrements a character to the end of the list
 // but retains a null if a shift is required.
 if (plcIndex === 0) {
   const prevValue = decrement(stringReplace.slice(0, -1), true);
 
   return prevValue ? `${prevValue}${characters[characters.length - 1]}` : null;
 }
 
 // In the case of decrementing from any string ending in '1', we can not follow
 // the normal process as we can get stuck in a situation where there can be no
 // position in between two order values to insert into. For example there is no
 // position between 'aa' and 'aa0'.
 let nextChar = characters[plcIndex - 1];
 
 if (!allowHangingZeros && plcIndex === 1) {
   nextChar = '0z';
 }
 
 // This case is for when no additional calculation is required because
 // we simply shift the character one position down and no carry over
 // is required.
 return `${stringReplace.slice(0, -1)}${nextChar}`;
};
 
// **************
// This function is required to indicate if handle the case of null returns from
// Increment. This happens if a 'zzzzz' is incremented and the string needs to start
// with an extra character on the end.
const handleIncrement = (stringReplace) => {
 const incrementResult = increment(stringReplace, false);
 
 // Required conditional to add an extra character on the end if max values reached.
 // Note that a one is used instead of a zero to prevent dangling zeros. The issues
 // with these are noted above.
 return incrementResult || `${stringReplace}1`;
};
 
// **************
// Function that allows us to increment by a value that is greater than one so that
// we can minimize the amount of times that we have items directly next to one
// another. It is safest for this to be used when there is no value above this one,
// for example adding to the end of a list.
const incrementBy = (stringToIncrement, columnsFromRightToIncrement) => {
 // Note that if the incoming string is the same as the columns input then it can
 // break increment.
 if (stringToIncrement.length <= columnsFromRightToIncrement) {
   return handleIncrement(stringToIncrement);
 }
 
 // Save the characters that are being skipped over. These represent the amount of
 // space between the returned value and the inputted value.
 const savedChars = stringToIncrement.slice(-columnsFromRightToIncrement);
 
 const prefixToIncrement = stringToIncrement.slice(0, -columnsFromRightToIncrement);
 
 // The characters in the higher priority positions after they have been incremented.
 const incremented = increment(prefixToIncrement, true);
 
 // This last conditional is for the case when 'zzzzz' is the prefix. In this case
 // we need to add an extra character on the end.
 let prefix = incremented;
 
 if (!incremented) {
   prefix = prefixToIncrement;
 }
 
 return `${prefix}${savedChars}${incremented ? '' : '1'}`;
};
 
// **************
// Duplication of function above only in reverse so as to give some space when putting
// new items at the beginning.
const decrementBy = (stringToDecrement, columnsFromRightToDecrement) => {
 if (stringToDecrement.length <= columnsFromRightToDecrement) {
   return decrement(stringToDecrement, false);
 }
 
 const savedChars = stringToDecrement.slice(-columnsFromRightToDecrement);
 
 const prefixOfToDecrement = stringToDecrement.slice(0, -columnsFromRightToDecrement);
 
 const decremented = decrement(prefixOfToDecrement, true);
 
 // In the case that decrement indicates a shift is required, instead simply decrement
 // the entire string by one
 if (!decremented) return decrement(stringToDecrement, false);
 
 return `${decremented}${savedChars}`;
};
 
// **************
// Below method is the function that can handle grabbing the mid point between two
// lexicographical points.
const getMidPoint = ({ previous, next }) => {
 let midPoint = '';
 const length = previous.length > next.length ? previous.length : next.length;
 
 // Loop through both items and select midpoint char for each value.
 for (let i = 0; i < length; i += 1) {
   let prevIndex = characters.indexOf(previous[i]);
   let nextIndex = characters.indexOf(next[i]);
 
   if (prevIndex < 0) prevIndex = 0;
 
   if (nextIndex < 0) nextIndex = 0;
 
   // In the case that both strings have the same char at any given point then
   // that char should go in the new point as well.
   if (prevIndex === nextIndex) {
     midPoint = `${midPoint}${previous[i]}`;
   } else if (prevIndex < nextIndex) {
     // Handle situation where the prev and next occur without wrapping around the
     // end of the characters string.
     const midCharIndex = Math.ceil(((nextIndex - prevIndex) / 2) + prevIndex);
     midPoint = `${midPoint}${characters[midCharIndex]}`;
   } else {
     // Account for situation where the next is at the beginning of the characters list
     // and the previous character is at the end of the characters list.
     const midCharIndex = (((((characters.length - 1) - prevIndex) + nextIndex) / 2)
       + prevIndex) % (characters.length - 1);
 
     midPoint = `${midPoint}${characters[midCharIndex]}`;
   }
 }
 
 // Check to prevent that there are no dangling zeros
 const lastChar = midPoint.slice(-1);
 
 if (lastChar === '0') {
   return `${midPoint}0U`;
 }
 
 return midPoint;
};
 
// **************
// This function is called and requires the previous and next order values in order
// to calculate the new order values. Note, however that these can and in some cases
// should be null, to represent empty lists or placing an item at one end of a list.
export default ({ previous, next }) => {
 // This initial value gives some room for decrementation without causing
 // a high risk of shifting.
 if (!next && !previous) return 'UUUUU';
 
 // If there is no next this means we are moving an object to the end of
 // a list and only a simple increment is required
 if (!next) return incrementBy(previous, 2);
 
 // No additional checks are required if no previous is detected. Either this will
 // return a valid new order with a decrement or will pass back null indicating that
 // a shift will be required for all values.
 if (!previous) return decrementBy(next, 2);
 
 // The following handles situations where the new id should be between two other items.
 // Firstly we try to grab the mid point between these two items.
 const midValue = getMidPoint({ previous, next });
 
 if (midValue > previous && midValue < next) return midValue;
 
 // If the mid function fails to give us an acceptable value then we need to either increment
 // or decrement the other items based on which has the longer string. The reason for this
 // is that in the case 'aa' as previous and 'aab' as next, if we increment 'aa' we will get
 // 'ab' which will not be less than previous, but 'aaa' is after 'aa'. The same applies in
 // when previous is longer than next.
 if (previous.length > next.length) return handleIncrement(previous);
 
 if (next.length > previous.length) return decrement(next, false);
 
 // This is in the case that the strings are the same length and there is no space in between
 // for example 'aa' and 'ab'. In this case the only solution is to add an extra character to
 // the end of previous to make it 'aaU' which will provide space between both prev and next.
 return `${previous}U`;
};

Need help with your custom software development? Trying to find a web development company that can address your custom enterprise business needs? VizworX has you covered. With powerful custom application development services, we are your one-stop-shop for immersive technology, artificial intelligence and data visualization.

Web Development
Code
How-to
Technical
Learn

Subscribe to our newsletter

Stay up-to-date with our latest products and solutions

Subscribe

119 6 Ave SW #101
Calgary, AB T2P 0P8 Canada


T: 

+1 (833) 849 9679

©  2022  VizworX