// Package unorm is a self-contained Unicode normalization implementation
// (UAX #15): NFC, NFD, NFKC, NFKD plus the is-normalized predicate, over
// tables generated from the pinned UCD version (gen/main.go) -- no
// golang.org/x/text dependency. Verified against the full official
// NormalizationTest.txt conformance suite.
package unorm

import (
	
	
	
)

// Form is a Unicode normalization form.
type Form uint8

const (
	NFC Form = iota
	NFD
	NFKC
	NFKD
)

// ParseForm resolves a form name (case-insensitive); ok is false for an
// unknown name.
func ( string) (Form, bool) {
	switch strings.ToUpper() {
	case "NFC":
		return NFC, true
	case "NFD":
		return NFD, true
	case "NFKC":
		return NFKC, true
	case "NFKD":
		return NFKD, true
	}
	return 0, false
}

// Hangul syllable composition constants (UAX #15 section 3.12).
const (
	hangulSBase  = 0xAC00
	hangulLBase  = 0x1100
	hangulVBase  = 0x1161
	hangulTBase  = 0x11A7
	hangulLCount = 19
	hangulVCount = 21
	hangulTCount = 28
	hangulNCount = hangulVCount * hangulTCount
	hangulSCount = hangulLCount * hangulNCount
)

// combiningClass is the canonical combining class of r (0 for the vast
// majority of runes).
func combiningClass( rune) uint8 {
	,  := 0, len(cccKey)
	for  <  {
		 := ( + ) / 2
		if cccKey[] <  {
			 =  + 1
		} else {
			 = 
		}
	}
	if  < len(cccKey) && cccKey[] ==  {
		return cccVal[]
	}
	return 0
}

// decompose looks r up in the requested full-decomposition table; nil
// when r decomposes to itself.
func decompose( rune,  bool) []rune {
	, ,  := canonKey[:], canonIdx[:], canonPool[:]
	if  {
		, ,  = compatKey[:], compatIdx[:], compatPool[:]
	}
	,  := 0, len()
	for  <  {
		 := ( + ) / 2
		if [] <  {
			 =  + 1
		} else {
			 = 
		}
	}
	if  < len() && [] ==  {
		 := []
		,  := >>8, &0xff
		return [ : +]
	}
	return nil
}

// composePair is the primary composite of (a, b), or 0 -- Hangul LV/LVT
// composition handled algorithmically, the rest by table lookup.
func composePair(,  rune) rune {
	if  >= hangulLBase &&  < hangulLBase+hangulLCount &&
		 >= hangulVBase &&  < hangulVBase+hangulVCount {
		return hangulSBase + ((-hangulLBase)*hangulVCount+(-hangulVBase))*hangulTCount
	}
	if  >= hangulSBase &&  < hangulSBase+hangulSCount && (-hangulSBase)%hangulTCount == 0 &&
		 > hangulTBase &&  < hangulTBase+hangulTCount {
		return  + ( - hangulTBase)
	}
	,  := 0, len(compFirst)
	for  <  {
		 := ( + ) / 2
		if compFirst[] <  || (compFirst[] ==  && compSecond[] < ) {
			 =  + 1
		} else {
			 = 
		}
	}
	if  < len(compFirst) && compFirst[] ==  && compSecond[] ==  {
		return compResult[]
	}
	return 0
}

// quickYes reports whether every rune of s is a QC-Yes starter for form
// -- such a string is already normalized and IsNormalized/Normalize can
// answer without allocating. ASCII scans byte-wise.
func quickYes( string,  Form) bool {
	var ,  []rune
	switch  {
	case NFC:
		,  = qcNFCLo[:], qcNFCHi[:]
	case NFD:
		,  = qcNFDLo[:], qcNFDHi[:]
	case NFKC:
		,  = qcNFKCLo[:], qcNFKCHi[:]
	default:
		,  = qcNFKDLo[:], qcNFKDHi[:]
	}
	for  := 0;  < len(); {
		 := []
		if  < utf8.RuneSelf {
			++
			continue
		}
		,  := utf8.DecodeRuneInString([:])
		 += 
		 := sort.Search(len(), func( int) bool { return [] >=  })
		if  < len() && [] <=  {
			return false
		}
	}
	return true
}

// appendDecomposed appends r's full decomposition for the form to dst,
// Hangul algorithmically (UAX #15 syllable arithmetic).
func appendDecomposed( []rune,  rune,  bool) []rune {
	if  >= hangulSBase &&  < hangulSBase+hangulSCount {
		 :=  - hangulSBase
		 = append(, hangulLBase+/hangulNCount, hangulVBase+(%hangulNCount)/hangulTCount)
		if  :=  % hangulTCount;  != 0 {
			 = append(, hangulTBase+)
		}
		return 
	}
	if  := decompose(, );  != nil {
		return append(, ...)
	}
	return append(, )
}

// canonicalOrder sorts every maximal run of nonzero-ccc runes stably by
// combining class (the canonical ordering algorithm).
func canonicalOrder( []rune) {
	for  := 0;  < len(); {
		if combiningClass([]) == 0 {
			++
			continue
		}
		 := 
		for  < len() && combiningClass([]) != 0 {
			++
		}
		sort.SliceStable([:], func(,  int) bool {
			return combiningClass([+]) < combiningClass([+])
		})
		 = 
	}
}

// compose runs the canonical composition algorithm in place over a
// canonically-ordered decomposition, returning the shortened slice.
func compose( []rune) []rune {
	if len() == 0 {
		return 
	}
	// out[last] is the most recent starter; blocked tracks the highest
	// combining class seen since it (UAX #15 D115 blocking).
	 := [:1]
	 := -1
	if combiningClass([0]) == 0 {
		 = 0
	}
	 := combiningClass([0])
	for ,  := range [1:] {
		 := combiningClass()
		if  >= 0 && ( == 0 ||  < ) {
			if  := composePair([], );  != 0 {
				[] = 
				continue
			}
		}
		 = append(, )
		if  == 0 {
			 = len() - 1
			 = 0
		} else {
			 = 
		}
	}
	return 
}

// Normalize returns s in the requested form, returning s itself when the
// quick-check scan proves it already normalized (the common case
// allocates nothing).
func ( string,  Form) string {
	if quickYes(, ) {
		return 
	}
	 :=  == NFKC ||  == NFKD
	 := make([]rune, 0, len()+8)
	for ,  := range  {
		 = appendDecomposed(, , )
	}
	canonicalOrder()
	if  == NFC ||  == NFKC {
		 = compose()
	}
	return string()
}

// IsNormalized reports whether s is in the requested form: the
// quick-check scan answers the common case without allocating, the rest
// normalize-and-compare.
func ( string,  Form) bool {
	if quickYes(, ) {
		return true
	}
	return Normalize(, ) == 
}