| // Copyright 2015 AlexStocks(https://github.com/AlexStocks). |
| // All rights reserved. Use of this source code is |
| // governed by Apache License 2.0. |
| |
| // Package list implements a xor-doubly linked list in xor style |
| // whose interface is partially compatible with golang's list. |
| // incompatible interfaces: XorElement.Prev & XorElement.Next |
| // & XorList.Front & XorList.Back. |
| // |
| // To iterate over a list (where l is a *XorList): |
| // var p *XorElement = nil |
| // for e := l.Front(); e != nil; p, e = e, e.Next(p) { |
| // // do something with e.Value |
| // } |
| // or |
| // To iterate over a list in reverse (where l is a *XorList): |
| // var n *XorElement = nil |
| // for e := l.Back(); e != nil; n, e = e, e.Prev(n) { |
| // // do something with e.Value |
| // } |
| // or |
| // To delete a element in iteration |
| // var p *XorElement = nil |
| // for e := l.Front(); e != nil; p, e = e, e.Next(p) { |
| // if condition (e) { |
| // elem := e |
| // e, p = p, p.Prev(e) |
| // l.Remove(elem) |
| // } |
| // } |
| |
| package gxxorlist |
| |
| import ( |
| "fmt" |
| "unsafe" |
| ) |
| |
| // XorElement is an element of a xor-linked list. |
| type XorElement struct { |
| // Compute the bitwise XOR of this element's previous |
| // element's address and its next element's address |
| // and @PN stores the result |
| PN uintptr |
| |
| // The value stored with this element. |
| Value interface{} |
| } |
| |
| func uptr(p *XorElement) uintptr { |
| return (uintptr)(unsafe.Pointer(p)) |
| } |
| |
| func ptr(u uintptr) *XorElement { |
| return (*XorElement)(unsafe.Pointer(u)) |
| } |
| |
| // Next returns the next list element or nil. |
| func (e *XorElement) Next(prev *XorElement) *XorElement { |
| if e == nil || e.PN == 0 { |
| return nil |
| } |
| next := ptr(uptr(prev) ^ e.PN) |
| if next != nil && ptr(next.PN) == e { // then next is list's tail |
| next = nil |
| } |
| |
| return next |
| } |
| |
| // Prev returns the previous list element or nil. |
| func (e *XorElement) Prev(next *XorElement) *XorElement { |
| if e == nil || e.PN == 0 { |
| return nil |
| } |
| prev := ptr(uptr(next) ^ e.PN) |
| if prev != nil && ptr(prev.PN) == e { // then prev is list's head |
| prev = nil |
| } |
| |
| return prev |
| } |
| |
| // XorList represents a doubly linked list. |
| // The zero value for XorList is an empty list ready to use. |
| type XorList struct { |
| head XorElement // first sentinel list element, only &head, head.prev, and head.next are used |
| tail XorElement // last sentinel list element, only &tail, tail.prev, and tail.next are used |
| len int // current list length excluding @list.s two sentinel element |
| } |
| |
| // just for test |
| func (l *XorList) Output() { |
| fmt.Printf("fake head{addr:%p, PN:%#x, value:%v} --> \n", &l.head, l.head.PN, l.head.Value) |
| for e, p := l.Front(); e != nil; p, e = e, e.Next(p) { |
| fmt.Printf(" element{addr:%p, PN:%#x, value:%v} --> \n", &e, e.PN, e.Value) |
| } |
| fmt.Printf("fake tail{addr:%p, PN:%#x, value:%v}\n", &l.tail, l.tail.PN, l.tail.Value) |
| } |
| |
| // Init initializes or clears list l. |
| func (l *XorList) Init() *XorList { |
| l.head.PN = uptr(&l.tail) |
| l.tail.PN = uptr(&l.head) |
| l.len = 0 |
| |
| return l |
| } |
| |
| // New returns an initialized list. |
| func New() *XorList { return new(XorList).Init() } |
| |
| // Len returns the number of elements of list l. |
| // The complexity is O(1). |
| func (l *XorList) Len() int { return l.len } |
| |
| // Front returns the first element of list l or nil. |
| func (l *XorList) Front() (front, head *XorElement) { |
| if l.len == 0 { |
| return nil, nil |
| } |
| |
| return ptr(l.head.PN), &l.head |
| } |
| |
| // Back returns the last element of list l or nil. |
| func (l *XorList) Back() (back, tail *XorElement) { |
| if l.len == 0 { |
| return nil, nil |
| } |
| |
| return ptr(l.tail.PN), &l.tail |
| } |
| |
| // lazyInit lazily initializes a zero XorList value. |
| func (l *XorList) lazyInit() { |
| if l.head.PN == 0 || l.tail.PN == 0 || ptr(l.head.PN) == &l.tail { |
| l.Init() |
| } |
| } |
| |
| // insert inserts e after @prev and before @next, increments l.len, and returns e. |
| func (l *XorList) insert(e, prev, next *XorElement) *XorElement { |
| e.PN = uptr(prev) ^ uptr(next) |
| prev.PN ^= uptr(next) ^ uptr(e) |
| next.PN ^= uptr(prev) ^ uptr(e) |
| |
| l.len++ |
| |
| return e |
| } |
| |
| // insertValue is a convenience wrapper for insert(&XorElement{Value: v}, prev, next). |
| func (l *XorList) insertValue(v interface{}, prev, next *XorElement) *XorElement { |
| return l.insert(&XorElement{Value: v}, prev, next) |
| } |
| |
| // remove removes e from its list, decrements l.len, and returns e. |
| func (l *XorList) remove(e, prev, next *XorElement) *XorElement { |
| prev.PN ^= uptr(e) ^ uptr(next) |
| next.PN ^= uptr(e) ^ uptr(prev) |
| e.PN = 0 |
| |
| l.len-- |
| |
| return e |
| } |
| |
| func (l *XorList) prev(e *XorElement) *XorElement { |
| prev := &l.head |
| cur := prev.Next(nil) |
| for cur != nil && cur != e && cur != &l.tail { |
| prev, cur = cur, cur.Next(prev) |
| } |
| |
| if cur != e { |
| prev = nil |
| } |
| |
| return prev |
| } |
| |
| func (l *XorList) next(e *XorElement) *XorElement { |
| next := &l.tail |
| cur := next.Prev(nil) |
| for cur != nil && cur != e && cur != &l.head { |
| next, cur = cur, cur.Prev(next) |
| } |
| |
| if cur != e { |
| next = nil |
| } |
| |
| return next |
| } |
| |
| // Remove removes e from l if e is an element of list l. |
| // It returns the element value e.Value. |
| func (l *XorList) Remove(e *XorElement) interface{} { |
| prev := l.prev(e) |
| if prev != nil { |
| // if e.list == l, l must have been initialized when e was inserted |
| // in l or l == nil (e is a zero XorElement) and l.remove will crash |
| next := e.Next(prev) |
| if next == nil { |
| next = &l.tail |
| } |
| l.remove(e, prev, next) |
| } |
| |
| return e.Value |
| } |
| |
| // PushFront inserts a new element e with value v at the front of list l and returns e. |
| func (l *XorList) PushFront(v interface{}) *XorElement { |
| l.lazyInit() |
| return l.insertValue(v, &l.head, ptr(l.head.PN)) |
| } |
| |
| // PushBack inserts a new element e with value v at the back of list l and returns e. |
| func (l *XorList) PushBack(v interface{}) *XorElement { |
| l.lazyInit() |
| return l.insertValue(v, ptr(l.tail.PN), &l.tail) |
| } |
| |
| // 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 *XorList) InsertBefore(v interface{}, mark *XorElement) *XorElement { |
| prev := l.prev(mark) |
| if prev == nil { |
| return nil |
| } |
| |
| // see comment in XorList.Remove about initialization of l |
| return l.insertValue(v, prev, mark) |
| } |
| |
| // 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 *XorList) InsertAfter(v interface{}, mark *XorElement) *XorElement { |
| next := l.next(mark) |
| if next == nil { |
| return nil |
| } |
| |
| // see comment in XorList.Remove about initialization of l |
| return l.insertValue(v, mark, next) |
| } |
| |
| // 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 *XorList) MoveToFront(e *XorElement) { |
| prev := l.prev(e) |
| if prev == nil { |
| return |
| } |
| next := e.Next(prev) |
| if next == nil { |
| next = &l.tail |
| } |
| e = l.remove(e, prev, next) |
| |
| // see comment in XorList.Remove about initialization of l |
| l.insert(e, &l.head, ptr(l.head.PN)) |
| } |
| |
| // 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 *XorList) MoveToBack(e *XorElement) { |
| prev := l.prev(e) |
| if prev == nil { |
| return |
| } |
| next := e.Next(prev) |
| if next == nil { |
| next = &l.tail |
| } |
| e = l.remove(e, prev, next) |
| |
| // see comment in XorList.Remove about initialization of l |
| l.insert(e, ptr(l.tail.PN), &l.tail) |
| } |
| |
| // MoveBefore moves element e to its new position before mark. |
| // If e or mark is not an element of l, or e == mark, the list is not modified. |
| func (l *XorList) MoveBefore(e, mark *XorElement) { |
| if e == nil || mark == nil || e == mark { |
| return |
| } |
| |
| mark_prev := l.prev(mark) |
| if mark_prev == nil { |
| return |
| } |
| |
| e_prev := l.prev(e) |
| if e_prev == nil { |
| return |
| } |
| |
| e_next := e.Next(e_prev) |
| if e_next == nil { |
| e_next = &l.tail |
| } |
| e = l.remove(e, e_prev, e_next) |
| |
| mark_prev = l.prev(mark) |
| if mark_prev == nil { |
| return |
| } |
| l.insert(e, mark_prev, mark) |
| } |
| |
| // MoveAfter moves element e to its new position after mark. |
| // If e or mark is not an element of l, or e == mark, the list is not modified. |
| func (l *XorList) MoveAfter(e, mark *XorElement) { |
| if e == nil || mark == nil || e == mark { |
| return |
| } |
| |
| mark_prev := l.prev(mark) |
| if mark_prev == nil { |
| return |
| } |
| |
| e_prev := l.prev(e) |
| if e_prev == nil { |
| return |
| } |
| |
| e_next := e.Next(e_prev) |
| if e_next == nil { |
| e_next = &l.tail |
| } |
| e = l.remove(e, e_prev, e_next) |
| |
| mark_next := l.next(mark) |
| if mark_next == nil { |
| return |
| } |
| /* |
| mark_next = mark.Next(mark_prev) |
| if mark_next == nil { |
| mark_next = &l.tail |
| } |
| */ |
| l.insert(e, mark, mark_next) |
| } |
| |
| // 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 *XorList) PushBackList(other *XorList) { |
| l.lazyInit() |
| i := other.Len() |
| for e, p := other.Front(); i > 0 && e != nil; e, p = e.Next(p), e { |
| // l.insertValue(e.Value, l.tail.Prev(nil), &l.tail) |
| l.PushBack(e.Value) |
| i-- |
| } |
| } |
| |
| // 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 *XorList) PushFrontList(other *XorList) { |
| l.lazyInit() |
| i := other.Len() |
| for e, n := other.Back(); i > 0 && e != nil; n, e = e, e.Prev(n) { |
| // l.insertValue(e.Value, &l.head, (&l.head).Next(nil)) |
| l.PushFront(e.Value) |
| i-- |
| } |
| } |