fracdex

README

Fractional Indexing

This is based on Implementing Fractional Indexing by David Greenspan .

Fractional indexing is a technique to create an ordering that can be used for Realtime Editing of Ordered Sequences.

This implementation includes variable-length integers, and the prepend/append optimization described in David's article.

This should be byte-for-byte compatible with https://github.com/rocicorp/fractional-indexing.

Example

package main

import (
	"fmt"

	"roci.dev/fracdex"
)

func main() {
	first, _ := fracdex.KeyBetween("", "") // a0
	fmt.Println(first)

	// Insert after 1st
	second, _ := fracdex.KeyBetween(first, "") // "a1"
	fmt.Println(second)

	// Insert after 2nd
	third, _ := fracdex.KeyBetween(second, "") // "a2"
	fmt.Println(third)

	// Insert before 1st
	zeroth, _ := fracdex.KeyBetween("", first) // "Zz"
	fmt.Println(zeroth)

	// Insert in between 2nd and 3rd
	secondAndHalf, _ := fracdex.KeyBetween(second, third) // "a1V"
	fmt.Println(secondAndHalf)
}

Documentation

Index

• func Float64Approx(key string) (float64, error)
• func KeyBetween(a, b string) (string, error)
• func NKeysBetween(a, b string, n uint) ([]string, error)

Functions

func Float64Approx

func Float64Approx(key string) (float64, error)

Float64Approx converts a key as generated by KeyBetween() to a float64. Because the range of keys is far larger than float64 can represent accurately, this is necessarily approximate. But for many use cases it should be, as they say, close enough for jazz.

func KeyBetween

func KeyBetween(a, b string) (string, error)

KeyBetween returns a key that sorts lexicographically between a and b. Either a or b can be empty strings. If a is empty it indicates smallest key, If b is empty it indicates largest key. b must be empty string or > a.

func NKeysBetween

func NKeysBetween(a, b string, n uint) ([]string, error)

NKeysBetween returns n keys between a and b that sorts lexicographically. Either a or b can be empty strings. If a is empty it indicates smallest key, If b is empty it indicates largest key. b must be empty string or > a.