orderedmap.go

package gds

// OrderedMap is a map that remembers insertion order.
// Re-setting an existing key updates its value without changing its position.
// It is not safe for concurrent use.
type OrderedMap[K comparable, V any] struct {
	m    map[K]V
	keys []K
}

// NewOrderedMap returns an empty OrderedMap.
func NewOrderedMap[K comparable, V any]() *OrderedMap[K, V] {
	return &OrderedMap[K, V]{m: make(map[K]V)}
}

// Set inserts or updates the value for key.
// If key is new, it is appended at the end of the order.
func (o *OrderedMap[K, V]) Set(key K, value V) {
	if _, exists := o.m[key]; !exists {
		o.keys = append(o.keys, key)
	}
	o.m[key] = value
}

// Get returns the value for key and whether the key was found.
func (o *OrderedMap[K, V]) Get(key K) (V, bool) {
	v, ok := o.m[key]
	return v, ok
}

// Has reports whether key exists in the map.
func (o *OrderedMap[K, V]) Has(key K) bool {
	_, ok := o.m[key]
	return ok
}

// Delete removes the key and its value. Reports whether the key was present.
func (o *OrderedMap[K, V]) Delete(key K) bool {
	if _, ok := o.m[key]; !ok {
		return false
	}
	delete(o.m, key)
	for i, k := range o.keys {
		if k == key {
			o.keys = append(o.keys[:i], o.keys[i+1:]...)
			break
		}
	}
	return true
}

// Len returns the number of key-value pairs.
func (o *OrderedMap[K, V]) Len() int { return len(o.m) }

// IsEmpty reports whether the map has no entries.
func (o *OrderedMap[K, V]) IsEmpty() bool { return len(o.m) == 0 }

// Keys returns all keys in insertion order.
func (o *OrderedMap[K, V]) Keys() []K {
	out := make([]K, len(o.keys))
	copy(out, o.keys)
	return out
}

// Values returns all values in insertion order.
func (o *OrderedMap[K, V]) Values() []V {
	out := make([]V, len(o.keys))
	for i, k := range o.keys {
		out[i] = o.m[k]
	}
	return out
}

// Range calls fn for each key-value pair in insertion order.
// Iteration stops early if fn returns false.
func (o *OrderedMap[K, V]) Range(fn func(K, V) bool) {
	for _, k := range o.keys {
		if !fn(k, o.m[k]) {
			return
		}
	}
}