P1 SkipList Specification_ 2022 Fall_ Data Structures and Algorithms
8/29/22, 8:55 AM P1 Ski Li S eci ca i : 2022 Fall: Da a S c e a d Alg i hm
h :
ca a . .ed /c e /156039/ age / 1- ki li - eci ca i 1/5
P1 SkipList Specification
Many applications areas such as computer graphics, geographic information systems, and VLSI
design require the ability to store and query a collection of rectangles. In 2D, typical queries include
the ability to find all rectangles that cover a query point or query rectangle, and to report all
intersections from among the set of rectangles. Adding and removing rectangles from the collection
are also fundamental operations.
For this project, you will create a simple spatial database for handling inserting, deleting, and
performing queries on a collection of rectangles. The data structure used to store the collection will
e the Skip List (see the "Skip Lists" of the openDSA textbook for more information about Skip Lists).
The Skip List fills the same role as a Binary Search Tree in applications that need to insert, remove,
and search for data objects based on some search key such as a name. The Skip List is roughly as
complex as a BST to implement, but it generally gives better performance since its worst case
ehavior depends purely on chance, not on the order of insertion for the data. Thus, the Skip List
provides a good organization for answering non-spatial queries on the collection (in particular, fo
organizing the objects by name). However, as you will discover, it is difficult and inefficient for the
Skip List to accomplish spatial queries.
The program will be invoked from the command-line as:
%> a a Rec a e1 c a dF e
where: Rec a e1 is then name of the program. The file where you have your a () method must
e called Rec a e1. a a . c a dF e is the name of the command file to read. It is a text file.
Your program will read from the text file c a d- e a series of commands, with one command
per line. The program should terminate after reading the end of the file. The commands are free-
format in that any number of spaces may come before, between, or after the command name and its
parameters. All commands should generate the required output message. All h ld be
i en he anda d c n le. E e c mmand ha i ce ed h ld gene a e
me f me age indica e he he he c mmand a cce f l n .
8/29/22, 8:55 AM P1 Ski Li S eci ca i : 2022 Fall: Da a S c e a d Alg i hm
h :
ca a . .ed /c e /156039/ age / 1- ki li - eci ca i 2/5
The command file may contain any mix of the following additional commands. In the following
description, terms in are parameters to the command. The curly-
ace characters '{' and '}'
seen below will not actually be present. However, the output of several commands will include
parentheses.
Insert a rectangle named a e with upper left corner ( , ) , width and height . It is
permissible for two or more rectangles to have the same name, and it is permissible for two or more
ectangles to have the same spatial dimensions and position. The name must begin with a letter, and
may contain letters, digits, and underscore characters. Names are case sensitive. A rectangle should
e rejected for insertion if its height or width are not greater than 0. All rectangles must fit within the
“world box” that is 1024 by 1024 units in size and has upper left corner at (0, 0). If a rectangle is all o
partly out of this world box, it should be rejected for insertion.
Command Format e a e
Command Example e e XXXXXXXXXX
Output on Success
Example
Rec a e e ed: ( e , 2, 5,
1, 5)
Output on Failure
Example
Rec a e e ec ed: ( e , 1020,
1020, 1, 7)
Return a “dump” of the Skip List. The Skip List dump should print out each Skip List node, from left to
ight. For each Skip List node, print that node’s value and the number of pointers that it contains.
Remember that the head node should always match the highest 'depth' your SkipList has created.
Command Format d
Command Example d
Output on Success
Example
S L d :
N de a de 3, Va e ( )
N de a de 3, Va e (a, 1, 0, 2, 4)
N de a de 2, Va e (b, 2, 0, 4, 8)
S L e : 2
8/29/22, 8:55 AM P1 Ski Li S eci ca i : 2022 Fall: Da a S c e a d Alg i hm
h :
ca a . .ed /c e /156039/ age / 1- ki li - eci ca i 3/5
Output on Success
Example2
S L d :
N de a de 1, Va e ( )
S L e : 0
Remove the rectangle with name a e . If two or more rectangle have the same name, then any one
such rectangle may be removed. If no rectangle exists with this name, it should be so reported.
Command Format e e a e
Command Example e e eRec
Output on Success
Example
Rec a e e ed: (a, 1, 0, 2,
4)
Output on Failure
Example
Rec a e e ed: (b)
Remove the rectangle with the specified dimensions. If two or more rectangles have the same
dimensions, then any one such rectangle may be removed. If no rectangle exists with these
dimensions, it should be so reported.
Command Format e e
Command
Example
e e XXXXXXXXXX
Output on Success
Example
Rec a e e ed: ( dYa, 2, 5,
1, 5)
Output on Failure
Example
Rec a e e ed: (2, 5, 1, 5)
Report all rectangles cu
ently in the database that intersect the query rectangle specified by the
e ea c parameters. For each such rectangle, list out its name and coordinates. A
e ea c command should be rejected if the height or width are not greater than 0. However, it is
8/29/22, 8:55 AM P1 Ski Li S eci ca i : 2022 Fall: Da a S c e a d Alg i hm
h :
ca a . .ed /c e /156039/ age / 1- ki li - eci ca i 4/5
(syntactically) acceptable for the regionsearch rectangle to be all or partly outside of the 1024 by
1024 world box.
Command Format e ea c
Command Example e ea c XXXXXXXXXX
Output on Success
Example
Rec a e e ec e (-900, 5, 500
0, 20):
(a, 45, 0, 10, 10)
(b, 400, 0, 100, 310)
Output on Success
Example2
Rec a e e ec e (2, 2, 1, 1):
Output on Failure
Example
Rec a e e ec ed: (-900, 5, 0, 50)
Report all pairs of rectangles within the database that intersect.
Command Format e ec
Command Example XXXXXXXXXXe ec
Output on Success
Example
I e ec a :
( dRec , 5, 3, 56, 56 dRec 3,
25, 3, 6, 6)
( dRec 3, 25, 3, 6, 6 dRec ,
5, 3, 56, 56)
Output on Failure
Example
I e ec a :
Return the information about the rectangles(s), if any, that have name a e .
Command Format ea c a e
Command Example XXXXXXXXXXea c a Rec
8/29/22, 8:55 AM P1 Ski Li S eci ca i : 2022 Fall: Da a S c e a d Alg i hm
h :
ca a . .ed /c e /156039/ age / 1- ki li - eci ca i 5/5
Output on Success
Example
Rec a e d:
( a Rec , 25, 3, 6, 6)
( a Rec , 111, 23, 16, 16)
Output on Failure
Example
Rec a e d: ( a Rec )
The rectangles will be maintained in a Skip List, sorted by the name. Use compareTo() to determine
the relative ordering of two names, and to determine if two names are identical. You are using the
Skip List to maintain your list of rectangles, but the Skip List is a general container class. Therefore, it
should not be implemented to know anything about rectangles.
Be aware that for this project, the Skip List is being asked to do two things. First, the Skip List will
handle searches on rectangle name, which acts as the record’s key value. The Skip List can do this
efficiently, as it will organize its records using the name as the search key. But you also need to do
several things that the Skip List cannot handle well, including removing by rectangle shape, doing a
egion search, and computing rectangle intersections. So you will need to add functions to the Skip
List to handle these actions, but these particular methods can go away in Project 2. You should
design in anticipation of adding a second data structure in Project 2 to handle these actions. Make
sure you handle these actions in a general way that does not require the Skip List to understand its
data type.
The biggest implementation difficulty that you are likely to encounter relates to traversing the Skip
List during the intersections command. The problem is that you need to make a complete traversal of
the Skip List for each rectangle in the Skip List (comparing it to all of the other rectangles). This leads
to the question of how do you remember where you are in the “outer loop” of the