orderedmap

README

Go ordered map

Go implementation of an ordered map using generics.

Implementation

An ordered map is a map that additionally maintains ordering among its entries. This data structure can be used to solve a variety of problems: one very common use case is implementing LRU or LRU-like cache replacement policies.

This implementation supports O(1) lookup, update, removal, insertion to front/back, insertion before/after a specific key, move to front/back, move before/after a specific key.

Under the hood this is implemented as a combination of a map and doubly-linked list, whereby each value in the map is node of the list. The list is implemented by forking the standard library container/list package and adding support for generics.

This implementation is not safe for concurrent usage.

Installation

You can get this module by invoking from your terminal

go get -u github.com/lorenzosaino/go-orderedmap

and then importing it in your code with

import orderedmap "github.com/lorenzosaino/go-orderedmap"

Since it requires generics support, you will need Go 1.18 or above.

Usage

For reference and examples, see Go doc.

Development

You can invoke make help to see all make targets provided.

$ make help
all                            Run all checks and tests
mod-upgrade                    Upgrade all vendored dependencies
mod-update                     Ensure all used dependencies are tracked in go.{mod|sum} and vendored
fmt-check                      Validate that all source files pass "go fmt"
lint                           Run go lint
vet                            Run go vet
staticcheck                    Run staticcheck
test                           Run all tests
container-shell                Open a shell on a Docker container
container-%                    Run any target of this Makefile in a Docker container
help                           Print help

License

BSD 3-clause

Documentation

Overview

Package orderedmap implements an ordered map using generics.

An ordered map is a map whose values are ordered and all connected with a doubly-linked list. It provides O(1) lookup, update, removal, insertion to front/back, insertion before/after a specific key, move to front/back, move before/after a specific key.

This implementation is not safe for concurrent usage. You may want to use a sync.RWLock to synchronize access to it if you intend to use it concurrently.

Index

• Variables
• type Item
• type OrderedMap
  • func New[K comparable, V any]() *OrderedMap[K, V]
  • func (m *OrderedMap[K, V]) Back() (item Item[K, V], ok bool)
  • func (m *OrderedMap[K, V]) Clear()
  • func (m *OrderedMap[K, V]) Delete(key K) (value V, ok bool)
  • func (m *OrderedMap[K, V]) Filter(f func(key K, value V) bool) *OrderedMap[K, V]
  • func (m *OrderedMap[K, V]) Front() (item Item[K, V], ok bool)
  • func (m *OrderedMap[K, V]) Get(key K) (value V, ok bool)
  • func (m *OrderedMap[K, V]) InsertAfter(key K, value V, mark K) error
  • func (m *OrderedMap[K, V]) InsertBefore(key K, value V, mark K) error
  • func (m *OrderedMap[K, V]) Items() []Item[K, V]
  • func (m *OrderedMap[K, V]) Keys() []K
  • func (m *OrderedMap[K, V]) Len() int
  • func (m *OrderedMap[K, V]) Map() map[K]V
  • func (m *OrderedMap[K, V]) MoveAfter(key K, mark K) error
  • func (m *OrderedMap[K, V]) MoveBefore(key K, mark K) error
  • func (m *OrderedMap[K, V]) MoveToBack(key K) error
  • func (m *OrderedMap[K, V]) MoveToFront(key K) error
  • func (m *OrderedMap[K, V]) Next(key K) (next Item[K, V], ok bool)
  • func (m *OrderedMap[K, V]) PopBack() (item Item[K, V], ok bool)
  • func (m *OrderedMap[K, V]) PopFront() (item Item[K, V], ok bool)
  • func (m *OrderedMap[K, V]) Prev(key K) (prev Item[K, V], ok bool)
  • func (m *OrderedMap[K, V]) PushBack(key K, value V) error
  • func (m *OrderedMap[K, V]) PushFront(key K, value V) error
  • func (m *OrderedMap[K, V]) Range(f func(key K, value V) bool)
  • func (m *OrderedMap[K, V]) RangeReverse(f func(key K, value V) bool)
  • func (m *OrderedMap[K, V]) Reverse() *OrderedMap[K, V]
  • func (m *OrderedMap[K, V]) Update(key K, value V) (oldValue V, err error)

Examples

• OrderedMap (Iteration)
• OrderedMap (ReverseIteration)
• OrderedMap.Filter
• OrderedMap.Reverse

Variables

