order

Documentation

Overview

Package order implements data structures that provide ordered operations like an ordered symbol table as described in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Index

• type Map
  • func (m *Map[K, V]) All() iter.Seq2[K, V]
  • func (m *Map[K, V]) Contains(key K) bool
  • func (m *Map[K, V]) Get(key K) (V, bool)
  • func (m *Map[K, V]) IsEmpty() bool
  • func (m *Map[K, V]) Min() (K, bool)
  • func (m *Map[K, V]) Put(key K, value V)
  • func (m Map[K, V]) RenderDot(w io.Writer)

Types

type Map

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

Map is an ordered symbol table as described in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. A summary of the API can be found in https://algs4.cs.princeton.edu/31elementary. Map is implemented as a left-leaning red-black binary search tree as described in the paper Left-leaning Red-Black Trees by Robert Sedgewick https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf. All operations are thus guaranteed to run in O(log N) with N number of keys.

func (*Map[K, V]) All

func (m *Map[K, V]) All() iter.Seq2[K, V]

All returns an in iterator iterating in ascending order over all key-value pairs.

func (*Map[K, V]) Contains

func (m *Map[K, V]) Contains(key K) bool

Contains returns true if the given key was found and false otherwise.

func (*Map[K, V]) Get

func (m *Map[K, V]) Get(key K) (V, bool)

Get returns the value associated with the given key and true if the key was found. The zero value and false is returned if the key was not found.

func (*Map[K, V]) IsEmpty

func (m *Map[K, V]) IsEmpty() bool

IsEmpty returns true if the map contains no keys and false otherwise.

func (*Map[K, V]) Min

func (m *Map[K, V]) Min() (K, bool)

Min returns the smallest key in the map and true if the map is not empty. The zero value and false is returned if the map is empty.

func (*Map[K, V]) Put

func (m *Map[K, V]) Put(key K, value V)

Put associates the given key with the given value. The value of an existing key is updated. TODO allow nil value to delete the key?

func (Map[K, V]) RenderDot

func (m Map[K, V]) RenderDot(w io.Writer)