-
Notifications
You must be signed in to change notification settings - Fork 22
/
walker.go
100 lines (79 loc) · 2.98 KB
/
walker.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
package walker
import (
"container/list"
"github.com/iotaledger/hive.go/ds/orderedmap"
"github.com/iotaledger/hive.go/ds/types"
"github.com/iotaledger/hive.go/lo"
)
// region Walker /////////////////////////////////////////////////////////////////////////////////////////////////////////
// Walker implements a generic data structure that simplifies walks over collections or data structures.
type Walker[T comparable] struct {
stack *list.List
pushedElements *orderedmap.OrderedMap[T, types.Empty]
walkStopped bool
revisitElements bool
}
// New is the constructor of the Walker. It accepts an optional boolean flag that controls whether the Walker will visit
// the same Element multiple times.
func New[T comparable](revisitElements ...bool) *Walker[T] {
return &Walker[T]{
stack: list.New(),
pushedElements: orderedmap.New[T, types.Empty](),
revisitElements: len(revisitElements) > 0 && revisitElements[0],
}
}
// HasNext returns true if the Walker has another element that shall be visited.
func (w *Walker[T]) HasNext() bool {
return w.stack.Len() > 0 && !w.walkStopped
}
// Pushed returns true if the passed element was Pushed to the Walker.
func (w *Walker[T]) Pushed(element T) bool {
return w.pushedElements.Has(element)
}
// Next returns the next element of the walk.
func (w *Walker[T]) Next() (nextElement T) {
currentEntry := w.stack.Front()
w.stack.Remove(currentEntry)
//nolint:forcetypeassert // false positive, we know that the element is of type T
return currentEntry.Value.(T)
}
// Push adds a new element to the walk, which can consequently be retrieved by calling the Next method.
func (w *Walker[T]) Push(nextElement T) (walker *Walker[T]) {
if lo.Return2(w.pushedElements.Set(nextElement, types.Void)) && !w.revisitElements {
return w
}
w.stack.PushBack(nextElement)
return w
}
// PushAll adds new elements to the walk, which can consequently be retrieved by calling the Next method.
func (w *Walker[T]) PushAll(nextElements ...T) (walker *Walker[T]) {
for _, nextElement := range nextElements {
w.Push(nextElement)
}
return w
}
// PushFront adds a new element to the front of the queue, which can consequently be retrieved by calling the Next method.
func (w *Walker[T]) PushFront(nextElements ...T) (walker *Walker[T]) {
for _, nextElement := range nextElements {
if lo.Return2(w.pushedElements.Set(nextElement, types.Void)) && !w.revisitElements {
return w
}
w.stack.PushFront(nextElement)
}
return w
}
// StopWalk aborts the walk and forces HasNext to always return false.
func (w *Walker[T]) StopWalk() {
w.walkStopped = true
}
// WalkStopped returns true if the Walk has been stopped.
func (w *Walker[T]) WalkStopped() bool {
return w.walkStopped
}
// Reset removes all queued elements and reset walkStopped.
func (w *Walker[T]) Reset() {
w.stack.Init()
w.pushedElements.Clear()
w.walkStopped = false
}
// endregion ///////////////////////////////////////////////////////////////////////////////////////////////////////////