var (
	// ErrKeyMissing indicates that the key specified is not present in the ordered map
	ErrKeyMissing = errors.New("key missing")

	// ErrMarkKeyMissing indicates that the mark key specified is not present in the ordered map
	ErrMarkKeyMissing = errors.New("mark key missing")

	// ErrKeyAlreadyPresent indicates that key to be inserted is already present in the ordered map
	ErrKeyAlreadyPresent = errors.New("key already present")
)

Types

type Item

type Item[K comparable, V any] struct {
	Key   K
	Value V
}

Item is a key-value item stored in the ordered map

type OrderedMap

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

OrderedMap is an implementation of an ordered map.

K and V are respectively the types of keys and values.

Example (Iteration)

m := orderedmap.New[int, string]()
m.PushBack(1, "one")
m.PushBack(2, "two")
m.PushBack(3, "three")

f := func(k int, v string) bool {
	fmt.Println(k, v)
	return true
}
m.Range(f)

Output:

1 one
2 two
3 three

Example (ReverseIteration)

m := orderedmap.New[int, string]()
m.PushBack(1, "one")
m.PushBack(2, "two")
m.PushBack(3, "three")

f := func(k int, v string) bool {
	fmt.Println(k, v)
	return true
}
m.RangeReverse(f)

Output:

3 three
2 two
1 one

func New

func New[K comparable, V any]() *OrderedMap[K, V]

New returns a new ordered map instance.

func (*OrderedMap[K, V]) Back

func (m *OrderedMap[K, V]) Back() (item Item[K, V], ok bool)

Front returns the item at the back of the map.

If the map is empty, it returns the zero value of Item[K, V] and ok is set to false.

func (*OrderedMap[K, V]) Clear

func (m *OrderedMap[K, V]) Clear()

Clear empties the ordered map.

func (*OrderedMap[K, V]) Delete

func (m *OrderedMap[K, V]) Delete(key K) (value V, ok bool)

Delete deletes an item from a map and returns the value deleted.

If the item to be deleted was already missing from the map, ok is set to false.

func (*OrderedMap[K, V]) Filter

func (m *OrderedMap[K, V]) Filter(f func(key K, value V) bool) *OrderedMap[K, V]

Filter returns a filtered copy of the ordered map.

The returned map only includes the (key, value) items such that f(key, value) == true.

Example

m := orderedmap.New[int, string]()
m.PushBack(1, "one")
m.PushBack(2, "two")
m.PushBack(3, "three")
m.PushBack(4, "four")

isKeyEven := func(key int, val string) bool {
	return key%2 == 0
}

filteredMap := m.Filter(isKeyEven)

for e, ok := filteredMap.Front(); ok; e, ok = filteredMap.Next(e.Key) {
	fmt.Println(e.Key, e.Value)
}

Output:

2 two
4 four

func (*OrderedMap[K, V]) Front

func (m *OrderedMap[K, V]) Front() (item Item[K, V], ok bool)

Front returns the item at the front of the map.

If the map is empty, it returns the zero value of Item[K, V] and ok is set to false.

func (*OrderedMap[K, V]) Get

func (m *OrderedMap[K, V]) Get(key K) (value V, ok bool)

Get returns the value associated to a key in the map.

If the key is not present in the map, it returns the zero value of V and ok is set to false.

func (*OrderedMap[K, V]) InsertAfter

func (m *OrderedMap[K, V]) InsertAfter(key K, value V, mark K) error

InsertAfter insert a new key and value immediately after a mark key.

It returns ErrKeyAlreadyPresent if the key to be inserted is already present and ErrMarkKeyMissing if the mark key is missing.

func (*OrderedMap[K, V]) InsertBefore

func (m *OrderedMap[K, V]) InsertBefore(key K, value V, mark K) error

InsertBefore insert a new key and value immediately before a mark key.

It returns ErrKeyAlreadyPresent if the key to be inserted is already present and ErrMarkKeyMissing if the mark key is missing.

func (*OrderedMap[K, V]) Items

func (m *OrderedMap[K, V]) Items() []Item[K, V]

Item returns the a ordered slice of items of the content of the map.

Note that while this function could be used to iterate over the items stored in the ordered map, it allocates a new slice and copy all items in the map. For better performance, you may want to iterate using Prev() and Next() instead.

func (*OrderedMap[K, V]) Keys

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

Item returns the a ordered slice of keys of the content of the map.

Note that while this function could be used to iterate over the items stored in the ordered map, it allocates a new slice and copy all items in the map. For better performance, you may want to iterate using Prev() and Next() instead.

