orderedmap

README

OrderedMap Package

A high-performance, thread-safe implementation of an ordered map data structure in Go, using a doubly linked list for order maintenance and a hash map for fast lookups.

Features

Core Functionality

• Thread-safe operations with RWMutex
• O(1) lookups using hash map
• O(1) insertions and deletions using doubly linked list
• Memory-efficient implementation with proper GC handling
• Generic key-value storage using any type

Operations

• Set: Add or update key-value pairs - O(1)
• Get: Retrieve values by key - O(1)
• Delete: Remove key-value pairs - O(1)
• Clear: Remove all elements - O(n)
• Copy: Create a deep copy - O(n)
• Has: Check key existence - O(1)
• Len: Get number of elements - O(1)

Order-Aware Operations

• Keys: Get all keys in insertion order - O(n)
• Values: Get all values in insertion order - O(n)
• Range: Iterate over pairs in order - O(n)
• String: Get ordered string representation - O(n)

Note: This OrderedMap implementation is part of a larger data structures project. However, this repo is more comprehensive. For a more comprehensive collection of data structures and algorithms in Go, visit the main repository at @mstgnz/data-structures.

Usage Examples

Basic Operations

// Create a new ordered map
om := NewOrderedMap()

// Add key-value pairs
om.Set("first", 1)
om.Set("second", 2)
om.Set("third", 3)

// Get value by key
value, exists := om.Get("second")
if exists {
    fmt.Println(value) // Outputs: 2
}

// Delete a key-value pair
om.Delete("second")

// Check if key exists
exists = om.Has("first") // returns true

Iteration and Order

// Get all keys in order
keys := om.Keys() // ["first", "third"]

// Get all values in order
values := om.Values() // [1, 3]

// Iterate over pairs in order
om.Range(func(key, value any) bool {
    fmt.Printf("%v: %v\n", key, value)
    return true // continue iteration
})

Implementation Details

Data Structure

• Doubly linked list for order maintenance
• Hash map for O(1) lookups
• Thread-safe with RWMutex

type Node struct {
    Key   any
    Value any
    prev  *Node
    next  *Node
}

type OrderedMap struct {
    mu      sync.RWMutex
    head    *Node
    tail    *Node
    nodeMap map[any]*Node
    length  int
}

Performance Characteristics

• Memory efficient: No slice reallocations
• O(1) operations for basic functions
• Optimized for large datasets
• Efficient garbage collection
• No memory leaks

Thread Safety

• Read operations can occur concurrently
• Write operations are serialized
• Safe for concurrent access
• Deadlock prevention with deferred unlocks

Benchmarks

Run benchmarks using:

go test -bench=. -benchmem

Benchmark Results

Below are the benchmark results on Apple M1 CPU:

BenchmarkSet          3384583    305.2 ns/op    141 B/op    3 allocs/op
BenchmarkGet         73489630     15.2 ns/op      0 B/op    0 allocs/op
BenchmarkDelete       8095078    181.1 ns/op      0 B/op    0 allocs/op
BenchmarkRange         706783   1424.0 ns/op      0 B/op    0 allocs/op
BenchmarkCopy          10000  144245.0 ns/op  164603 B/op  1014 allocs/op

Parallel Operations

BenchmarkParallelSet  5840424    218.2 ns/op     33 B/op    2 allocs/op
BenchmarkParallelGet 24743820     82.2 ns/op      0 B/op    0 allocs/op

Performance Analysis

• Get Operations: Extremely fast with ~15ns per operation and zero allocations
• Set Operations: Efficient with ~305ns per operation and minimal memory usage
• Delete Operations: Quick with ~181ns per operation and no additional memory allocation
• Range Operations: Linear time complexity as expected, processing 1000 items in ~1.4µs
• Copy Operations: Most resource-intensive at ~144µs per operation with significant memory allocation
• Parallel Operations: Shows good scalability with reduced latency under concurrent load

Testing

Comprehensive test suite including:

• Basic operations
• Edge cases
• Concurrent operations
• Data consistency
• Memory management
• Large dataset handling

Test coverage: 100% of statements

Run tests:

go test ./...

Run tests with coverage:

go test -cover

Contributing

This project is open-source, and contributions are welcome. Feel free to contribute or provide feedback of any kind.

License

MIT License - see LICENSE file for details

Documentation

Index

