func (t *Terminal) constrain() {
	count := t.merger.Length()
	height := t.maxItems()
	diffpos := t.cy - t.offset

	t.cy = util.Constrain(t.cy, 0, count-1)
	t.offset = util.Constrain(t.offset, t.cy-height+1, t.cy)
	// Adjustment
	if count-t.offset < height {
		t.offset = util.Max(0, count-height)
		t.cy = util.Constrain(t.offset+diffpos, 0, count-1)
	}
	t.offset = util.Max(0, t.offset)
}

func (t *Terminal) maxItems() int {
	max := t.maxHeight() - 2 - len(t.header)
	if t.inlineInfo {
		max++
	}
	return util.Max(max, 0)
}

// Tokenize tokenizes the given string with the delimiter
func Tokenize(text util.Chars, delimiter Delimiter) []Token {
	if delimiter.str == nil && delimiter.regex == nil {
		// AWK-style (\S+\s*)
		tokens, prefixLength := awkTokenizer(text)
		return withPrefixLengths(tokens, prefixLength)
	}

	if delimiter.str != nil {
		return withPrefixLengths(text.Split(*delimiter.str), 0)
	}

	// FIXME performance
	var tokens []string
	if delimiter.regex != nil {
		str := text.ToString()
		for len(str) > 0 {
			loc := delimiter.regex.FindStringIndex(str)
			if loc == nil {
				loc = []int{0, len(str)}
			}
			last := util.Max(loc[1], 1)
			tokens = append(tokens, str[:last])
			str = str[last:]
		}
	}
	asRunes := make([]util.Chars, len(tokens))
	for i, token := range tokens {
		asRunes[i] = util.RunesToChars([]rune(token))
	}
	return withPrefixLengths(asRunes, 0)
}

// Tokenize tokenizes the given string with the delimiter
func Tokenize(runes []rune, delimiter Delimiter) []Token {
	if delimiter.str == nil && delimiter.regex == nil {
		// AWK-style (\S+\s*)
		tokens, prefixLength := awkTokenizer(runes)
		return withPrefixLengths(tokens, prefixLength)
	}

	var tokens []string
	if delimiter.str != nil {
		tokens = strings.Split(string(runes), *delimiter.str)
		for i := 0; i < len(tokens)-1; i++ {
			tokens[i] = tokens[i] + *delimiter.str
		}
	} else if delimiter.regex != nil {
		str := string(runes)
		for len(str) > 0 {
			loc := delimiter.regex.FindStringIndex(str)
			if loc == nil {
				loc = []int{0, len(str)}
			}
			last := util.Max(loc[1], 1)
			tokens = append(tokens, str[:last])
			str = str[last:]
		}
	}
	asRunes := make([][]rune, len(tokens))
	for i, token := range tokens {
		asRunes[i] = []rune(token)
	}
	return withPrefixLengths(asRunes, 0)
}

func (t *Terminal) maxItems() int {
	max := C.MaxY() - 2 - len(t.header)
	if t.inlineInfo {
		max += 1
	}
	return util.Max(max, 0)
}

// Transform is used to transform the input when --with-nth option is given
func Transform(tokens []Token, withNth []Range) []Token {
	transTokens := make([]Token, len(withNth))
	numTokens := len(tokens)
	for idx, r := range withNth {
		part := []rune{}
		minIdx := 0
		if r.begin == r.end {
			idx := r.begin
			if idx == rangeEllipsis {
				part = append(part, joinTokensAsRunes(tokens)...)
			} else {
				if idx < 0 {
					idx += numTokens + 1
				}
				if idx >= 1 && idx <= numTokens {
					minIdx = idx - 1
					part = append(part, tokens[idx-1].text...)
				}
			}
		} else {
			var begin, end int
			if r.begin == rangeEllipsis { // ..N
				begin, end = 1, r.end
				if end < 0 {
					end += numTokens + 1
				}
			} else if r.end == rangeEllipsis { // N..
				begin, end = r.begin, numTokens
				if begin < 0 {
					begin += numTokens + 1
				}
			} else {
				begin, end = r.begin, r.end
				if begin < 0 {
					begin += numTokens + 1
				}
				if end < 0 {
					end += numTokens + 1
				}
			}
			minIdx = util.Max(0, begin-1)
			for idx := begin; idx <= end; idx++ {
				if idx >= 1 && idx <= numTokens {
					part = append(part, tokens[idx-1].text...)
				}
			}
		}
		var prefixLength int
		if minIdx < numTokens {
			prefixLength = tokens[minIdx].prefixLength
		} else {
			prefixLength = 0
		}
		transTokens[idx] = Token{part, prefixLength}
	}
	return transTokens
}

