advent-of-code-2024/go/question9/collections.go

package main

type DllId int64

type DoubleLinkedList[T any] struct {
	data            map[DllId]T
	nodes           map[DllId]*DLLNode
	FirstNode       DllId
	LastNode        DllId
	length          int
	lastGeneratedId DllId
}

func NewDLL[T any]() *DoubleLinkedList[T] {
	return &DoubleLinkedList[T]{
		make(map[DllId]T),
		make(map[DllId]*DLLNode),
		-1,
		-1,
		0,
		-1,
	}
}

type DLLNode struct {
	Id         DllId
	NextId     DllId
	PreviousId DllId
}

func (l *DoubleLinkedList[T]) IsEmpty() bool {
	return l.length == 0
}

func (l *DoubleLinkedList[T]) insertEmpty(data T) DllId {
	newId := l.nextId()
	node := standaloneNode(newId)
	l.data[newId] = data
	l.nodes[newId] = node
	l.FirstNode = newId
	l.LastNode = newId
	l.length++
	return newId
}

func (l *DoubleLinkedList[T]) InsertBefore(id DllId, data T) (DllId, bool) {
	if node, ok := l.nodes[id]; ok {
		return l.insertBetween(l.previousNode(node), node, data)
	} else {
		return -1, false
	}
}

func (l *DoubleLinkedList[T]) InsertAfter(id DllId, data T) (DllId, bool) {

	if node := l.nodes[id]; node.Id == id {
		return l.insertBetween(node, l.nextNode(node), data)
	}

	return -1, false
}

func (l *DoubleLinkedList[T]) InsertFirst(data T) DllId {
	if l.IsEmpty() {
		return l.insertEmpty(data)
	}
	newId := l.nextId()
	node := standaloneNode(newId)
	l.data[newId] = data
	l.nodes[newId] = node
	firstNode := l.nodes[l.FirstNode]
	node.NextId = firstNode.Id
	firstNode.PreviousId = newId
	l.FirstNode = newId
	l.length++
	return newId
}

func (l *DoubleLinkedList[T]) InsertLast(data T) DllId {
	if l.IsEmpty() {
		return l.insertEmpty(data)
	}
	newId := l.nextId()
	node := standaloneNode(newId)
	l.data[newId] = data
	l.nodes[newId] = node
	lastNode := l.nodes[l.LastNode]
	node.PreviousId = lastNode.Id
	lastNode.NextId = newId
	l.LastNode = newId
	l.length++
	return newId
}

func standaloneNode(id DllId) *DLLNode {
	return &DLLNode{id, -1, -1}
}

func (l *DoubleLinkedList[T]) nextId() DllId {
	l.lastGeneratedId++
	return l.lastGeneratedId
}

func mapNodes[T, K any](l *DoubleLinkedList[T], fn func(T, *DLLNode) K) <-chan K {
	ch := make(chan K)
	go func() {
		defer close(ch)
		iterId := l.FirstNode
		for iterId > -1 {
			val := fn(l.data[iterId], l.nodes[iterId])
			ch <- val
			iterId = l.nodes[iterId].NextId

		}
	}()
	return ch
}

func (l *DoubleLinkedList[T]) Iter() <-chan T {
	return mapNodes(l, func(datum T, node *DLLNode) T { return datum })
}

func (l *DoubleLinkedList[T]) IterIds() <-chan DllId {
	return mapNodes(l, func(datum T, node *DLLNode) DllId { return node.Id })
}

func (l *DoubleLinkedList[T]) IterNodes() <-chan *DLLNode {
	return mapNodes(l, func(datum T, node *DLLNode) *DLLNode { return node })
}

func (l *DoubleLinkedList[T]) IterIdsFromLast() <-chan DllId {
	ch := make(chan DllId)
	go func() {
		defer close(ch)
		iterId := l.LastNode
		for iterId > -1 {
			ch <- iterId
			iterId = l.nodes[iterId].PreviousId
		}
	}()
	return ch
}

func (l *DoubleLinkedList[T]) GetById(id DllId) (T, bool) {
	if d, ok := l.data[id]; ok {
		return d, ok
	} else {
		var empty T
		return empty, false
	}
	//for iterId := range l.IterIds() {
	//	if iterId == id {
	//		return l.data[id], true
	//	}
	//}
	//var nilValue T
	//return nilValue, false
}

func (l *DoubleLinkedList[T]) Last() (T, bool) {
	if l.IsEmpty() {
		var empty T
		return empty, false
	}
	return l.data[l.lastGeneratedId], true
}

func (l *DoubleLinkedList[T]) LastId() (DllId, bool) {
	if l.IsEmpty() {
		return -1, false
	}
	return l.LastNode, true
}

func (l *DoubleLinkedList[T]) FirstId() (DllId, bool) {
	if l.IsEmpty() {
		return -1, false
	}
	return l.FirstNode, true
}

func (l *DoubleLinkedList[T]) NextId(id DllId) (DllId, bool) {
	nextId := l.nodes[id].NextId
	return nextId, nextId > -1
}

func (l *DoubleLinkedList[T]) previousNode(node *DLLNode) *DLLNode {
	if node.PreviousId != -1 {
		return l.nodes[node.PreviousId]
	}
	return nil
}

func (l *DoubleLinkedList[T]) nextNode(node *DLLNode) *DLLNode {
	if node.NextId != -1 {
		return l.nodes[node.NextId]
	}
	return nil
}

func (l *DoubleLinkedList[T]) insertBetween(before *DLLNode, after *DLLNode, data T) (DllId, bool) {
	if before == nil && after == nil {
		return l.insertEmpty(data), true
	}
	if before == nil {
		return l.InsertFirst(data), true
	}
	if after == nil {
		return l.InsertLast(data), true
	}
	id := l.nextId()
	node := standaloneNode(id)
	l.data[id] = data
	l.nodes[id] = node
	node.PreviousId = before.Id
	node.NextId = after.Id
	before.NextId = id
	after.PreviousId = id

	l.length++
	return id, true
}

func (l *DoubleLinkedList[T]) GroupByInPlace(combineValues func(a, b T) (T, bool)) {
	for node := l.nodes[l.FirstNode]; node.NextId > -1; node = l.nodes[node.NextId] {

		if _, ok := combineValues(l.data[node.Id], l.data[node.NextId]); ok {
			//l.InsertAfter(nodeId, combinedVal)
			//toRemove = append(toRemove, nodeId)

		}
	}
}

func (l *DoubleLinkedList[T]) FilterInPlace(predicate func(a T) bool) {

	toRemove := make([]DllId, 0)
	for node := range l.IterNodes() {
		//node := l.nodes[nodeId]
		if !predicate(l.data[node.Id]) {
			toRemove = append(toRemove, node.Id)
		}
	}
	for _, id := range toRemove {
		l.RemoveById(id)
	}
}

func (l *DoubleLinkedList[T]) RemoveById(id DllId) {
	node := l.nodes[id]

	if nextNode, nextOk := l.nodes[node.NextId]; nextOk {
		nextNode.PreviousId = node.PreviousId
	}

	if prevNode, prevOk := l.nodes[node.PreviousId]; prevOk {
		prevNode.NextId = node.NextId
	}
	delete(l.data, id)
	delete(l.nodes, id)
	l.length--

}