LexoRank

A .NET implementation of the Atlassian LexoRank algorithm. LexoRank is a ranking system that allows for efficient reordering of items in a list without requiring updates to other items.

Features

• Core LexoRank Logic: Full implementation of buckets, base36 arithmetic, and rank generation.
• Timestamp Conversion: Convert timestamps to LexoRank values to preserve chronological order.
• String-based Calculation: Helper methods to calculate ranks between two strings.
• Thread-Safe: Immutable design ensures safe concurrent access.
• Robust: Handles edge cases and ensures correct rank distribution.

How It Works

LexoRank is a ranking system that uses lexicographically ordered strings to maintain item positions. Unlike traditional integer-based ranking systems, LexoRank allows you to insert items between any two existing items without updating other items in the list.

Key Concepts

Base36 Encoding: LexoRank uses base36 (0-9, a-z) to represent rank values, providing a large namespace for positions.

Buckets: The system uses three buckets (0, 1, 2) to manage rebalancing. When a bucket becomes too dense with items, you can move items to another bucket to maintain spacing.

Between Operation: The core operation calculates a rank between two existing ranks by finding the lexicographic midpoint.

Example

var rank1 = LexoRank.Min();           // "0|000000:"
var rank2 = LexoRank.Max();           // "0|zzzzzz:"
var middle = rank1.Between(rank2);    // "0|hzzzzz:"
var next = middle.GenNext();          // "0|i00007:"

Performance Characteristics

• Insert Between: O(1) - No other items need to be updated
• Generate Next/Previous: O(1) - Constant time operation
• String Comparison: O(n) where n is the length of the rank string (typically 8-10 characters)
• Memory: Each rank is approximately 8-10 bytes as a string
• Thread Safety: All operations are thread-safe due to immutable design

When to Rebalance

While LexoRank minimizes updates, you may need to rebalance when:

• Ranks become very long (>20 characters) due to many insertions
• A bucket becomes too dense
• You want to optimize for shorter rank strings

Rebalancing involves moving items to a different bucket or regenerating ranks with better spacing.

Installation

Install the package via NuGet:

dotnet add package Innoloft.LexoRank

Usage

Basic Usage

using LexoRank;

// Get the minimum and maximum ranks
var min = LexoRank.Min();
var max = LexoRank.Max();

// Get the middle rank
var middle = LexoRank.Middle();

// Generate the next rank
var next = middle.GenNext();

// Generate the previous rank
var prev = middle.GenPrev();

// Calculate a rank between two ranks
var between = min.Between(max);

Timestamp to LexoRank

You can convert a DateTime to a LexoRank. This is useful for initializing ranks based on creation time.

var now = DateTime.UtcNow;
var rank = LexoRank.FromTimestamp(now);

String-based Calculation

If you are storing ranks as strings and want to calculate a new rank between two existing rank strings:

string prevRank = "0|000000:";
string nextRank = "0|zzzzzz:";

// Calculate rank between prev and next
var newRank = LexoRank.CalculateBetween(prevRank, nextRank);

// Calculate rank at the beginning (before nextRank)
var startRank = LexoRank.CalculateBetween(null, nextRank);

// Calculate rank at the end (after prevRank)
var endRank = LexoRank.CalculateBetween(prevRank, null);

Buckets

LexoRank uses buckets to manage rebalancing. This implementation supports the standard 3 buckets (0, 1, 2).

// Get the bucket of a rank
var bucket = rank.Bucket;

// Move to the next bucket
var nextBucketRank = rank.InNextBucket();

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

1. Fork the repository
2. Create your feature branch (git checkout -b feature/AmazingFeature)
3. Commit your changes (git commit -m 'Add some AmazingFeature')
4. Push to the branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

License

MIT