func TestFuzzyMatch(t *testing.T) {
	for _, fn := range []Algo{FuzzyMatchV1, FuzzyMatchV2} {
		for _, forward := range []bool{true, false} {
			assertMatch(t, fn, false, forward, "fooBarbaz1", "oBZ", 2, 9,
				scoreMatch*3+bonusCamel123+scoreGapStart+scoreGapExtention*3)
			assertMatch(t, fn, false, forward, "foo bar baz", "fbb", 0, 9,
				scoreMatch*3+bonusBoundary*bonusFirstCharMultiplier+
					bonusBoundary*2+2*scoreGapStart+4*scoreGapExtention)
			assertMatch(t, fn, false, forward, "/AutomatorDocument.icns", "rdoc", 9, 13,
				scoreMatch*4+bonusCamel123+bonusConsecutive*2)
			assertMatch(t, fn, false, forward, "/man1/zshcompctl.1", "zshc", 6, 10,
				scoreMatch*4+bonusBoundary*bonusFirstCharMultiplier+bonusBoundary*3)
			assertMatch(t, fn, false, forward, "/.oh-my-zsh/cache", "zshc", 8, 13,
				scoreMatch*4+bonusBoundary*bonusFirstCharMultiplier+bonusBoundary*3+scoreGapStart)
			assertMatch(t, fn, false, forward, "ab0123 456", "12356", 3, 10,
				scoreMatch*5+bonusConsecutive*3+scoreGapStart+scoreGapExtention)
			assertMatch(t, fn, false, forward, "abc123 456", "12356", 3, 10,
				scoreMatch*5+bonusCamel123*bonusFirstCharMultiplier+bonusCamel123*2+bonusConsecutive+scoreGapStart+scoreGapExtention)
			assertMatch(t, fn, false, forward, "foo/bar/baz", "fbb", 0, 9,
				scoreMatch*3+bonusBoundary*bonusFirstCharMultiplier+
					bonusBoundary*2+2*scoreGapStart+4*scoreGapExtention)
			assertMatch(t, fn, false, forward, "fooBarBaz", "fbb", 0, 7,
				scoreMatch*3+bonusBoundary*bonusFirstCharMultiplier+
					bonusCamel123*2+2*scoreGapStart+2*scoreGapExtention)
			assertMatch(t, fn, false, forward, "foo barbaz", "fbb", 0, 8,
				scoreMatch*3+bonusBoundary*bonusFirstCharMultiplier+bonusBoundary+
					scoreGapStart*2+scoreGapExtention*3)
			assertMatch(t, fn, false, forward, "fooBar Baz", "foob", 0, 4,
				scoreMatch*4+bonusBoundary*bonusFirstCharMultiplier+bonusBoundary*3)
			assertMatch(t, fn, false, forward, "xFoo-Bar Baz", "foo-b", 1, 6,
				scoreMatch*5+bonusCamel123*bonusFirstCharMultiplier+bonusCamel123*2+
					bonusNonWord+bonusBoundary)

			assertMatch(t, fn, true, forward, "fooBarbaz", "oBz", 2, 9,
				scoreMatch*3+bonusCamel123+scoreGapStart+scoreGapExtention*3)
			assertMatch(t, fn, true, forward, "Foo/Bar/Baz", "FBB", 0, 9,
				scoreMatch*3+bonusBoundary*(bonusFirstCharMultiplier+2)+
					scoreGapStart*2+scoreGapExtention*4)
			assertMatch(t, fn, true, forward, "FooBarBaz", "FBB", 0, 7,
				scoreMatch*3+bonusBoundary*bonusFirstCharMultiplier+bonusCamel123*2+
					scoreGapStart*2+scoreGapExtention*2)
			assertMatch(t, fn, true, forward, "FooBar Baz", "FooB", 0, 4,
				scoreMatch*4+bonusBoundary*bonusFirstCharMultiplier+bonusBoundary*2+
					util.Max(bonusCamel123, bonusBoundary))

			// Consecutive bonus updated
			assertMatch(t, fn, true, forward, "foo-bar", "o-ba", 2, 6,
				scoreMatch*4+bonusBoundary*3)

			// Non-match
			assertMatch(t, fn, true, forward, "fooBarbaz", "oBZ", -1, -1, 0)
			assertMatch(t, fn, true, forward, "Foo Bar Baz", "fbb", -1, -1, 0)
			assertMatch(t, fn, true, forward, "fooBarbaz", "fooBarbazz", -1, -1, 0)
		}
	}
}

