mask.go

   1 // Copyright (C) The Lightning Authors. All rights reserved.
   2 //
   3 // SPDX-License-Identifier: AGPL-3.0
   4
   5 package lightning
   6
   7 import (
   8         "sort"
   9 )
  10
  11 type interval struct {
  12         start int
  13         end   int
  14 }
  15
  16 type intervalTreeNode struct {
  17         interval interval
  18         maxend   int
  19 }
  20
  21 type intervalTree []intervalTreeNode
  22
  23 type mask struct {
  24         intervals map[string][]interval
  25         itrees    map[string]intervalTree
  26         frozen    bool
  27 }
  28
  29 func (m *mask) Add(seqname string, start, end int) {
  30         if m.intervals == nil {
  31                 m.intervals = map[string][]interval{}
  32         }
  33         m.intervals[seqname] = append(m.intervals[seqname], interval{start, end})
  34 }
  35
  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)
  40         }
  41         m.frozen = true
  42 }
  43
  44 func (m *mask) Check(seqname string, start, end int) bool {
  45         if !m.frozen {
  46                 panic("bug: (*mask)Check() called before Freeze()")
  47         }
  48         return m.itrees[seqname].check(0, interval{start, end})
  49 }
  50
  51 func (m *mask) freeze(in []interval) intervalTree {
  52         if len(in) == 0 {
  53                 return nil
  54         }
  55         sort.Slice(in, func(i, j int) bool {
  56                 return in[i].start < in[j].start
  57         })
  58         itreesize := 1
  59         for itreesize < len(in) {
  60                 itreesize = itreesize * 2
  61         }
  62         itree := make(intervalTree, itreesize)
  63         itree.importSlice(0, in)
  64         for i := len(in); i < itreesize; i++ {
  65                 itree[i].maxend = -1
  66         }
  67         return itree
  68 }
  69
  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))
  76 }
  77
  78 func (itree intervalTree) importSlice(root int, in []interval) int {
  79         mid := len(in) / 2
  80         node := intervalTreeNode{interval: in[mid], maxend: in[mid].end}
  81         if mid > 0 {
  82                 end := itree.importSlice(root*2+1, in[0:mid])
  83                 if end > node.maxend {
  84                         node.maxend = end
  85                 }
  86         }
  87         if mid+1 < len(in) {
  88                 end := itree.importSlice(root*2+2, in[mid+1:])
  89                 if end > node.maxend {
  90                         node.maxend = end
  91                 }
  92         }
  93         itree[root] = node
  94         return node.maxend
  95 }