%intervalquery <filename> A B
You may assume that B >= A
intervalquery should report all intervals specified in the file
that totally contain the interval [A,B). You may assume an event '"AAA"
16 32' specified in the input file corresponds to the open interval [16,32).
Just to be consistent with the
sample input of part 4, I will keep the root of the segment tree as
[0,255). I am using the same input file as in part 4.
In addition to reporting the relevant intervals, intervalquery should
also dump the segment tree corresponding to the
input file in a file named segment_tree.txt
The input file input.txt ...
"AAA" 16 32
"BBB" 16 56
"CCC " 80 128
"DDD" 40 192
"EEE" 56 96
The segment_tree.txt file for all of the following queries:
Node 1
Parent: none
Low: 0
High: 255
Lines: nil
Node 2
Parent: 1
Low: 0
High: 128
Lines: nil
Node 4
Parent: 2
Low: 0
High: 64
Lines: nil
Node 8
Parent: 4
Low: 0
High: 32
Lines: nil
Node 17
Parent: 8
Low: 16
High: 32
Lines: AAA, BBB
Node 9
Parent: 4
Low: 32
High: 64
Lines: nil
Node 18
Parent: 9
Low: 32
High: 48
Lines: BBB
Node 37
Parent: 18
Low: 40
High: 48
Lines: DDD
Node 19
Parent: 9
Low: 48
High: 64
Lines: DDD
Node 38
Parent: 19
Low: 48
High: 56
Lines: BBB
Node 39
Parent: 19
Low: 56
High: 64
Lines: EEE
Node 5
Parent: 2
Low: 64
High: 128
Lines: DDD
Node 10
Parent: 5
Low: 64
High: 96
Lines: EEE
Node 21
Parent: 10
Low: 80
High: 96
Lines: CCC
Node 11
Parent: 5
Low: 96
High: 128
Lines: CCC
Node 3
Parent: 1
Low: 128
High: 255
Lines: nil
Node 6
Parent: 3
Low: 128
High: 192
Lines: DDD
Some sample queries with results:
%intervalquery input.txt 0 64
Looked at seg-tree nodes 0-255, 0-128, 0-64
Found nothing
%intervalquery input.txt 16 32
Looked at seg-tree nodes 0-255, 0-128, 0-64, 0-32, 16-32
Found
AAA 16 32
BBB 16 56
%intervalquery input.txt 60 190
Looked at seg-tree nodes 0-255, 0-128, 0-64, 32-64, 48-64, 56-64,
64-128, 128-255, 128-192
Found
DDD 40 192