func (*OrderedMap[K, V]) Len

func (m *OrderedMap[K, V]) Len() int

Len returns the number of items stored in the ordered map.

func (*OrderedMap[K, V]) Map

func (m *OrderedMap[K, V]) Map() map[K]V

Map returns a map of all items stored in the OrderedMap.

func (*OrderedMap[K, V]) MoveAfter

func (m *OrderedMap[K, V]) MoveAfter(key K, mark K) error

MoveAfter moves an existing key immediately after a mark key.

It returns ErrKeyMissing if the key to be moved is missing and ErrMarkKeyMissing if the mark key is missing.

func (*OrderedMap[K, V]) MoveBefore

func (m *OrderedMap[K, V]) MoveBefore(key K, mark K) error

MoveAfter moves an existing key immediately before a mark key.

It returns ErrKeyMissing if the key to be moved is missing and ErrMarkKeyMissing if the mark key is missing.

func (*OrderedMap[K, V]) MoveToBack

func (m *OrderedMap[K, V]) MoveToBack(key K) error

MoveToBack moves an existing key to the back of the map.

It returns ErrKeyMissing if the key to be moved is not in the map.

func (*OrderedMap[K, V]) MoveToFront

func (m *OrderedMap[K, V]) MoveToFront(key K) error

MoveToFront moves an existing key to the front of the map.

It returns ErrKeyMissing if the key to be moved is not in the map.

func (*OrderedMap[K, V]) Next

func (m *OrderedMap[K, V]) Next(key K) (next Item[K, V], ok bool)

Next returns the item succeeding a given item in the map.

If the specified item is missing or it is at the back of the map, ok is set to false.

func (*OrderedMap[K, V]) PopBack

func (m *OrderedMap[K, V]) PopBack() (item Item[K, V], ok bool)

PopBack pops the element at the back of the map and returns its value.

If the map is empty, it returns the zero value of Item[K, V] and ok is set to false.

func (*OrderedMap[K, V]) PopFront

func (m *OrderedMap[K, V]) PopFront() (item Item[K, V], ok bool)

PopFront pops the element at the front of the map and returns its value.

If the map is empty, it returns the zero value of Item[K, V] and ok is set to false.

func (*OrderedMap[K, V]) Prev

func (m *OrderedMap[K, V]) Prev(key K) (prev Item[K, V], ok bool)

Prev returns the item preceding a given item in the map.

If the specified item is missing or it is at the front of the map, ok is set to false.

func (*OrderedMap[K, V]) PushBack

func (m *OrderedMap[K, V]) PushBack(key K, value V) error

PushBack insert a new key and value at the back of the map.

It returns ErrKeyAlreadyPresent if the key to be inserted is already present.

func (*OrderedMap[K, V]) PushFront

func (m *OrderedMap[K, V]) PushFront(key K, value V) error

PushFront insert a new key and value at the front of the map.

It returns ErrKeyAlreadyPresent if the key to be inserted is already present.

func (*OrderedMap[K, V]) Range

func (m *OrderedMap[K, V]) Range(f func(key K, value V) bool)

Range calls f sequentially for each key and value present in the ordered map starting from the front element. If f returns false, Range stops the iteration.

func (*OrderedMap[K, V]) RangeReverse

func (m *OrderedMap[K, V]) RangeReverse(f func(key K, value V) bool)

Range calls f sequentially for each key and value present in the ordered map starting from the back element. If f returns false, RangeReverse stops the iteration.

func (*OrderedMap[K, V]) Reverse

func (m *OrderedMap[K, V]) Reverse() *OrderedMap[K, V]

Reverse returns a copy of the ordered map with reversed ordering.

Example

m := orderedmap.New[int, string]()
m.PushBack(1, "one")
m.PushBack(2, "two")
m.PushBack(3, "three")

fmt.Println("original map:")
for e, ok := m.Front(); ok; e, ok = m.Next(e.Key) {
	fmt.Println(e.Key, e.Value)
}

m = m.Reverse()

fmt.Println("reversed map:")
for e, ok := m.Front(); ok; e, ok = m.Next(e.Key) {
	fmt.Println(e.Key, e.Value)
}

Output:

original map:
1 one
2 two
3 three
reversed map:
3 three
2 two
1 one

func (*OrderedMap[K, V]) Update

func (m *OrderedMap[K, V]) Update(key K, value V) (oldValue V, err error)

Update updates the value associated to an existing key and returns the old value.

If the key is not present, then ErrKeyMissing is returned.