package main

import (
	"errors"
	"fmt"
	"slices"
	"strings"
	"sync"
)

// These bounded in-memory models do not provide durable or distributed storage.
func allocate(links map[string]string, target string, candidates []string) (string, error) {
	for _, code := range candidates {
		if _, exists := links[code]; !exists {
			links[code] = target
			return code, nil
		}
	}
	return "", errors.New("collision budget exhausted")
}

type Sale struct {
	mu     sync.Mutex
	Stock  int
	Orders map[string]bool
}

func (s *Sale) Reserve(key string) bool {
	s.mu.Lock()
	defer s.mu.Unlock()
	if ok, exists := s.Orders[key]; exists {
		return ok
	}
	ok := s.Stock > 0
	if ok {
		s.Stock--
	}
	s.Orders[key] = ok
	return ok
}

func feed(pushed, pulled []int, before, limit int) []int {
	seen := map[int]bool{}
	out := []int{}
	for _, src := range [][]int{pushed, pulled} {
		for _, id := range src {
			if id < before && !seen[id] {
				seen[id] = true
				out = append(out, id)
			}
		}
	}
	slices.Sort(out)
	slices.Reverse(out)
	if len(out) > limit {
		out = out[:limit]
	}
	return out
}

type Message struct {
	Seq       int
	Key, Text string
}
type Chat struct {
	Messages []Message
	Seen     map[string]Message
}

func (c *Chat) Send(key, text string) (Message, error) {
	if old, ok := c.Seen[key]; ok {
		if old.Text != text {
			return Message{}, errors.New("payload conflict")
		}
		return old, nil
	}
	m := Message{len(c.Messages) + 1, key, text}
	c.Seen[key] = m
	c.Messages = append(c.Messages, m)
	return m, nil
}
func (c *Chat) After(seq int) []Message {
	out := []Message{}
	for _, m := range c.Messages {
		if m.Seq > seq {
			out = append(out, m)
		}
	}
	return out
}

type Bucket struct {
	Tokens, Capacity, Rate float64
	LastMS                 int64
}

func (b *Bucket) Allow(nowMS int64) (bool, error) {
	if nowMS < b.LastMS {
		return false, errors.New("clock moved backward")
	}
	b.Tokens = min(b.Capacity, b.Tokens+float64(nowMS-b.LastMS)/1000*b.Rate)
	b.LastMS = nowMS
	if b.Tokens < 1 {
		return false, nil
	}
	b.Tokens--
	return true, nil
}

type IDGen struct {
	Worker, Last, Seq int64
	Started           bool
}

func (g *IDGen) Next(ms int64) (int64, error) {
	if g.Worker < 0 || g.Worker >= 1024 || ms < 0 || ms >= 1<<41 {
		return 0, errors.New("out of range")
	}
	if g.Started && ms < g.Last {
		return 0, errors.New("clock moved backward")
	}
	seq := int64(0)
	if g.Started && ms == g.Last {
		seq = g.Seq + 1
	}
	if seq >= 4096 {
		return 0, errors.New("sequence exhausted; advance clock")
	}
	g.Last, g.Seq, g.Started = ms, seq, true
	return ms<<22 | g.Worker<<12 | seq, nil
}

type Job struct {
	Due, LeaseUntil int64
	Epoch           int
	Done            bool
}

func (j *Job) Claim(now, lease int64) (int, bool) {
	if lease <= 0 || j.Done || now < j.Due || now < j.LeaseUntil {
		return 0, false
	}
	j.Epoch++
	j.LeaseUntil = now + lease
	return j.Epoch, true
}
func (j *Job) Ack(epoch int) bool {
	if j.Done || epoch != j.Epoch || epoch == 0 {
		return false
	}
	j.Done = true
	return true
}

type Score struct {
	User   string
	Points int
}

func ranking(xs []Score) []Score {
	out := slices.Clone(xs)
	slices.SortFunc(out, func(a, b Score) int {
		if a.Points > b.Points {
			return -1
		}
		if a.Points < b.Points {
			return 1
		}
		return strings.Compare(a.User, b.User)
	})
	return out
}

type Counter struct {
	Value int
	Seen  map[string]bool
}

func (c *Counter) Add(event string, n int) {
	if c.Seen[event] {
		return
	}
	c.Seen[event] = true
	c.Value += n
}
func mergeG(a, b map[string]int) map[string]int {
	out := map[string]int{}
	for k, v := range a {
		out[k] = v
	}
	for k, v := range b {
		out[k] = max(out[k], v)
	}
	return out
}
func sum(m map[string]int) int {
	n := 0
	for _, v := range m {
		n += v
	}
	return n
}

type Suggestion struct {
	Text   string
	Weight int
}

// Linear scan is only a reference for ranking correctness, not a production index.
func suggest(dict []Suggestion, prefix string, k int) []string {
	prefix = strings.ToLower(strings.TrimSpace(prefix))
	xs := []Suggestion{}
	for _, x := range dict {
		if strings.HasPrefix(x.Text, prefix) {
			xs = append(xs, x)
		}
	}
	slices.SortFunc(xs, func(a, b Suggestion) int {
		if a.Weight > b.Weight {
			return -1
		}
		if a.Weight < b.Weight {
			return 1
		}
		return strings.Compare(a.Text, b.Text)
	})
	if len(xs) > k {
		xs = xs[:k]
	}
	out := []string{}
	for _, x := range xs {
		out = append(out, x.Text)
	}
	return out
}

