main.go

     1  // Copyright 2021 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 main
     6  
     7  import (
     8  	"./a"
     9  	"fmt"
    10  	"strconv"
    11  )
    12  
    13  func TestList() {
    14  	l := a.New[string]()
    15  	a.CheckListPointers(l, []*(a.Element[string]){})
    16  
    17  	// Single element list
    18  	e := l.PushFront("a")
    19  	a.CheckListPointers(l, []*(a.Element[string]){e})
    20  	l.MoveToFront(e)
    21  	a.CheckListPointers(l, []*(a.Element[string]){e})
    22  	l.MoveToBack(e)
    23  	a.CheckListPointers(l, []*(a.Element[string]){e})
    24  	l.Remove(e)
    25  	a.CheckListPointers(l, []*(a.Element[string]){})
    26  
    27  	// Bigger list
    28  	l2 := a.New[int]()
    29  	e2 := l2.PushFront(2)
    30  	e1 := l2.PushFront(1)
    31  	e3 := l2.PushBack(3)
    32  	e4 := l2.PushBack(600)
    33  	a.CheckListPointers(l2, []*(a.Element[int]){e1, e2, e3, e4})
    34  
    35  	l2.Remove(e2)
    36  	a.CheckListPointers(l2, []*(a.Element[int]){e1, e3, e4})
    37  
    38  	l2.MoveToFront(e3) // move from middle
    39  	a.CheckListPointers(l2, []*(a.Element[int]){e3, e1, e4})
    40  
    41  	l2.MoveToFront(e1)
    42  	l2.MoveToBack(e3) // move from middle
    43  	a.CheckListPointers(l2, []*(a.Element[int]){e1, e4, e3})
    44  
    45  	l2.MoveToFront(e3) // move from back
    46  	a.CheckListPointers(l2, []*(a.Element[int]){e3, e1, e4})
    47  	l2.MoveToFront(e3) // should be no-op
    48  	a.CheckListPointers(l2, []*(a.Element[int]){e3, e1, e4})
    49  
    50  	l2.MoveToBack(e3) // move from front
    51  	a.CheckListPointers(l2, []*(a.Element[int]){e1, e4, e3})
    52  	l2.MoveToBack(e3) // should be no-op
    53  	a.CheckListPointers(l2, []*(a.Element[int]){e1, e4, e3})
    54  
    55  	e2 = l2.InsertBefore(2, e1) // insert before front
    56  	a.CheckListPointers(l2, []*(a.Element[int]){e2, e1, e4, e3})
    57  	l2.Remove(e2)
    58  	e2 = l2.InsertBefore(2, e4) // insert before middle
    59  	a.CheckListPointers(l2, []*(a.Element[int]){e1, e2, e4, e3})
    60  	l2.Remove(e2)
    61  	e2 = l2.InsertBefore(2, e3) // insert before back
    62  	a.CheckListPointers(l2, []*(a.Element[int]){e1, e4, e2, e3})
    63  	l2.Remove(e2)
    64  
    65  	e2 = l2.InsertAfter(2, e1) // insert after front
    66  	a.CheckListPointers(l2, []*(a.Element[int]){e1, e2, e4, e3})
    67  	l2.Remove(e2)
    68  	e2 = l2.InsertAfter(2, e4) // insert after middle
    69  	a.CheckListPointers(l2, []*(a.Element[int]){e1, e4, e2, e3})
    70  	l2.Remove(e2)
    71  	e2 = l2.InsertAfter(2, e3) // insert after back
    72  	a.CheckListPointers(l2, []*(a.Element[int]){e1, e4, e3, e2})
    73  	l2.Remove(e2)
    74  
    75  	// Check standard iteration.
    76  	sum := 0
    77  	for e := l2.Front(); e != nil; e = e.Next() {
    78  		sum += e.Value
    79  	}
    80  	if sum != 604 {
    81  		panic(fmt.Sprintf("sum over l = %d, want 604", sum))
    82  	}
    83  
    84  	// Clear all elements by iterating
    85  	var next *a.Element[int]
    86  	for e := l2.Front(); e != nil; e = next {
    87  		next = e.Next()
    88  		l2.Remove(e)
    89  	}
    90  	a.CheckListPointers(l2, []*(a.Element[int]){})
    91  }
    92  
    93  func checkList[T comparable](l *a.List[T], es []interface{}) {
    94  	if !a.CheckListLen(l, len(es)) {
    95  		return
    96  	}
    97  
    98  	i := 0
    99  	for e := l.Front(); e != nil; e = e.Next() {
   100  		le := e.Value
   101  		// Comparison between a generically-typed variable le and an interface.
   102  		if le != es[i] {
   103  			panic(fmt.Sprintf("elt[%d].Value = %v, want %v", i, le, es[i]))
   104  		}
   105  		i++
   106  	}
   107  }
   108  
   109  func TestExtending() {
   110  	l1 := a.New[int]()
   111  	l2 := a.New[int]()
   112  
   113  	l1.PushBack(1)
   114  	l1.PushBack(2)
   115  	l1.PushBack(3)
   116  
   117  	l2.PushBack(4)
   118  	l2.PushBack(5)
   119  
   120  	l3 := a.New[int]()
   121  	l3.PushBackList(l1)
   122  	checkList(l3, []interface{}{1, 2, 3})
   123  	l3.PushBackList(l2)
   124  	checkList(l3, []interface{}{1, 2, 3, 4, 5})
   125  
   126  	l3 = a.New[int]()
   127  	l3.PushFrontList(l2)
   128  	checkList(l3, []interface{}{4, 5})
   129  	l3.PushFrontList(l1)
   130  	checkList(l3, []interface{}{1, 2, 3, 4, 5})
   131  
   132  	checkList(l1, []interface{}{1, 2, 3})
   133  	checkList(l2, []interface{}{4, 5})
   134  
   135  	l3 = a.New[int]()
   136  	l3.PushBackList(l1)
   137  	checkList(l3, []interface{}{1, 2, 3})
   138  	l3.PushBackList(l3)
   139  	checkList(l3, []interface{}{1, 2, 3, 1, 2, 3})
   140  
   141  	l3 = a.New[int]()
   142  	l3.PushFrontList(l1)
   143  	checkList(l3, []interface{}{1, 2, 3})
   144  	l3.PushFrontList(l3)
   145  	checkList(l3, []interface{}{1, 2, 3, 1, 2, 3})
   146  
   147  	l3 = a.New[int]()
   148  	l1.PushBackList(l3)
   149  	checkList(l1, []interface{}{1, 2, 3})
   150  	l1.PushFrontList(l3)
   151  	checkList(l1, []interface{}{1, 2, 3})
   152  }
   153  
   154  func TestRemove() {
   155  	l := a.New[int]()
   156  	e1 := l.PushBack(1)
   157  	e2 := l.PushBack(2)
   158  	a.CheckListPointers(l, []*(a.Element[int]){e1, e2})
   159  	e := l.Front()
   160  	l.Remove(e)
   161  	a.CheckListPointers(l, []*(a.Element[int]){e2})
   162  	l.Remove(e)
   163  	a.CheckListPointers(l, []*(a.Element[int]){e2})
   164  }
   165  
   166  func TestIssue4103() {
   167  	l1 := a.New[int]()
   168  	l1.PushBack(1)
   169  	l1.PushBack(2)
   170  
   171  	l2 := a.New[int]()
   172  	l2.PushBack(3)
   173  	l2.PushBack(4)
   174  
   175  	e := l1.Front()
   176  	l2.Remove(e) // l2 should not change because e is not an element of l2
   177  	if n := l2.Len(); n != 2 {
   178  		panic(fmt.Sprintf("l2.Len() = %d, want 2", n))
   179  	}
   180  
   181  	l1.InsertBefore(8, e)
   182  	if n := l1.Len(); n != 3 {
   183  		panic(fmt.Sprintf("l1.Len() = %d, want 3", n))
   184  	}
   185  }
   186  
   187  func TestIssue6349() {
   188  	l := a.New[int]()
   189  	l.PushBack(1)
   190  	l.PushBack(2)
   191  
   192  	e := l.Front()
   193  	l.Remove(e)
   194  	if e.Value != 1 {
   195  		panic(fmt.Sprintf("e.value = %d, want 1", e.Value))
   196  	}
   197  	if e.Next() != nil {
   198  		panic(fmt.Sprintf("e.Next() != nil"))
   199  	}
   200  	if e.Prev() != nil {
   201  		panic(fmt.Sprintf("e.Prev() != nil"))
   202  	}
   203  }
   204  
   205  func TestMove() {
   206  	l := a.New[int]()
   207  	e1 := l.PushBack(1)
   208  	e2 := l.PushBack(2)
   209  	e3 := l.PushBack(3)
   210  	e4 := l.PushBack(4)
   211  
   212  	l.MoveAfter(e3, e3)
   213  	a.CheckListPointers(l, []*(a.Element[int]){e1, e2, e3, e4})
   214  	l.MoveBefore(e2, e2)
   215  	a.CheckListPointers(l, []*(a.Element[int]){e1, e2, e3, e4})
   216  
   217  	l.MoveAfter(e3, e2)
   218  	a.CheckListPointers(l, []*(a.Element[int]){e1, e2, e3, e4})
   219  	l.MoveBefore(e2, e3)
   220  	a.CheckListPointers(l, []*(a.Element[int]){e1, e2, e3, e4})
   221  
   222  	l.MoveBefore(e2, e4)
   223  	a.CheckListPointers(l, []*(a.Element[int]){e1, e3, e2, e4})
   224  	e2, e3 = e3, e2
   225  
   226  	l.MoveBefore(e4, e1)
   227  	a.CheckListPointers(l, []*(a.Element[int]){e4, e1, e2, e3})
   228  	e1, e2, e3, e4 = e4, e1, e2, e3
   229  
   230  	l.MoveAfter(e4, e1)
   231  	a.CheckListPointers(l, []*(a.Element[int]){e1, e4, e2, e3})
   232  	e2, e3, e4 = e4, e2, e3
   233  
   234  	l.MoveAfter(e2, e3)
   235  	a.CheckListPointers(l, []*(a.Element[int]){e1, e3, e2, e4})
   236  	e2, e3 = e3, e2
   237  }
   238  
   239  // Test PushFront, PushBack, PushFrontList, PushBackList with uninitialized a.List
   240  func TestZeroList() {
   241  	var l1 = new(a.List[int])
   242  	l1.PushFront(1)
   243  	checkList(l1, []interface{}{1})
   244  
   245  	var l2 = new(a.List[int])
   246  	l2.PushBack(1)
   247  	checkList(l2, []interface{}{1})
   248  
   249  	var l3 = new(a.List[int])
   250  	l3.PushFrontList(l1)
   251  	checkList(l3, []interface{}{1})
   252  
   253  	var l4 = new(a.List[int])
   254  	l4.PushBackList(l2)
   255  	checkList(l4, []interface{}{1})
   256  }
   257  
   258  // Test that a list l is not modified when calling InsertBefore with a mark that is not an element of l.
   259  func TestInsertBeforeUnknownMark() {
   260  	var l a.List[int]
   261  	l.PushBack(1)
   262  	l.PushBack(2)
   263  	l.PushBack(3)
   264  	l.InsertBefore(1, new(a.Element[int]))
   265  	checkList(&l, []interface{}{1, 2, 3})
   266  }
   267  
   268  // Test that a list l is not modified when calling InsertAfter with a mark that is not an element of l.
   269  func TestInsertAfterUnknownMark() {
   270  	var l a.List[int]
   271  	l.PushBack(1)
   272  	l.PushBack(2)
   273  	l.PushBack(3)
   274  	l.InsertAfter(1, new(a.Element[int]))
   275  	checkList(&l, []interface{}{1, 2, 3})
   276  }
   277  
   278  // Test that a list l is not modified when calling MoveAfter or MoveBefore with a mark that is not an element of l.
   279  func TestMoveUnknownMark() {
   280  	var l1 a.List[int]
   281  	e1 := l1.PushBack(1)
   282  
   283  	var l2 a.List[int]
   284  	e2 := l2.PushBack(2)
   285  
   286  	l1.MoveAfter(e1, e2)
   287  	checkList(&l1, []interface{}{1})
   288  	checkList(&l2, []interface{}{2})
   289  
   290  	l1.MoveBefore(e1, e2)
   291  	checkList(&l1, []interface{}{1})
   292  	checkList(&l2, []interface{}{2})
   293  }
   294  
   295  // Test the Transform function.
   296  func TestTransform() {
   297  	l1 := a.New[int]()
   298  	l1.PushBack(1)
   299  	l1.PushBack(2)
   300  	l2 := a.Transform(l1, strconv.Itoa)
   301  	checkList(l2, []interface{}{"1", "2"})
   302  }
   303  
   304  func main() {
   305  	TestList()
   306  	TestExtending()
   307  	TestRemove()
   308  	TestIssue4103()
   309  	TestIssue6349()
   310  	TestMove()
   311  	TestZeroList()
   312  	TestInsertBeforeUnknownMark()
   313  	TestInsertAfterUnknownMark()
   314  	TestTransform()
   315  }
   316
View as plain text