← Back to branch summary

~john-koepi/ubuntu/trusty/golang/default

« back to all changes in this revision

Viewing changes to src/pkg/container/list/list.go

  • Committer: Bazaar Package Importer
  • Author(s): Ondřej Surý
  • Date: 2011-04-20 17:36:48 UTC
  • Revision ID: james.westby@ubuntu.com-20110420173648-ifergoxyrm832trd
Tags: upstream-2011.03.07.1
Import upstream version 2011.03.07.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/container/list/list.go
 
1
// Copyright 2009 The Go Authors. All rights reserved.
 
2
// Use of this source code is governed by a BSD-style
 
3
// license that can be found in the LICENSE file.
 
4
 
 
5
// The list package implements a doubly linked list.
 
6
//
 
7
// To iterate over a list (where l is a *List):
 
8
//      for e := l.Front(); e != nil; e = e.Next() {
 
9
//              // do something with e.Value
 
10
//      }
 
11
//
 
12
package list
 
13
 
 
14
// Element is an element in the linked list.
 
15
type Element struct {
 
16
        // Next and previous pointers in the doubly-linked list of elements.
 
17
        // The front of the list has prev = nil, and the back has next = nil.
 
18
        next, prev *Element
 
19
 
 
20
        // The list to which this element belongs.
 
21
        list *List
 
22
 
 
23
        // The contents of this list element.
 
24
        Value interface{}
 
25
}
 
26
 
 
27
// Next returns the next list element or nil.
 
28
func (e *Element) Next() *Element { return e.next }
 
29
 
 
30
// Prev returns the previous list element or nil.
 
31
func (e *Element) Prev() *Element { return e.prev }
 
32
 
 
33
// List represents a doubly linked list.
 
34
// The zero value for List is an empty list ready to use.
 
35
type List struct {
 
36
        front, back *Element
 
37
        len         int
 
38
}
 
39
 
 
40
// Init initializes or clears a List.
 
41
func (l *List) Init() *List {
 
42
        l.front = nil
 
43
        l.back = nil
 
44
        l.len = 0
 
45
        return l
 
46
}
 
47
 
 
48
// New returns an initialized list.
 
49
func New() *List { return new(List) }
 
50
 
 
51
// Front returns the first element in the list.
 
52
func (l *List) Front() *Element { return l.front }
 
53
 
 
54
// Back returns the last element in the list.
 
55
func (l *List) Back() *Element { return l.back }
 
56
 
 
57
// Remove removes the element from the list
 
58
// and returns its Value.
 
59
func (l *List) Remove(e *Element) interface{} {
 
60
        l.remove(e)
 
61
        e.list = nil // do what remove does not
 
62
        return e.Value
 
63
}
 
64
 
 
65
// remove the element from the list, but do not clear the Element's list field.
 
66
// This is so that other List methods may use remove when relocating Elements
 
67
// without needing to restore the list field.
 
68
func (l *List) remove(e *Element) {
 
69
        if e.list != l {
 
70
                return
 
71
        }
 
72
        if e.prev == nil {
 
73
                l.front = e.next
 
74
        } else {
 
75
                e.prev.next = e.next
 
76
        }
 
77
        if e.next == nil {
 
78
                l.back = e.prev
 
79
        } else {
 
80
                e.next.prev = e.prev
 
81
        }
 
82
 
 
83
        e.prev = nil
 
84
        e.next = nil
 
85
        l.len--
 
86
}
 
87
 
 
88
func (l *List) insertBefore(e *Element, mark *Element) {
 
89
        if mark.prev == nil {
 
90
                // new front of the list
 
91
                l.front = e
 
92
        } else {
 
93
                mark.prev.next = e
 
94
        }
 
95
        e.prev = mark.prev
 
96
        mark.prev = e
 
97
        e.next = mark
 
98
        l.len++
 
99
}
 
