func subsetOf(a1, a2 *Automaton) bool {
	assert2(a1.deterministic, "a1 must be deterministic")
	assert2(a2.deterministic, "a2 must be deterministic")
	assert(!hasDeadStatesFromInitial(a1))
	assert2(!hasDeadStatesFromInitial(a2), "%v", a2)
	if a1.numStates() == 0 {
		return true
	} else if a2.numStates() == 0 {
		return isEmpty(a1)
	}
	transitions1 := a1.sortedTransitions()
	transitions2 := a2.sortedTransitions()
	worklist := list.New()
	visited := make(map[string]*StatePair)
	hash := func(p *StatePair) string {
		return fmt.Sprintf("%v/%v", p.s1, p.s2)
	}
	p := &StatePair{-1, 0, 0}
	worklist.PushBack(p)
	visited[hash(p)] = p
	for worklist.Len() > 0 {
		p = worklist.Remove(worklist.Front()).(*StatePair)
		if a1.IsAccept(p.s1) && !a2.IsAccept(p.s2) {
			return false
		}
		t1 := transitions1[p.s1]
		t2 := transitions2[p.s2]
		for n1, b2, t1Len := 0, 0, len(t1); n1 < t1Len; n1++ {
			t2Len := len(t2)
			for b2 < t2Len && t2[b2].max < t1[n1].min {
				b2++
			}
			min1, max1 := t1[n1].min, t1[n1].max
			for n2 := b2; n2 < t2Len && t1[n1].max >= t2[n2].min; n2++ {
				if t2[n2].min > min1 {
					return false
				}
				if t2[n2].max < unicode.MaxRune {
					min1 = t2[n2].max + 1
				} else {
					min1, max1 = unicode.MaxRune, MIN_CODE_POINT
				}
				q := &StatePair{-1, t1[n1].dest, t2[n2].dest}
				if _, ok := visited[hash(q)]; !ok {
					worklist.PushBack(q)
					visited[hash(q)] = q
				}
			}
			if min1 <= max1 {
				return false
			}
		}
	}
	return true
}
/*
Returns true if the language of a1 is a subset of the language of a2.
As a side-effect, a2 is determinized if not already marked as
deterministic.
package automaton
import (
	"container/list"
	"fmt"
	"github.com/balzaczyy/golucene/core/util"
	"unicode"
)
func concatenate(a1, a2 *Automaton) *Automaton {
	return concatenateN([]*Automaton{a1, a2})
}
func concatenateN(l []*Automaton) *Automaton {
	ans := newEmptyAutomaton()
	for _, a := range l {
		if a.numStates() == 0 {
			ans.finishState()
			return ans
		}
		numStates := a.numStates()
		for s := 0; s < numStates; s++ {
			ans.createState()
		}
	}
	stateOffset := 0
	t := newTransition()
	for i, a := range l {
		numStates := a.numStates()
		var nextA *Automaton
		if i < len(l)-1 {
			nextA = l[i+1]
		}
		for s := 0; s < numStates; s++ {
			numTransitions := a.initTransition(s, t)
			for j := 0; j < numTransitions; j++ {
				a.nextTransition(t)
				ans.addTransitionRange(stateOffset+s, stateOffset+t.dest, t.min, t.max)
			}
			if a.IsAccept(s) {
				followA := nextA
				followOffset := stateOffset
				upto := i + 1
				for {
					if followA != nil {
						numTransitions = followA.initTransition(0, t)
						for j := 0; j < numTransitions; j++ {
							followA.nextTransition(t)
							ans.addTransitionRange(stateOffset+s, followOffset+numStates+t.dest, t.min, t.max)
						}
						if followA.IsAccept(0) {
							followOffset += followA.numStates()
							if upto < len(l)-1 {
								followA = l[upto+1]
							} else {
								followA = nil
							}
							upto++
						} else {
							break
						}
					} else {
						ans.setAccept(stateOffset+s, true)
						break
					}
				}
			}
		}
		stateOffset += numStates
	}
	if ans.numStates() == 0 {
		ans.createState()
	}
	ans.finishState()
	return ans
}
func optional(a *Automaton) *Automaton {
	ans := newEmptyAutomaton()
	ans.createState()
	ans.setAccept(0, true)
	if a.numStates() > 0 {
		ans.copy(a)
		ans.addEpsilon(0, 1)
	}
	ans.finishState()
	return ans
}
func repeat(a *Automaton) *Automaton {
	if isEmpty(a) {
		return a
	}
	b := newAutomatonBuilder()
	b.createState()
	b.setAccept(0, true)
	b.copy(a)
	t := newTransition()
	count := a.initTransition(0, t)
	for i := 0; i < count; i++ {
		a.nextTransition(t)
		b.addTransitionRange(0, t.dest+1, t.min, t.max)
	}
	numStates := a.numStates()
	for s := 0; s < numStates; s++ {
		if a.IsAccept(s) {
			count = a.initTransition(0, t)
			for i := 0; i < count; i++ {
				a.nextTransition(t)
				b.addTransitionRange(s+1, t.dest+1, t.min, t.max)
			}
		}
	}
	return b.finish()
}
func repeatMin(a *Automaton, min int) *Automaton {
	if min == 0 {
		return repeat(a)
	}
	as := make([]*Automaton, 0, min+1)
	for min > 0 {
		as = append(as, a)
		min--
	}
	as = append(as, repeat(a))
	return concatenateN(as)
}
func complement(a *Automaton) *Automaton {
	a = totalize(determinize(a))
	numStates := a.numStates()
	for p := 0; p < numStates; p++ {
		a.setAccept(p, !a.IsAccept(p))
	}
	return removeDeadStates(a)
}
func minus(a1, a2 *Automaton) *Automaton {
	if isEmpty(a1) || a1 == a2 {
		return MakeEmpty()
	}
	if isEmpty(a2) {
		return a1
	}
	return intersection(a1, complement(a2))
}
type StatePair struct{ s, s1, s2 int }
func intersection(a1, a2 *Automaton) *Automaton {
	if a1 == a2 || a1.numStates() == 0 {
		return a1
	}
	if a2.numStates() == 0 {
		return a2
	}
	transitions1 := a1.sortedTransitions()
	transitions2 := a2.sortedTransitions()
	c := newEmptyAutomaton()
	c.createState()
	worklist := list.New()
	newstates := make(map[string]*StatePair)
	hash := func(p *StatePair) string {
		return fmt.Sprintf("%v/%v", p.s1, p.s2)
	}
	p := &StatePair{0, 0, 0}
	worklist.PushBack(p)
	newstates[hash(p)] = p
	for worklist.Len() > 0 {
		p = worklist.Remove(worklist.Front()).(*StatePair)
		c.setAccept(p.s, a1.IsAccept(p.s1) && a2.IsAccept(p.s2))
		t1 := transitions1[p.s1]
		t2 := transitions2[p.s2]
		for n1, b2 := 0, 0; n1 < len(t1); n1++ {
			for b2 < len(t2) && t2[b2].max < t1[n1].min {
				b2++
			}
			for n2 := b2; n2 < len(t2) && t1[n1].max >= t2[n2].min; n2++ {
				if t2[n2].max >= t1[n1].min {
					q := &StatePair{-1, t1[n1].dest, t2[n2].dest}
					r, ok := newstates[hash(q)]
					if !ok {
						q.s = c.createState()
						worklist.PushBack(q)
						newstates[hash(q)] = q
						r = q
					}
					min := or(t1[n1].min > t2[n2].min, t1[n1].min, t2[n2].min).(int)
					max := or(t1[n1].max < t2[n2].max, t1[n1].max, t2[n2].max).(int)
					c.addTransitionRange(p.s, r.s, min, max)
				}
			}
		}
	}
	c.finishState()
	return removeDeadStates(c)
}
func sameLanguage(a1, a2 *Automaton) bool {
	if a1 == a2 {
		return true
	}
	return subsetOf(a2, a1) && subsetOf(a1, a2)
}
func hasDeadStates(a *Automaton) bool {
	liveStates := liveStates(a)
	numLive := liveStates.Cardinality()
	numStates := a.numStates()
	assert2(numLive <= int64(numStates), "numLive=%v numStates=%v %v", numLive, numStates, liveStates)
	return numLive < int64(numStates)
}
func hasDeadStatesFromInitial(a *Automaton) bool {
	r1 := liveStatesFromInitial(a)
	r2 := liveStatesToAccept(a)
	r1.AndNot(r2)
	return !r1.IsEmpty()
}