diff options
Diffstat (limited to 'vendor/golang.org/x/text/unicode/rangetable/merge.go')
| -rw-r--r-- | vendor/golang.org/x/text/unicode/rangetable/merge.go | 260 |
1 files changed, 0 insertions, 260 deletions
diff --git a/vendor/golang.org/x/text/unicode/rangetable/merge.go b/vendor/golang.org/x/text/unicode/rangetable/merge.go deleted file mode 100644 index ea2a080..0000000 --- a/vendor/golang.org/x/text/unicode/rangetable/merge.go +++ /dev/null @@ -1,260 +0,0 @@ -// 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 ( - "unicode" -) - -// 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 Merge(ranges ...*unicode.RangeTable) *unicode.RangeTable { - rt := &unicode.RangeTable{} - if len(ranges) == 0 { - return rt - } - - iter := tablesIter(make([]tableIndex, len(ranges))) - - for i, t := range ranges { - iter[i] = tableIndex{t, 0, atEnd} - if len(t.R16) > 0 { - iter[i].next = rune(t.R16[0].Lo) - } - } - - if r0 := iter.next16(); r0.Stride != 0 { - for { - r1 := iter.next16() - if r1.Stride == 0 { - rt.R16 = append(rt.R16, r0) - break - } - stride := r1.Lo - r0.Hi - if (r1.Lo == r1.Hi || stride == r1.Stride) && (r0.Lo == r0.Hi || stride == r0.Stride) { - // Fully merge the next range into the previous one. - r0.Hi, r0.Stride = r1.Hi, stride - continue - } else if stride == r0.Stride { - // Move the first element of r1 to r0. This may eliminate an - // entry. - r0.Hi = r1.Lo - r0.Stride = stride - r1.Lo = r1.Lo + r1.Stride - if r1.Lo > r1.Hi { - continue - } - } - rt.R16 = append(rt.R16, r0) - r0 = r1 - } - } - - for i, t := range ranges { - iter[i] = tableIndex{t, 0, atEnd} - if len(t.R32) > 0 { - iter[i].next = rune(t.R32[0].Lo) - } - } - - if r0 := iter.next32(); r0.Stride != 0 { - for { - r1 := iter.next32() - if r1.Stride == 0 { - rt.R32 = append(rt.R32, r0) - break - } - stride := r1.Lo - r0.Hi - if (r1.Lo == r1.Hi || stride == r1.Stride) && (r0.Lo == r0.Hi || stride == r0.Stride) { - // Fully merge the next range into the previous one. - r0.Hi, r0.Stride = r1.Hi, stride - continue - } else if stride == r0.Stride { - // Move the first element of r1 to r0. This may eliminate an - // entry. - r0.Hi = r1.Lo - r1.Lo = r1.Lo + r1.Stride - if r1.Lo > r1.Hi { - continue - } - } - rt.R32 = append(rt.R32, r0) - r0 = r1 - } - } - - for i := 0; i < len(rt.R16) && rt.R16[i].Hi <= unicode.MaxLatin1; i++ { - rt.LatinOffset = i + 1 - } - - return rt -} - -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(t []tableIndex) { - for i := range t { - for j := i; j > 0 && t[j-1].next > t[j].next; j-- { - t[j], t[j-1] = t[j-1], t[j] - } - } -} - -// 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 (ti tablesIter) next16() unicode.Range16 { - sortIter(ti) - - t0 := ti[0] - if t0.next == atEnd { - return unicode.Range16{} - } - r0 := t0.t.R16[t0.p] - r0.Lo = uint16(t0.next) - - // We restrict the Hi of the current range if it overlaps with another range. - for i := range ti { - tn := ti[i] - // 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(r0.Hi) <= tn.next { - break - } - rn := tn.t.R16[tn.p] - rn.Lo = uint16(tn.next) - - // Limit r0.Hi based on next ranges in list, but allow it to overlap - // with ranges as long as it subsumes it. - m := (rn.Lo - r0.Lo) % r0.Stride - if m == 0 && (rn.Stride == r0.Stride || rn.Lo == rn.Hi) { - // Overlap, take the min of the two Hi values: for simplicity's sake - // we only process one range at a time. - if r0.Hi > rn.Hi { - r0.Hi = rn.Hi - } - } else { - // Not a compatible stride. Set to the last possible value before - // rn.Lo, but ensure there is at least one value. - if x := rn.Lo - m; r0.Lo <= x { - r0.Hi = x - } - break - } - } - - // Update the next values for each table. - for i := range ti { - tn := &ti[i] - if rune(r0.Hi) < tn.next { - break - } - rn := tn.t.R16[tn.p] - stride := rune(rn.Stride) - tn.next += stride * (1 + ((rune(r0.Hi) - tn.next) / stride)) - if rune(rn.Hi) < tn.next { - if tn.p++; int(tn.p) == len(tn.t.R16) { - tn.next = atEnd - } else { - tn.next = rune(tn.t.R16[tn.p].Lo) - } - } - } - - if r0.Lo == r0.Hi { - r0.Stride = 1 - } - - return r0 -} - -// 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 (ti tablesIter) next32() unicode.Range32 { - sortIter(ti) - - t0 := ti[0] - if t0.next == atEnd { - return unicode.Range32{} - } - r0 := t0.t.R32[t0.p] - r0.Lo = uint32(t0.next) - - // We restrict the Hi of the current range if it overlaps with another range. - for i := range ti { - tn := ti[i] - // 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(r0.Hi) <= tn.next { - break - } - rn := tn.t.R32[tn.p] - rn.Lo = uint32(tn.next) - - // Limit r0.Hi based on next ranges in list, but allow it to overlap - // with ranges as long as it subsumes it. - m := (rn.Lo - r0.Lo) % r0.Stride - if m == 0 && (rn.Stride == r0.Stride || rn.Lo == rn.Hi) { - // Overlap, take the min of the two Hi values: for simplicity's sake - // we only process one range at a time. - if r0.Hi > rn.Hi { - r0.Hi = rn.Hi - } - } else { - // Not a compatible stride. Set to the last possible value before - // rn.Lo, but ensure there is at least one value. - if x := rn.Lo - m; r0.Lo <= x { - r0.Hi = x - } - break - } - } - - // Update the next values for each table. - for i := range ti { - tn := &ti[i] - if rune(r0.Hi) < tn.next { - break - } - rn := tn.t.R32[tn.p] - stride := rune(rn.Stride) - tn.next += stride * (1 + ((rune(r0.Hi) - tn.next) / stride)) - if rune(rn.Hi) < tn.next { - if tn.p++; int(tn.p) == len(tn.t.R32) { - tn.next = atEnd - } else { - tn.next = rune(tn.t.R32[tn.p].Lo) - } - } - } - - if r0.Lo == r0.Hi { - r0.Stride = 1 - } - - return r0 -} |