// Copyright 2015 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 rangetable

import (
	
)

// atEnd is used to mark a completed iteration.
const atEnd = unicode.MaxRune + 1

// Merge returns a new RangeTable that is the union of the given tables.
// It can also be used to compact user-created RangeTables. The entries in
// R16 and R32 for any given RangeTable should be sorted and non-overlapping.
//
// A lookup in the resulting table can be several times faster than using In
// directly on the ranges. Merge is an expensive operation, however, and only
// makes sense if one intends to use the result for more than a couple of
// hundred lookups.
func ( ...*unicode.RangeTable) *unicode.RangeTable {
	 := &unicode.RangeTable{}
	if len() == 0 {
		return 
	}

	 := tablesIter(make([]tableIndex, len()))

	for ,  := range  {
		[] = tableIndex{, 0, atEnd}
		if len(.R16) > 0 {
			[].next = rune(.R16[0].Lo)
		}
	}

	if  := .next16(); .Stride != 0 {
		for {
			 := .next16()
			if .Stride == 0 {
				.R16 = append(.R16, )
				break
			}
			 := .Lo - .Hi
			if (.Lo == .Hi ||  == .Stride) && (.Lo == .Hi ||  == .Stride) {
				// Fully merge the next range into the previous one.
				.Hi, .Stride = .Hi, 
				continue
			} else if  == .Stride {
				// Move the first element of r1 to r0. This may eliminate an
				// entry.
				.Hi = .Lo
				.Stride = 
				.Lo = .Lo + .Stride
				if .Lo > .Hi {
					continue
				}
			}
			.R16 = append(.R16, )
			 = 
		}
	}

	for ,  := range  {
		[] = tableIndex{, 0, atEnd}
		if len(.R32) > 0 {
			[].next = rune(.R32[0].Lo)
		}
	}

	if  := .next32(); .Stride != 0 {
		for {
			 := .next32()
			if .Stride == 0 {
				.R32 = append(.R32, )
				break
			}
			 := .Lo - .Hi
			if (.Lo == .Hi ||  == .Stride) && (.Lo == .Hi ||  == .Stride) {
				// Fully merge the next range into the previous one.
				.Hi, .Stride = .Hi, 
				continue
			} else if  == .Stride {
				// Move the first element of r1 to r0. This may eliminate an
				// entry.
				.Hi = .Lo
				.Lo = .Lo + .Stride
				if .Lo > .Hi {
					continue
				}
			}
			.R32 = append(.R32, )
			 = 
		}
	}

	for  := 0;  < len(.R16) && .R16[].Hi <= unicode.MaxLatin1; ++ {
		.LatinOffset =  + 1
	}

	return 
}

type tableIndex struct {
	t    *unicode.RangeTable
	p    uint32
	next rune
}

type tablesIter []tableIndex

// sortIter does an insertion sort using the next field of tableIndex. Insertion
// sort is a good sorting algorithm for this case.
func sortIter( []tableIndex) {
	for  := range  {
		for  := ;  > 0 && [-1].next > [].next; -- {
			[], [-1] = [-1], []
		}
	}
}

// next16 finds the ranged to be added to the table. If ranges overlap between
// multiple tables it clips the result to a non-overlapping range if the
// elements are not fully subsumed. It returns a zero range if there are no more
// ranges.
func ( tablesIter) () unicode.Range16 {
	sortIter()

	 := [0]
	if .next == atEnd {
		return unicode.Range16{}
	}
	 := .t.R16[.p]
	.Lo = uint16(.next)

	// We restrict the Hi of the current range if it overlaps with another range.
	for  := range  {
		 := []
		// Since our tableIndices are sorted by next, we can break if the there
		// is no overlap. The first value of a next range can always be merged
		// into the current one, so we can break in case of equality as well.
		if rune(.Hi) <= .next {
			break
		}
		 := .t.R16[.p]
		.Lo = uint16(.next)

		// Limit r0.Hi based on next ranges in list, but allow it to overlap
		// with ranges as long as it subsumes it.
		 := (.Lo - .Lo) % .Stride
		if  == 0 && (.Stride == .Stride || .Lo == .Hi) {
			// Overlap, take the min of the two Hi values: for simplicity's sake
			// we only process one range at a time.
			if .Hi > .Hi {
				.Hi = .Hi
			}
		} else {
			// Not a compatible stride. Set to the last possible value before
			// rn.Lo, but ensure there is at least one value.
			if  := .Lo - ; .Lo <=  {
				.Hi = 
			}
			break
		}
	}

	// Update the next values for each table.
	for  := range  {
		 := &[]
		if rune(.Hi) < .next {
			break
		}
		 := .t.R16[.p]
		 := rune(.Stride)
		.next +=  * (1 + ((rune(.Hi) - .next) / ))
		if rune(.Hi) < .next {
			if .p++; int(.p) == len(.t.R16) {
				.next = atEnd
			} else {
				.next = rune(.t.R16[.p].Lo)
			}
		}
	}

	if .Lo == .Hi {
		.Stride = 1
	}

	return 
}

// next32 finds the ranged to be added to the table. If ranges overlap between
// multiple tables it clips the result to a non-overlapping range if the
// elements are not fully subsumed. It returns a zero range if there are no more
// ranges.
func ( tablesIter) () unicode.Range32 {
	sortIter()

	 := [0]
	if .next == atEnd {
		return unicode.Range32{}
	}
	 := .t.R32[.p]
	.Lo = uint32(.next)

	// We restrict the Hi of the current range if it overlaps with another range.
	for  := range  {
		 := []
		// Since our tableIndices are sorted by next, we can break if the there
		// is no overlap. The first value of a next range can always be merged
		// into the current one, so we can break in case of equality as well.
		if rune(.Hi) <= .next {
			break
		}
		 := .t.R32[.p]
		.Lo = uint32(.next)

		// Limit r0.Hi based on next ranges in list, but allow it to overlap
		// with ranges as long as it subsumes it.
		 := (.Lo - .Lo) % .Stride
		if  == 0 && (.Stride == .Stride || .Lo == .Hi) {
			// Overlap, take the min of the two Hi values: for simplicity's sake
			// we only process one range at a time.
			if .Hi > .Hi {
				.Hi = .Hi
			}
		} else {
			// Not a compatible stride. Set to the last possible value before
			// rn.Lo, but ensure there is at least one value.
			if  := .Lo - ; .Lo <=  {
				.Hi = 
			}
			break
		}
	}

	// Update the next values for each table.
	for  := range  {
		 := &[]
		if rune(.Hi) < .next {
			break
		}
		 := .t.R32[.p]
		 := rune(.Stride)
		.next +=  * (1 + ((rune(.Hi) - .next) / ))
		if rune(.Hi) < .next {
			if .p++; int(.p) == len(.t.R32) {
				.next = atEnd
			} else {
				.next = rune(.t.R32[.p].Lo)
			}
		}
	}

	if .Lo == .Hi {
		.Stride = 1
	}

	return 
}