This repository has been archived by the owner on Jun 9, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
list.go
80 lines (63 loc) · 1.84 KB
/
list.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
package synclist
import (
"github.com/djordje200179/extendedlibrary/datastructures/iter"
"sync/atomic"
)
// List is a lock-free singly linked list.
// It is safe to use it concurrently from multiple goroutines.
// The zero value is ready to use. Do not copy a non-zero List.
type List[T any] struct {
head atomic.Pointer[Node[T]]
}
// New creates an empty List.
func New[T any]() *List[T] {
return new(List[T])
}
// NewFromIterable creates a List from the specified iter.Iterable in
// reverse order. List.Reverse can be used to restore the original order.
func NewFromIterable[T any](iterable iter.Iterable[T]) *List[T] {
list := New[T]()
for it := iterable.Iterator(); it.Valid(); it.Move() {
list.Prepend(it.Get())
}
return list
}
// Prepend adds the specified value to the beginning of the List.
func (list *List[T]) Prepend(value T) {
node := &Node[T]{Value: value}
node.next = list.head.Swap(node)
}
// Clear removes all elements from the List.
func (list *List[T]) Clear() {
list.head.Store(nil)
}
// Reverse reverses the order of the elements in the List.
// This method is not thread-safe. It is meant to be used after
// all concurrent operations on the List have finished.
func (list *List[T]) Reverse() {
var prev *Node[T]
curr := list.head.Load()
for curr != nil {
next := curr.next
curr.next = prev
prev = curr
curr = next
}
list.head.Store(prev)
}
// Iterator returns an iterator over the elements in the List.
func (list *List[T]) Iterator() iter.Iterator[T] {
return &Iterator[T]{curr: list.head.Load()}
}
// Stream streams the elements of the List.
func (list *List[T]) Stream(yield func(T) bool) {
for curr := list.head.Load(); curr != nil; curr = curr.next {
if !yield(curr.Value) {
break
}
}
}
// Head returns the first element in the List.
func (list *List[T]) Head() *Node[T] {
return list.head.Load()
}