func (t *Terminal) constrain() {
	count := t.merger.Length()
	height := t.maxItems()
	diffpos := t.cy - t.offset

	t.cy = util.Constrain(t.cy, 0, count-1)

	if t.cy > t.offset+(height-1) {
		// Ceil
		t.offset = t.cy - (height - 1)
	} else if t.offset > t.cy {
		// Floor
		t.offset = t.cy
	}

	// Adjustment
	if count-t.offset < height {
		t.offset = util.Max(0, count-height)
		t.cy = util.Constrain(t.offset+diffpos, 0, count-1)
	}
	t.offset = util.Max(0, t.offset)
}

func buildResult(item *Item, offsets []Offset, score int, trimLen int) *Result {
	if len(offsets) > 1 {
		sort.Sort(ByOrder(offsets))
	}

	result := Result{item: item, rank: rank{index: item.index}}
	numChars := item.text.Length()
	minBegin := math.MaxUint16
	maxEnd := 0
	validOffsetFound := false
	for _, offset := range offsets {
		b, e := int(offset[0]), int(offset[1])
		if b < e {
			minBegin = util.Min(b, minBegin)
			maxEnd = util.Max(e, maxEnd)
			validOffsetFound = true
		}
	}

	for idx, criterion := range sortCriteria {
		val := uint16(math.MaxUint16)
		switch criterion {
		case byScore:
			// Higher is better
			val = math.MaxUint16 - util.AsUint16(score)
		case byLength:
			// If offsets is empty, trimLen will be 0, but we don't care
			val = util.AsUint16(trimLen)
		case byBegin, byEnd:
			if validOffsetFound {
				whitePrefixLen := 0
				for idx := 0; idx < numChars; idx++ {
					r := item.text.Get(idx)
					whitePrefixLen = idx
					if idx == minBegin || !unicode.IsSpace(r) {
						break
					}
				}
				if criterion == byBegin {
					val = util.AsUint16(minBegin - whitePrefixLen)
				} else {
					val = util.AsUint16(math.MaxUint16 - math.MaxUint16*(maxEnd-whitePrefixLen)/trimLen)
				}
			}
		}
		result.rank.points[idx] = val
	}

	return &result
}

func wrapLine(input string, prefixLength int, max int, tabstop int) []wrappedLine {
	lines := []wrappedLine{}
	width := 0
	line := ""
	for _, r := range input {
		w := util.Max(util.RuneWidth(r, prefixLength+width, 8), 1)
		width += w
		str := string(r)
		if r == '\t' {
			str = repeat(" ", w)
		}
		if prefixLength+width <= max {
			line += str
		} else {
			lines = append(lines, wrappedLine{string(line), width - w})
			line = str
			prefixLength = 0
			width = util.RuneWidth(r, prefixLength, 8)
		}
	}
	lines = append(lines, wrappedLine{string(line), width})
	return lines
}

