// 第 10 周 – 带哨兵的链表：Head 指向第一个结点，End 指向哨兵；空链表：Head = End。
// 运行：go run ./w10/sentinellist
package main

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

type Node struct {
	Value int
	Next  *Node
}

type SentinelList struct {
	Head, End *Node
}

// NewSentinelList：只有一个哨兵结点，Head = End
func NewSentinelList() *SentinelList {
	s := &Node{}
	return &SentinelList{Head: s, End: s}
}

func (l *SentinelList) IsEmpty() bool { return l.Head == l.End }

func (l *SentinelList) String() string {
	var parts []string
	for p := l.Head; p != l.End; p = p.Next { // 直到哨兵，而不是直到 nil!
		parts = append(parts, fmt.Sprint(p.Value))
	}
	return "[" + strings.Join(parts, " ") + "]"
}

// Search：哨兵查找 – 循环只有一个条件
func (l *SentinelList) Search(x int) *Node {
	l.End.Value = x
	p := l.Head
	for p.Value != x {
		p = p.Next
	}
	if p == l.End {
		return nil
	}
	return p
}

// InsertBefore：在 p 之前插入 – O(1)（把 p 的内容复制到 q,p 存放新数据）
func (l *SentinelList) InsertBefore(p *Node, x int) {
	q := &Node{Value: p.Value, Next: p.Next}
	p.Value = x
	p.Next = q
	if p == l.End {
		l.End = q
	}
}

func (l *SentinelList) InsertLast(x int)  { l.InsertBefore(l.End, x) }
func (l *SentinelList) InsertFirst(x int) { l.InsertBefore(l.Head, x) }

// Delete：删除 p – O(1)（把后继结点的内容复制到 p）
func (l *SentinelList) Delete(p *Node) {
	if p == l.End {
		panic("the sentinel cannot be deleted")
	}
	q := p.Next
	p.Value = q.Value
	p.Next = q.Next
	if q == l.End {
		l.End = p
	}
}

func (l *SentinelList) Clear() { l.Head = l.End }

// InsertSorted：插在第一个更大的元素之前 – 没有特殊情况
func (l *SentinelList) InsertSorted(x int) {
	l.End.Value = math.MaxInt
	p := l.Head
	for p.Value < x {
		p = p.Next
	}
	l.InsertBefore(p, x)
}

func main() {
	l := NewSentinelList()
	fmt.Println("empty:", l)
	l.InsertLast(3)
	l.InsertLast(9)
	l.InsertLast(4)
	l.InsertFirst(1)
	fmt.Println("InsertLast 3, 9, 4; InsertFirst 1:", l)
	fmt.Println("Search(9) found?", l.Search(9) != nil, ", Search(7) found?", l.Search(7) != nil)
	l.InsertBefore(l.Search(9), 8)
	fmt.Println("InsertBefore(9, 8):", l)
	l.Delete(l.Search(4))
	fmt.Println("Delete(4):", l)
	l.Delete(l.Search(1))
	fmt.Println("Delete(1):", l)

	s := NewSentinelList()
	for _, x := range []int{5, 2, 8, 1, 9, 3} {
		s.InsertSorted(x)
	}
	fmt.Println("with sorted insertion:", s)
	s.Clear()
	fmt.Println("empty after Clear?", s.IsEmpty())
}