// Copyright (c) 2012-2016 The go-diff authors. All rights reserved.
// https://github.com/sergi/go-diff
// See the included LICENSE file for license details.
//
// go-diff is a Go implementation of Google's Diff, Match, and Patch library
// Original library is Copyright (c) 2006 Google Inc.
// http://code.google.com/p/google-diff-match-patch/

package diffmatchpatch

import (
	
)

// MatchMain locates the best instance of 'pattern' in 'text' near 'loc'.
// Returns -1 if no match found.
func ( *DiffMatchPatch) (,  string,  int) int {
	// Check for null inputs not needed since null can't be passed in C#.

	 = int(math.Max(0, math.Min(float64(), float64(len()))))
	if  ==  {
		// Shortcut (potentially not guaranteed by the algorithm)
		return 0
	} else if len() == 0 {
		// Nothing to match.
		return -1
	} else if +len() <= len() && [:+len()] ==  {
		// Perfect match at the perfect spot!  (Includes case of null pattern)
		return 
	}
	// Do a fuzzy compare.
	return .MatchBitap(, , )
}

// MatchBitap locates the best instance of 'pattern' in 'text' near 'loc' using the Bitap algorithm.
// Returns -1 if no match was found.
func ( *DiffMatchPatch) (,  string,  int) int {
	// Initialise the alphabet.
	 := .MatchAlphabet()

	// Highest score beyond which we give up.
	 := .MatchThreshold
	// Is there a nearby exact match? (speedup)
	 := indexOf(, , )
	if  != -1 {
		 = math.Min(.matchBitapScore(0, , ,
			), )
		// What about in the other direction? (speedup)
		 = lastIndexOf(, , +len())
		if  != -1 {
			 = math.Min(.matchBitapScore(0, , ,
				), )
		}
	}

	// Initialise the bit arrays.
	 := 1 << uint((len() - 1))
	 = -1

	var ,  int
	 := len() + len()
	 := []int{}
	for  := 0;  < len(); ++ {
		// Scan for the best match; each iteration allows for one more error. Run a binary search to determine how far from 'loc' we can stray at this error level.
		 = 0
		 = 
		for  <  {
			if .matchBitapScore(, +, , ) <=  {
				 = 
			} else {
				 = 
			}
			 = (-)/2 + 
		}
		// Use the result from this iteration as the maximum for the next.
		 = 
		 := int(math.Max(1, float64(-+1)))
		 := int(math.Min(float64(+), float64(len())) + float64(len()))

		 := make([]int, +2)
		[+1] = (1 << uint()) - 1

		for  := ;  >= ; -- {
			var  int
			if len() <= -1 {
				// Out of range.
				 = 0
			} else if ,  := [[-1]]; ! {
				 = 0
			} else {
				 = [[-1]]
			}

			if  == 0 {
				// First pass: exact match.
				[] = (([+1] << 1) | 1) & 
			} else {
				// Subsequent passes: fuzzy match.
				[] = (([+1]<<1)|1)& | ((([+1] | []) << 1) | 1) | [+1]
			}
			if ([] & ) != 0 {
				 := .matchBitapScore(, -1, , )
				// This match will almost certainly be better than any existing match.  But check anyway.
				if  <=  {
					// Told you so.
					 = 
					 =  - 1
					if  >  {
						// When passing loc, don't exceed our current distance from loc.
						 = int(math.Max(1, float64(2*-)))
					} else {
						// Already passed loc, downhill from here on in.
						break
					}
				}
			}
		}
		if .matchBitapScore(+1, , , ) >  {
			// No hope for a (better) match at greater error levels.
			break
		}
		 = 
	}
	return 
}

// matchBitapScore computes and returns the score for a match with e errors and x location.
func ( *DiffMatchPatch) (, ,  int,  string) float64 {
	 := float64() / float64(len())
	 := math.Abs(float64( - ))
	if .MatchDistance == 0 {
		// Dodge divide by zero error.
		if  == 0 {
			return 
		}

		return 1.0
	}
	return  + ( / float64(.MatchDistance))
}

// MatchAlphabet initialises the alphabet for the Bitap algorithm.
func ( *DiffMatchPatch) ( string) map[byte]int {
	 := map[byte]int{}
	 := []byte()
	for ,  := range  {
		,  := []
		if ! {
			[] = 0
		}
	}
	 := 0

	for ,  := range  {
		 := [] | int(uint(1)<<uint((len()--1)))
		[] = 
		++
	}
	return 
}