// Copyright 2011 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package strings

import (
	
	
)

// Replacer replaces a list of strings with replacements.
// It is safe for concurrent use by multiple goroutines.
type Replacer struct {
	once   sync.Once // guards buildOnce method
	r      replacer
	oldnew []string
}

// replacer is the interface that a replacement algorithm needs to implement.
type replacer interface {
	Replace(s string) string
	WriteString(w io.Writer, s string) (n int, err error)
}

// NewReplacer returns a new Replacer from a list of old, new string
// pairs. Replacements are performed in the order they appear in the
// target string, without overlapping matches. The old string
// comparisons are done in argument order.
//
// NewReplacer panics if given an odd number of arguments.
func ( ...string) *Replacer {
	if len()%2 == 1 {
		panic("strings.NewReplacer: odd argument count")
	}
	return &Replacer{oldnew: append([]string(nil), ...)}
}

func ( *Replacer) () {
	.r = .build()
	.oldnew = nil
}

func ( *Replacer) () replacer {
	 := .oldnew
	if len() == 2 && len([0]) > 1 {
		return makeSingleStringReplacer([0], [1])
	}

	 := true
	for  := 0;  < len();  += 2 {
		if len([]) != 1 {
			return makeGenericReplacer()
		}
		if len([+1]) != 1 {
			 = false
		}
	}

	if  {
		 := byteReplacer{}
		for  := range  {
			[] = byte()
		}
		// The first occurrence of old->new map takes precedence
		// over the others with the same old string.
		for  := len() - 2;  >= 0;  -= 2 {
			 := [][0]
			 := [+1][0]
			[] = 
		}
		return &
	}

	 := byteStringReplacer{toReplace: make([]string, 0, len()/2)}
	// The first occurrence of old->new map takes precedence
	// over the others with the same old string.
	for  := len() - 2;  >= 0;  -= 2 {
		 := [][0]
		 := [+1]
		// To avoid counting repetitions multiple times.
		if .replacements[] == nil {
			// We need to use string([]byte{o}) instead of string(o),
			// to avoid utf8 encoding of o.
			// E. g. byte(150) produces string of length 2.
			.toReplace = append(.toReplace, string([]byte{}))
		}
		.replacements[] = []byte()

	}
	return &
}

// Replace returns a copy of s with all replacements performed.
func ( *Replacer) ( string) string {
	.once.Do(.buildOnce)
	return .r.Replace()
}

// WriteString writes s to w with all replacements performed.
func ( *Replacer) ( io.Writer,  string) ( int,  error) {
	.once.Do(.buildOnce)
	return .r.WriteString(, )
}

// trieNode is a node in a lookup trie for prioritized key/value pairs. Keys
// and values may be empty. For example, the trie containing keys "ax", "ay",
// "bcbc", "x" and "xy" could have eight nodes:
//
//  n0  -
//  n1  a-
//  n2  .x+
//  n3  .y+
//  n4  b-
//  n5  .cbc+
//  n6  x+
//  n7  .y+
//
// n0 is the root node, and its children are n1, n4 and n6; n1's children are
// n2 and n3; n4's child is n5; n6's child is n7. Nodes n0, n1 and n4 (marked
// with a trailing "-") are partial keys, and nodes n2, n3, n5, n6 and n7
// (marked with a trailing "+") are complete keys.
type trieNode struct {
	// value is the value of the trie node's key/value pair. It is empty if
	// this node is not a complete key.
	value string
	// priority is the priority (higher is more important) of the trie node's
	// key/value pair; keys are not necessarily matched shortest- or longest-
	// first. Priority is positive if this node is a complete key, and zero
	// otherwise. In the example above, positive/zero priorities are marked
	// with a trailing "+" or "-".
	priority int

	// A trie node may have zero, one or more child nodes:
	//  * if the remaining fields are zero, there are no children.
	//  * if prefix and next are non-zero, there is one child in next.
	//  * if table is non-zero, it defines all the children.
	//
	// Prefixes are preferred over tables when there is one child, but the
	// root node always uses a table for lookup efficiency.

	// prefix is the difference in keys between this trie node and the next.
	// In the example above, node n4 has prefix "cbc" and n4's next node is n5.
	// Node n5 has no children and so has zero prefix, next and table fields.
	prefix string
	next   *trieNode

	// table is a lookup table indexed by the next byte in the key, after
	// remapping that byte through genericReplacer.mapping to create a dense
	// index. In the example above, the keys only use 'a', 'b', 'c', 'x' and
	// 'y', which remap to 0, 1, 2, 3 and 4. All other bytes remap to 5, and
	// genericReplacer.tableSize will be 5. Node n0's table will be
	// []*trieNode{ 0:n1, 1:n4, 3:n6 }, where the 0, 1 and 3 are the remapped
	// 'a', 'b' and 'x'.
	table []*trieNode
}

