package subex

import (
	"main/walk"
)

// Where slots are stored
type Store map[rune][]walk.Atom
// Return a new store with all the data from this one
func (store Store) clone() Store {
	newStore := make(Store)
	for key, val := range store {
		newStore[key] = val
	}
	return newStore
}
// Return a copy of this store but with an additional slot set
func (store Store) withValue(key rune, value []walk.Atom) Store {
	newStore := store.clone()
	newStore[key] = value
	return newStore
}

// Compile the SubexAST into a transducer SubexState that can be run
func CompileTransducer(transducerAst SubexAST) SubexState {
	return transducerAst.compileWith(&SubexNoneState{})
}

// An immutable stack for outputting to
type OutputStack struct {
	head []walk.Atom
	tail *OutputStack
}
func (stack OutputStack) pop() ([]walk.Atom, OutputStack) {
	return stack.head, *stack.tail
}
func (stack OutputStack) push(atoms []walk.Atom) OutputStack {
	return OutputStack {
		head: atoms,
		tail: &stack,
	}
}
func (stack OutputStack) replace(atoms []walk.Atom) OutputStack {
	return OutputStack {
		head: atoms,
		tail: stack.tail,
	}
}
func (stack OutputStack) peek() []walk.Atom {
	return stack.head
}

func topAppend(outputStack OutputStack, atoms []walk.Atom) OutputStack {
	head := outputStack.peek()
	return outputStack.replace(walk.ConcatData(head, atoms))
}

// One branch of subex execution
type SubexBranch struct {
	// Content of slots in this branch
	store Store
	// State in this branch
	state SubexState
	// The output stack. At the end of the program, whatever is on top of this will be output
	// States may push or pop to the stack as they wish, creating sort of a call stack that allows states to capture the output of other states
	outputStack OutputStack
}
// Read a single character and return all the branches resulting from this branch consuming it
func (pair SubexBranch) eat(char walk.Atom) []SubexBranch {
	return pair.state.eat(pair.store, pair.outputStack, char)
}
func (pair SubexBranch) accepting() []OutputStack {
	return pair.state.accepting(pair.store, pair.outputStack)
}

func equalStates(left SubexBranch, right SubexBranch) bool {
	// Only care about if they are the same pointer
	return left.state == right.state
}

// If two branches have the same state, only the first has a chance of being successful
// This function removes all of the pointless execution branches to save execution time
func pruneStates(states []SubexBranch) (newStates []SubexBranch) {
	outer: for _, state := range states {
		for _, newState := range newStates {
			if equalStates(state, newState) {
				continue outer
			}
		}
		newStates = append(newStates, state)
	}
	return newStates
}

// Run the subex transducer
func RunTransducer(transducer SubexState, input []walk.Atom) (output []walk.Atom, err bool) {
	states := []SubexBranch{{
		state: transducer,
		outputStack: OutputStack {
			head: nil,
			tail: nil,
		},
		store: make(Store),
	}}
	for _, piece := range input {
		var newStates []SubexBranch
		for _, state := range states {
			newStates = append(newStates, state.eat(piece)...)
		}
		states = pruneStates(newStates)
		if len(states) == 0 {
			return nil, true
		}
	}
	for _, state := range states {
		acceptingStacks := state.accepting()
		for _, stack := range acceptingStacks {
			output := stack.head
			return output, false
		}
	}
	return nil, true
}