list2.go

     1  // run
     2  
     3  // Copyright 2021 The Go Authors. All rights reserved.
     4  // Use of this source code is governed by a BSD-style
     5  // license that can be found in the LICENSE file.
     6  
     7  // Package list provides a doubly linked list of some element type
     8  // (generic form of the "container/list" package).
     9  
    10  package main
    11  
    12  import (
    13  	"fmt"
    14  	"strconv"
    15  )
    16  
    17  // _Element is an element of a linked list.
    18  type _Element[T any] struct {
    19  	// Next and previous pointers in the doubly-linked list of elements.
    20  	// To simplify the implementation, internally a list l is implemented
    21  	// as a ring, such that &l.root is both the next element of the last
    22  	// list element (l.Back()) and the previous element of the first list
    23  	// element (l.Front()).
    24  	next, prev *_Element[T]
    25  
    26  	// The list to which this element belongs.
    27  	list *_List[T]
    28  
    29  	// The value stored with this element.
    30  	Value T
    31  }
    32  
    33  // Next returns the next list element or nil.
    34  func (e *_Element[T]) Next() *_Element[T] {
    35  	if p := e.next; e.list != nil && p != &e.list.root {
    36  		return p
    37  	}
    38  	return nil
    39  }
    40  
    41  // Prev returns the previous list element or nil.
    42  func (e *_Element[T]) Prev() *_Element[T] {
    43  	if p := e.prev; e.list != nil && p != &e.list.root {
    44  		return p
    45  	}
    46  	return nil
    47  }
    48  
    49  // _List represents a doubly linked list.
    50  // The zero value for _List is an empty list ready to use.
    51  type _List[T any] struct {
    52  	root _Element[T] // sentinel list element, only &root, root.prev, and root.next are used
    53  	len  int         // current list length excluding (this) sentinel element
    54  }
    55  
    56  // Init initializes or clears list l.
    57  func (l *_List[T]) Init() *_List[T] {
    58  	l.root.next = &l.root
    59  	l.root.prev = &l.root
    60  	l.len = 0
    61  	return l
    62  }
    63  
    64  // New returns an initialized list.
    65  func _New[T any]() *_List[T] { return new(_List[T]).Init() }
    66  
    67  // Len returns the number of elements of list l.
    68  // The complexity is O(1).
    69  func (l *_List[_]) Len() int { return l.len }
    70  
    71  // Front returns the first element of list l or nil if the list is empty.
    72  func (l *_List[T]) Front() *_Element[T] {
    73  	if l.len == 0 {
    74  		return nil
    75  	}
    76  	return l.root.next
    77  }
    78  
    79  // Back returns the last element of list l or nil if the list is empty.
    80  func (l *_List[T]) Back() *_Element[T] {
    81  	if l.len == 0 {
    82  		return nil
    83  	}
    84  	return l.root.prev
    85  }
    86  
    87  // lazyInit lazily initializes a zero _List value.
    88  func (l *_List[_]) lazyInit() {
    89  	if l.root.next == nil {
    90  		l.Init()
    91  	}
    92  }
    93  
    94  // insert inserts e after at, increments l.len, and returns e.
    95  func (l *_List[T]) insert(e, at *_Element[T]) *_Element[T] {
    96  	e.prev = at
    97  	e.next = at.next
    98  	e.prev.next = e
    99  	e.next.prev = e
   100  	e.list = l
   101  	l.len++
   102  	return e
   103  }
   104  
   105  // insertValue is a convenience wrapper for insert(&_Element[T]{Value: v}, at).
   106  func (l *_List[T]) insertValue(v T, at *_Element[T]) *_Element[T] {
   107  	return l.insert(&_Element[T]{Value: v}, at)
   108  }
   109  
   110  // remove removes e from its list, decrements l.len, and returns e.
   111  func (l *_List[T]) remove(e *_Element[T]) *_Element[T] {
   112  	e.prev.next = e.next
   113  	e.next.prev = e.prev
   114  	e.next = nil // avoid memory leaks
   115  	e.prev = nil // avoid memory leaks
   116  	e.list = nil
   117  	l.len--
   118  	return e
   119  }
   120  
   121  // move moves e to next to at and returns e.
   122  func (l *_List[T]) move(e, at *_Element[T]) *_Element[T] {
   123  	if e == at {
   124  		return e
   125  	}
   126  	e.prev.next = e.next
   127  	e.next.prev = e.prev
   128  
   129  	e.prev = at
   130  	e.next = at.next
   131  	e.prev.next = e
   132  	e.next.prev = e
   133  
   134  	return e
   135  }
   136  
   137  // Remove removes e from l if e is an element of list l.
   138  // It returns the element value e.Value.
   139  // The element must not be nil.
   140  func (l *_List[T]) Remove(e *_Element[T]) T {
   141  	if e.list == l {
   142  		// if e.list == l, l must have been initialized when e was inserted
   143  		// in l or l == nil (e is a zero _Element) and l.remove will crash
   144  		l.remove(e)
   145  	}
   146  	return e.Value
   147  }
   148  
   149  // PushFront inserts a new element e with value v at the front of list l and returns e.
   150  func (l *_List[T]) PushFront(v T) *_Element[T] {
   151  	l.lazyInit()
   152  	return l.insertValue(v, &l.root)
   153  }
   154  
   155  // PushBack inserts a new element e with value v at the back of list l and returns e.
   156  func (l *_List[T]) PushBack(v T) *_Element[T] {
   157  	l.lazyInit()
   158  	return l.insertValue(v, l.root.prev)
   159  }
   160  
   161  // InsertBefore inserts a new element e with value v immediately before mark and returns e.
   162  // If mark is not an element of l, the list is not modified.
   163  // The mark must not be nil.
   164  func (l *_List[T]) InsertBefore(v T, mark *_Element[T]) *_Element[T] {
   165  	if mark.list != l {
   166  		return nil
   167  	}
   168  	// see comment in _List.Remove about initialization of l
   169  	return l.insertValue(v, mark.prev)
   170  }
   171  
   172  // InsertAfter inserts a new element e with value v immediately after mark and returns e.
   173  // If mark is not an element of l, the list is not modified.
   174  // The mark must not be nil.
   175  func (l *_List[T]) InsertAfter(v T, mark *_Element[T]) *_Element[T] {
   176  	if mark.list != l {
   177  		return nil
   178  	}
   179  	// see comment in _List.Remove about initialization of l
   180  	return l.insertValue(v, mark)
   181  }
   182  
   183  // MoveToFront moves element e to the front of list l.
   184  // If e is not an element of l, the list is not modified.
   185  // The element must not be nil.
   186  func (l *_List[T]) MoveToFront(e *_Element[T]) {
   187  	if e.list != l || l.root.next == e {
   188  		return
   189  	}
   190  	// see comment in _List.Remove about initialization of l
   191  	l.move(e, &l.root)
   192  }
   193  
   194  // MoveToBack moves element e to the back of list l.
   195  // If e is not an element of l, the list is not modified.
   196  // The element must not be nil.
   197  func (l *_List[T]) MoveToBack(e *_Element[T]) {
   198  	if e.list != l || l.root.prev == e {
   199  		return
   200  	}
   201  	// see comment in _List.Remove about initialization of l
   202  	l.move(e, l.root.prev)
   203  }
   204  
   205  // MoveBefore moves element e to its new position before mark.
   206  // If e or mark is not an element of l, or e == mark, the list is not modified.
   207  // The element and mark must not be nil.
   208  func (l *_List[T]) MoveBefore(e, mark *_Element[T]) {
   209  	if e.list != l || e == mark || mark.list != l {
   210  		return
   211  	}
   212  	l.move(e, mark.prev)
   213  }
   214  
   215  // MoveAfter moves element e to its new position after mark.
   216  // If e or mark is not an element of l, or e == mark, the list is not modified.
   217  // The element and mark must not be nil.
   218  func (l *_List[T]) MoveAfter(e, mark *_Element[T]) {
   219  	if e.list != l || e == mark || mark.list != l {
   220  		return
   221  	}
   222  	l.move(e, mark)
   223  }
   224  
   225  // PushBackList inserts a copy of an other list at the back of list l.
   226  // The lists l and other may be the same. They must not be nil.
   227  func (l *_List[T]) PushBackList(other *_List[T]) {
   228  	l.lazyInit()
   229  	for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
   230  		l.insertValue(e.Value, l.root.prev)
   231  	}
   232  }
   233  
   234  // PushFrontList inserts a copy of an other list at the front of list l.
   235  // The lists l and other may be the same. They must not be nil.
   236  func (l *_List[T]) PushFrontList(other *_List[T]) {
   237  	l.lazyInit()
   238  	for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
   239  		l.insertValue(e.Value, &l.root)
   240  	}
   241  }
   242  
   243  // Transform runs a transform function on a list returning a new list.
   244  func _Transform[TElem1, TElem2 any](lst *_List[TElem1], f func(TElem1) TElem2) *_List[TElem2] {
   245  	ret := _New[TElem2]()
   246  	for p := lst.Front(); p != nil; p = p.Next() {
   247  		ret.PushBack(f(p.Value))
   248  	}
   249  	return ret
   250  }
   251  
   252  func checkListLen[T any](l *_List[T], len int) bool {
   253  	if n := l.Len(); n != len {
   254  		panic(fmt.Sprintf("l.Len() = %d, want %d", n, len))
   255  		return false
   256  	}
   257  	return true
   258  }
   259  
   260  func checkListPointers[T any](l *_List[T], es []*_Element[T]) {
   261  	root := &l.root
   262  
   263  	if !checkListLen(l, len(es)) {
   264  		return
   265  	}
   266  
   267  	// zero length lists must be the zero value or properly initialized (sentinel circle)
   268  	if len(es) == 0 {
   269  		if l.root.next != nil && l.root.next != root || l.root.prev != nil && l.root.prev != root {
   270  			panic(fmt.Sprintf("l.root.next = %p, l.root.prev = %p; both should both be nil or %p", l.root.next, l.root.prev, root))
   271  		}
   272  		return
   273  	}
   274  	// len(es) > 0
   275  
   276  	// check internal and external prev/next connections
   277  	for i, e := range es {
   278  		prev := root
   279  		Prev := (*_Element[T])(nil)
   280  		if i > 0 {
   281  			prev = es[i-1]
   282  			Prev = prev
   283  		}
   284  		if p := e.prev; p != prev {
   285  			panic(fmt.Sprintf("elt[%d](%p).prev = %p, want %p", i, e, p, prev))
   286  		}
   287  		if p := e.Prev(); p != Prev {
   288  			panic(fmt.Sprintf("elt[%d](%p).Prev() = %p, want %p", i, e, p, Prev))
   289  		}
   290  
   291  		next := root
   292  		Next := (*_Element[T])(nil)
   293  		if i < len(es)-1 {
   294  			next = es[i+1]
   295  			Next = next
   296  		}
   297  		if n := e.next; n != next {
   298  			panic(fmt.Sprintf("elt[%d](%p).next = %p, want %p", i, e, n, next))
   299  		}
   300  		if n := e.Next(); n != Next {
   301  			panic(fmt.Sprintf("elt[%d](%p).Next() = %p, want %p", i, e, n, Next))
   302  		}
   303  	}
   304  }
   305  
   306  func TestList() {
   307  	l := _New[string]()
   308  	checkListPointers(l, []*(_Element[string]){})
   309  
   310  	// Single element list
   311  	e := l.PushFront("a")
   312  	checkListPointers(l, []*(_Element[string]){e})
   313  	l.MoveToFront(e)
   314  	checkListPointers(l, []*(_Element[string]){e})
   315  	l.MoveToBack(e)
   316  	checkListPointers(l, []*(_Element[string]){e})
   317  	l.Remove(e)
   318  	checkListPointers(l, []*(_Element[string]){})
   319  
   320  	// Bigger list
   321  	l2 := _New[int]()
   322  	e2 := l2.PushFront(2)
   323  	e1 := l2.PushFront(1)
   324  	e3 := l2.PushBack(3)
   325  	e4 := l2.PushBack(600)
   326  	checkListPointers(l2, []*(_Element[int]){e1, e2, e3, e4})
   327  
   328  	l2.Remove(e2)
   329  	checkListPointers(l2, []*(_Element[int]){e1, e3, e4})
   330  
   331  	l2.MoveToFront(e3) // move from middle
   332  	checkListPointers(l2, []*(_Element[int]){e3, e1, e4})
   333  
   334  	l2.MoveToFront(e1)
   335  	l2.MoveToBack(e3) // move from middle
   336  	checkListPointers(l2, []*(_Element[int]){e1, e4, e3})
   337  
   338  	l2.MoveToFront(e3) // move from back
   339  	checkListPointers(l2, []*(_Element[int]){e3, e1, e4})
   340  	l2.MoveToFront(e3) // should be no-op
   341  	checkListPointers(l2, []*(_Element[int]){e3, e1, e4})
   342  
   343  	l2.MoveToBack(e3) // move from front
   344  	checkListPointers(l2, []*(_Element[int]){e1, e4, e3})
   345  	l2.MoveToBack(e3) // should be no-op
   346  	checkListPointers(l2, []*(_Element[int]){e1, e4, e3})
   347  
   348  	e2 = l2.InsertBefore(2, e1) // insert before front
   349  	checkListPointers(l2, []*(_Element[int]){e2, e1, e4, e3})
   350  	l2.Remove(e2)
   351  	e2 = l2.InsertBefore(2, e4) // insert before middle
   352  	checkListPointers(l2, []*(_Element[int]){e1, e2, e4, e3})
   353  	l2.Remove(e2)
   354  	e2 = l2.InsertBefore(2, e3) // insert before back
   355  	checkListPointers(l2, []*(_Element[int]){e1, e4, e2, e3})
   356  	l2.Remove(e2)
   357  
   358  	e2 = l2.InsertAfter(2, e1) // insert after front
   359  	checkListPointers(l2, []*(_Element[int]){e1, e2, e4, e3})
   360  	l2.Remove(e2)
   361  	e2 = l2.InsertAfter(2, e4) // insert after middle
   362  	checkListPointers(l2, []*(_Element[int]){e1, e4, e2, e3})
   363  	l2.Remove(e2)
   364  	e2 = l2.InsertAfter(2, e3) // insert after back
   365  	checkListPointers(l2, []*(_Element[int]){e1, e4, e3, e2})
   366  	l2.Remove(e2)
   367  
   368  	// Check standard iteration.
   369  	sum := 0
   370  	for e := l2.Front(); e != nil; e = e.Next() {
   371  		sum += e.Value
   372  	}
   373  	if sum != 604 {
   374  		panic(fmt.Sprintf("sum over l = %d, want 604", sum))
   375  	}
   376  
   377  	// Clear all elements by iterating
   378  	var next *_Element[int]
   379  	for e := l2.Front(); e != nil; e = next {
   380  		next = e.Next()
   381  		l2.Remove(e)
   382  	}
   383  	checkListPointers(l2, []*(_Element[int]){})
   384  }
   385  
   386  func checkList[T comparable](l *_List[T], es []interface{}) {
   387  	if !checkListLen(l, len(es)) {
   388  		return
   389  	}
   390  
   391  	i := 0
   392  	for e := l.Front(); e != nil; e = e.Next() {
   393  		le := e.Value
   394  		// Comparison between a generically-typed variable le and an interface.
   395  		if le != es[i] {
   396  			panic(fmt.Sprintf("elt[%d].Value = %v, want %v", i, le, es[i]))
   397  		}
   398  		i++
   399  	}
   400  }
   401  
   402  func TestExtending() {
   403  	l1 := _New[int]()
   404  	l2 := _New[int]()
   405  
   406  	l1.PushBack(1)
   407  	l1.PushBack(2)
   408  	l1.PushBack(3)
   409  
   410  	l2.PushBack(4)
   411  	l2.PushBack(5)
   412  
   413  	l3 := _New[int]()
   414  	l3.PushBackList(l1)
   415  	checkList(l3, []interface{}{1, 2, 3})
   416  	l3.PushBackList(l2)
   417  	checkList(l3, []interface{}{1, 2, 3, 4, 5})
   418  
   419  	l3 = _New[int]()
   420  	l3.PushFrontList(l2)
   421  	checkList(l3, []interface{}{4, 5})
   422  	l3.PushFrontList(l1)
   423  	checkList(l3, []interface{}{1, 2, 3, 4, 5})
   424  
   425  	checkList(l1, []interface{}{1, 2, 3})
   426  	checkList(l2, []interface{}{4, 5})
   427  
   428  	l3 = _New[int]()
   429  	l3.PushBackList(l1)
   430  	checkList(l3, []interface{}{1, 2, 3})
   431  	l3.PushBackList(l3)
   432  	checkList(l3, []interface{}{1, 2, 3, 1, 2, 3})
   433  
   434  	l3 = _New[int]()
   435  	l3.PushFrontList(l1)
   436  	checkList(l3, []interface{}{1, 2, 3})
   437  	l3.PushFrontList(l3)
   438  	checkList(l3, []interface{}{1, 2, 3, 1, 2, 3})
   439  
   440  	l3 = _New[int]()
   441  	l1.PushBackList(l3)
   442  	checkList(l1, []interface{}{1, 2, 3})
   443  	l1.PushFrontList(l3)
   444  	checkList(l1, []interface{}{1, 2, 3})
   445  }
   446  
   447  func TestRemove() {
   448  	l := _New[int]()
   449  	e1 := l.PushBack(1)
   450  	e2 := l.PushBack(2)
   451  	checkListPointers(l, []*(_Element[int]){e1, e2})
   452  	e := l.Front()
   453  	l.Remove(e)
   454  	checkListPointers(l, []*(_Element[int]){e2})
   455  	l.Remove(e)
   456  	checkListPointers(l, []*(_Element[int]){e2})
   457  }
   458  
   459  func TestIssue4103() {
   460  	l1 := _New[int]()
   461  	l1.PushBack(1)
   462  	l1.PushBack(2)
   463  
   464  	l2 := _New[int]()
   465  	l2.PushBack(3)
   466  	l2.PushBack(4)
   467  
   468  	e := l1.Front()
   469  	l2.Remove(e) // l2 should not change because e is not an element of l2
   470  	if n := l2.Len(); n != 2 {
   471  		panic(fmt.Sprintf("l2.Len() = %d, want 2", n))
   472  	}
   473  
   474  	l1.InsertBefore(8, e)
   475  	if n := l1.Len(); n != 3 {
   476  		panic(fmt.Sprintf("l1.Len() = %d, want 3", n))
   477  	}
   478  }
   479  
   480  func TestIssue6349() {
   481  	l := _New[int]()
   482  	l.PushBack(1)
   483  	l.PushBack(2)
   484  
   485  	e := l.Front()
   486  	l.Remove(e)
   487  	if e.Value != 1 {
   488  		panic(fmt.Sprintf("e.value = %d, want 1", e.Value))
   489  	}
   490  	if e.Next() != nil {
   491  		panic(fmt.Sprintf("e.Next() != nil"))
   492  	}
   493  	if e.Prev() != nil {
   494  		panic(fmt.Sprintf("e.Prev() != nil"))
   495  	}
   496  }
   497  
   498  func TestMove() {
   499  	l := _New[int]()
   500  	e1 := l.PushBack(1)
   501  	e2 := l.PushBack(2)
   502  	e3 := l.PushBack(3)
   503  	e4 := l.PushBack(4)
   504  
   505  	l.MoveAfter(e3, e3)
   506  	checkListPointers(l, []*(_Element[int]){e1, e2, e3, e4})
   507  	l.MoveBefore(e2, e2)
   508  	checkListPointers(l, []*(_Element[int]){e1, e2, e3, e4})
   509  
   510  	l.MoveAfter(e3, e2)
   511  	checkListPointers(l, []*(_Element[int]){e1, e2, e3, e4})
   512  	l.MoveBefore(e2, e3)
   513  	checkListPointers(l, []*(_Element[int]){e1, e2, e3, e4})
   514  
   515  	l.MoveBefore(e2, e4)
   516  	checkListPointers(l, []*(_Element[int]){e1, e3, e2, e4})
   517  	e2, e3 = e3, e2
   518  
   519  	l.MoveBefore(e4, e1)
   520  	checkListPointers(l, []*(_Element[int]){e4, e1, e2, e3})
   521  	e1, e2, e3, e4 = e4, e1, e2, e3
   522  
   523  	l.MoveAfter(e4, e1)
   524  	checkListPointers(l, []*(_Element[int]){e1, e4, e2, e3})
   525  	e2, e3, e4 = e4, e2, e3
   526  
   527  	l.MoveAfter(e2, e3)
   528  	checkListPointers(l, []*(_Element[int]){e1, e3, e2, e4})
   529  	e2, e3 = e3, e2
   530  }
   531  
   532  // Test PushFront, PushBack, PushFrontList, PushBackList with uninitialized _List
   533  func TestZeroList() {
   534  	var l1 = new(_List[int])
   535  	l1.PushFront(1)
   536  	checkList(l1, []interface{}{1})
   537  
   538  	var l2 = new(_List[int])
   539  	l2.PushBack(1)
   540  	checkList(l2, []interface{}{1})
   541  
   542  	var l3 = new(_List[int])
   543  	l3.PushFrontList(l1)
   544  	checkList(l3, []interface{}{1})
   545  
   546  	var l4 = new(_List[int])
   547  	l4.PushBackList(l2)
   548  	checkList(l4, []interface{}{1})
   549  }
   550  
   551  // Test that a list l is not modified when calling InsertBefore with a mark that is not an element of l.
   552  func TestInsertBeforeUnknownMark() {
   553  	var l _List[int]
   554  	l.PushBack(1)
   555  	l.PushBack(2)
   556  	l.PushBack(3)
   557  	l.InsertBefore(1, new(_Element[int]))
   558  	checkList(&l, []interface{}{1, 2, 3})
   559  }
   560  
   561  // Test that a list l is not modified when calling InsertAfter with a mark that is not an element of l.
   562  func TestInsertAfterUnknownMark() {
   563  	var l _List[int]
   564  	l.PushBack(1)
   565  	l.PushBack(2)
   566  	l.PushBack(3)
   567  	l.InsertAfter(1, new(_Element[int]))
   568  	checkList(&l, []interface{}{1, 2, 3})
   569  }
   570  
   571  // Test that a list l is not modified when calling MoveAfter or MoveBefore with a mark that is not an element of l.
   572  func TestMoveUnknownMark() {
   573  	var l1 _List[int]
   574  	e1 := l1.PushBack(1)
   575  
   576  	var l2 _List[int]
   577  	e2 := l2.PushBack(2)
   578  
   579  	l1.MoveAfter(e1, e2)
   580  	checkList(&l1, []interface{}{1})
   581  	checkList(&l2, []interface{}{2})
   582  
   583  	l1.MoveBefore(e1, e2)
   584  	checkList(&l1, []interface{}{1})
   585  	checkList(&l2, []interface{}{2})
   586  }
   587  
   588  // Test the Transform function.
   589  func TestTransform() {
   590  	l1 := _New[int]()
   591  	l1.PushBack(1)
   592  	l1.PushBack(2)
   593  	l2 := _Transform(l1, strconv.Itoa)
   594  	checkList(l2, []interface{}{"1", "2"})
   595  }
   596  
   597  func main() {
   598  	TestList()
   599  	TestExtending()
   600  	TestRemove()
   601  	TestIssue4103()
   602  	TestIssue6349()
   603  	TestMove()
   604  	TestZeroList()
   605  	TestInsertBeforeUnknownMark()
   606  	TestInsertAfterUnknownMark()
   607  	TestTransform()
   608  }
   609
View as plain text