func ( *trieNode) (,  string,  int,  *genericReplacer) {
	if  == "" {
		if .priority == 0 {
			.value = 
			.priority = 
		}
		return
	}

	if .prefix != "" {
		// Need to split the prefix among multiple nodes.
		var  int // length of the longest common prefix
		for ;  < len(.prefix) &&  < len(); ++ {
			if .prefix[] != [] {
				break
			}
		}
		if  == len(.prefix) {
			.next.([:], , , )
		} else if  == 0 {
			// First byte differs, start a new lookup table here. Looking up
			// what is currently t.prefix[0] will lead to prefixNode, and
			// looking up key[0] will lead to keyNode.
			var  *trieNode
			if len(.prefix) == 1 {
				 = .next
			} else {
				 = &trieNode{
					prefix: .prefix[1:],
					next:   .next,
				}
			}
			 := new(trieNode)
			.table = make([]*trieNode, .tableSize)
			.table[.mapping[.prefix[0]]] = 
			.table[.mapping[[0]]] = 
			.prefix = ""
			.next = nil
			.([1:], , , )
		} else {
			// Insert new node after the common section of the prefix.
			 := &trieNode{
				prefix: .prefix[:],
				next:   .next,
			}
			.prefix = .prefix[:]
			.next = 
			.([:], , , )
		}
	} else if .table != nil {
		// Insert into existing table.
		 := .mapping[[0]]
		if .table[] == nil {
			.table[] = new(trieNode)
		}
		.table[].([1:], , , )
	} else {
		.prefix = 
		.next = new(trieNode)
		.next.("", , , )
	}
}

func ( *genericReplacer) ( string,  bool) ( string,  int,  bool) {
	// Iterate down the trie to the end, and grab the value and keylen with
	// the highest priority.
	 := 0
	 := &.root
	 := 0
	for  != nil {
		if .priority >  && !( &&  == &.root) {
			 = .priority
			 = .value
			 = 
			 = true
		}

		if  == "" {
			break
		}
		if .table != nil {
			 := .mapping[[0]]
			if int() == .tableSize {
				break
			}
			 = .table[]
			 = [1:]
			++
		} else if .prefix != "" && HasPrefix(, .prefix) {
			 += len(.prefix)
			 = [len(.prefix):]
			 = .next
		} else {
			break
		}
	}
	return
}

// genericReplacer is the fully generic algorithm.
// It's used as a fallback when nothing faster can be used.
type genericReplacer struct {
	root trieNode
	// tableSize is the size of a trie node's lookup table. It is the number
	// of unique key bytes.
	tableSize int
	// mapping maps from key bytes to a dense index for trieNode.table.
	mapping [256]byte
}

func makeGenericReplacer( []string) *genericReplacer {
	 := new(genericReplacer)
	// Find each byte used, then assign them each an index.
	for  := 0;  < len();  += 2 {
		 := []
		for  := 0;  < len(); ++ {
			.mapping[[]] = 1
		}
	}

	for ,  := range .mapping {
		.tableSize += int()
	}

	var  byte
	for ,  := range .mapping {
		if  == 0 {
			.mapping[] = byte(.tableSize)
		} else {
			.mapping[] = 
			++
		}
	}
	// Ensure root node uses a lookup table (for performance).
	.root.table = make([]*trieNode, .tableSize)

	for  := 0;  < len();  += 2 {
		.root.add([], [+1], len()-, )
	}
	return 
}

type appendSliceWriter []byte

// Write writes to the buffer to satisfy io.Writer.
func ( *appendSliceWriter) ( []byte) (int, error) {
	* = append(*, ...)
	return len(), nil
}

// WriteString writes to the buffer without string->[]byte->string allocations.
func ( *appendSliceWriter) ( string) (int, error) {
	* = append(*, ...)
	return len(), nil
}

type stringWriter struct {
	w io.Writer
}

func ( stringWriter) ( string) (int, error) {
	return .w.Write([]byte())
}

func getStringWriter( io.Writer) io.StringWriter {
	,  := .(io.StringWriter)
	if ! {
		 = stringWriter{}
	}
	return 
}

func ( *genericReplacer) ( string) string {
	 := make(appendSliceWriter, 0, len())
	.WriteString(&, )
	return string()
}

func ( *genericReplacer) ( io.Writer,  string) ( int,  error) {
	 := getStringWriter()
	var ,  int
	var  bool
	for  := 0;  <= len(); {
		// Fast path: s[i] is not a prefix of any pattern.
		if  != len() && .root.priority == 0 {
			 := int(.mapping[[]])
			if  == .tableSize || .root.table[] == nil {
				++
				continue
			}
		}

		// Ignore the empty match iff the previous loop found the empty match.
		, ,  := .lookup([:], )
		 =  &&  == 0
		if  {
			,  = .WriteString([:])
			 += 
			if  != nil {
				return
			}
			,  = .WriteString()
			 += 
			if  != nil {
				return
			}
			 += 
			 = 
			continue
		}
		++
	}
	if  != len() {
		,  = .WriteString([:])
		 += 
	}
	return
}