type Entry struct {
	Account string
	Amount  int64
}
type Payment struct {
	State                string
	Amount               int64
	Currency, ProviderID string
}
type Ledger struct {
	Payments map[string]Payment
	Posted   map[string]bool
	Entries  []Entry
}

func (l *Ledger) Reconcile(id, providerID, currency string, amount int64) error {
	p, ok := l.Payments[id]
	if !ok {
		return errors.New("unknown payment")
	}
	if amount <= 0 || amount != p.Amount || currency != p.Currency || providerID == "" {
		return errors.New("reconciliation mismatch")
	}
	if p.ProviderID != "" && p.ProviderID != providerID {
		return errors.New("provider ID conflict")
	}
	if l.Posted[id] {
		return nil
	}
	// One local atomic transition is assumed; this is neither a banking ledger nor a provider call.
	l.Entries = append(l.Entries, Entry{"provider-clearing", amount}, Entry{"merchant-payable", -amount})
	p.State, p.ProviderID = "succeeded", providerID
	l.Payments[id] = p
	l.Posted[id] = true
	return nil
}
func balance(es []Entry) int64 {
	var n int64
	for _, e := range es {
		n += e.Amount
	}
	return n
}

type Notification struct {
	Seen     map[string]bool
	Visible  int
	Attempts int
}

func (n *Notification) Deliver(id string, loseACK bool) error {
	n.Attempts++
	// Models a receiver that supports persistent dedupe; many providers do not.
	if !n.Seen[id] {
		n.Seen[id] = true
		n.Visible++
	}
	if loseACK {
		return errors.New("ack lost: result unknown")
	}
	return nil
}

func demos() []string {
	out := []string{}
	links := map[string]string{"a": "old"}
	code, err := allocate(links, "new", []string{"a", "b"})
	out = append(out, fmt.Sprintf("shortlink code=%s old=%s err=%v", code, links["a"], err))
	sale := &Sale{Stock: 1, Orders: map[string]bool{}}
	a, b, c := sale.Reserve("u1"), sale.Reserve("u1"), sale.Reserve("u2")
	out = append(out, fmt.Sprintf("sale first=%v replay=%v other=%v stock=%d", a, b, c, sale.Stock))
	out = append(out, fmt.Sprintf("feed=%v", feed([]int{7, 4}, []int{9, 7}, 10, 3)))
	chat := &Chat{Seen: map[string]Message{}}
	m1, _ := chat.Send("client-1", "hi")
	m2, _ := chat.Send("client-1", "hi")
	out = append(out, fmt.Sprintf("chat seq=%d replay=%d missed=%d", m1.Seq, m2.Seq, len(chat.After(0))))
	bucket := &Bucket{Tokens: 2, Capacity: 2, Rate: 1}
	r1, _ := bucket.Allow(0)
	r2, _ := bucket.Allow(0)
	r3, _ := bucket.Allow(0)
	r4, _ := bucket.Allow(1000)
	out = append(out, fmt.Sprintf("limit=%v %v %v %v", r1, r2, r3, r4))
	gen := &IDGen{Worker: 3}
	id1, _ := gen.Next(100)
	id2, _ := gen.Next(100)
	_, err = gen.Next(99)
	out = append(out, fmt.Sprintf("ids distinct=%v rollback=%v", id1 != id2, err))
	job := &Job{Due: 10}
	e1, _ := job.Claim(10, 5)
	e2, _ := job.Claim(15, 5)
	old, current := job.Ack(e1), job.Ack(e2)
	out = append(out, fmt.Sprintf("job old_ack=%v current_ack=%v", old, current))
	out = append(out, fmt.Sprintf("ranking=%v", ranking([]Score{{"z", 90}, {"b", 100}, {"a", 90}})))
	counter := &Counter{Seen: map[string]bool{}}
	counter.Add("e1", 1)
	counter.Add("e1", 1)
	merged := mergeG(map[string]int{"a": 2}, map[string]int{"a": 1, "b": 3})
	out = append(out, fmt.Sprintf("counter dedup=%d merged=%d", counter.Value, sum(merged)))
	out = append(out, fmt.Sprintf("suggest=%v", suggest([]Suggestion{{"go", 9}, {"golang", 7}, {"gopher", 5}, {"java", 10}}, "Go", 2)))
	ledger := &Ledger{Payments: map[string]Payment{"p1": {State: "unknown", Amount: 100, Currency: "USD"}}, Posted: map[string]bool{}}
	_ = ledger.Reconcile("p1", "fake-charge-1", "USD", 100)
	_ = ledger.Reconcile("p1", "fake-charge-1", "USD", 100)
	out = append(out, fmt.Sprintf("payment state=%s entries=%d balance=%d", ledger.Payments["p1"].State, len(ledger.Entries), balance(ledger.Entries)))
	n := &Notification{Seen: map[string]bool{}}
	_ = n.Deliver("event-1", true)
	_ = n.Deliver("event-1", false)
	out = append(out, fmt.Sprintf("notify attempts=%d visible=%d", n.Attempts, n.Visible))
	return out
}
func main() {
	for _, line := range demos() {
		fmt.Println(line)
	}
}