/
list.go
139 lines (125 loc) · 3.09 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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
package seq
// A List is an implementation of Seq in the form of a single-linked-list, and
// is used as the underlying structure for Seqs for most methods that return a
// Seq. It is probably the most efficient and simplest of the implementations.
// Even though, conceptually, all Seq operations return a new Seq, the old Seq
// can actually share nodes with the new Seq (if both are Lists), thereby saving
// memory and copies.
type List struct {
el interface{}
next *List
}
// Returns a new List comprised of the given elements (or no elements, for an
// empty list)
func NewList(els ...interface{}) *List {
elsl := len(els)
if elsl == 0 {
return nil
}
var cur *List
for i := 0; i < elsl; i++ {
cur = &List{els[elsl-i-1], cur}
}
return cur
}
// Implementation of FirstRest for Seq interface. Completes in O(1) time.
func (l *List) FirstRest() (interface{}, Seq, bool) {
if l == nil {
return nil, l, false
} else {
return l.el, l.next, true
}
}
// Implementation of String for Stringer interface.
func (l *List) String() string {
return ToString(l, "(", ")")
}
// Prepends the given element to the front of the list, returning a copy of the
// new list. Completes in O(1) time.
func (l *List) Prepend(el interface{}) *List {
return &List{el, l}
}
// Prepends the argument Seq to the beginning of the callee List, returning a
// copy of the new List. Completes in O(N) time, N being the length of the
// argument Seq
func (l *List) PrependSeq(s Seq) *List {
var first, cur, prev *List
var el interface{}
var ok bool
for {
el, s, ok = s.FirstRest()
if !ok {
break
}
cur = &List{el, nil}
if first == nil {
first = cur
}
if prev != nil {
prev.next = cur
}
prev = cur
}
// prev will be nil if s is empty
if prev == nil {
return l
}
prev.next = l
return first
}
// Appends the given element to the end of the List, returning a copy of the new
// List. While most methods on List don't actually copy much data, this one
// copies the entire list. Completes in O(N) time.
func (l *List) Append(el interface{}) *List {
var first, cur, prev *List
for l != nil {
cur = &List{l.el, nil}
if first == nil {
first = cur
}
if prev != nil {
prev.next = cur
}
prev = cur
l = l.next
}
final := &List{el, nil}
if prev == nil {
return final
}
prev.next = final
return first
}
// Returns the nth index element (starting at 0), with bool being false if i is
// out of bounds. Completes in O(N) time.
func (l *List) Nth(n uint64) (interface{}, bool) {
var el interface{}
var ok bool
s := Seq(l)
for i := uint64(0);; i++ {
el, s, ok = s.FirstRest()
if !ok {
return nil, false
} else if i == n {
return el, true
}
}
}
// Returns the elements in the Seq as a List. Has similar properties as
// ToSlice. In general this completes in O(N) time. If the given Seq is already
// a List it will complete in O(1) time.
func ToList(s Seq) *List {
var ok bool
var l *List
if l, ok = s.(*List); ok {
return l
}
var el interface{}
for ret := NewList();; {
if el, s, ok = s.FirstRest(); ok {
ret = ret.Prepend(el)
} else {
return Reverse(ret).(*List)
}
}
}