Insert
I/O Format
insert {name} {x} {y} {w} {h}
# valid insert
Rectangle inserted: ({name}, {x}, {y}, {w}, {h})
# invalid insert
Rectangle rejected: ({name}, {x}, {y}, {w}, {h})
Example Input
insert a 1 0 2 4
insert a0 1 0 2048 4
insert a_1 1 0 2 4
insert a2 -1 0 2 4
insert a 1 0 2 4
insert a4 1 0 -2 4
Example Output
Rectangle inserted: (a, 1, 0, 2, 4)
Rectangle rejected: (a0, 1, 0, 2048, 4)
Rectangle inserted: (a_1, 1, 0, 2, 4)
Rectangle rejected: (a2, -1, 0, 2, 4)
Rectangle inserted: (a, 1, 0, 2, 4)
Rectangle rejected: (a4, 1, 0, -2, 4)
remove
I/O Format
remove {name}
# name exist in skiplist
Rectangle removed: ({name}, {x}, {y}, {w}, {h})
# name does not exist in skiplist
Rectangle not found: ({name})
remove {x} {y} {w} {h}
# at least on rectangle with the dimensions exist in the skiplist
Rectangle removed: ({name}, {x}, {y}, {w}, {h})
# no rectangle with the dimensions exist in the skiplist
Rectangle not found: ({x}, {y}, {w}, {h})
# invalid rectangle
Rectangle rejected: ({x}, {y}, {w}, {h})
Example Input
insert a 1 0 2 4
insert a6 1 0 5 8
insert a2 20 30 12 84
insert a3 1 0 2 4
insert a4 1 0 5 8
insert a 2 3 2 4
remove a
remove 20 30 12 84
remove 20 30 12 84
remove a3
remove a
remove a
remove -1 20 1 30
Example Output
Rectangle inserted: (a, 1, 0, 2, 4)
Rectangle inserted: (a6, 1, 0, 5, 8)
Rectangle inserted: (a2, 20, 30, 12, 84)
Rectangle inserted: (a3, 1, 0, 2, 4)
Rectangle inserted: (a4, 1, 0, 5, 8)
Rectangle inserted: (a, 2, 3, 2, 4)
Rectangle removed: (a, 2, 3, 2, 4)
Rectangle removed: (a2, 20, 30, 12, 84)
Rectangle not found: (20, 30, 12, 84)
Rectangle removed: (a3, 1, 0, 2, 4)
Rectangle removed: (a, 1, 0, 2, 4)
Rectangle not found: (a)
Rectangle rejected: (-1, 20, 1, 30)
regionsearch
I/O Format
regionsearch {x} {y} {w} {h}
# valid region with n rectangles
# the list of rectangle does not have to be in any particular order
Rectangles intersecting region ({x}, {y}, {w}, {h}):
({name1}, {x1}, {y1}, {w1}, {h1})
...
({namen}, {xn}, {yn}, {wn}, {hn})
# valid region with 0 rectangles
Rectangles intersecting region ({x}, {y}, {w}, {h}):
# invalid region
Rectangle rejected: ({x}, {y}, {w}, {h})
Example Input
insert a 1 0 2 4
insert a6 1 0 5 8
insert a2 20 30 12 84
insert a3 1 0 2 4
insert a4 1 0 5 8
insert a 2 3 2 4
regionsearch 0 0 20 20
regionsearch 984 10 1024 1024
regionsearch 0 0 -20 -20
Example Output
Rectangle inserted: (a, 1, 0, 2, 4)
Rectangle inserted: (a6, 1, 0, 5, 8)
Rectangle inserted: (a2, 20, 30, 12, 84)
Rectangle inserted: (a3, 1, 0, 2, 4)
Rectangle inserted: (a4, 1, 0, 5, 8)
Rectangle inserted: (a, 2, 3, 2, 4)
Rectangles intersecting region (0, 0, 20, 20):
(a, 2, 3, 2, 4)
(a, 1, 0, 2, 4)
(a3, 1, 0, 2, 4)
(a4, 1, 0, 5, 8)
(a6, 1, 0, 5, 8)
Rectangles intersecting region (984, 10, 1024, 1024):
Rectangle rejected: (0, 0, -20, -20)
intersections
I/O Format
intersections
# when no intersection exists
Intersections pairs:
# when there are intersections
# note: you have to report both (a|b) and (b|a) pairs
# the list of intersections does not have to be in any particular order
Intersections pairs:
({name1}, {x1}, {y1}, {w1}, {h1}|{name2}, {x2}, {y2}, {w2}, {h2})
...
({namen}, {xn}, {yn}, {wn}, {h1}|{namen-1}, {xn-1}, {yn-1}, {wn-1}, {hn-1})
Example Input
intersections
insert a 1 0 2 4
insert a6 1 0 5 8
insert a2 20 30 12 84
insert a2 21 30 12 84
insert a3 1 0 2 4
insert a4 1 0 5 8
insert a 2 3 2 4
intersections
Example Output
Intersections pairs:
Rectangle inserted: (a, 1, 0, 2, 4)
Rectangle inserted: (a6, 1, 0, 5, 8)
Rectangle inserted: (a2, 20, 30, 12, 84)
Rectangle inserted: (a2, 21, 30, 12, 84)
Rectangle inserted: (a3, 1, 0, 2, 4)
Rectangle inserted: (a4, 1, 0, 5, 8)
Rectangle inserted: (a, 2, 3, 2, 4)
Intersections pairs:
(a, 2, 3, 2, 4 | a, 1, 0, 2, 4)
(a, 2, 3, 2, 4 | a3, 1, 0, 2, 4)
(a, 2, 3, 2, 4 | a4, 1, 0, 5, 8)
(a, 2, 3, 2, 4 | a6, 1, 0, 5, 8)
(a, 1, 0, 2, 4 | a, 2, 3, 2, 4)
(a, 1, 0, 2, 4 | a3, 1, 0, 2, 4)
(a, 1, 0, 2, 4 | a4, 1, 0, 5, 8)
(a, 1, 0, 2, 4 | a6, 1, 0, 5, 8)
(a2, 21, 30, 12, 84 | a2, 20, 30, 12, 84)
(a2, 20, 30, 12, 84 | a2, 21, 30, 12, 84)
(a3, 1, 0, 2, 4 | a, 2, 3, 2, 4)
(a3, 1, 0, 2, 4 | a, 1, 0, 2, 4)
(a3, 1, 0, 2, 4 | a4, 1, 0, 5, 8)
(a3, 1, 0, 2, 4 | a6, 1, 0, 5, 8)
(a4, 1, 0, 5, 8 | a, 2, 3, 2, 4)
(a4, 1, 0, 5, 8 | a, 1, 0, 2, 4)
(a4, 1, 0, 5, 8 | a3, 1, 0, 2, 4)
(a4, 1, 0, 5, 8 | a6, 1, 0, 5, 8)
(a6, 1, 0, 5, 8 | a, 2, 3, 2, 4)
(a6, 1, 0, 5, 8 | a, 1, 0, 2, 4)
(a6, 1, 0, 5, 8 | a3, 1, 0, 2, 4)
(a6, 1, 0, 5, 8 | a4, 1, 0, 5, 8)
search
I/O Format
search {name}
# rectangles with name exist
# the list of rectangles does not have to be in any particular order
Rectangles found:
({name}, {x1}, {y1}, {w1}, {h1})
...
({name}, {xn}, {yn}, {wn}, {hn})
# rectangle with name does not exist
Rectangle not found: {name}
Example Input
insert a 1 0 2 4
insert a6 1 0 5 8
insert a2 20 30 12 84
insert a2 21 30 12 84
insert a3 1 0 2 4
insert a4 1 0 5 8
insert a 2 3 2 4
search ax
search a2
Example Output
Rectangle inserted: (a, 1, 0, 2, 4)
Rectangle inserted: (a6, 1, 0, 5, 8)
Rectangle inserted: (a2, 20, 30, 12, 84)
Rectangle inserted: (a2, 21, 30, 12, 84)
Rectangle inserted: (a3, 1, 0, 2, 4)
Rectangle inserted: (a4, 1, 0, 5, 8)
Rectangle inserted: (a, 2, 3, 2, 4)
Rectangle not found: ax
Rectangles found:
(a2, 21, 30, 12, 84)
(a2, 20, 30, 12, 84)
dump
I/O Format
dump
# Empty SkipList
SkipList dump:
Node has depth 1, Value (null)
SkipList size is: 0
# SkipList with n rectangles
# this output has to be ordered
SkipList dump:
Node has depth {dx}, Value (null)
Node has depth {d1}, Value ({name1}, {x1}, {y1}, {w1}, {h1})
...
Node has depth {dn}, Value ({namen}, {xn}, {yn}, {wn}, {hn})
SkipList size is: {n}
Example Input
dump
insert a 1 0 2 4
insert a1 1 0 5 8
insert a 1 0 2 4
dump
Example Output
SkipList dump:
Node has depth 1, Value (null)
SkipList size is: 0
Rectangle inserted: (a, 1, 0, 2, 4)
Rectangle inserted: (a1, 1, 0, 5, 8)
Rectangle inserted: (a, 1, 0, 2, 4)
SkipList dump:
Node has depth 2, Value (null)
Node has depth 1, Value (a, 1, 0, 2, 4)
Node has depth 1, Value (a, 1, 0, 2, 4)
Node has depth 2, Value (a1, 1, 0, 5, 8)
SkipList size is: 3