barometer: update DMA's vendoring packages
[barometer.git] / src / dma / vendor / golang.org / x / text / unicode / rangetable / merge.go
1 // Copyright 2015 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package rangetable
6
7 import (
8         "unicode"
9 )
10
11 // atEnd is used to mark a completed iteration.
12 const atEnd = unicode.MaxRune + 1
13
14 // Merge returns a new RangeTable that is the union of the given tables.
15 // It can also be used to compact user-created RangeTables. The entries in
16 // R16 and R32 for any given RangeTable should be sorted and non-overlapping.
17 //
18 // A lookup in the resulting table can be several times faster than using In
19 // directly on the ranges. Merge is an expensive operation, however, and only
20 // makes sense if one intends to use the result for more than a couple of
21 // hundred lookups.
22 func Merge(ranges ...*unicode.RangeTable) *unicode.RangeTable {
23         rt := &unicode.RangeTable{}
24         if len(ranges) == 0 {
25                 return rt
26         }
27
28         iter := tablesIter(make([]tableIndex, len(ranges)))
29
30         for i, t := range ranges {
31                 iter[i] = tableIndex{t, 0, atEnd}
32                 if len(t.R16) > 0 {
33                         iter[i].next = rune(t.R16[0].Lo)
34                 }
35         }
36
37         if r0 := iter.next16(); r0.Stride != 0 {
38                 for {
39                         r1 := iter.next16()
40                         if r1.Stride == 0 {
41                                 rt.R16 = append(rt.R16, r0)
42                                 break
43                         }
44                         stride := r1.Lo - r0.Hi
45                         if (r1.Lo == r1.Hi || stride == r1.Stride) && (r0.Lo == r0.Hi || stride == r0.Stride) {
46                                 // Fully merge the next range into the previous one.
47                                 r0.Hi, r0.Stride = r1.Hi, stride
48                                 continue
49                         } else if stride == r0.Stride {
50                                 // Move the first element of r1 to r0. This may eliminate an
51                                 // entry.
52                                 r0.Hi = r1.Lo
53                                 r0.Stride = stride
54                                 r1.Lo = r1.Lo + r1.Stride
55                                 if r1.Lo > r1.Hi {
56                                         continue
57                                 }
58                         }
59                         rt.R16 = append(rt.R16, r0)
60                         r0 = r1
61                 }
62         }
63
64         for i, t := range ranges {
65                 iter[i] = tableIndex{t, 0, atEnd}
66                 if len(t.R32) > 0 {
67                         iter[i].next = rune(t.R32[0].Lo)
68                 }
69         }
70
71         if r0 := iter.next32(); r0.Stride != 0 {
72                 for {
73                         r1 := iter.next32()
74                         if r1.Stride == 0 {
75                                 rt.R32 = append(rt.R32, r0)
76                                 break
77                         }
78                         stride := r1.Lo - r0.Hi
79                         if (r1.Lo == r1.Hi || stride == r1.Stride) && (r0.Lo == r0.Hi || stride == r0.Stride) {
80                                 // Fully merge the next range into the previous one.
81                                 r0.Hi, r0.Stride = r1.Hi, stride
82                                 continue
83                         } else if stride == r0.Stride {
84                                 // Move the first element of r1 to r0. This may eliminate an
85                                 // entry.
86                                 r0.Hi = r1.Lo
87                                 r1.Lo = r1.Lo + r1.Stride
88                                 if r1.Lo > r1.Hi {
89                                         continue
90                                 }
91                         }
92                         rt.R32 = append(rt.R32, r0)
93                         r0 = r1
94                 }
95         }
96
97         for i := 0; i < len(rt.R16) && rt.R16[i].Hi <= unicode.MaxLatin1; i++ {
98                 rt.LatinOffset = i + 1
99         }
100
101         return rt
102 }
103
104 type tableIndex struct {
105         t    *unicode.RangeTable
106         p    uint32
107         next rune
108 }
109
110 type tablesIter []tableIndex
111
112 // sortIter does an insertion sort using the next field of tableIndex. Insertion
113 // sort is a good sorting algorithm for this case.
114 func sortIter(t []tableIndex) {
115         for i := range t {
116                 for j := i; j > 0 && t[j-1].next > t[j].next; j-- {
117                         t[j], t[j-1] = t[j-1], t[j]
118                 }
119         }
120 }
121
122 // next16 finds the ranged to be added to the table. If ranges overlap between
123 // multiple tables it clips the result to a non-overlapping range if the
124 // elements are not fully subsumed. It returns a zero range if there are no more
125 // ranges.
126 func (ti tablesIter) next16() unicode.Range16 {
127         sortIter(ti)
128
129         t0 := ti[0]
130         if t0.next == atEnd {
131                 return unicode.Range16{}
132         }
133         r0 := t0.t.R16[t0.p]
134         r0.Lo = uint16(t0.next)
135
136         // We restrict the Hi of the current range if it overlaps with another range.
137         for i := range ti {
138                 tn := ti[i]
139                 // Since our tableIndices are sorted by next, we can break if the there
140                 // is no overlap. The first value of a next range can always be merged
141                 // into the current one, so we can break in case of equality as well.
142                 if rune(r0.Hi) <= tn.next {
143                         break
144                 }
145                 rn := tn.t.R16[tn.p]
146                 rn.Lo = uint16(tn.next)
147
148                 // Limit r0.Hi based on next ranges in list, but allow it to overlap
149                 // with ranges as long as it subsumes it.
150                 m := (rn.Lo - r0.Lo) % r0.Stride
151                 if m == 0 && (rn.Stride == r0.Stride || rn.Lo == rn.Hi) {
152                         // Overlap, take the min of the two Hi values: for simplicity's sake
153                         // we only process one range at a time.
154                         if r0.Hi > rn.Hi {
155                                 r0.Hi = rn.Hi
156                         }
157                 } else {
158                         // Not a compatible stride. Set to the last possible value before
159                         // rn.Lo, but ensure there is at least one value.
160                         if x := rn.Lo - m; r0.Lo <= x {
161                                 r0.Hi = x
162                         }
163                         break
164                 }
165         }
166
167         // Update the next values for each table.
168         for i := range ti {
169                 tn := &ti[i]
170                 if rune(r0.Hi) < tn.next {
171                         break
172                 }
173                 rn := tn.t.R16[tn.p]
174                 stride := rune(rn.Stride)
175                 tn.next += stride * (1 + ((rune(r0.Hi) - tn.next) / stride))
176                 if rune(rn.Hi) < tn.next {
177                         if tn.p++; int(tn.p) == len(tn.t.R16) {
178                                 tn.next = atEnd
179                         } else {
180                                 tn.next = rune(tn.t.R16[tn.p].Lo)
181                         }
182                 }
183         }
184
185         if r0.Lo == r0.Hi {
186                 r0.Stride = 1
187         }
188
189         return r0
190 }
191
192 // next32 finds the ranged to be added to the table. If ranges overlap between
193 // multiple tables it clips the result to a non-overlapping range if the
194 // elements are not fully subsumed. It returns a zero range if there are no more
195 // ranges.
196 func (ti tablesIter) next32() unicode.Range32 {
197         sortIter(ti)
198
199         t0 := ti[0]
200         if t0.next == atEnd {
201                 return unicode.Range32{}
202         }
203         r0 := t0.t.R32[t0.p]
204         r0.Lo = uint32(t0.next)
205
206         // We restrict the Hi of the current range if it overlaps with another range.
207         for i := range ti {
208                 tn := ti[i]
209                 // Since our tableIndices are sorted by next, we can break if the there
210                 // is no overlap. The first value of a next range can always be merged
211                 // into the current one, so we can break in case of equality as well.
212                 if rune(r0.Hi) <= tn.next {
213                         break
214                 }
215                 rn := tn.t.R32[tn.p]
216                 rn.Lo = uint32(tn.next)
217
218                 // Limit r0.Hi based on next ranges in list, but allow it to overlap
219                 // with ranges as long as it subsumes it.
220                 m := (rn.Lo - r0.Lo) % r0.Stride
221                 if m == 0 && (rn.Stride == r0.Stride || rn.Lo == rn.Hi) {
222                         // Overlap, take the min of the two Hi values: for simplicity's sake
223                         // we only process one range at a time.
224                         if r0.Hi > rn.Hi {
225                                 r0.Hi = rn.Hi
226                         }
227                 } else {
228                         // Not a compatible stride. Set to the last possible value before
229                         // rn.Lo, but ensure there is at least one value.
230                         if x := rn.Lo - m; r0.Lo <= x {
231                                 r0.Hi = x
232                         }
233                         break
234                 }
235         }
236
237         // Update the next values for each table.
238         for i := range ti {
239                 tn := &ti[i]
240                 if rune(r0.Hi) < tn.next {
241                         break
242                 }
243                 rn := tn.t.R32[tn.p]
244                 stride := rune(rn.Stride)
245                 tn.next += stride * (1 + ((rune(r0.Hi) - tn.next) / stride))
246                 if rune(rn.Hi) < tn.next {
247                         if tn.p++; int(tn.p) == len(tn.t.R32) {
248                                 tn.next = atEnd
249                         } else {
250                                 tn.next = rune(tn.t.R32[tn.p].Lo)
251                         }
252                 }
253         }
254
255         if r0.Lo == r0.Hi {
256                 r0.Stride = 1
257         }
258
259         return r0
260 }