Source file 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	// 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	}