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 ring

import (
        "fmt"
        "testing"
)

// For debugging - keep around.
func dump(r *Ring) {
        if r == nil {
                fmt.Println("empty")
                return
        }
        i, n := 0, r.Len()
        for p := r; i < n; p = p.next {
                fmt.Printf("%4d: %p = {<- %p | %p ->}\n", i, p, p.prev, p.next)
                i++
        }
        fmt.Println()
}

func verify(t *testing.T, r *Ring, N int, sum int) {
        // Len
        n := r.Len()
        if n != N {
                t.Errorf("r.Len() == %d; expected %d", n, N)
        }

        // iteration
        n = 0
        s := 0
        r.Do(func(p interface{}) {
                n++
                if p != nil {
                        s += p.(int)
                }
        })
        if n != N {
                t.Errorf("number of forward iterations == %d; expected %d", n, N)
        }
        if sum >= 0 && s != sum {
                t.Errorf("forward ring sum = %d; expected %d", s, sum)
        }

        if r == nil {
                return
        }

        // connections
        if r.next != nil {
                var p *Ring // previous element
                for q := r; p == nil || q != r; q = q.next {
                        if p != nil && p != q.prev {
                                t.Errorf("prev = %p, expected q.prev = %p\n", p, q.prev)
                        }
                        p = q
                }
                if p != r.prev {
                        t.Errorf("prev = %p, expected r.prev = %p\n", p, r.prev)
                }
        }

        // Next, Prev
        if r.Next() != r.next {
                t.Errorf("r.Next() != r.next")
        }
        if r.Prev() != r.prev {
                t.Errorf("r.Prev() != r.prev")
        }

        // Move
        if r.Move(0) != r {
                t.Errorf("r.Move(0) != r")
        }
        if r.Move(N) != r {
                t.Errorf("r.Move(%d) != r", N)
        }
        if r.Move(-N) != r {
                t.Errorf("r.Move(%d) != r", -N)
        }
        for i := 0; i < 10; i++ {
                ni := N + i
                mi := ni % N
                if r.Move(ni) != r.Move(mi) {
                        t.Errorf("r.Move(%d) != r.Move(%d)", ni, mi)
                }
                if r.Move(-ni) != r.Move(-mi) {
                        t.Errorf("r.Move(%d) != r.Move(%d)", -ni, -mi)
                }
        }
}

func TestCornerCases(t *testing.T) {
        var (
                r0 *Ring
                r1 Ring
        )
        // Basics
        verify(t, r0, 0, 0)
        verify(t, &r1, 1, 0)
        // Insert
        r1.Link(r0)
        verify(t, r0, 0, 0)
        verify(t, &r1, 1, 0)
        // Insert
        r1.Link(r0)
        verify(t, r0, 0, 0)
        verify(t, &r1, 1, 0)
        // Unlink
        r1.Unlink(0)
        verify(t, &r1, 1, 0)
}

func makeN(n int) *Ring {
        r := New(n)
        for i := 1; i <= n; i++ {
                r.Value = i
                r = r.Next()
        }
        return r
}

func sumN(n int) int { return (n*n + n) / 2 }

func TestNew(t *testing.T) {
        for i := 0; i < 10; i++ {
                r := New(i)
                verify(t, r, i, -1)
        }
        for i := 0; i < 10; i++ {
                r := makeN(i)
                verify(t, r, i, sumN(i))
        }
}

func TestLink1(t *testing.T) {
        r1a := makeN(1)
        var r1b Ring
        r2a := r1a.Link(&r1b)
        verify(t, r2a, 2, 1)
        if r2a != r1a {
                t.Errorf("a) 2-element link failed")
        }

        r2b := r2a.Link(r2a.Next())
        verify(t, r2b, 2, 1)
        if r2b != r2a.Next() {
                t.Errorf("b) 2-element link failed")
        }

        r1c := r2b.Link(r2b)
        verify(t, r1c, 1, 1)
        verify(t, r2b, 1, 0)
}

func TestLink2(t *testing.T) {
        var r0 *Ring
        r1a := &Ring{Value: 42}
        r1b := &Ring{Value: 77}
        r10 := makeN(10)

        r1a.Link(r0)
        verify(t, r1a, 1, 42)

        r1a.Link(r1b)
        verify(t, r1a, 2, 42+77)

        r10.Link(r0)
        verify(t, r10, 10, sumN(10))

        r10.Link(r1a)
        verify(t, r10, 12, sumN(10)+42+77)
}

func TestLink3(t *testing.T) {
        var r Ring
        n := 1
        for i := 1; i < 100; i++ {
                n += i
                verify(t, r.Link(New(i)), n, -1)
        }
}

func TestUnlink(t *testing.T) {
        r10 := makeN(10)
        s10 := r10.Move(6)

        sum10 := sumN(10)

        verify(t, r10, 10, sum10)
        verify(t, s10, 10, sum10)

        r0 := r10.Unlink(0)
        verify(t, r0, 0, 0)

        r1 := r10.Unlink(1)
        verify(t, r1, 1, 2)
        verify(t, r10, 9, sum10-2)

        r9 := r10.Unlink(9)
        verify(t, r9, 9, sum10-2)
        verify(t, r10, 9, sum10-2)
}

func TestLinkUnlink(t *testing.T) {
        for i := 1; i < 4; i++ {
                ri := New(i)
                for j := 0; j < i; j++ {
                        rj := ri.Unlink(j)
                        verify(t, rj, j, -1)
                        verify(t, ri, i-j, -1)
                        ri.Link(rj)
                        verify(t, ri, i, -1)
                }
        }
}