map.go

package ordered

import "iter"

// NewMap returns a new, empty ordered map. Options can be provided to configure
// the map during construction (see [WithCapacity]).
func NewMap[K comparable, V any](opts ...Option) *Map[K, V] {
	cfg := new(config)
	for _, opt := range opts {
		opt(cfg)
	}

	var m map[K]*entry[K, V]
	if cfg.capacity != nil {
		m = make(map[K]*entry[K, V], *cfg.capacity)
	} else {
		m = make(map[K]*entry[K, V])
	}

	return &Map[K, V]{
		m: m,
		l: new(list[K, V]),
	}
}

// Map is an ordered map backed by a doubly-linked list.
type Map[K comparable, V any] struct {
	m map[K]*entry[K, V]
	l *list[K, V]
}

// Get retrieves the value for a given key and a bool indicating whether the key was present.
func (m *Map[K, V]) Get(key K) (value V, present bool) {
	var e *entry[K, V]
	if e, present = m.m[key]; present {
		return e.value, present
	}

	return value, false
}

// Set stores a value for a given key.
// If the key already exists, then the associated value is updated.
// If the key is new to the map then it is added as the latest item in order.
func (m *Map[K, V]) Set(key K, value V) {
	if e, ok := m.m[key]; ok {
		e.value = value
	} else {
		e = &entry[K, V]{key: key, value: value}
		m.l.append(e)
		m.m[key] = e
	}
}

// Delete removes a given key from the map.
// If the key does not exist then this is a no-op.
// The Map order is updated to reflect the removal of this item.
func (m *Map[K, V]) Delete(key K) {
	if e, ok := m.m[key]; ok {
		m.l.remove(e)
		delete(m.m, key)
	}
}

// Pop returns the value for a given key and a bool indicating whether the key was present.
// Additionally, the key is removed from the map and the order updated to reflect this.
func (m *Map[K, V]) Pop(key K) (value V, present bool) {
	var e *entry[K, V]
	if e, present = m.m[key]; present {
		m.l.remove(e)
		delete(m.m, key)
		return e.value, present
	}
	return value, false
}

// Push stores the value for the given key as the last entry in the map.
// If the key already exists, its value is updated, and it is moved to the back of the order.
func (m *Map[K, V]) Push(key K, value V) {
	if e, present := m.m[key]; present {
		e.value = value
		m.l.remove(e)
		m.l.append(e)
	} else {
		e = &entry[K, V]{key: key, value: value}
		m.l.append(e)
		m.m[key] = e
	}
}

// Insert stores the value for the given key as the first entry in the map.
// If the key is already present, its value is updated, and it is moved to the front of the order.
func (m *Map[K, V]) Insert(key K, value V) {
	if e, present := m.m[key]; present {
		e.value = value
		m.l.remove(e)
		m.l.prepend(e)
	} else {
		e = &entry[K, V]{key: key, value: value}
		m.l.prepend(e)
		m.m[key] = e
	}
}

// Len returns the number of items in the map.
func (m *Map[K, V]) Len() int {
	return len(m.m)
}

// Clear removes all entries in the map.
func (m *Map[K, V]) Clear() {
	// Instead of iterating over the keyspace, we simply create a new backing map and list and let the garbage collector
	// handle the old stores/values. This is fine because Go's tracing-based garbage collector can handle the circular
	// references in our map/list/entries.
	m.m = make(map[K]*entry[K, V])
	m.l = new(list[K, V])
}

// Keys yields an iterator of keys over the map's ordered keyspace.
func (m *Map[K, V]) Keys() iter.Seq[K] {
	return func(yield func(K) bool) {
		for e := m.l.head; e != nil; e = e.next {
			if !yield(e.key) {
				return
			}
		}
	}
}

// Values yields an iterator of values over the map's ordered keyspace.
func (m *Map[K, V]) Values() iter.Seq[V] {
	return func(yield func(V) bool) {
		for e := m.l.head; e != nil; e = e.next {
			if !yield(e.value) {
				return
			}
		}
	}
}

// Entries yields an iterator of key/value pair entries over the map's ordered keyspace.
func (m *Map[K, V]) Entries() iter.Seq2[K, V] {
	return func(yield func(K, V) bool) {
		for e := m.l.head; e != nil; e = e.next {
			if !yield(e.key, e.value) {
				return
			}
		}
	}
}

// Reverse returns a [Reversed] view that yields iterators in reverse order over the [Map] keyspace.
func (m *Map[K, V]) Reverse() Reversed[K, V] {
	return &reversedMap[K, V]{m}
}