func (t *Terminal) printHighlighted(result *Result, attr tui.Attr, col1 tui.ColorPair, col2 tui.ColorPair, current bool) {
	item := result.item

	// Overflow
	text := make([]rune, item.text.Length())
	copy(text, item.text.ToRunes())
	matchOffsets := []Offset{}
	var pos *[]int
	if t.merger.pattern != nil {
		_, matchOffsets, pos = t.merger.pattern.MatchItem(item, true, t.slab)
	}
	charOffsets := matchOffsets
	if pos != nil {
		charOffsets = make([]Offset, len(*pos))
		for idx, p := range *pos {
			offset := Offset{int32(p), int32(p + 1)}
			charOffsets[idx] = offset
		}
		sort.Sort(ByOrder(charOffsets))
	}
	var maxe int
	for _, offset := range charOffsets {
		maxe = util.Max(maxe, int(offset[1]))
	}

	offsets := result.colorOffsets(charOffsets, t.theme, col2, attr, current)
	maxWidth := t.window.Width - 3
	maxe = util.Constrain(maxe+util.Min(maxWidth/2-2, t.hscrollOff), 0, len(text))
	if overflow(text, maxWidth) {
		if t.hscroll {
			// Stri..
			if !overflow(text[:maxe], maxWidth-2) {
				text, _ = trimRight(text, maxWidth-2)
				text = append(text, []rune("..")...)
			} else {
				// Stri..
				if overflow(text[maxe:], 2) {
					text = append(text[:maxe], []rune("..")...)
				}
				// ..ri..
				var diff int32
				text, diff = trimLeft(text, maxWidth-2)

				// Transform offsets
				for idx, offset := range offsets {
					b, e := offset.offset[0], offset.offset[1]
					b += 2 - diff
					e += 2 - diff
					b = util.Max32(b, 2)
					offsets[idx].offset[0] = b
					offsets[idx].offset[1] = util.Max32(b, e)
				}
				text = append([]rune(".."), text...)
			}
		} else {
			text, _ = trimRight(text, maxWidth-2)
			text = append(text, []rune("..")...)

			for idx, offset := range offsets {
				offsets[idx].offset[0] = util.Min32(offset.offset[0], int32(maxWidth-2))
				offsets[idx].offset[1] = util.Min32(offset.offset[1], int32(maxWidth))
			}
		}
	}

	var index int32
	var substr string
	var prefixWidth int
	maxOffset := int32(len(text))
	for _, offset := range offsets {
		b := util.Constrain32(offset.offset[0], index, maxOffset)
		e := util.Constrain32(offset.offset[1], index, maxOffset)

		substr, prefixWidth = processTabs(text[index:b], prefixWidth)
		t.window.CPrint(col1, attr, substr)

		if b < e {
			substr, prefixWidth = processTabs(text[b:e], prefixWidth)
			t.window.CPrint(offset.color, offset.attr, substr)
		}

		index = e
		if index >= maxOffset {
			break
		}
	}
	if index < maxOffset {
		substr, _ = processTabs(text[index:], prefixWidth)
		t.window.CPrint(col1, attr, substr)
	}
}

