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.frozen {
  31                 panic("bug: (*mask)Add() called after Freeze()")
  32         }
  33         if m.intervals == nil {
  34                 m.intervals = map[string][]interval{}
  35         }
  36         m.intervals[seqname] = append(m.intervals[seqname], interval{start, end})
  37 }
  38
  39 func (m *mask) Freeze() {
  40         m.itrees = map[string]intervalTree{}
  41         for seqname, intervals := range m.intervals {
  42                 m.itrees[seqname] = m.freeze(intervals)
  43         }
  44         m.frozen = true
  45 }
  46
  47 func (m *mask) Check(seqname string, start, end int) bool {
  48         if !m.frozen {
  49                 panic("bug: (*mask)Check() called before Freeze()")
  50         }
  51         return m.itrees[seqname].check(0, interval{start, end})
  52 }
  53
  54 func (m *mask) Len() int {
  55         if !m.frozen {
  56                 return 0
  57         }
  58         n := 0
  59         for _, intervals := range m.intervals {
  60                 n += len(intervals)
  61         }
  62         return n
  63 }
  64
  65 func (m *mask) freeze(in []interval) intervalTree {
  66         if len(in) == 0 {
  67                 return nil
  68         }
  69         sort.Slice(in, func(i, j int) bool {
  70                 return in[i].start < in[j].start
  71         })
  72         itreesize := 1
  73         for itreesize < len(in) {
  74                 itreesize = itreesize * 2
  75         }
  76         itree := make(intervalTree, itreesize)
  77         for i := 0; i < itreesize; i++ {
  78                 itree[i].maxend = -1
  79         }
  80         itree.importSlice(0, in)
  81         return itree
  82 }
  83
  84 func (itree intervalTree) check(root int, q interval) bool {
  85         return root < len(itree) &&
  86                 itree[root].maxend >= q.start &&
  87                 ((itree[root].interval.start <= q.end && itree[root].interval.end >= q.start) ||
  88                         itree.check(root*2+1, q) ||
  89                         itree.check(root*2+2, q))
  90 }
  91
  92 func (itree intervalTree) importSlice(root int, in []interval) int {
  93         mid := len(in) / 2
  94         node := intervalTreeNode{interval: in[mid], maxend: in[mid].end}
  95         if mid > 0 {
  96                 end := itree.importSlice(root*2+1, in[0:mid])
  97                 if end > node.maxend {
  98                         node.maxend = end
  99                 }
 100         }
 101         if mid+1 < len(in) {
 102                 end := itree.importSlice(root*2+2, in[mid+1:])
 103                 if end > node.maxend {
 104                         node.maxend = end
 105                 }
 106         }
 107         itree[root] = node
 108         return node.maxend
 109 }