container: github.com/ionous/container/inlist Index | Examples | Files

package inlist

import "github.com/ionous/container/inlist"

Package inlist implements an intrusive doubly linked list.

To iterate over a list (where l is a *List):

for e := l.Front(); e != nil; e = inlist.Next(e) {
	// do something with e
}

Code:

// Create a new list and put some numbers in it.
l := inlist.New()
e4 := l.PushBack(inlist.NewElement(4))
e1 := l.PushFront(inlist.NewElement(1))
l.InsertBefore(inlist.NewElement(3), e4)
l.InsertAfter(inlist.NewElement(2), e1)

// Iterate through list and print its contents.
for e := l.Front(); e != nil; e = inlist.Next(e) {
    fmt.Println(inlist.Value(e))
}

Output:

1
2
3
4

Index

Examples

Package Files

list.go

func Value Uses

func Value(i Intrusive) interface{}

Value returns the contents of an element created via NewElement. This panics if i is nil, or of any type other than Element.

type Element Uses

type Element struct {
    Hook
    Value interface{}
}

Element mimics golang's container/list/Element; this implements the ilist/inlist/Intrusive interface to allow the storage of generic values in inlist.List. see also: NewElement(), and Value()

type Hook Uses

type Hook struct {
    // contains filtered or unexported fields
}

Hook provides an implementation of Intrusive with no additional data. Use this as an anonymous member of a struct to create an intrusive element. ( Alternatively, you can implement the Intrusive interface yourself. )

For example: type MyElement struct {

inlist.Hook
MyData int // or whatever data you need.

} l:= inlist.New() l.PushBack(&MyElement{MyData:23})

Code:

// Create a custom list element
type MyElement struct {
    inlist.Hook     // anonymous support for the intrusive list; alternatively, users can implement the inlist.Intrusive interface for more control.
    MyData      int // some example data.
}
l := inlist.New()
l.PushBack(&MyElement{MyData: 17})
l.PushFront(&MyElement{MyData: 20})
//
for e := l.Front(); e != nil; e = inlist.Next(e) {
    fmt.Println(e.(*MyElement).MyData)
}

Output:

20
17

func (*Hook) List Uses

func (s *Hook) List() *List

List implements Intrusive.List: returning the list pointer provided by SetElements().

func (*Hook) Predecessor Uses

func (s *Hook) Predecessor() Intrusive

Predecessor implements Intrusive.Predecessor: returning the prev sibling provided by SetElements().

func (*Hook) SetElements Uses

func (s *Hook) SetElements(l *List, p Intrusive, n Intrusive)

SetElements implements Intrusive.SetElements: storing the passed values without checking or changing them.

func (*Hook) Successor Uses

func (s *Hook) Successor() Intrusive

Successor implements Intrusive.Successor: returning the next sibling provided by SetElements().

type Intrusive Uses

type Intrusive interface {
    // List, return the list given via SetElements.
    List() *List
    // Predecessor, return the prev element given via SetElements.
    Predecessor() Intrusive
    // Successor, return the next element given via SetElements.
    Successor() Intrusive
    // SetElements, record the passed values as given.
    SetElements(list *List, prev Intrusive, next Intrusive)
}

Intrusive provides an interface for intrusive linked list manipulation. Use inlist.Next(), inlist.Prev() for list traversal.

func NewElement Uses

func NewElement(v interface{}) Intrusive

NewElement creates an intrusive Element to store the passed value.

func Next Uses

func Next(e Intrusive) (ret Intrusive)

Next returns the next list element or nil. Unlike e.Successor, this accounts for the list's sentinel.

func Prev Uses

func Prev(e Intrusive) (ret Intrusive)

Prev returns the previous list element or nil. Unlike e.Predecessor, this accounts for the list's sentinel.

type List Uses

type List struct {
    // contains filtered or unexported fields
}

List is an intrusive doubly linked list, implemented as a ring. The zero value for List is empty and ready to use.

func New Uses

func New() *List

New returns an initialized list.

func (*List) Back Uses

func (l *List) Back() (ret Intrusive)

Back returns the last element of list l or nil.

func (*List) Front Uses

func (l *List) Front() (ret Intrusive)

Front returns the first element of list l or nil.

func (*List) Init Uses

func (l *List) Init() *List

Init initializes or clears list l.

func (*List) InsertAfter Uses

func (l *List) InsertAfter(v Intrusive, mark Intrusive) (ret Intrusive)

InsertAfter inserts e directly following mark and returns e. If mark is not in this list, no insertion occurs, and this returns nil.

func (*List) InsertBefore Uses

func (l *List) InsertBefore(v Intrusive, mark Intrusive) (ret Intrusive)

InsertBefore inserts e directly ahead of mark and returns e. If mark is not in this list, no insertion occurs, and this returns nil.

func (*List) Len Uses

func (l *List) Len() int

Len returns the number of elements of list l. The complexity is O(1).

func (*List) MoveAfter Uses

func (l *List) MoveAfter(e, mark Intrusive) (okay bool)

MoveAfter puts element e directly behind mark, and returns true. If e or mark is not in this list, or e == mark, the list is not modified, and this returns false.

func (*List) MoveBackList Uses

func (l *List) MoveBackList(other *List)

MoveBackList moves all elements from other to the end of this list.

func (*List) MoveBefore Uses

func (l *List) MoveBefore(e, mark Intrusive) (okay bool)

MoveBefore puts e directly in front of mark, and returns true. If e or mark is not in this list, or e == mark, the list is not modified, and this returns false.

func (*List) MoveFrontList Uses

func (l *List) MoveFrontList(other *List)

MoveFrontList moves all elements from other to the front of this list.

func (*List) MoveToBack Uses

func (l *List) MoveToBack(e Intrusive) (okay bool)

MoveToBack puts e at the tail of the list, and returns true. If e is not in this list, the list is not modified, and this returns false.

func (*List) MoveToFront Uses

func (l *List) MoveToFront(e Intrusive) (okay bool)

MoveToFront moves element e to the head the list, and returns true. If e is not in this list, the list is not modified, and this returns false.

func (*List) PushBack Uses

func (l *List) PushBack(e Intrusive) Intrusive

PushBack inserts e at the tail of list l and returns e.

func (*List) PushFront Uses

func (l *List) PushFront(e Intrusive) Intrusive

PushFront inserts e at the head of list l and returns e.

func (*List) Remove Uses

func (l *List) Remove(e Intrusive) (okay bool)

Remove removes e from l if e is an element of list l. It returns true if it was removed.

Updated 2017-03-12. Refresh now. Tools for package owners.