lexid

lexid

lexid is a micro library to increment lexically ordered numerical ids.

Throughout the sequence of ids, this expression will always be true, whether you are dealing with integers or strings:

older_id < newer_id

The left most character/digit is only used to maintain lexical order, so that the position in the sequence is maintained in the remaining digits.

Such ids can be useful as build or version numbers, which are often displayed by tooling which does not understand their correct ordering.

Project/Repo:

Code Quality/CI:

Name	role	since	until
Manuel Barkhau ([e-mail])	author/maintainer	2020-09	-

Usage

$ pip install lexid
$ lexid_incr 1001
1002
$ lexid_incr 1999
22000
$ lexid_incr 1
22
$ lexid_incr 1 -n 100
22
..
28
29
330
331
...
398
399
4400
4401
...

In Python.

>>> import lexid
>>> lexid.incr("1")
'22'
>>> lexid.incr("0001")
'0002'
>>> lexid.incr("0999")
'11000'

To avoid possible zero truncation issues (e.g. with "0001" -> "1") and to reduce rollovers, start at a higher number:

>>> lexid.incr("1001")
'1002'
>>> lexid.incr("1002")
'1003'
>>> lexid.incr("1999")
'22000'

Lexical Ids

The key thing to look at is how padding may eventually be exhausted. In order to preserve lexical ordering, build numbers are incremented in a special way. Examples will perhaps illustrate more clearly.

"0001"
"0002"
"0003"
...
"0999"
"11000"
"11001"
...
"19998"
"19999"
"220000"
"220001"

What is happening here is that the left-most digit is incremented early/preemptively. Whenever the left-most digit would change, the padding of the id is expanded through a multiplication by 11.

>>> prev_id  = "0999"
>>> num_digits = len(prev_id)
>>> num_digits
4
>>> prev_int = int(prev_id, 10)
>>> prev_int
999
>>> maybe_next_int = prev_int + 1
>>> maybe_next_int
1000
>>> maybe_next_id = f"{maybe_next_int:0{num_digits}}"
>>> maybe_next_id
"1000"
>>> is_padding_ok = prev_id[0] == maybe_next_id[0]
>>> is_padding_ok
False
>>> if is_padding_ok:
...     # normal case
...     next_id = maybe_next_id
... else:
...     # extra padding needed
...     next_int = maybe_next_int * 11
...     next_id  = str(next_int)
>>> next_id
"11000"

This behaviour ensures that the following semantic is always preserved: new_version > old_version. This will be true, regardless of padding expansion. To illustrate the issue this solves, consider what would happen if we did not expand the padding and instead just incremented numerically.

"0001"
"0002"
"0003"
...
"0999"
"1000"
...
"9999"
"10000"

Here we eventually run into a build number where the lexical ordering is not preserved, since "10000" > "9999" == False (because the string "1" is lexically smaller than "9"). With large enough padding this may be a non issue, but it's better to not have to think about it.

Just as an example of why lexical ordering is a nice property to have, there are lots of software which read git tags, but which have no logic to parse version strings. This software can nonetheless order the version tags correctly using commonly used lexical ordering. At the most basic level it can allow you to use the UNIX sort command, for example to parse VCS tags.

$ printf "v0.9.0\nv0.10.0\nv0.11.0\n" | sort
v0.10.0
v0.11.0
v0.9.0

$ printf "v0.9.0\nv0.10.0\nv0.11.0\n" | sort -n
v0.10.0
v0.11.0
v0.9.0

$ lexid_incr 0997 -n 5 | sort
0998
0999
11000
11001
11002

This sorting even works correctly in JavaScript!

> var versions = ["11002", "11001", "11000", "0999", "0998"];
> versions.sort();
["0998", "0999", "11000", "11001", "11002"]

Changelog for https://github.com/mbarkhau/lexid

2021.1006

• Minor packaging updates

2020.1005

• Initial release (extracted from pycalver)