Subversion Repositories openrisc

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package list

import (
        "testing"
)

func checkListPointers(t *testing.T, l *List, es []*Element) {
        if len(es) == 0 {
                if l.front != nil || l.back != nil {
                        t.Errorf("l.front/l.back = %v/%v should be nil/nil", l.front, l.back)
                }
                return
        }

        if l.front != es[0] {
                t.Errorf("l.front = %v, want %v", l.front, es[0])
        }
        if last := es[len(es)-1]; l.back != last {
                t.Errorf("l.back = %v, want %v", l.back, last)
        }

        for i, e := range es {
                var e_prev, e_next *Element = nil, nil
                if i > 0 {
                        e_prev = es[i-1]
                }
                if i < len(es)-1 {
                        e_next = es[i+1]
                }
                if e.prev != e_prev {
                        t.Errorf("elt #%d (%v) has prev=%v, want %v", i, e, e.prev, e_prev)
                }
                if e.next != e_next {
                        t.Errorf("elt #%d (%v) has next=%v, want %v", i, e, e.next, e_next)
                }
        }
}

func checkListLen(t *testing.T, l *List, n int) {
        if an := l.Len(); an != n {
                t.Errorf("l.Len() = %d, want %d", an, n)
        }
}

func TestList(t *testing.T) {
        l := New()
        checkListPointers(t, l, []*Element{})
        checkListLen(t, l, 0)

        // Single element list
        e := l.PushFront("a")
        checkListLen(t, l, 1)
        checkListPointers(t, l, []*Element{e})
        l.MoveToFront(e)
        checkListPointers(t, l, []*Element{e})
        l.MoveToBack(e)
        checkListPointers(t, l, []*Element{e})
        checkListLen(t, l, 1)
        l.Remove(e)
        checkListPointers(t, l, []*Element{})
        checkListLen(t, l, 0)

        // Bigger list
        e2 := l.PushFront(2)
        e1 := l.PushFront(1)
        e3 := l.PushBack(3)
        e4 := l.PushBack("banana")
        checkListPointers(t, l, []*Element{e1, e2, e3, e4})
        checkListLen(t, l, 4)

        l.Remove(e2)
        checkListPointers(t, l, []*Element{e1, e3, e4})
        checkListLen(t, l, 3)

        l.MoveToFront(e3) // move from middle
        checkListPointers(t, l, []*Element{e3, e1, e4})

        l.MoveToFront(e1)
        l.MoveToBack(e3) // move from middle
        checkListPointers(t, l, []*Element{e1, e4, e3})

        l.MoveToFront(e3) // move from back
        checkListPointers(t, l, []*Element{e3, e1, e4})
        l.MoveToFront(e3) // should be no-op
        checkListPointers(t, l, []*Element{e3, e1, e4})

        l.MoveToBack(e3) // move from front
        checkListPointers(t, l, []*Element{e1, e4, e3})
        l.MoveToBack(e3) // should be no-op
        checkListPointers(t, l, []*Element{e1, e4, e3})

        e2 = l.InsertBefore(2, e1) // insert before front
        checkListPointers(t, l, []*Element{e2, e1, e4, e3})
        l.Remove(e2)
        e2 = l.InsertBefore(2, e4) // insert before middle
        checkListPointers(t, l, []*Element{e1, e2, e4, e3})
        l.Remove(e2)
        e2 = l.InsertBefore(2, e3) // insert before back
        checkListPointers(t, l, []*Element{e1, e4, e2, e3})
        l.Remove(e2)

        e2 = l.InsertAfter(2, e1) // insert after front
        checkListPointers(t, l, []*Element{e1, e2, e4, e3})
        l.Remove(e2)
        e2 = l.InsertAfter(2, e4) // insert after middle
        checkListPointers(t, l, []*Element{e1, e4, e2, e3})
        l.Remove(e2)
        e2 = l.InsertAfter(2, e3) // insert after back
        checkListPointers(t, l, []*Element{e1, e4, e3, e2})
        l.Remove(e2)

        // Check standard iteration.
        sum := 0
        for e := l.Front(); e != nil; e = e.Next() {
                if i, ok := e.Value.(int); ok {
                        sum += i
                }
        }
        if sum != 4 {
                t.Errorf("sum over l.Iter() = %d, want 4", sum)
        }

        // Clear all elements by iterating
        var next *Element
        for e := l.Front(); e != nil; e = next {
                next = e.Next()
                l.Remove(e)
        }
        checkListPointers(t, l, []*Element{})
        checkListLen(t, l, 0)
}

func checkList(t *testing.T, l *List, es []interface{}) {
        if l.Len() != len(es) {
                t.Errorf("list has len=%v, want %v", l.Len(), len(es))
                return
        }
        i := 0
        for e := l.Front(); e != nil; e = e.Next() {
                le := e.Value.(int)
                if le != es[i] {
                        t.Errorf("elt #%d has value=%v, want %v", i, le, es[i])
                }
                i++
        }
}

func TestExtending(t *testing.T) {
        l1 := New()
        l2 := New()

        l1.PushBack(1)
        l1.PushBack(2)
        l1.PushBack(3)

        l2.PushBack(4)
        l2.PushBack(5)

        l3 := New()
        l3.PushBackList(l1)
        checkList(t, l3, []interface{}{1, 2, 3})
        l3.PushBackList(l2)
        checkList(t, l3, []interface{}{1, 2, 3, 4, 5})

        l3 = New()
        l3.PushFrontList(l2)
        checkList(t, l3, []interface{}{4, 5})
        l3.PushFrontList(l1)
        checkList(t, l3, []interface{}{1, 2, 3, 4, 5})

        checkList(t, l1, []interface{}{1, 2, 3})
        checkList(t, l2, []interface{}{4, 5})

        l3 = New()
        l3.PushBackList(l1)
        checkList(t, l3, []interface{}{1, 2, 3})
        l3.PushBackList(l3)
        checkList(t, l3, []interface{}{1, 2, 3, 1, 2, 3})

        l3 = New()
        l3.PushFrontList(l1)
        checkList(t, l3, []interface{}{1, 2, 3})
        l3.PushFrontList(l3)
        checkList(t, l3, []interface{}{1, 2, 3, 1, 2, 3})

        l3 = New()
        l1.PushBackList(l3)
        checkList(t, l1, []interface{}{1, 2, 3})
        l1.PushFrontList(l3)
        checkList(t, l1, []interface{}{1, 2, 3})
}

func TestRemove(t *testing.T) {
        l := New()
        e1 := l.PushBack(1)
        e2 := l.PushBack(2)
        checkListPointers(t, l, []*Element{e1, e2})
        e := l.Front()
        l.Remove(e)
        checkListPointers(t, l, []*Element{e2})
        checkListLen(t, l, 1)
        l.Remove(e)
        checkListPointers(t, l, []*Element{e2})
        checkListLen(t, l, 1)
}