Starting from:
$30
COP-Assignment 2 Skip list Solved
Build a skip list data structure to support the traversal, searching, addition, and deletion of integers from a skip list. This implementation will support building a skip list to support integers in the range of 0 to 5,000. The objective of this assignment requires the reading of an input file which contains commands and data to build a skip list containing integers using commands to insert, search, delete, and print a skip list.
2 Requirements
Read the input file formatted as follows. The input file will contain at least one command per line, either insert, delete, search, print, or quit. These are defined in detail below. And if appropriate, a second parameter may be required. The second parameter, if appropriate, will always be an integer for this assignment.
The commands are shown in the table below:
Command
Description
Parameter(s)
i
Insert
expects a space, followed by an integer
s
Search
expects a space, followed by an integer
d
Delete
expects a space, followed by an integer
p
Print
does not expect any additional data
Table 1: Input File Commands
2.1 Design Constraints
The input file(s) provided will have the following properties.
1. Each record in the input file will consist of a command, described above, appropriately followed by an integer.
2. There is not a maximum number of skip levels.
3. The test input integers will be within the range of 1 to 5,000.
4. There is no requirement for persistence. The data in the skip list does not need to be stored or archived on disk before the program exits.
2.2 Commands
2.2.1 Insert
The insert command uses the single character i as the command token. The command token will be followed by a single space, then an integer. This integer will then be inserted into the skip list. Note that a skip list requires that data be inserted into the skip list in ascending order.
1. Insertion requires that the specified integer will be inserted at the lowest level of the skip list and will be appropriately connected with the preceding integer and the next integer on the lowest level. For example inserting a 5 between a 3 and a 7 would result in the the 3 becoming the preceding integer and 7 becoming the next integer relative the newly inserted 5.
• In the event that the inserted integer would be placed at either the lowest or highest rank, that is at the lowest or highest possible value for the lowest skip list level make sure that new lowest or highest rank integer is appropriately connected or represented as connected to either −∞ or +∞.
2. Insertion of an integer that requires a probabilistic mechanism to decide if this integer will also be promoted to the next higher level regardless of whether it is the lowest or highest rank integer. The method discussed in lecture is flipping a fair coin. The flipping of a fair coin can be emulated using the Random object in Java to generate a “random number” then taking that number modulo 2 to generate a 1 or 0. The optional seeding of the Random number generator will be the second command line parameter specified by an upper or lower case R . In the event that the R parameter is not specified, seed the Random number generator with the integer 42. The promotion method used to generate the test cases used a 1 to represent heads and correspondingly a 0 to represent tails. Each flip of the coin that produces a heads causes that integer to be promoted and appropriately linked into the skip list. This process is terminated when a tails has been “flipped”.
3. In the event that the number to be inserted already exists in the skipList it can be ignored as there is no requirement for duplicate entries in this implementation.
Inputs i xx where xx is an integer between 1 and 5,000.
Outputs
N/A
2.2.2 Delete
The delete command uses the single character d as the command token. The command token will be followed by a single integer. In order to successfully delete an entry from the skip list, the integer must be found.
In the event that the integer cannot be found, the program will issue the error message xx integer not found - delete not successful, where xx is the specified integer. The program will recover gracefully to continue to accept commands.
Once the integer is found, it will be deleted from the lowest level, and any additional level(s) that integer had been promoted to upon insertion. Remember to appropriately connect the previous and next values across all levels that contained the deleted integer. (This command’s success can be verified by using the print command.)
Inputs d xx where xx is an integer between 1 and 5,000.
Outputs
Success xx deleted :where xx is the integer being deleted
Failure
xx integer not found - delete not successful :where xx is the integer being deleted was not found
2.2.3 Search
The search command uses the single character s as the command token. The command token will be followed by a single space, then the integer that is to be searched
The search command will take advantage of the skip list structure and implement the following algorithm. A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. If the current element is equal to the target, it has been found. If the current element is greater than the target, or the search reaches the end of the linked list, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list.[1]
Upon completion of the search for the target integer, the following messages shall be output. Inputs s xx where xx is an integer between 1 and 5,000.
Outputs
Success xx found :where xx is the integer being searched for
Failure xx NOT FOUND :where xx is the integer being searched for and was not found
2.2.4 Print
The print command uses the single character p as the command token. This command will invoke the printAll function described in detail below.
This command is critical for verification of all the commands specified above.
Inputs p
Outputs
EUSTIS_SYSTEM_PROMPT$java Hw02 H2in-a1.txt bs123456;3.141592653;10
For the input file named H2in-a1.txt With the RNG unseeded, the current Skip List is shown below:
---infinity
110;
198;
270;
302; 302;
354;
503;
596;
603;
629; 629;
947;
+++infinity
---End of Skip List---
2.3 Classes and Functions
2.3.1 Classes
SkipList The SkipList class shall contain, at a minimum, the following methods.
insert The features and performance of the insert method is defined by the behavior described above.
promote The features and performance of the promote method is defined by the behavior described in the behavior of the insert commmand decribed above.
delete The features and performance of the delete method is defined by the behavior described above. search The features and performance of the search method is defined by the behavior described above.
printAll The printAll method prints the contents of the whole skip list in the format specified below.
Additional methods and properties will be required to successfully implement the methods specified above.
2.3.2 Functions complexityIndicator Prints to STDERR the following:
NID
A difficulty rating of difficult you found this assignment on a scale of 1.0 (easy-peasy) through 5.0 (knuckle busting degree of difficulty).
Duration, in hours, of the time you spent on this assignment.
Sample output:
EUSTIS_SYSTEM_PROMPT$java Hw02 H2in-a1.txt bs123456;3.141592653;10
3 Testing
Make sure to test your code on Eustis even if it works perfectly on your machine. If your code does not compile on Eustis you will receive a 0 for the assignment. There will be 10 input files and 10 output files provided for testing your code, they are respectively shown in Table 2 and in Table 3.
Filename
Description
H2in-a1.txt
Inserts 10 integers, prints the skip list
H2in-a2.txt
Inserts 25 integers, prints the skip list
H2in-a3.txt
Inserts 50 integers, prints the skip list
H2in-a4.txt
Inserts 100 integers, prints the skip list
H2in-a5.txt
Inserts 27 integers, deletes 2 random numbers, prints the skip list
H2in-a6.txt
Inserts 26 integers, searches for 1 random number, deletes 1 random number, prints the skip list
H2in-a7.txt
Inserts 25 integers, searches for 2 random numbers, prints the skip list
H2in-a8.txt
Inserts 798 integers, deletes 201 random numbers, prints the skip list
H2in-a9.txt
Inserts 3957 integers, deletes 1043 random numbers, prints the skip list
H2in-a10.txt
Inserts 4008 integers, deletes 993 random integers, prints the skip list
Table 2: Input files
The expected output for these test cases will also be provided as defined in Table 3. To compare your output to the expected output you will first need to redirect STDOUT to a text file. Run your code with the following command (substitute the actual names of the input and output file appropriately):
java Hw02 inputFile output.txt
The run the following command (substitute the actual name of the expected output file): diff output.txt expectedOutputFile
Make sure that the Random Number Generator is NOT seeded with anything other than 42. That is, do not use the r option when testing.
If there are any differences the relevant lines will be displayed (note that even a single extra space will cause a difference to be detected). If nothing is displayed, then congratulations - the outputs match! For each of the five (5) test cases, your code will need to output to STDOUT text that is identical to the corresponding expectedOutputFile. If your code crashes for a particular test case, you will not get credit for that case
2 Requirements
Read the input file formatted as follows. The input file will contain at least one command per line, either insert, delete, search, print, or quit. These are defined in detail below. And if appropriate, a second parameter may be required. The second parameter, if appropriate, will always be an integer for this assignment.
The commands are shown in the table below:
Command
Description
Parameter(s)
i
Insert
expects a space, followed by an integer
s
Search
expects a space, followed by an integer
d
Delete
expects a space, followed by an integer
p
does not expect any additional data
Table 1: Input File Commands
2.1 Design Constraints
The input file(s) provided will have the following properties.
1. Each record in the input file will consist of a command, described above, appropriately followed by an integer.
2. There is not a maximum number of skip levels.
3. The test input integers will be within the range of 1 to 5,000.
4. There is no requirement for persistence. The data in the skip list does not need to be stored or archived on disk before the program exits.
2.2 Commands
2.2.1 Insert
The insert command uses the single character i as the command token. The command token will be followed by a single space, then an integer. This integer will then be inserted into the skip list. Note that a skip list requires that data be inserted into the skip list in ascending order.
1. Insertion requires that the specified integer will be inserted at the lowest level of the skip list and will be appropriately connected with the preceding integer and the next integer on the lowest level. For example inserting a 5 between a 3 and a 7 would result in the the 3 becoming the preceding integer and 7 becoming the next integer relative the newly inserted 5.
• In the event that the inserted integer would be placed at either the lowest or highest rank, that is at the lowest or highest possible value for the lowest skip list level make sure that new lowest or highest rank integer is appropriately connected or represented as connected to either −∞ or +∞.
2. Insertion of an integer that requires a probabilistic mechanism to decide if this integer will also be promoted to the next higher level regardless of whether it is the lowest or highest rank integer. The method discussed in lecture is flipping a fair coin. The flipping of a fair coin can be emulated using the Random object in Java to generate a “random number” then taking that number modulo 2 to generate a 1 or 0. The optional seeding of the Random number generator will be the second command line parameter specified by an upper or lower case R . In the event that the R parameter is not specified, seed the Random number generator with the integer 42. The promotion method used to generate the test cases used a 1 to represent heads and correspondingly a 0 to represent tails. Each flip of the coin that produces a heads causes that integer to be promoted and appropriately linked into the skip list. This process is terminated when a tails has been “flipped”.
3. In the event that the number to be inserted already exists in the skipList it can be ignored as there is no requirement for duplicate entries in this implementation.
Inputs i xx where xx is an integer between 1 and 5,000.
Outputs
N/A
2.2.2 Delete
The delete command uses the single character d as the command token. The command token will be followed by a single integer. In order to successfully delete an entry from the skip list, the integer must be found.
In the event that the integer cannot be found, the program will issue the error message xx integer not found - delete not successful, where xx is the specified integer. The program will recover gracefully to continue to accept commands.
Once the integer is found, it will be deleted from the lowest level, and any additional level(s) that integer had been promoted to upon insertion. Remember to appropriately connect the previous and next values across all levels that contained the deleted integer. (This command’s success can be verified by using the print command.)
Inputs d xx where xx is an integer between 1 and 5,000.
Outputs
Success xx deleted :where xx is the integer being deleted
Failure
xx integer not found - delete not successful :where xx is the integer being deleted was not found
2.2.3 Search
The search command uses the single character s as the command token. The command token will be followed by a single space, then the integer that is to be searched
The search command will take advantage of the skip list structure and implement the following algorithm. A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. If the current element is equal to the target, it has been found. If the current element is greater than the target, or the search reaches the end of the linked list, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list.[1]
Upon completion of the search for the target integer, the following messages shall be output. Inputs s xx where xx is an integer between 1 and 5,000.
Outputs
Success xx found :where xx is the integer being searched for
Failure xx NOT FOUND :where xx is the integer being searched for and was not found
2.2.4 Print
The print command uses the single character p as the command token. This command will invoke the printAll function described in detail below.
This command is critical for verification of all the commands specified above.
Inputs p
Outputs
EUSTIS_SYSTEM_PROMPT$java Hw02 H2in-a1.txt bs123456;3.141592653;10
For the input file named H2in-a1.txt With the RNG unseeded, the current Skip List is shown below:
---infinity
110;
198;
270;
302; 302;
354;
503;
596;
603;
629; 629;
947;
+++infinity
---End of Skip List---
2.3 Classes and Functions
2.3.1 Classes
SkipList The SkipList class shall contain, at a minimum, the following methods.
insert The features and performance of the insert method is defined by the behavior described above.
promote The features and performance of the promote method is defined by the behavior described in the behavior of the insert commmand decribed above.
delete The features and performance of the delete method is defined by the behavior described above. search The features and performance of the search method is defined by the behavior described above.
printAll The printAll method prints the contents of the whole skip list in the format specified below.
Additional methods and properties will be required to successfully implement the methods specified above.
2.3.2 Functions complexityIndicator Prints to STDERR the following:
NID
A difficulty rating of difficult you found this assignment on a scale of 1.0 (easy-peasy) through 5.0 (knuckle busting degree of difficulty).
Duration, in hours, of the time you spent on this assignment.
Sample output:
EUSTIS_SYSTEM_PROMPT$java Hw02 H2in-a1.txt bs123456;3.141592653;10
3 Testing
Make sure to test your code on Eustis even if it works perfectly on your machine. If your code does not compile on Eustis you will receive a 0 for the assignment. There will be 10 input files and 10 output files provided for testing your code, they are respectively shown in Table 2 and in Table 3.
Filename
Description
H2in-a1.txt
Inserts 10 integers, prints the skip list
H2in-a2.txt
Inserts 25 integers, prints the skip list
H2in-a3.txt
Inserts 50 integers, prints the skip list
H2in-a4.txt
Inserts 100 integers, prints the skip list
H2in-a5.txt
Inserts 27 integers, deletes 2 random numbers, prints the skip list
H2in-a6.txt
Inserts 26 integers, searches for 1 random number, deletes 1 random number, prints the skip list
H2in-a7.txt
Inserts 25 integers, searches for 2 random numbers, prints the skip list
H2in-a8.txt
Inserts 798 integers, deletes 201 random numbers, prints the skip list
H2in-a9.txt
Inserts 3957 integers, deletes 1043 random numbers, prints the skip list
H2in-a10.txt
Inserts 4008 integers, deletes 993 random integers, prints the skip list
Table 2: Input files
The expected output for these test cases will also be provided as defined in Table 3. To compare your output to the expected output you will first need to redirect STDOUT to a text file. Run your code with the following command (substitute the actual names of the input and output file appropriately):
java Hw02 inputFile output.txt
The run the following command (substitute the actual name of the expected output file): diff output.txt expectedOutputFile
Make sure that the Random Number Generator is NOT seeded with anything other than 42. That is, do not use the r option when testing.
If there are any differences the relevant lines will be displayed (note that even a single extra space will cause a difference to be detected). If nothing is displayed, then congratulations - the outputs match! For each of the five (5) test cases, your code will need to output to STDOUT text that is identical to the corresponding expectedOutputFile. If your code crashes for a particular test case, you will not get credit for that case
1 file (3.0KB)
