// 第 10 周 – 实践课练习的参考答案
// 运行：go run ./w10/exercises
package main

import (
	"fmt"
	"math"
	"strings"
)

type Node struct {
	Value      int
	Next, Prev *Node
}

var head, end *Node

func initSentinel(values ...int) {
	end = &Node{}
	head = end
	for _, v := range values {
		insertBefore(end, v)
	}
}

func insertBefore(p *Node, x int) {
	q := &Node{Value: p.Value, Next: p.Next}
	p.Value, p.Next = x, q
	if p == end {
		end = q
	}
}

func sentinelStr() string {
	var parts []string
	for p := head; p != end; p = p.Next {
		parts = append(parts, fmt.Sprint(p.Value))
	}
	return "[" + strings.Join(parts, " ") + "]"
}

// E1. 带哨兵链表的最大值
func maxValue() int {
	m := math.MinInt
	for p := head; p != end; p = p.Next {
		m = max(m, p.Value)
	}
	return m
}

// E2. 用哨兵查找统计出现次数
func countSentinel(x int) int {
	end.Value = x
	c := 0
	p := head
	for {
		for p.Value != x {
			p = p.Next
		}
		if p == end {
			return c
		}
		c++
		p = p.Next
	}
}

// E3. 用“复制后继结点”的技巧删除偶数
func removeEven() {
	p := head
	for p != end {
		if p.Value%2 == 0 {
			q := p.Next
			p.Value, p.Next = q.Value, q.Next
			if q == end {
				end = p
			}
		} else {
			p = p.Next
		}
	}
}

// E4. 双向链表是否是回文？
func isPalindromeDoubly(a ...int) bool {
	var h, t *Node
	for _, v := range a {
		n := &Node{Value: v, Prev: t}
		if t != nil {
			t.Next = n
		} else {
			h = n
		}
		t = n
	}
	for h != t && t.Next != h {
		if h.Value != t.Value {
			return false
		}
		h, t = h.Next, t.Prev
	}
	return true
}

// E5. 循环链表的大小
func circularSize(last *Node) int {
	if last == nil {
		return 0
	}
	c := 0
	for p := last.Next; ; {
		c++
		p = p.Next
		if p == last.Next {
			return c
		}
	}
}

func main() {
	initSentinel(4, 9, 2, 9, 7, 6)
	fmt.Println("E1. list", sentinelStr(), ", max =", maxValue())
	fmt.Println("E2. countSentinel(9) =", countSentinel(9), ", countSentinel(5) =", countSentinel(5))
	removeEven()
	fmt.Println("E3. after deleting the even elements:", sentinelStr())
	fmt.Println("E4. is [1 2 3 2 1] a palindrome?", isPalindromeDoubly(1, 2, 3, 2, 1), ", [1 2 2 3]?", isPalindromeDoubly(1, 2, 2, 3))
	a, b, c := &Node{Value: 1}, &Node{Value: 2}, &Node{Value: 3}
	a.Next, b.Next, c.Next = b, c, a
	fmt.Println("E5. size of the circular list:", circularSize(c))
}