100
 
 
101
func (l *List) insertAfter(e *Element, mark *Element) {
 
102
        if mark.next == nil {
 
103
                // new back of the list
 
104
                l.back = e
 
105
        } else {
 
106
                mark.next.prev = e
 
107
        }
 
108
        e.next = mark.next
 
109
        mark.next = e
 
110
        e.prev = mark
 
111
        l.len++
 
112
}
 
113
 
 
114
func (l *List) insertFront(e *Element) {
 
115
        if l.front == nil {
 
116
                // empty list
 
117
                l.front, l.back = e, e
 
118
                e.prev, e.next = nil, nil
 
119
                l.len = 1
 
120
                return
 
121
        }
 
122
        l.insertBefore(e, l.front)
 
123
}
 
124
 
 
125
func (l *List) insertBack(e *Element) {
 
126
        if l.back == nil {
 
127
                // empty list
 
128
                l.front, l.back = e, e
 
129
                e.prev, e.next = nil, nil
 
130
                l.len = 1
 
131
                return
 
132
        }
 
133
        l.insertAfter(e, l.back)
 
134
}
 
135
 
 
136
// PushFront inserts the value at the front of the list and returns a new Element containing the value.
 
137
func (l *List) PushFront(value interface{}) *Element {
 
138
        e := &Element{nil, nil, l, value}
 
139
        l.insertFront(e)
 
140
        return e
 
141
}
 
142
 
 
143
// PushBack inserts the value at the back of the list and returns a new Element containing the value.
 
144
func (l *List) PushBack(value interface{}) *Element {
 
145
        e := &Element{nil, nil, l, value}
 
146
        l.insertBack(e)
 
147
        return e
 
148
}
 
149
 
 
150
// InsertBefore inserts the value immediately before mark and returns a new Element containing the value.
 
151
func (l *List) InsertBefore(value interface{}, mark *Element) *Element {
 
152
        if mark.list != l {
 
153
                return nil
 
154
        }
 
155
        e := &Element{nil, nil, l, value}
 
156
        l.insertBefore(e, mark)
 
157
        return e
 
158
}
 
159
 
 
160
// InsertAfter inserts the value immediately after mark and returns a new Element containing the value.
 
161
func (l *List) InsertAfter(value interface{}, mark *Element) *Element {
 
162
        if mark.list != l {
 
163
                return nil
 
164
        }
 
165
        e := &Element{nil, nil, l, value}
 
166
        l.insertAfter(e, mark)
 
167
        return e
 
168
}
 
169
 
 
170
// MoveToFront moves the element to the front of the list.
 
171
func (l *List) MoveToFront(e *Element) {
 
172
        if e.list != l || l.front == e {
 
173
                return
 
174
        }
 
175
        l.remove(e)
 
176
        l.insertFront(e)
 
177
}
 
178
 
 
179
// MoveToBack moves the element to the back of the list.
 
180
func (l *List) MoveToBack(e *Element) {
 
181
        if e.list != l || l.back == e {
 
182
                return
 
183
        }
 
184
        l.remove(e)
 
185
        l.insertBack(e)
 
186
}
 
187
 
 
188
// Len returns the number of elements in the list.
 
189
func (l *List) Len() int { return l.len }
 
190
 
 
191
// PushBackList inserts each element of ol at the back of the list.
 
192
func (l *List) PushBackList(ol *List) {
 
193
        last := ol.Back()
 
194
        for e := ol.Front(); e != nil; e = e.Next() {
 
195
                l.PushBack(e.Value)
 
196
                if e == last {
 
197
                        break
 
198
                }
 
199
        }
 
200
}
 
201
 
 
202
// PushFrontList inserts each element of ol at the front of the list. The ordering of the passed list is preserved.
 
203
func (l *List) PushFrontList(ol *List) {
 
204
        first := ol.Front()
 
205
        for e := ol.Back(); e != nil; e = e.Prev() {
 
206
                l.PushFront(e.Value)
 
207
                if e == first {
 
208
                        break
 
209
                }
 
210
        }
 
211
}