A crate that provides a gap-query optimized interval-tree
data-structure.
no_std is supported and should work with the default features.
There are three main operations available on this data-structure:
insertion, removal and gap-queries. Each of which are O(log(N) + K) where N is the total number of intervals in the tree and K
is the number of intervals required to be processed.
Here are visualizations of the three operations:
<sodipodi:namedview
id=“namedview1114”
pagecolor=“#888888”
bordercolor=“#000000”
borderopacity=“0.25”
inkscape:showpageshadow=“2”
inkscape:pageopacity=“0”
inkscape:pagecheckerboard=“true”
inkscape:deskcolor=“#d1d1d1”
inkscape:document-units=“mm”
showgrid=“true”
inkscape:zoom=“1.0973349”
inkscape:cx=“-26.883315”
inkscape:cy=“132.59398”
inkscape:window-width=“1920”
inkscape:window-height=“1080”
inkscape:window-x=“0”
inkscape:window-y=“0”
inkscape:window-maximized=“1”
inkscape:current-layer=“layer1”>
<inkscape:grid
type=“xygrid”
id=“grid1333”
originx=“-31.256108”
originy=“-136.56029” />
</sodipodi:namedview>
+ = {c} {a} {a,b} {b} {b} {a} {a,b} {a,b,c} {c} {b,c} {b,c}
<sodipodi:namedview
id=“namedview1462”
pagecolor=“#8c7c7c”
bordercolor=“#000000”
borderopacity=“0.25”
inkscape:showpageshadow=“2”
inkscape:pageopacity=“0”
inkscape:pagecheckerboard=“true”
inkscape:deskcolor=“#d1d1d1”
inkscape:document-units=“mm”
showgrid=“true”
inkscape:zoom=“23.4528”
inkscape:cx=“48.437714”
inkscape:cy=“118.64255”
inkscape:window-width=“1920”
inkscape:window-height=“1080”
inkscape:window-x=“0”
inkscape:window-y=“0”
inkscape:window-maximized=“1”
inkscape:current-layer=“layer1”>
<inkscape:grid
type=“xygrid”
id=“grid1636”
originx=“-41.358888”
originy=“-128.17935” />
</sodipodi:namedview>
- = {a} {a} {a,b} {b} {b} {b} {a} {a,b}
<sodipodi:namedview
id=“namedview1697”
pagecolor=“#8b8b8b”
bordercolor=“#000000”
borderopacity=“0.25”
inkscape:showpageshadow=“2”
inkscape:pageopacity=“0”
inkscape:pagecheckerboard=“true”
inkscape:deskcolor=“#d1d1d1”
inkscape:document-units=“mm”
showgrid=“true”
showborder=“true”
inkscape:zoom=“3.1037318”
inkscape:cx=“130.32698”
inkscape:cy=“65.727329”
inkscape:window-width=“1920”
inkscape:window-height=“1080”
inkscape:window-x=“0”
inkscape:window-y=“0”
inkscape:window-maximized=“1”
inkscape:current-layer=“layer1”>
<inkscape:grid
type=“xygrid”
id=“grid1699”
originx=“0”
originy=“0”
spacingy=“1”
spacingx=“1”
units=“mm”
visible=“true” />
</sodipodi:namedview>
= gap-query in {a} {b} {b} {a} {b} {a} {b} {b}