• type JSONOptions
• type Node
• type OrderedMap
  • func NewOrderedMap() *OrderedMap
  • func (om *OrderedMap) Clear()
  • func (om *OrderedMap) Copy() *OrderedMap
  • func (om *OrderedMap) Delete(key any) error
  • func (om *OrderedMap) Filter(predicate func(key, value any) bool) *OrderedMap
  • func (om *OrderedMap) First() (key, value any, exists bool)
  • func (om *OrderedMap) FromJSON(data []byte, opts *JSONOptions) error
  • func (om *OrderedMap) Get(key any) (any, bool)
  • func (om *OrderedMap) Has(key any) bool
  • func (om *OrderedMap) Keys() []any
  • func (om *OrderedMap) Last() (key, value any, exists bool)
  • func (om *OrderedMap) Len() int
  • func (om *OrderedMap) Map(mapper func(key, value any) (any, any)) *OrderedMap
  • func (om *OrderedMap) MarshalJSON() ([]byte, error)
  • func (om *OrderedMap) Range(f func(key, value any) bool)
  • func (om *OrderedMap) Reverse() *OrderedMap
  • func (om *OrderedMap) Set(key, value any) error
  • func (om *OrderedMap) String() string
  • func (om *OrderedMap) ToJSON(opts *JSONOptions) ([]byte, error)
  • func (om *OrderedMap) UnmarshalJSON(data []byte) error
  • func (om *OrderedMap) Values() []any

Types

type JSONOptions

type JSONOptions struct {
	// KeyAsString determines whether to force convert all keys to strings
	KeyAsString bool
	// PreserveType attempts to preserve the original type of numeric values
	PreserveType bool
	// PrettyPrint formats the JSON output with indentation
	PrettyPrint bool
}

JSONOptions represents configuration options for JSON marshaling/unmarshaling

type Node

type Node struct {
	Key   any // The key of the key-value pair
	Value any // The value associated with the key
	// contains filtered or unexported fields
}

Node represents a node in the doubly linked list that maintains the order of elements. Each node contains a key-value pair and pointers to the previous and next nodes.

type OrderedMap

type OrderedMap struct {
	// contains filtered or unexported fields
}

OrderedMap is a thread-safe implementation of an ordered map data structure. It combines a doubly linked list for maintaining insertion order with a hash map for O(1) lookups. All operations are protected by a read-write mutex for thread safety.

func NewOrderedMap

func NewOrderedMap() *OrderedMap

NewOrderedMap creates and initializes a new empty OrderedMap. The returned map is ready to use and is thread-safe.

Example:

om := NewOrderedMap()
om.Set("key", "value")

func (*OrderedMap) Clear

func (om *OrderedMap) Clear()

Clear removes all elements from the map, resetting it to an empty state. This operation is not atomic - if you need atomicity, you should implement your own locking around this method.

Example:

om.Clear()

func (*OrderedMap) Copy

func (om *OrderedMap) Copy() *OrderedMap

Copy creates a deep copy of the OrderedMap. The new map contains copies of all key-value pairs in the same order. This method is thread-safe.

Example:

newMap := om.Copy()

func (*OrderedMap) Delete

func (om *OrderedMap) Delete(key any) error

Delete removes the element with the given key from the map. If the key doesn't exist, the operation is a no-op and returns nil. The method is thread-safe and returns an error if the key is nil.

Example:

err := om.Delete("key")
if err != nil {
    log.Fatal(err)
}

func (*OrderedMap) Filter

func (om *OrderedMap) Filter(predicate func(key, value any) bool) *OrderedMap

Filter returns a new OrderedMap containing only the elements that satisfy the given predicate function. This method is thread-safe.

Example:

filtered := om.Filter(func(key, value any) bool {
    // Keep only values greater than 10
    if val, ok := value.(int); ok {
        return val > 10
    }
    return false
})

func (*OrderedMap) First

func (om *OrderedMap) First() (key, value any, exists bool)

First returns the first key-value pair in the map. Returns nil values and false if the map is empty. This method is thread-safe.

Example:

if key, value, exists := om.First(); exists {
    fmt.Printf("First element - Key: %v, Value: %v\n", key, value)
}

func (*OrderedMap) FromJSON

func (om *OrderedMap) FromJSON(data []byte, opts *JSONOptions) error

FromJSON populates the OrderedMap from a JSON byte array with the specified options. This method is thread-safe.

Example:

opts := &JSONOptions{
    KeyAsString: true,
    PreserveType: true,
}
err := om.FromJSON(data, opts)
if err != nil {
    log.Fatal(err)
}

func (*OrderedMap) Get

func (om *OrderedMap) Get(key any) (any, bool)

Get retrieves the value associated with the given key. Returns the value and true if the key exists, nil and false otherwise. The method is thread-safe and returns nil, false if the key is nil.

