1 // Copyright (C) The Lightning Authors. All rights reserved.
3 // SPDX-License-Identifier: AGPL-3.0
11 type interval struct {
16 type intervalTreeNode struct {
21 type intervalTree []intervalTreeNode
24 intervals map[string][]interval
25 itrees map[string]intervalTree
29 func (m *mask) Add(seqname string, start, end int) {
30 if m.intervals == nil {
31 m.intervals = map[string][]interval{}
33 m.intervals[seqname] = append(m.intervals[seqname], interval{start, end})
36 func (m *mask) Freeze() {
37 m.itrees = map[string]intervalTree{}
38 for seqname, intervals := range m.intervals {
39 m.itrees[seqname] = m.freeze(intervals)
44 func (m *mask) Check(seqname string, start, end int) bool {
46 panic("bug: (*mask)Check() called before Freeze()")
48 return m.itrees[seqname].check(0, interval{start, end})
51 func (m *mask) freeze(in []interval) intervalTree {
55 sort.Slice(in, func(i, j int) bool {
56 return in[i].start < in[j].start
59 for itreesize < len(in) {
60 itreesize = itreesize * 2
62 itree := make(intervalTree, itreesize)
63 itree.importSlice(0, in)
64 for i := len(in); i < itreesize; i++ {
70 func (itree intervalTree) check(root int, q interval) bool {
71 return root < len(itree) &&
72 itree[root].maxend >= q.start &&
73 ((itree[root].interval.start <= q.end && itree[root].interval.end >= q.start) ||
74 itree.check(root*2+1, q) ||
75 itree.check(root*2+2, q))
78 func (itree intervalTree) importSlice(root int, in []interval) int {
80 node := intervalTreeNode{interval: in[mid], maxend: in[mid].end}
82 end := itree.importSlice(root*2+1, in[0:mid])
83 if end > node.maxend {
88 end := itree.importSlice(root*2+2, in[mid+1:])
89 if end > node.maxend {