Sorted Containers for Go

This is a Go implementation of sorted containers, inspired by the Python sortedcontainers library. The SortedList provides efficient insertion, deletion, and searching operations with O(log n) time complexity.

Installation

go get github.com/isdmx/sortedcontainers/sortedlist

Usage

Basic Usage

package main

import (
    "fmt"
    "github.com/isdmx/sortedcontainers/sortedlist"
)

func main() {
    // Create a new sorted list
    sl := sortedlist.New(3, 1, 4, 1, 5, 9, 2, 6)
    fmt.Println(sl) // Output: SortedList([1 1 2 3 4 5 6 9])

    // Add elements
    sl.Add(0)
    sl.Add(7)
    fmt.Println(sl) // Output: SortedList([0 1 1 2 3 4 5 6 7 9])

    // Check if element exists
    fmt.Println(sl.Contains(5)) // Output: true
    fmt.Println(sl.Contains(8)) // Output: false

    // Get element by index
    val, err := sl.At(5)
    if err == nil {
        fmt.Println(val) // Output: 5
    }

    // Remove element
    removed := sl.Remove(5) // returns true if removed
    fmt.Println(removed)    // Output: true
    fmt.Println(sl)         // Output: SortedList([0 1 1 2 3 4 6 7 9])
}

Common Operations

// Create empty sorted list
sl := sortedlist.New[int]()

// Add elements one by one
sl.Add(10)
sl.Add(5)
sl.Add(15)
sl.Add(5)  // Duplicates allowed
fmt.Println(sl) // Output: SortedList([5 5 10 15])

// Update with multiple values at once
sl.Update([]int{1, 20, 8})
fmt.Println(sl) // Output: SortedList([1 5 5 8 10 15 20])

// Get length
fmt.Println(sl.Len()) // Output: 7

// Get element at index
val, _ := sl.At(0)  // First element
fmt.Println(val)    // Output: 1

// Get last element
val, _ = sl.At(-1)
fmt.Println(val)    // Output: 20

Search Operations

sl := sortedlist.New(1, 2, 3, 4, 5, 7, 8, 9)

// Find index of element
index := sl.IndexOf(5)
fmt.Println(index) // Output: 4

// Binary search operations
left := sl.BisectLeft(6)   // Index to insert 6 to keep sorted order (on the left)
right := sl.BisectRight(6) // Index to insert 6 to keep sorted order (on the right)
fmt.Println(left, right)   // Output: 5 5

// Count occurrences
sl.Add(5)
count := sl.Count(5)
fmt.Println(count) // Output: 2 (now there are 2 occurrences of 5)

Range and Slicing Operations