// singleStringReplacer is the implementation that's used when there is only
// one string to replace (and that string has more than one byte).
type singleStringReplacer struct {
	finder *stringFinder
	// value is the new string that replaces that pattern when it's found.
	value string
}

func makeSingleStringReplacer( string,  string) *singleStringReplacer {
	return &singleStringReplacer{finder: makeStringFinder(), value: }
}

func ( *singleStringReplacer) ( string) string {
	var  []byte
	,  := 0, false
	for {
		 := .finder.next([:])
		if  == -1 {
			break
		}
		 = true
		 = append(, [:+]...)
		 = append(, .value...)
		 +=  + len(.finder.pattern)
	}
	if ! {
		return 
	}
	 = append(, [:]...)
	return string()
}

func ( *singleStringReplacer) ( io.Writer,  string) ( int,  error) {
	 := getStringWriter()
	var ,  int
	for {
		 := .finder.next([:])
		if  == -1 {
			break
		}
		,  = .WriteString([ : +])
		 += 
		if  != nil {
			return
		}
		,  = .WriteString(.value)
		 += 
		if  != nil {
			return
		}
		 +=  + len(.finder.pattern)
	}
	,  = .WriteString([:])
	 += 
	return
}

// byteReplacer is the implementation that's used when all the "old"
// and "new" values are single ASCII bytes.
// The array contains replacement bytes indexed by old byte.
type byteReplacer [256]byte

func ( *byteReplacer) ( string) string {
	var  []byte // lazily allocated
	for  := 0;  < len(); ++ {
		 := []
		if [] !=  {
			if  == nil {
				 = []byte()
			}
			[] = []
		}
	}
	if  == nil {
		return 
	}
	return string()
}

func ( *byteReplacer) ( io.Writer,  string) ( int,  error) {
	// TODO(bradfitz): use io.WriteString with slices of s, avoiding allocation.
	 := 32 << 10
	if len() <  {
		 = len()
	}
	 := make([]byte, )

	for len() > 0 {
		 := copy(, )
		 = [:]
		for ,  := range [:] {
			[] = []
		}
		,  := .Write([:])
		 += 
		if  != nil {
			return , 
		}
	}
	return , nil
}

// byteStringReplacer is the implementation that's used when all the
// "old" values are single ASCII bytes but the "new" values vary in size.
type byteStringReplacer struct {
	// replacements contains replacement byte slices indexed by old byte.
	// A nil []byte means that the old byte should not be replaced.
	replacements [256][]byte
	// toReplace keeps a list of bytes to replace. Depending on length of toReplace
	// and length of target string it may be faster to use Count, or a plain loop.
	// We store single byte as a string, because Count takes a string.
	toReplace []string
}

// countCutOff controls the ratio of a string length to a number of replacements
// at which (*byteStringReplacer).Replace switches algorithms.
// For strings with higher ration of length to replacements than that value,
// we call Count, for each replacement from toReplace.
// For strings, with a lower ratio we use simple loop, because of Count overhead.
// countCutOff is an empirically determined overhead multiplier.
// TODO(tocarip) revisit once we have register-based abi/mid-stack inlining.
const countCutOff = 8

func ( *byteStringReplacer) ( string) string {
	 := len()
	 := false
	// Is it faster to use Count?
	if len(.toReplace)*countCutOff <= len() {
		for ,  := range .toReplace {
			if  := Count(, );  != 0 {
				// The -1 is because we are replacing 1 byte with len(replacements[b]) bytes.
				 +=  * (len(.replacements[[0]]) - 1)
				 = true
			}

		}
	} else {
		for  := 0;  < len(); ++ {
			 := []
			if .replacements[] != nil {
				// See above for explanation of -1
				 += len(.replacements[]) - 1
				 = true
			}
		}
	}
	if ! {
		return 
	}
	 := make([]byte, )
	 := 0
	for  := 0;  < len(); ++ {
		 := []
		if .replacements[] != nil {
			 += copy([:], .replacements[])
		} else {
			[] = 
			++
		}
	}
	return string()
}

func ( *byteStringReplacer) ( io.Writer,  string) ( int,  error) {
	 := getStringWriter()
	 := 0
	for  := 0;  < len(); ++ {
		 := []
		if .replacements[] == nil {
			continue
		}
		if  !=  {
			,  := .WriteString([:])
			 += 
			if  != nil {
				return , 
			}
		}
		 =  + 1
		,  := .Write(.replacements[])
		 += 
		if  != nil {
			return , 
		}
	}
	if  != len() {
		var  int
		,  = .WriteString([:])
		 += 
	}
	return
}