--- /dev/null
+// 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
+}
Code Review / barometer.git / blobdiff