// NewTerminal returns new Terminal object
func NewTerminal(opts *Options, eventBox *util.EventBox) *Terminal {
	input := []rune(opts.Query)
	var header []string
	if opts.Reverse {
		header = opts.Header
	} else {
		header = reverseStringArray(opts.Header)
	}
	var delay time.Duration
	if opts.Tac {
		delay = initialDelayTac
	} else {
		delay = initialDelay
	}
	var previewBox *util.EventBox
	if len(opts.Preview.command) > 0 {
		previewBox = util.NewEventBox()
	}
	strongAttr := tui.Bold
	if !opts.Bold {
		strongAttr = tui.AttrRegular
	}
	var renderer tui.Renderer
	if opts.Height.size > 0 {
		maxHeightFunc := func(termHeight int) int {
			var maxHeight int
			if opts.Height.percent {
				maxHeight = util.Min(termHeight,
					util.Max(int(opts.Height.size*float64(termHeight)/100.0), opts.MinHeight))
			} else {
				maxHeight = util.Min(termHeight, int(opts.Height.size))
			}
			if opts.InlineInfo {
				return util.Max(maxHeight, minHeight-1)
			}
			return util.Max(maxHeight, minHeight)
		}
		renderer = tui.NewLightRenderer(opts.Theme, opts.Black, opts.Mouse, opts.Tabstop, maxHeightFunc)
	} else {
		renderer = tui.NewFullscreenRenderer(opts.Theme, opts.Black, opts.Mouse)
	}
	wordRubout := "[^[:alnum:]][[:alnum:]]"
	wordNext := "[[:alnum:]][^[:alnum:]]|(.$)"
	if opts.FileWord {
		sep := regexp.QuoteMeta(string(os.PathSeparator))
		wordRubout = fmt.Sprintf("%s[^%s]", sep, sep)
		wordNext = fmt.Sprintf("[^%s]%s|(.$)", sep, sep)
	}
	return &Terminal{
		initDelay:  delay,
		inlineInfo: opts.InlineInfo,
		prompt:     opts.Prompt,
		reverse:    opts.Reverse,
		hscroll:    opts.Hscroll,
		hscrollOff: opts.HscrollOff,
		wordRubout: wordRubout,
		wordNext:   wordNext,
		cx:         len(input),
		cy:         0,
		offset:     0,
		yanked:     []rune{},
		input:      input,
		multi:      opts.Multi,
		sort:       opts.Sort > 0,
		toggleSort: opts.ToggleSort,
		delimiter:  opts.Delimiter,
		expect:     opts.Expect,
		keymap:     opts.Keymap,
		execmap:    opts.Execmap,
		pressed:    "",
		printQuery: opts.PrintQuery,
		history:    opts.History,
		margin:     opts.Margin,
		strong:     strongAttr,
		cycle:      opts.Cycle,
		header:     header,
		header0:    header,
		ansi:       opts.Ansi,
		tabstop:    opts.Tabstop,
		reading:    true,
		jumping:    jumpDisabled,
		jumpLabels: opts.JumpLabels,
		printer:    opts.Printer,
		merger:     EmptyMerger,
		selected:   make(map[int32]selectedItem),
		reqBox:     util.NewEventBox(),
		preview:    opts.Preview,
		previewer:  previewer{"", 0, 0, previewBox != nil && !opts.Preview.hidden},
		previewBox: previewBox,
		eventBox:   eventBox,
		mutex:      sync.Mutex{},
		suppress:   true,
		slab:       util.MakeSlab(slab16Size, slab32Size),
		theme:      opts.Theme,
		startChan:  make(chan bool, 1),
		tui:        renderer,
		initFunc:   func() { renderer.Init() }}
}

// Transform is used to transform the input when --with-nth option is given
func Transform(tokens []Token, withNth []Range) *Transformed {
	transTokens := make([]Token, len(withNth))
	numTokens := len(tokens)
	whole := ""
	for idx, r := range withNth {
		part := ""
		minIdx := 0
		if r.begin == r.end {
			idx := r.begin
			if idx == rangeEllipsis {
				part += joinTokens(tokens)
			} else {
				if idx < 0 {
					idx += numTokens + 1
				}
				if idx >= 1 && idx <= numTokens {
					minIdx = idx - 1
					part += *tokens[idx-1].text
				}
			}
		} else {
			var begin, end int
			if r.begin == rangeEllipsis { // ..N
				begin, end = 1, r.end
				if end < 0 {
					end += numTokens + 1
				}
			} else if r.end == rangeEllipsis { // N..
				begin, end = r.begin, numTokens
				if begin < 0 {
					begin += numTokens + 1
				}
			} else {
				begin, end = r.begin, r.end
				if begin < 0 {
					begin += numTokens + 1
				}
				if end < 0 {
					end += numTokens + 1
				}
			}
			minIdx = util.Max(0, begin-1)
			for idx := begin; idx <= end; idx++ {
				if idx >= 1 && idx <= numTokens {
					part += *tokens[idx-1].text
				}
			}
		}
		whole += part
		var prefixLength int
		if minIdx < numTokens {
			prefixLength = tokens[minIdx].prefixLength
		} else {
			prefixLength = 0
		}
		transTokens[idx] = Token{&part, prefixLength}
	}
	return &Transformed{
		whole: &whole,
		parts: transTokens}
}

