URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [container/] [list/] [list.go] - Blame information for rev 774

Go to most recent revision | Details | Compare with Previous | View Log


// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
 
// Package list implements a doubly linked list.
//
// To iterate over a list (where l is a *List):
//      for e := l.Front(); e != nil; e = e.Next() {
//              // do something with e.Value
//      }
//
package list
 
// Element is an element in the linked list.
type Element struct {
        // Next and previous pointers in the doubly-linked list of elements.
        // The front of the list has prev = nil, and the back has next = nil.
        next, prev *Element
 
        // The list to which this element belongs.
        list *List
 
        // The contents of this list element.
        Value interface{}
}
 
// Next returns the next list element or nil.
func (e *Element) Next() *Element { return e.next }
 
// Prev returns the previous list element or nil.
func (e *Element) Prev() *Element { return e.prev }
 
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
        front, back *Element
        len         int
}
 
// Init initializes or clears a List.
func (l *List) Init() *List {
        l.front = nil
        l.back = nil
        l.len = 0
        return l
}
 
// New returns an initialized list.
func New() *List { return new(List) }
 
// Front returns the first element in the list.
func (l *List) Front() *Element { return l.front }
 
// Back returns the last element in the list.
func (l *List) Back() *Element { return l.back }
 
// Remove removes the element from the list
// and returns its Value.
func (l *List) Remove(e *Element) interface{} {
        l.remove(e)
        e.list = nil // do what remove does not
        return e.Value
}
 
// remove the element from the list, but do not clear the Element's list field.
// This is so that other List methods may use remove when relocating Elements
// without needing to restore the list field.
func (l *List) remove(e *Element) {
        if e.list != l {
                return
        }
        if e.prev == nil {
                l.front = e.next
        } else {
                e.prev.next = e.next
        }
        if e.next == nil {
                l.back = e.prev
        } else {
                e.next.prev = e.prev
        }
 
        e.prev = nil
        e.next = nil
        l.len--
}
 
func (l *List) insertBefore(e *Element, mark *Element) {
        if mark.prev == nil {
                // new front of the list
                l.front = e
        } else {
                mark.prev.next = e
        }
        e.prev = mark.prev
        mark.prev = e
        e.next = mark
        l.len++
}
 
func (l *List) insertAfter(e *Element, mark *Element) {
        if mark.next == nil {
                // new back of the list
                l.back = e
        } else {
                mark.next.prev = e
        }
        e.next = mark.next
        mark.next = e
        e.prev = mark
        l.len++
}
 
func (l *List) insertFront(e *Element) {
        if l.front == nil {
                // empty list
                l.front, l.back = e, e
                e.prev, e.next = nil, nil
                l.len = 1
                return
        }
        l.insertBefore(e, l.front)
}
 
func (l *List) insertBack(e *Element) {
        if l.back == nil {
                // empty list
                l.front, l.back = e, e
                e.prev, e.next = nil, nil
                l.len = 1
                return
        }
        l.insertAfter(e, l.back)
}
 
// PushFront inserts the value at the front of the list and returns a new Element containing the value.
func (l *List) PushFront(value interface{}) *Element {
        e := &Element{nil, nil, l, value}
        l.insertFront(e)
        return e
}
 
// PushBack inserts the value at the back of the list and returns a new Element containing the value.
func (l *List) PushBack(value interface{}) *Element {
        e := &Element{nil, nil, l, value}
        l.insertBack(e)
        return e
}
 
// InsertBefore inserts the value immediately before mark and returns a new Element containing the value.
func (l *List) InsertBefore(value interface{}, mark *Element) *Element {
        if mark.list != l {
                return nil
        }
        e := &Element{nil, nil, l, value}
        l.insertBefore(e, mark)
        return e
}
 
// InsertAfter inserts the value immediately after mark and returns a new Element containing the value.
func (l *List) InsertAfter(value interface{}, mark *Element) *Element {
        if mark.list != l {
                return nil
        }
        e := &Element{nil, nil, l, value}
        l.insertAfter(e, mark)
        return e
}
 
// MoveToFront moves the element to the front of the list.
func (l *List) MoveToFront(e *Element) {
        if e.list != l || l.front == e {
                return
        }
        l.remove(e)
        l.insertFront(e)
}
 
// MoveToBack moves the element to the back of the list.
func (l *List) MoveToBack(e *Element) {
        if e.list != l || l.back == e {
                return
        }
        l.remove(e)
        l.insertBack(e)
}
 
// Len returns the number of elements in the list.
func (l *List) Len() int { return l.len }
 
// PushBackList inserts each element of ol at the back of the list.
func (l *List) PushBackList(ol *List) {
        last := ol.Back()
        for e := ol.Front(); e != nil; e = e.Next() {
                l.PushBack(e.Value)
                if e == last {
                        break
                }
        }
}
 
// PushFrontList inserts each element of ol at the front of the list. The ordering of the passed list is preserved.
func (l *List) PushFrontList(ol *List) {
        first := ol.Front()
        for e := ol.Back(); e != nil; e = e.Prev() {
                l.PushFront(e.Value)
                if e == first {
                        break
                }
        }
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [container/] [list/] [list.go] - Blame information for rev 774

Line No.	Rev	Author	Line
1	747	jeremybenn	`// 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			`// Package list 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			`}`