// 第 10 周 – 只有一个 End(Last)指针的循环单链表
// 运行：go run ./w10/circularlist
package main

import "fmt"

type Node struct {
	Value int
	Next  *Node
}

type CircularList struct {
	Last *Node // 第一个结点：Last.Next
}

func (c *CircularList) InsertLast(x int) { // O(1)
	n := &Node{Value: x}
	if c.Last == nil {
		n.Next = n
	} else {
		n.Next = c.Last.Next
		c.Last.Next = n
	}
	c.Last = n
}

func (c *CircularList) InsertFirst(x int) { // O(1):Last 不动
	n := &Node{Value: x}
	if c.Last == nil {
		n.Next = n
		c.Last = n
		return
	}
	n.Next = c.Last.Next
	c.Last.Next = n
}

func (c *CircularList) String() string {
	if c.Last == nil {
		return "[]"
	}
	s := "["
	p := c.Last.Next
	for { // Go 没有 do-while：用无限循环 + break
		s += fmt.Sprint(p.Value)
		p = p.Next
		if p == c.Last.Next {
			break
		}
		s += " "
	}
	return s + "] (and back to the beginning)"
}

func (c *CircularList) Josephus(k int) int {
	prev := c.Last
	fmt.Print("order of elimination: ")
	for prev.Next != prev {
		for i := 1; i < k; i++ {
			prev = prev.Next
		}
		out := prev.Next
		fmt.Print(out.Value, " ")
		prev.Next = out.Next
	}
	c.Last = prev
	return prev.Value
}

func main() {
	var c CircularList
	for i := 1; i <= 7; i++ {
		c.InsertLast(i)
	}
	fmt.Println(&c)
	c.InsertFirst(0)
	fmt.Println("InsertFirst(0):", &c)

	var j CircularList
	for i := 1; i <= 7; i++ {
		j.InsertLast(i)
	}
	fmt.Println("-> survivor:", j.Josephus(3))
}