ordmap

README

ordmap: ordered map using Go generics

Package ordmap implements an ordered map that retains the order of items added to a slice, while also providing fast key-based map lookup of items, using the Go 1.18 generics system.

The implementation is fully visible and the API provides a minimal subset of methods, compared to other implementations that are heavier, so that additional functionality can be added as needed. Iteration can be performed directly on the Order using standard Go range function.

The slice structure holds the Key and Val for items as they are added, enabling direct updating of the corresponding map, which holds the index into the slice.

Adding and access are fast, while deleting and inserting are relatively slow, requiring updating of the index map, but these are already slow due to the slice updating.

Documentation

Overview

package ordmap implements an ordered map that retains the order of items added to a slice, while also providing fast key-based map lookup of items, using the Go 1.18 generics system.

The implementation is fully visible and the API provides a minimal subset of methods, compared to other implementations that are heavier, so that additional functionality can be added as needed.

The slice structure holds the Key and Val for items as they are added, enabling direct updating of the corresponding map, which holds the index into the slice. Adding and access are fast, while deleting and inserting are relatively slow, requiring updating of the index map, but these are already slow due to the slice updating.

Index

• type KeyValue
• type Map
  • func Make[K comparable, V any](vals []KeyValue[K, V]) *Map[K, V]
  • func New[K comparable, V any]() *Map[K, V]
  • func (om *Map[K, V]) Add(key K, val V)
  • func (om *Map[K, V]) Copy(from *Map[K, V])
  • func (om *Map[K, V]) DeleteIndex(i, j int)
  • func (om *Map[K, V]) DeleteKey(key K) bool
  • func (om *Map[K, V]) GoString() string
  • func (om *Map[K, V]) IndexByKey(key K) int
  • func (om *Map[K, V]) IndexByKeyTry(key K) (int, bool)
  • func (om *Map[K, V]) IndexIsValid(idx int) error
  • func (om *Map[K, V]) Init()
  • func (om *Map[K, V]) InsertAtIndex(idx int, key K, val V)
  • func (om *Map[K, V]) KeyByIndex(idx int) K
  • func (om *Map[K, V]) Keys() []K
  • func (om *Map[K, V]) Len() int
  • func (om *Map[K, V]) ReplaceIndex(idx int, key K, val V)
  • func (om *Map[K, V]) Reset()
  • func (om *Map[K, V]) String() string
  • func (om *Map[K, V]) ValueByIndex(idx int) V
  • func (om *Map[K, V]) ValueByKey(key K) V
  • func (om *Map[K, V]) ValueByKeyTry(key K) (V, bool)
  • func (om *Map[K, V]) Values() []V

Types

type KeyValue

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

KeyValue represents a key-value pair.

type Map

type Map[K comparable, V any] struct {

	// Order is an ordered list of values and associated keys, in the order added.
	Order []KeyValue[K, V]

	// Map is the key to index mapping.
	Map map[K]int `view:"-"`
}

Map is a generic ordered map that combines the order of a slice and the fast key lookup of a map. A map stores an index into a slice that has the value and key associated with the value.

func Make

func Make[K comparable, V any](vals []KeyValue[K, V]) *Map[K, V]

Make constructs a new ordered map with the given key-value pairs

func New

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

New returns a new ordered map.

func (*Map[K, V]) Add

func (om *Map[K, V]) Add(key K, val V)

Add adds a new value for given key. If key already exists in map, it replaces the item at that existing index, otherwise it is added to the end.

func (*Map[K, V]) Copy

func (om *Map[K, V]) Copy(from *Map[K, V])

Copy copies all of the entries from the given ordered map into this ordered map. It keeps existing entries in this map unless they also exist in the given map, in which case they are overwritten.

func (*Map[K, V]) DeleteIndex

func (om *Map[K, V]) DeleteIndex(i, j int)

DeleteIndex deletes item(s) within the index range [i:j]. This is relatively slow because it needs to renumber the index map above the deleted range.

func (*Map[K, V]) DeleteKey

func (om *Map[K, V]) DeleteKey(key K) bool

DeleteKey deletes the item with the given key, returning false if it does not find it.

func (*Map[K, V]) GoString

func (om *Map[K, V]) GoString() string

GoString returns the map as Go code.

func (*Map[K, V]) IndexByKey

func (om *Map[K, V]) IndexByKey(key K) int

IndexByKey returns the index of the given key, with a -1 for missing key. See Map.IndexByKeyTry for a version returning a bool for missing key.

func (*Map[K, V]) IndexByKeyTry

func (om *Map[K, V]) IndexByKeyTry(key K) (int, bool)

IndexByKeyTry returns the index of the given key, with false for a missing key.

func (*Map[K, V]) IndexIsValid

func (om *Map[K, V]) IndexIsValid(idx int) error

IndexIsValid returns an error if the given index is invalid

func (*Map[K, V]) Init

func (om *Map[K, V]) Init()

Init initializes the map if it isn't already.

func (*Map[K, V]) InsertAtIndex

func (om *Map[K, V]) InsertAtIndex(idx int, key K, val V)

InsertAtIndex inserts the given value with the given key at the given index. This is relatively slow because it needs to renumber the index map above the inserted value. It will panic if the key already exists because the behavior is undefined in that situation.

func (*Map[K, V]) KeyByIndex

func (om *Map[K, V]) KeyByIndex(idx int) K

KeyByIndex returns the key for the given index in the ordered slice.

func (*Map[K, V]) Keys

func (om *Map[K, V]) Keys() []K

Keys returns a slice of the keys in order.

func (*Map[K, V]) Len

func (om *Map[K, V]) Len() int

Len returns the number of items in the map.

func (*Map[K, V]) ReplaceIndex

func (om *Map[K, V]) ReplaceIndex(idx int, key K, val V)

ReplaceIndex replaces the value at the given index with the given new item with the given key.

func (*Map[K, V]) Reset

func (om *Map[K, V]) Reset()

Reset resets the map, removing any existing elements.

func (*Map[K, V]) String

func (om *Map[K, V]) String() string

String returns a string representation of the map.

func (*Map[K, V]) ValueByIndex

func (om *Map[K, V]) ValueByIndex(idx int) V

ValueByIndex returns the value at the given index in the ordered slice.

func (*Map[K, V]) ValueByKey

func (om *Map[K, V]) ValueByKey(key K) V

ValueByKey returns the value corresponding to the given key, with a zero value returned for a missing key. See Map.ValueByKeyTry for one that returns a bool for missing keys.

func (*Map[K, V]) ValueByKeyTry

func (om *Map[K, V]) ValueByKeyTry(key K) (V, bool)

ValueByKeyTry returns the value corresponding to the given key, with false returned for a missing key.

func (*Map[K, V]) Values

func (om *Map[K, V]) Values() []V

Values returns a slice of the values in order.