// orderedmap implements an ordered map (ordered dictionary or linked hash map).
// This can be useful in scenarios where we need to maintain the order of access and/or insertion (ex: LRU Cache).
// For learning purposes. Use container/list.
package orderedmap

func NewOrderedMap() *OrderedMap {
    return &OrderedMap{
        dict: make(map[string]*Node),
    }
}

type OrderedMap struct {
    dict map[string]*Node
    head *Node
    tail *Node
}

func (od *OrderedMap) Set(key string, value any) {
    if _, ok := od.dict[key]; ok {
        // Key already exists, update the value if needed
        // We can also change its position (order) if needed
        // (Ex: LRU Cache where Set() is considered as "used")
        // This could be easily done by removing it before adding it.
        return
    }

    node := &Node{
        key:   key,
        value: value,
        prev:  od.tail,
    }

    if od.head == nil {
        od.head = node
    }

    if od.tail != nil {
        od.tail.next = node
    }

    od.tail = node
    od.dict[key] = node
}

func (od *OrderedMap) Front(key string) (*Node, bool) {
    if len(od.dict) == 0 {
        return nil, false
    }
    return od.head, true
}

func (od *OrderedMap) Get(key string) (any, bool) {
    if node, ok := od.dict[key]; ok {
        return node.value, true
    }
    return nil, false
}

func (od *OrderedMap) Remove(key string) {
    if node, ok := od.dict[key]; ok {
        if node.prev != nil {
            node.prev.next = node.next
        } else {
            od.head = node.next
        }

        if node.next != nil {
            node.next.prev = node.prev
        } else {
            od.tail = node.prev
        }

        delete(od.dict, key)
    }
}

func (od *OrderedMap) Keys() []string {
    keys := make([]string, 0, len(od.dict))
    node := od.head
    for node != nil {
        keys = append(keys, node.key)
        node = node.next
    }
    return keys
}

type Node struct {
    key   string
    value any
    prev  *Node
    next  *Node
}