sl := sortedlist.New(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

// Get slice of elements (from index 2 to 7, exclusive)
start, stop := 2, 7
slice := sl.Slice(&start, &stop)
fmt.Println(slice) // Output: [2 3 4 5 6]

// Iterator over index range
for val := range sl.Islice(&start, &stop, false) {
    fmt.Print(val, " ") // Output: 2 3 4 5 6
}
fmt.Println()

// Iterator over value range
min, max := 3, 7
for val := range sl.Irange(&min, &max, true, true, false) { // inclusive range [3,7]
    fmt.Print(val, " ") // Output: 3 4 5 6 7
}
fmt.Println()

// Reverse iterator over value range
for val := range sl.Irange(&min, &max, true, true, true) { // reverse order
    fmt.Print(val, " ") // Output: 7 6 5 4 3
}
fmt.Println()

Iteration

sl := sortedlist.New(1, 3, 5, 7, 9)

// Iterate through all elements
for val := range sl.All() {
    fmt.Print(val, " ") // Output: 1 3 5 7 9
}
fmt.Println()

// Iterate in reverse
for val := range sl.Reversed() {
    fmt.Print(val, " ") // Output: 9 7 5 3 1
}
fmt.Println()

// Get all values as slice
values := sl.Values()
fmt.Println(values) // Output: [1 3 5 7 9]

Advanced Operations

sl := sortedlist.New(1, 2, 3, 4, 5)

// Remove element by value (returns true if found)
success := sl.Remove(3)
fmt.Println(success) // Output: true

// Remove element by index
val, err := sl.Pop(0) // Remove first element
if err == nil {
    fmt.Println(val) // Output: 1
}

// Try remove that doesn't exist
success = sl.Remove(100)
fmt.Println(success) // Output: false

// Safe removal (no error if element doesn't exist)
sl.Discard(100) // No error even if not found

// Remove element with error if not found
err = sl.RemoveValue(2)
if err != nil {
    fmt.Println("Error:", err)
}

// Get shallow copy
copied := sl.Copy()
fmt.Println(copied) // Copy of the sorted list

// Get index with bounds checking
index, err := sl.Index(4)
if err == nil {
    fmt.Println("Index of 4:", index)
}

Delete Operations

sl := sortedlist.New(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

// Delete by index
err := sl.DeleteAt(0) // Remove first element
if err == nil {
    fmt.Println("Deleted first element")
}

// Delete by index range
start, stop := 2, 5
err = sl.DeleteSlice(&start, &stop)
if err == nil {
    fmt.Println("Deleted slice [2, 5)")
}

// Clear all elements
sl.Clear()
fmt.Println(sl.Len()) // Output: 0

API Reference

Constructor

• New[T cmp.Ordered](values ...T) *SortedList[T] - Creates a new sorted list with optional initial values

Adding Elements

• Add(value T) - Add value to sorted list in correct position
• Update(values []T) - Add multiple values at once
• Copy() - Create a shallow copy of the list

Accessing Elements

• At(index int) (T, error) - Get element at index (supports negative indices)
• Len() - Get number of elements
• Values() - Get all values as a slice
• All() - Iterator over all elements
• Reversed() - Iterator over all elements in reverse order

Searching

• Contains(value T) bool - Check if value exists
• IndexOf(value T) int - Get first index of value (-1 if not found)
• Index(value T) (int, error) - Get index of value (errors if not found)
• Count(value T) int - Count occurrences of value
• BisectLeft(value T) int - Index to insert keeping sorted order (left)
• BisectRight(value T) int - Index to insert keeping sorted order (right)
• Bisect(value T) int - Alias for BisectRight

Removing Elements

• Remove(value T) bool - Remove first occurrence (returns true if found)
• RemoveValue(value T) error - Remove first occurrence (errors if not found)
• Discard(value T) - Remove if present, no error if missing
• Pop(index int) (T, error) - Remove and return element at index
• DeleteAt(index int) error - Remove element at index
• DeleteSlice(start, stop *int) error - Remove elements in index range
• Clear() - Remove all elements

Range Operations

• Slice(start, stop *int) []T - Get slice of elements by index range
• Islice(start, stop *int, reverse bool) iter.Seq[T] - Iterator by index range
• Irange(minimum, maximum *T, inclusiveLeft, inclusiveRight bool, reverse bool) iter.Seq[T] - Iterator by value range

Type Conversion & Errors

• String() - String representation
• Append(value T) error - Raises error (not supported)
• Extend(values []T) error - Raises error (not supported)
• Insert(index int, value T) error - Raises error (not supported)
• Reverse() error - Raises error (not supported)

Pre-commit Setup

This project uses pre-commit hooks to ensure code quality and consistency. To set up pre-commit for this project:

1. Install pre-commit (if not already installed):

   pip install pre-commit
   # or on macOS with Homebrew: brew install pre-commit

2. Install the git hooks:

   pre-commit install

3. The following checks will now run automatically before each commit:

   • Go formatting and import organization
   • Go linters and static analysis
   • Code quality checks (cyclomatic complexity, security issues, etc.)
   • File formatting (trailing whitespace, end of file, etc.)
   • Go module tidying
   • Unit tests execution
   • Build validation

4. To run all checks manually on all files:

   pre-commit run --all-files

Development Commands

To install required tools for development:

go mod tidy
go install github.com/golangci/golangci-lint/cmd/golangci-lint@latest

Testing

Run all tests:

go test ./...

Run benchmarks:

go test -bench=. ./sortedlist

Run tests with coverage:

go test -coverprofile=coverage.out ./sortedlist && go tool cover -func=coverage.out

Performance

The SortedList implementation provides the following time complexities:

• Add: O(log n) average
• Remove: O(log n) average
• Contains: O(log n)
• At/Pop: O(log n)
• Update: O(k log n) where k is number of new elements
• Count: O(log n + c) where c is count of element

Project Structure

• sortedlist.go: Main SortedList implementation
• sortedlist_test.go: Core functionality tests
• sortedlist_extra_test.go: Additional tests
• sortedlist_new_methods_test.go: Tests for new methods
• sortedlist_final_coverage_test.go: Coverage-focused tests
• sortedlist_bench_test.go: Benchmark tests