ordmap

README

ordmap: ordered map using Go 1.18 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 KeyVal
• type Map
  • func New[K comparable, V any]() *Map[K, V]
  • func (om *Map[K, V]) Add(key K, val V)
  • func (om *Map[K, V]) DeleteIdx(i, j int)
  • func (om *Map[K, V]) DeleteKey(key K) bool
  • func (om *Map[K, V]) IdxByKey(key K) (int, bool)
  • func (om *Map[K, V]) IdxIsValid(idx int) error
  • func (om *Map[K, V]) Init()
  • func (om *Map[K, V]) InsertAtIdx(idx int, key K, val V)
  • func (om *Map[K, V]) KeyByIdx(idx int) K
  • func (om *Map[K, V]) Keys() []K
  • func (om *Map[K, V]) Len() int
  • func (om *Map[K, V]) ReplaceIdx(idx int, key K, val V)
  • func (om *Map[K, V]) Reset()
  • func (om *Map[K, V]) ValByIdx(idx int) V
  • func (om *Map[K, V]) ValByKey(key K) (V, bool)
  • func (om *Map[K, V]) Vals() []V

Types

type KeyVal

type KeyVal[K comparable, V any] struct {
	Key K
	Val V
}

KeyVal represents the Key and Value

type Map

type Map[K comparable, V any] struct {
	Order []*KeyVal[K, V] `desc:"ordered list of values and associated keys -- in order added"`
	Map   map[K]int       `desc:"key to index mapping"`
}

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 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]) DeleteIdx

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

DeleteIdx deletes item(s) within 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 item by given key, returns true if found

func (*Map[K, V]) IdxByKey

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

IdxByKey returns index of given Key, along with bool reflecting presence of key.

func (*Map[K, V]) IdxIsValid

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

IdxIsValid returns error if index is invalid

func (*Map[K, V]) Init

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

Init initializes the map if not done yet

func (*Map[K, V]) InsertAtIdx

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

InsertAtIdx inserts value with key at 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]) KeyByIdx

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

KeyByIdx returns key for given index, in ordered slice.

func (*Map[K, V]) Keys

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

Keys returns a slice of 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]) ReplaceIdx

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

ReplaceIdx replaces value at given index with new item with 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]) ValByIdx

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

ValByIdx returns value at given index, in ordered slice.

func (*Map[K, V]) ValByKey

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

ValByKey returns value based on Key, along with bool reflecting presence of key.

func (*Map[K, V]) Vals

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

Vals returns a slice of vals in order