orderedmap

README

ordered-map

Go has a built in 'map' datastructure that provides a key/value store. It is implemented with an unordered hashmap. A hashmap is good for many (most?) usage of a key/value store because its runtime complexity is O(1). The drawback of the go 'map' is that it is not ordered. Its can't be iterated over in order by keys. One solution is to implement an ordered map using a Red-Black search tree (or an AVL tree). These trees are O(log N) search, insert and delete with O(N) memory. They do this by a resonably tricky algorithm that keeps the tree mostly balanced at all times. Both types usupport iterating in order.

The reference for the algorithm is Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. This site has code for many algorithms and data structures, along with a textbook and a video course. The Go implementation here is based on the original Java code from .

The original port was made automatically using Anthropic Claude-3.5-Sonnet and aider-chat. The Java code is very extensive and complete, and the Go version is a manually pared down subset that supports functions similar to what a Go map provides, including Get, Put, Delete, Contains, IsEmpty and iterate over (in order).

Rust Implementation

A Rust implementation of the OrderedMap is also available. The Rust version provides similar functionality to the Go version, including methods for getting, putting, deleting, and checking the existence of keys, as well as iterating over keys in order.

Usage

To use the Rust implementation, add the following to your Cargo.toml:

[dependencies]
orderedmap = { path = "path/to/orderedmap" }

Then, in your Rust code, you can use the OrderedMap as follows:

use orderedmap::OrderedMap;

fn main() {
    let mut map = OrderedMap::new();

    map.put("C", 3);
    map.put("A", 1);
    map.put("G", 5);
    map.put("H", 6);
    map.put("B", 2);
    map.put("F", 4);

    println!("Size: {}", map.size());
    println!("Contains 'B': {}", map.contains("B"));
    println!("Value of 'C': {:?}", map.get("C"));

    map.delete("B");

    println!("Size after deleting 'B': {}", map.size());

    println!("Keys: ");
    for key in map.keys() {
        println!("{}: {:?}", key, map.get(key));
    }
}

Documentation

Index

• Constants
• type OrderedMap
  • func NewOrderedMap[K constraints.Ordered, V any]() *OrderedMap[K, V]
  • func (t *OrderedMap[K, V]) Contains(key K) bool
  • func (t *OrderedMap[K, V]) Delete(key K)
  • func (t *OrderedMap[K, V]) DeleteMax()
  • func (t *OrderedMap[K, V]) DeleteMin()
  • func (t *OrderedMap[K, V]) Get(key K) (V, bool)
  • func (t *OrderedMap[K, V]) IsEmpty() bool
  • func (t *OrderedMap[K, V]) Keys() []K
  • func (t *OrderedMap[K, V]) KeysInRange(lo, hi K) []K
  • func (t *OrderedMap[K, V]) KeysInRangeBFS() []K
  • func (t *OrderedMap[K, V]) Max() (K, bool)
  • func (t *OrderedMap[K, V]) Min() (K, bool)
  • func (t *OrderedMap[K, V]) Put(key K, val V)
  • func (t *OrderedMap[K, V]) Size() int

Constants

const (
	RED   color = true
	BLACK color = false
)

Types

type OrderedMap

type OrderedMap[K constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

func NewOrderedMap

func NewOrderedMap[K constraints.Ordered, V any]() *OrderedMap[K, V]

NewOrderedMap creates and returns a new empty OrderedMap.

func (*OrderedMap[K, V]) Contains

func (t *OrderedMap[K, V]) Contains(key K) bool

Contains checks if the given key exists in the OrderedMap.

func (*OrderedMap[K, V]) Delete

func (t *OrderedMap[K, V]) Delete(key K)

Delete removes the key-value pair with the given key from the OrderedMap. If the key doesn't exist, this operation does nothing.

func (*OrderedMap[K, V]) DeleteMax

func (t *OrderedMap[K, V]) DeleteMax()

DeleteMax removes the largest key and associated value from the map.

func (*OrderedMap[K, V]) DeleteMin

func (t *OrderedMap[K, V]) DeleteMin()

DeleteMin removes the smallest key and associated value from the map.

func (*OrderedMap[K, V]) Get

func (t *OrderedMap[K, V]) Get(key K) (V, bool)

Get retrieves the value associated with the given key.

func (*OrderedMap[K, V]) IsEmpty

func (t *OrderedMap[K, V]) IsEmpty() bool

IsEmpty returns true if the OrderedMap contains no elements, false otherwise.

func (*OrderedMap[K, V]) Keys

func (t *OrderedMap[K, V]) Keys() []K

Keys returns a slice containing all keys in the OrderedMap in sorted order.

func (*OrderedMap[K, V]) KeysInRange

func (t *OrderedMap[K, V]) KeysInRange(lo, hi K) []K

KeysInRange returns a slice of all keys in the OrderedMap between lo and hi, inclusive.

func (*OrderedMap[K, V]) KeysInRangeBFS

func (t *OrderedMap[K, V]) KeysInRangeBFS() []K

func (*OrderedMap[K, V]) Max

func (t *OrderedMap[K, V]) Max() (K, bool)

Max returns the largest key in the OrderedMap and a boolean indicating success. If the map is empty, it returns the zero value of K and false.

func (*OrderedMap[K, V]) Min

func (t *OrderedMap[K, V]) Min() (K, bool)

Min returns the smallest key in the OrderedMap and a boolean indicating success. If the map is empty, it returns the zero value of K and false.

func (*OrderedMap[K, V]) Put

func (t *OrderedMap[K, V]) Put(key K, val V)

Put inserts a key-value pair into the OrderedMap. If the key already exists, its value is updated.

func (*OrderedMap[K, V]) Size

func (t *OrderedMap[K, V]) Size() int

Size returns the number of key-value pairs in the OrderedMap.