Linked Hash Map in Generic Go (go2go)

linked_hash_map.go

// https://go2goplay.golang.org/p/MGkmOhAcV79

package main

import (
	"fmt"
)

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

type LinkedHashMap[K comparable, V any] struct {
	byKey   map[K]*LinkedListNode[Pair[K, V]]
	ordered LinkedList[Pair[K, V]]
}

func (lhm *LinkedHashMap[K, V]) Set(k K, v V) (orig V, existed bool) {
	if lhm.byKey == nil {
		lhm.byKey = make(map[K]*LinkedListNode[Pair[K, V]])
		link(&lhm.ordered.Head, &lhm.ordered.Tail)
	}
	prev, existed := lhm.byKey[k].Delete()
	orig = prev.Value
	lhm.byKey[k] = lhm.ordered.Tail.InsertBefore(Pair[K, V]{k, v})
	return
}

func (lhm *LinkedHashMap[K, V]) Get(k K) (v V, ok bool) {
	n, ok := lhm.byKey[k]
	v = n.Value.Value
	return
}

func (lhm *LinkedHashMap[K, V]) Delete(k K) (v V, ok bool) {
	n, ok := lhm.byKey[k].Delete()
	v = n.Value
	delete(lhm.byKey, k)
	return
}

func (lhm *LinkedHashMap[K, V]) Each(f func(K, V)) {
	for n := lhm.ordered.Head.Next; n != &lhm.ordered.Tail; n = n.Next {
		f(n.Value.Key, n.Value.Value)
	}
}

func (lhm *LinkedHashMap[K,V]) Len() int {
	return len(lhm.byKey)
}

func (lhm *LinkedHashMap[K,V]) Pop() (v V, ok bool) {
	if lhm.Len() == 0 {
		return v, false
	}
	n, ok := lhm.ordered.Head.Next.Delete()
	v = n.Value
	return
}

type LinkedList[V any] struct {
	Head, Tail LinkedListNode[V]
}

func NewLinkedList[V any]() *LinkedList[V] {
	var ll LinkedList[V]
	link(&ll.Head, &ll.Tail)
	return &ll
}

type LinkedListNode[V any] struct {
	Prev, Next *LinkedListNode[V]
	Value      V
}

func link[V any](a, b *LinkedListNode[V]) {
	a.Next = b
	b.Prev = a
}

func (lln *LinkedListNode[V]) InsertAfter(v V) *LinkedListNode[V] {
	if lln.Next == nil {
		panic("attempted InsertAfter on sentinel value")
	}

	n := &LinkedListNode[V]{Value: v}
	link(n, lln.Next)
	link(lln, n)
	return n
}

func (lln *LinkedListNode[V]) InsertBefore(v V) *LinkedListNode[V] {
	if lln.Prev == nil {
		panic("attempted InsertBefore on sentinel value")
	}

	n := &LinkedListNode[V]{Value: v}
	link(lln.Prev, n)
	link(n, lln)
	return n
}

func (lln *LinkedListNode[V]) Delete() (v V, ok bool) {
	if lln == nil {
		return v, false
	}
	if lln.Prev == nil || lln.Next == nil {
		panic("attempted deletion of sentinel value")
	}
	link(lln.Prev, lln.Next)
	lln.Prev, lln.Next = nil, nil
	return lln.Value, true
}

func main() {
	var lhm LinkedHashMap[string, int]
	for i := 100; i < 110; i++ {
		lhm.Set(fmt.Sprint("key", i), i)
	}
	
	lhm.Delete("key104")
	lhm.Set("key105", 155)
	lhm.Set("key102", 122)
	fmt.Println(lhm.Pop())
	
	lhm.Each(func(k string, v int) {
		fmt.Println(k, "=", v)
	})
}