test/typeparam/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 }