Created
September 23, 2015 19:01
-
-
Save iamralch/86acbeea21c02af69e70 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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. | |
// | |
// Modified into a gotemplate by Nick Craig-Wood <nick@craig-wood.com> | |
// 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 education | |
// template type List(A) | |
// ListElement is an element of a linked list. | |
type StudentListElement struct { | |
// Next and previous pointers in the doubly-linked list of elements. | |
// To simplify the implementation, internally a list l is implemented | |
// as a ring, such that &l.root is both the next element of the last | |
// list element (l.Back()) and the previous element of the first list | |
// element (l.Front()). | |
next, prev *StudentListElement | |
// The list to which this element belongs. | |
list *StudentList | |
// The value stored with this element. | |
Value Student | |
} | |
// Next returns the next list element or nil. | |
func (e *StudentListElement) Next() *StudentListElement { | |
if p := e.next; p != &e.list.root { | |
return p | |
} | |
return nil | |
} | |
// Prev returns the previous list element or nil. | |
func (e *StudentListElement) Prev() *StudentListElement { | |
if p := e.prev; p != &e.list.root { | |
return p | |
} | |
return nil | |
} | |
// List represents a doubly linked list. | |
// The zero value for List is an empty list ready to use. | |
type StudentList struct { | |
root StudentListElement // sentinel list element, only &root, root.prev, and root.next are used | |
len int // current list length excluding (this) sentinel element | |
} | |
// Init initializes or clears list l. | |
func (l *StudentList) Init() *StudentList { | |
l.root.next = &l.root | |
l.root.prev = &l.root | |
l.len = 0 | |
return l | |
} | |
// New returns an initialized list. | |
func NewStudentList() *StudentList { return new(StudentList).Init() } | |
// Len returns the number of elements of list l. | |
func (l *StudentList) Len() int { return l.len } | |
// Front returns the first element of list l or nil | |
func (l *StudentList) Front() *StudentListElement { | |
if l.len == 0 { | |
return nil | |
} | |
return l.root.next | |
} | |
// Back returns the last element of list l or nil. | |
func (l *StudentList) Back() *StudentListElement { | |
if l.len == 0 { | |
return nil | |
} | |
return l.root.prev | |
} | |
// lazyInit lazily initializes a zero List value. | |
func (l *StudentList) lazyInit() { | |
if l.root.next == nil { | |
l.Init() | |
} | |
} | |
// insert inserts e after at, increments l.len, and returns e. | |
func (l *StudentList) insert(e, at *StudentListElement) *StudentListElement { | |
n := at.next | |
at.next = e | |
e.prev = at | |
e.next = n | |
n.prev = e | |
e.list = l | |
l.len++ | |
return e | |
} | |
// insertValue is a convenience wrapper for insert(&ListElement{Value: v}, at). | |
func (l *StudentList) insertValue(v Student, at *StudentListElement) *StudentListElement { | |
return l.insert(&StudentListElement{Value: v}, at) | |
} | |
// remove removes e from its list, decrements l.len, and returns e. | |
func (l *StudentList) remove(e *StudentListElement) *StudentListElement { | |
e.prev.next = e.next | |
e.next.prev = e.prev | |
e.next = nil // avoid memory leaks | |
e.prev = nil // avoid memory leaks | |
e.list = nil | |
l.len-- | |
return e | |
} | |
// Remove removes e from l if e is an element of list l. | |
// It returns the element value e.Value. | |
func (l *StudentList) Remove(e *StudentListElement) Student { | |
if e.list == l { | |
// if e.list == l, l must have been initialized when e was inserted | |
// in l or l == nil (e is a zero ListElement) and l.remove will crash | |
l.remove(e) | |
} | |
return e.Value | |
} | |
// Pushfront inserts a new element e with value v at the front of list l and returns e. | |
func (l *StudentList) PushFront(v Student) *StudentListElement { | |
l.lazyInit() | |
return l.insertValue(v, &l.root) | |
} | |
// PushBack inserts a new element e with value v at the back of list l and returns e. | |
func (l *StudentList) PushBack(v Student) *StudentListElement { | |
l.lazyInit() | |
return l.insertValue(v, l.root.prev) | |
} | |
// InsertBefore inserts a new element e with value v immediately before mark and returns e. | |
// If mark is not an element of l, the list is not modified. | |
func (l *StudentList) InsertBefore(v Student, mark *StudentListElement) *StudentListElement { | |
if mark.list != l { | |
return nil | |
} | |
// see comment in List.Remove about initialization of l | |
return l.insertValue(v, mark.prev) | |
} | |
// InsertAfter inserts a new element e with value v immediately after mark and returns e. | |
// If mark is not an element of l, the list is not modified. | |
func (l *StudentList) InsertAfter(v Student, mark *StudentListElement) *StudentListElement { | |
if mark.list != l { | |
return nil | |
} | |
// see comment in List.Remove about initialization of l | |
return l.insertValue(v, mark) | |
} | |
// MoveToFront moves element e to the front of list l. | |
// If e is not an element of l, the list is not modified. | |
func (l *StudentList) MoveToFront(e *StudentListElement) { | |
if e.list != l || l.root.next == e { | |
return | |
} | |
// see comment in List.Remove about initialization of l | |
l.insert(l.remove(e), &l.root) | |
} | |
// MoveToBack moves element e to the back of list l. | |
// If e is not an element of l, the list is not modified. | |
func (l *StudentList) MoveToBack(e *StudentListElement) { | |
if e.list != l || l.root.prev == e { | |
return | |
} | |
// see comment in List.Remove about initialization of l | |
l.insert(l.remove(e), l.root.prev) | |
} | |
// PushBackList inserts a copy of an other list at the back of list l. | |
// The lists l and other may be the same. | |
func (l *StudentList) PushBackList(other *StudentList) { | |
l.lazyInit() | |
for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() { | |
l.insertValue(e.Value, l.root.prev) | |
} | |
} | |
// PushFrontList inserts a copy of an other list at the front of list l. | |
// The lists l and other may be the same. | |
func (l *StudentList) PushFrontList(other *StudentList) { | |
l.lazyInit() | |
for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() { | |
l.insertValue(e.Value, &l.root) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment