cblgh
7bfd1fcf2c
this stack implementation has a fixed-size. new items are pushed to the front and, if the capacity has been met, the last item gets evicted. if you push an item onto the stack that was already on the stack, this "bumps" that item by merely moves the item to the front (as opposed to allowing duplicates). the capacity is set at initialization. the intended use case for this data structure is for the iroh-tracker to only keep a fixed amount of topics and, per topic, a fixed amount of peers. topics that are actively recalled get pushed to the front, and peers within a topic that are seen often also get pushed to the front. see examples/stack-example.go for how it can be used eventually i'll refactor this to use just bytes instead as that is more useful for the purpose of the tracker. this could also be an opportunity to look into generics since string & byte are basically interchangeable.
45 lines
1.0 KiB
Go
45 lines
1.0 KiB
Go
package stack
|
|
|
|
type Stack struct {
|
|
items []string
|
|
}
|
|
|
|
// NOTE (2026-09-06): this stack approach works!!
|
|
func NewStack(size int) *Stack {
|
|
s := Stack{items: make([]string, 0, size)}
|
|
return &s
|
|
}
|
|
|
|
// get evicted item
|
|
func (s *Stack) Push (newItem string) string {
|
|
if len(s.items) > 0 && s.items[0] == newItem {
|
|
return ""
|
|
}
|
|
prev := newItem
|
|
for i, elem := range s.items {
|
|
// insert newItem at front
|
|
if i == 0 {
|
|
prev = s.items[0]
|
|
s.items[0] = newItem
|
|
// newItem was in stack previously, perform in place swap and exit early
|
|
} else if elem == newItem {
|
|
s.items[i] = prev
|
|
return ""
|
|
} else {
|
|
// propagate change outwards in stack, moving all items one step further
|
|
temp := s.items[i]
|
|
s.items[i] = prev
|
|
prev = temp
|
|
}
|
|
}
|
|
// if we have capacity still, append the last item back onto the end of the staack
|
|
if len(s.items) < cap(s.items) {
|
|
s.items = append(s.items, prev)
|
|
} else {
|
|
// we evict the list item, forgetting about it and return the evicted item
|
|
return prev
|
|
}
|
|
return ""
|
|
}
|
|
|