// Week 9 – Solutions of the practice exercises
// Run: go run ./w09/exercises
package main

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

type Node struct {
	Value int
	Next  *Node
}

func fromSlice(a ...int) *Node {
	var h *Node
	for i := len(a) - 1; i >= 0; i-- {
		h = &Node{a[i], h}
	}
	return h
}

func str(h *Node) string {
	var parts []string
	for p := h; p != nil; p = p.Next {
		parts = append(parts, fmt.Sprint(p.Value))
	}
	return "[" + strings.Join(parts, " ") + "]"
}

// E1. Sum and maximum
func sumAndMax(h *Node) (int, int) {
	sum, mx := 0, math.MinInt
	for p := h; p != nil; p = p.Next {
		sum += p.Value
		mx = max(mx, p.Value)
	}
	return sum, mx
}

// E2. The i-th element – O(i)
func get(h *Node, i int) (int, bool) {
	p := h
	for k := 0; k < i && p != nil; k++ {
		p = p.Next
	}
	if p == nil {
		return 0, false
	}
	return p.Value, true
}

// E3. Number of occurrences
func count(h *Node, x int) int {
	c := 0
	for p := h; p != nil; p = p.Next {
		if p.Value == x {
			c++
		}
	}
	return c
}

// E4. Reversing in place
func reverse(h *Node) *Node {
	var prev *Node
	for p := h; p != nil; {
		next := p.Next
		p.Next = prev
		prev, p = p, next
	}
	return prev
}

// E5. Deleting every x
func removeAll(h *Node, x int) *Node {
	for h != nil && h.Value == x {
		h = h.Next
	}
	if h == nil {
		return nil
	}
	for p := h; p.Next != nil; {
		if p.Next.Value == x {
			p.Next = p.Next.Next
		} else {
			p = p.Next
		}
	}
	return h
}

// E6. Middle element (hare and tortoise)
func middle(h *Node) int {
	slow, fast := h, h
	for fast != nil && fast.Next != nil {
		slow, fast = slow.Next, fast.Next.Next
	}
	return slow.Value
}

// E7. Sorted insertion
func insertSorted(h *Node, x int) *Node {
	if h == nil || x <= h.Value {
		return &Node{x, h}
	}
	p := h
	for p.Next != nil && p.Next.Value < x {
		p = p.Next
	}
	p.Next = &Node{x, p.Next}
	return h
}

func main() {
	h := fromSlice(4, 9, 2, 9, 7)
	s, m := sumAndMax(h)
	fmt.Println("E1. list", str(h), ": sum =", s, ", max =", m)
	v, ok := get(h, 3)
	_, ok2 := get(h, 10)
	fmt.Println("E2. get(3) =", v, ok, ", does get(10) exist?", ok2)
	fmt.Println("E3. count(9) =", count(h, 9))
	fmt.Println("E4. reverse =", str(reverse(fromSlice(1, 2, 3, 4, 5))))
	fmt.Println("E5. removeAll(9) =", str(removeAll(fromSlice(9, 4, 9, 9, 2, 9), 9)))
	fmt.Println("E6. middle([1..5]) =", middle(fromSlice(1, 2, 3, 4, 5)), ", middle([1..6]) =", middle(fromSlice(1, 2, 3, 4, 5, 6)))
	var sl *Node
	for _, x := range []int{5, 2, 8, 1, 9, 3} {
		sl = insertSorted(sl, x)
	}
	fmt.Println("E7. with sorted insertion:", str(sl))
}