Example:

if value, exists := om.Get("key"); exists {
    fmt.Printf("Value: %v\n", value)
}

func (*OrderedMap) Has

func (om *OrderedMap) Has(key any) bool

Has checks if a key exists in the map. Returns true if the key exists, false otherwise. The method is thread-safe and returns false if the key is nil.

Example:

if om.Has("key") {
    fmt.Println("Key exists")
}

func (*OrderedMap) Keys

func (om *OrderedMap) Keys() []any

Keys returns a slice containing all keys in the map in their insertion order. The returned slice is a copy of the keys, so modifications to the slice won't affect the map.

Example:

keys := om.Keys()
for _, key := range keys {
    fmt.Println(key)
}

func (*OrderedMap) Last

func (om *OrderedMap) Last() (key, value any, exists bool)

Last returns the last key-value pair in the map. Returns nil values and false if the map is empty. This method is thread-safe.

Example:

if key, value, exists := om.Last(); exists {
    fmt.Printf("Last element - Key: %v, Value: %v\n", key, value)
}

func (*OrderedMap) Len

func (om *OrderedMap) Len() int

Len returns the number of elements in the map. This method is thread-safe.

Example:

count := om.Len()
fmt.Printf("Map contains %d elements\n", count)

func (*OrderedMap) Map

func (om *OrderedMap) Map(mapper func(key, value any) (any, any)) *OrderedMap

Map creates a new OrderedMap by transforming each element using the given mapping function. This method is thread-safe.

Example:

doubled := om.Map(func(key, value any) (any, any) {
    if val, ok := value.(int); ok {
        return key, val * 2
    }
    return key, value
})

func (*OrderedMap) MarshalJSON

func (om *OrderedMap) MarshalJSON() ([]byte, error)

MarshalJSON implements the json.Marshaler interface. It converts the OrderedMap to a JSON object, maintaining the order of keys. Keys are converted to strings in the JSON representation.

Example:

data, err := json.Marshal(om)
if err != nil {
    log.Fatal(err)
}

func (*OrderedMap) Range

func (om *OrderedMap) Range(f func(key, value any) bool)

Range iterates over the map in insertion order and calls the given function for each key-value pair. If the function returns false, iteration stops. The method is thread-safe and holds a read lock during iteration.

Example:

om.Range(func(key, value any) bool {
    fmt.Printf("%v: %v\n", key, value)
    return true // continue iteration
})

func (*OrderedMap) Reverse

func (om *OrderedMap) Reverse() *OrderedMap

Reverse returns a new OrderedMap with all elements in reverse order. This method is thread-safe.

Example:

reversed := om.Reverse()
fmt.Println(reversed.String())

func (*OrderedMap) Set

func (om *OrderedMap) Set(key, value any) error

Set adds a new key-value pair to the map or updates an existing one. If the key already exists, its value is updated. If the key is new, the pair is added to the end of the ordered list.

The method is thread-safe and returns an error if the key is nil.

Example:

om := NewOrderedMap()
err := om.Set("key", "value")
if err != nil {
    log.Fatal(err)
}

func (*OrderedMap) String

func (om *OrderedMap) String() string

String returns a string representation of the map in the format {key1: value1, key2: value2}. The elements are ordered according to their insertion order. This method is thread-safe.

Example:

fmt.Println(om.String()) // Output: {key1: value1, key2: value2}

func (*OrderedMap) ToJSON

func (om *OrderedMap) ToJSON(opts *JSONOptions) ([]byte, error)

ToJSON converts the OrderedMap to a JSON byte array with the specified options. This method is thread-safe.

Example:

opts := &JSONOptions{
    KeyAsString: true,
    PreserveType: true,
    PrettyPrint: true,
}
data, err := om.ToJSON(opts)
if err != nil {
    log.Fatal(err)
}

func (*OrderedMap) UnmarshalJSON

func (om *OrderedMap) UnmarshalJSON(data []byte) error

UnmarshalJSON implements the json.Unmarshaler interface. It populates the OrderedMap from a JSON object, maintaining the order of keys as they appear in the JSON input.

Example:

var om OrderedMap
err := json.Unmarshal(data, &om)
if err != nil {
    log.Fatal(err)
}

func (*OrderedMap) Values

func (om *OrderedMap) Values() []any

Values returns a slice containing all values in the map in their insertion order. The returned slice is a copy of the values, so modifications to the slice won't affect the map.

Example:

values := om.Values()
for _, value := range values {
    fmt.Println(value)
}