/*
Determinizes the given automaton.

Split the code points in ranges, and merge overlapping states.

Worst case complexity: exponential in number of states.
*/
553053
func determinize(a *Automaton) *Automaton {
	if a.deterministic || a.numStates() <= 1 {
		return a
	}

	// subset construction
	b := newAutomatonBuilder()

	// fmt.Println("DET:")

	initialset := newFrozenIntSetOf(0, 0)

	// craete state 0:
	b.createState()

	worklist := list.New()
	newstate := make(map[string]int)
	hash := func(s *FrozenIntSet) string {
		return s.String()
	}

	worklist.PushBack(initialset)

	b.setAccept(0, a.IsAccept(0))
	newstate[hash(initialset)] = 0

	// like map[int]*PointTransitions
	points := newPointTransitionSet()

	// like sorted map[int]int
	statesSet := newSortedIntSet(5)

	t := newTransition()

	for worklist.Len() > 0 {
		s := worklist.Remove(worklist.Front()).(*FrozenIntSet)
		// fmt.Printf("det: pop set=%v\n", s)

		// Collate all outgoing transitions by min/1+max
		for _, s0 := range s.values {
			numTransitions := a.numTransitions(s0)
			a.initTransition(s0, t)
			for j := 0; j < numTransitions; j++ {
				a.nextTransition(t)
				points.add(t)
			}
		}

		if len(points.points) == 0 {
			// No outgoing transitions -- skip it
			continue
		}

		points.sort()

		lastPoint := -1
		accCount := 0

		r := s.state
		for _, v := range points.points {
			point := v.point

			if len(statesSet.values) > 0 {
				assert(lastPoint != -1)

				hashKey := statesSet.computeHash().String()

				q, ok := newstate[hashKey]
				if !ok {
					q = b.createState()
					p := statesSet.freeze(q)
					// fmt.Printf("  make new state=%v -> %v accCount=%v\n", q, p, accCount)
					worklist.PushBack(p)
					b.setAccept(q, accCount > 0)
					newstate[hash(p)] = q
				} else {
					assert2(b.isAccept(q) == (accCount > 0),
						"accCount=%v vs existing accept=%v states=%v",
						accCount, b.isAccept(q), statesSet)
				}

				// fmt.Printf("  add trans src=%v dest=%v min=%v max=%v\n",
				// 	r, q, lastPoint, point-1)
				b.addTransitionRange(r, q, lastPoint, point-1)
			}

			// process transitions that end on this point
			// (closes an overlapping interval)
			for j, limit := 0, len(v.ends.transitions); j < limit; j += 3 {
				dest := v.ends.transitions[j]
				statesSet.decr(dest)
				if a.IsAccept(dest) {
					accCount--
				}
			}
			v.ends.transitions = v.ends.transitions[:0] // reuse slice

			// process transitions that start on this point
			// (opens a new interval)
			for j, limit := 0, len(v.starts.transitions); j < limit; j += 3 {
				dest := v.starts.transitions[j]
				statesSet.incr(dest)
				if a.IsAccept(dest) {
					accCount++
				}
			}
			v.starts.transitions = v.starts.transitions[:0] // reuse slice

			lastPoint = point
		}
		points.reset()
		assert2(len(statesSet.values) == 0, "upto=%v", len(statesSet.values))
	}

	ans := b.finish()
	assert(ans.deterministic)
	return ans
}
1236697
func decomposeRecursive(form int, r rune, d Decomposition) Decomposition {
	dcomp := chars[r].forms[form].decomp
	if len(dcomp) == 0 {
		return insertOrdered(d, r)
	}
	for _, c := range dcomp {
		d = decomposeRecursive(form, c, d)
	}
	return d
}
752240
func shuffle(m []string) {
	for _ = range m {
		i := rand.Intn(len(m))
		j := rand.Intn(len(m))
		m[i], m[j] = m[j], m[i]
	}
}
894652
func (q *QueryStringQuery) MaxDeterminizedState(maxDeterminizedStates int) *QueryStringQuery {
	q.maxDeterminizedStates = &maxDeterminizedStates
	return q
}
1309861
func Reset() {
	states = stateMap{
		m: map[string]*remote.State{},
	}

	locks = lockMap{
		m: map[string]*state.LockInfo{},
	}
}
728252
func splitCommand(line string) (string, []string, string, error) {
	var args string
	var flags []string

	// Make sure we get the same results irrespective of leading/trailing spaces
	cmdline := tokenWhitespace.Split(strings.TrimSpace(line), 2)
	cmd := strings.ToLower(cmdline[0])

	if len(cmdline) == 2 {
		var err error
		args, flags, err = extractBuilderFlags(cmdline[1])
		if err != nil {
			return "", nil, "", err
		}
	}

	return cmd, flags, strings.TrimSpace(args), nil
}
260617
func _() {
	var _ Event = (*Absolute)(nil)        // assert *Absolute implements Event
	var _ Event = (*FAbsolute)(nil)       // assert *FAbsolute implements Event
	var _ Event = (*Gauge)(nil)           // assert *Gauge implements Event
	var _ Event = (*FGauge)(nil)          // assert *FGauge implements Event
	var _ Event = (*GaugeDelta)(nil)      // assert *GaugeDelta implements Event
	var _ Event = (*FGaugeDelta)(nil)     // assert *FGaugeDelta implements Event
	var _ Event = (*Increment)(nil)       // assert *Increment implements Event
	var _ Event = (*PrecisionTiming)(nil) // assert *PrecisionTiming implements Event
	var _ Event = (*Timing)(nil)          // assert *Timing implements Event
	var _ Event = (*Total)(nil)           // assert *Total implements Event
}
573000
func (m StatesSpec) Compile() (States, error) {
	sm := &StateMap{}
	for name, specs := range m {
		rules := make(State, 0, len(specs))
		for _, spec := range specs {
			rules = append(rules, spec.Compile(sm))
		}
		(*sm)[name] = rules
	}
	return sm, nil
}
582916
func (d *Dictionary) AutomatonIterator(a vellum.Automaton,
	startKeyInclusive, endKeyExclusive []byte) segment.DictionaryIterator {
	rv := &DictionaryIterator{
		d: d,
	}

	if d.fst != nil {
		itr, err := d.fst.Search(a, startKeyInclusive, endKeyExclusive)
		if err == nil {
			rv.itr = itr
		} else if err != vellum.ErrIteratorDone {
			rv.err = err
		}
	}

	return rv
}
1026280
func makeString(s string) *Automaton {
	a := newEmptyAutomaton()
	lastState := a.createState()
	for _, r := range s {
		state := a.createState()
		a.addTransitionRange(lastState, state, int(r), int(r))
		lastState = state
	}

	a.setAccept(lastState, true)
	a.finishState()

	assert(a.deterministic)
	assert(!hasDeadStates(a))

	return a
}
933711
func (s *scanner) takeState() int {
	if s.cached {
		s.cached = false
	}else{
	    s.peekState()
	}
	s.readPos += 1
	return s.cacheRecord.state
}
449508
func (i *FSTIterator) Reset(f *FST,
	startKeyInclusive, endKeyExclusive []byte, aut Automaton) error {
	if aut == nil {
		aut = alwaysMatchAutomaton
	}

	i.f = f
	i.startKeyInclusive = startKeyInclusive
	i.endKeyExclusive = endKeyExclusive
	i.aut = aut

	return i.pointTo(startKeyInclusive)
}
840370
func (m *matcher) computeNext(d *dstate, c int) *dstate {
	this, next := &m.z1, &m.z2
	this.dec(d.enc)

	// compute flags in effect before c
	flag := syntax.EmptyOp(0)
	if this.flag&flagBOL != 0 {
		flag |= syntax.EmptyBeginLine
	}
	if this.flag&flagBOT != 0 {
		flag |= syntax.EmptyBeginText
	}
	if this.flag&flagWord != 0 {
		if !isWordByte(c) {
			flag |= syntax.EmptyWordBoundary
		} else {
			flag |= syntax.EmptyNoWordBoundary
		}
	} else {
		if isWordByte(c) {
			flag |= syntax.EmptyWordBoundary
		} else {
			flag |= syntax.EmptyNoWordBoundary
		}
	}
	if c == '\n' {
		flag |= syntax.EmptyEndLine
	}
	if c == endText {
		flag |= syntax.EmptyEndLine | syntax.EmptyEndText
	}

	// re-expand queue using new flags.
	// TODO: only do this when it matters
	// (something is gating on word boundaries).
	m.stepEmpty(&this.q, &next.q, flag)
	this, next = next, this

	// now compute flags after c.
	flag = 0
	next.flag = 0
	if c == '\n' {
		flag |= syntax.EmptyBeginLine
		next.flag |= flagBOL
	}
	if isWordByte(c) {
		next.flag |= flagWord
	}

	// re-add start, process rune + expand according to flags.
	if m.stepByte(&this.q, &next.q, c, flag) {
		return &dmatch
	}
	return m.cache(next)
}
993997
func (a *Automaton) copy(other *Automaton) {
	// bulk copy and then fixup the state pointers
	stateOffset := a.numStates()
	a.states = append(a.states, other.states...)
	for i := 0; i < len(other.states); i += 2 {
		if a.states[stateOffset*2+i] != -1 {
			a.states[stateOffset*2+i] += len(a.transitions)
		}
	}
	otherAcceptState := other.isAccept
	for state := otherAcceptState.NextSetBit(0); state != -1; state = otherAcceptState.NextSetBit(state + 1) {
		a.setAccept(stateOffset+int(state), true)
	}

	// bulk copy and then fixup dest for each transition
	transOffset := len(a.transitions)
	a.transitions = append(a.transitions, other.transitions...)
	for i := 0; i < len(other.transitions); i += 3 {
		a.transitions[transOffset+i] += stateOffset
	}

	if !other.deterministic {
		a.deterministic = false
	}
}
1063647
func (a *Automaton) createState() int {
	state := len(a.states) / 2
	a.states = append(a.states, -1, 0)
	return state
}
270011
func makeCharRange(min, max int) *Automaton {
	if min > max {
		return MakeEmpty()
	}

	a := newEmptyAutomaton()
	s1 := a.createState()
	s2 := a.createState()
	a.setAccept(s2, true)
	a.addTransitionRange(s1, s2, min, max)
	a.finishState()
	return a
}
100383
func Permutations(pool []interface{}, r int) (*PermutationIterator, error) {
	n := len(pool)

	if r > n {
		return nil, errors.New("Result size is larger than input")
	}

	iter := &PermutationIterator{
		pool: pool,
		n:    n,
		r:    r,
		res:  make([]interface{}, r, r),
		max:  lenPermutations(n, r),
	}

	iter.Reset()

	return iter, nil
}