// Transform is used to transform the input when --with-nth option is given
func Transform(tokens []Token, withNth []Range) []Token {
	transTokens := make([]Token, len(withNth))
	numTokens := len(tokens)
	for idx, r := range withNth {
		parts := []*util.Chars{}
		minIdx := 0
		if r.begin == r.end {
			idx := r.begin
			if idx == rangeEllipsis {
				chars := util.RunesToChars(joinTokens(tokens))
				parts = append(parts, &chars)
			} else {
				if idx < 0 {
					idx += numTokens + 1
				}
				if idx >= 1 && idx <= numTokens {
					minIdx = idx - 1
					parts = append(parts, tokens[idx-1].text)
				}
			}
		} else {
			var begin, end int
			if r.begin == rangeEllipsis { // ..N
				begin, end = 1, r.end
				if end < 0 {
					end += numTokens + 1
				}
			} else if r.end == rangeEllipsis { // N..
				begin, end = r.begin, numTokens
				if begin < 0 {
					begin += numTokens + 1
				}
			} else {
				begin, end = r.begin, r.end
				if begin < 0 {
					begin += numTokens + 1
				}
				if end < 0 {
					end += numTokens + 1
				}
			}
			minIdx = util.Max(0, begin-1)
			for idx := begin; idx <= end; idx++ {
				if idx >= 1 && idx <= numTokens {
					parts = append(parts, tokens[idx-1].text)
				}
			}
		}
		// Merge multiple parts
		var merged util.Chars
		switch len(parts) {
		case 0:
			merged = util.RunesToChars([]rune{})
		case 1:
			merged = *parts[0]
		default:
			runes := []rune{}
			for _, part := range parts {
				runes = append(runes, part.ToRunes()...)
			}
			merged = util.RunesToChars(runes)
		}

		var prefixLength int32
		if minIdx < numTokens {
			prefixLength = tokens[minIdx].prefixLength
		} else {
			prefixLength = 0
		}
		transTokens[idx] = Token{&merged, prefixLength, int32(merged.TrimLength())}
	}
	return transTokens
}

func (t *Terminal) printHighlighted(item *Item, bold bool, col1 int, col2 int, current bool) {
	var maxe int
	for _, offset := range item.offsets {
		maxe = util.Max(maxe, int(offset[1]))
	}

	// Overflow
	text := make([]rune, len(item.text))
	copy(text, item.text)
	offsets := item.colorOffsets(col2, bold, current)
	maxWidth := C.MaxX() - 3 - t.marginInt[1] - t.marginInt[3]
	maxe = util.Constrain(maxe+util.Min(maxWidth/2-2, t.hscrollOff), 0, len(text))
	fullWidth := displayWidth(text)
	if fullWidth > maxWidth {
		if t.hscroll {
			// Stri..
			matchEndWidth := displayWidth(text[:maxe])
			if matchEndWidth <= maxWidth-2 {
				text, _ = trimRight(text, maxWidth-2)
				text = append(text, []rune("..")...)
			} else {
				// Stri..
				if matchEndWidth < fullWidth-2 {
					text = append(text[:maxe], []rune("..")...)
				}
				// ..ri..
				var diff int32
				text, diff = trimLeft(text, maxWidth-2)

				// Transform offsets
				for idx, offset := range offsets {
					b, e := offset.offset[0], offset.offset[1]
					b += 2 - diff
					e += 2 - diff
					b = util.Max32(b, 2)
					offsets[idx].offset[0] = b
					offsets[idx].offset[1] = util.Max32(b, e)
				}
				text = append([]rune(".."), text...)
			}
		} else {
			text, _ = trimRight(text, maxWidth-2)
			text = append(text, []rune("..")...)

			for idx, offset := range offsets {
				offsets[idx].offset[0] = util.Min32(offset.offset[0], int32(maxWidth-2))
				offsets[idx].offset[1] = util.Min32(offset.offset[1], int32(maxWidth))
			}
		}
	}

	var index int32
	var substr string
	var prefixWidth int
	maxOffset := int32(len(text))
	for _, offset := range offsets {
		b := util.Constrain32(offset.offset[0], index, maxOffset)
		e := util.Constrain32(offset.offset[1], index, maxOffset)

		substr, prefixWidth = processTabs(text[index:b], prefixWidth)
		C.CPrint(col1, bold, substr)

		if b < e {
			substr, prefixWidth = processTabs(text[b:e], prefixWidth)
			C.CPrint(offset.color, offset.bold, substr)
		}

		index = e
		if index >= maxOffset {
			break
		}
	}
	if index < maxOffset {
		substr, _ = processTabs(text[index:], prefixWidth)
		C.CPrint(col1, bold, substr)
	}
}