CMSC 420, Data Structures - Section 0101, Fall 2002

    Project 2

Updates:


The goal of Project 2 is to implement a data structure that allows the same kinds of queries as the segment tree of Project 1, and also allows user sessions to be inserted and deleted. The segment-tree data structure of Project 1 does not work well for inserting and deleting user sessions: each insertion or deletion would require reconstructing most of the segment tree. Of the various data structures that we've studied so far, I think the one that will make it easiest to insert and delete user sessions is a skip list.

For Project 2, you need to implement a "segment skip list" that allows the same kinds of queries as in Project 1, and that also allows insertions and deletions. A segment skip list is like an ordinary skip list except that the nodes have more data fields than in an ordinary skip list. More specifically:

As an example, consider the same set of login sessions that were used as an example in Project 1:

For this set of sessions, two of the possible segment skip lists are shown below. Each S is a start time, each U is a list of users, and each P is a pointer.

HEADER     NODE1    NODE2    NODE3    NODE4      NODE5       NODE6  NODE7
  P: ----> P: Lambda
           U:
  P: ----> P: -------------------------------> P: Lambda
           U: Jane                             U:
  P: ----> P: -------------> P: -------------> P: ----------------> P: Lambda
           U: Jean           U: John,Joan      U: Joan              U:
  P: ----> P: ----> P: ----> P: ----> P: ----> P: ---------> P: --> P: Lambda
           U:       U: John  U:       U: June  U: Jane,June  U:     U:
           S: 1     S: 2     S: 5     S: 6     S: 7          S: 9   S: 10
HEADER     NODE1    NODE2    NODE3    NODE4      NODE5       NODE6  NODE7



HEADER  NODE1        NODE2        NODE3   NODE 4       NODE5        NODE6  NODE7
 P: ---------------> P: Lambda
                     U:
 P: ---------------> P: -----------------------------> P: ---------------> P: Lambda
                     U: Jane,John                      U: Joan             U:
 P: ---------------> P: ----------------> P: --------> P: --------> P: --> P: Lambda
                     U:                   U: June,Joan U: Jane,June U:     U:
 P: --> P: --------> P: --------> P: ---> P: --------> P: --------> P: --> P: Lambda
        U: Jane,Jean U: Jean      U: Joan U:           U:           U:
        S: 1         S: 2         S: 5    S: 6         S: 7         S: 9   S: 10
HEADER  NODE1        NODE2        NODE3   NODE 4       NODE5        NODE6  NODE7

For this project you will need to write a program to create a segment skip list and answer several different queries on it. As before, we'll measure time in tenths of a second over a one-day period. Thus, each login and logout time will be an integer from 0 to 864000.

Recall that whenever you create a node in a skip list, you need to assign its number of levels randomly. So that all of your programs will create the same skip list, you all will need to use the same random-number generation algorithm. To get a copy of the algorithm, go here. Look for the heading "Pseudo-Random number generation using R250", and download either the C++ implementation or the Java implementation. In either case, you'll download a tar archive that contains several files. These files contain implementations of two different random-number algorithms: a simple one called randlcg and a complicated one called r250. Use randlcg (the simple one), and discard the coding for r250. If you're writing your project in C++, then to get a pseudorandom number in the range 0..1 you'll need to do something like the following:

r= randlcg()/(LONG_MAX+0.0);

In the Java version, you'll need to do something like

r = rani()/(float)(LONG_MAX+0.0);

This time, there will be only one input file. It will contain commands, one command per line, that your program will need to read and execute. Below is a list of the possible commands.

Command: MaxLevels Levels

This will always be the first command in the file. Levels is a positive integer. Your program should create an empty segment skip list whose maximum number of levels is Levels.

Output:

Created empty list with Levels levels.

Command: Seed Seed

This command sets the seed for your random number generator to the integer value Seed.

Output:

Set seed to Seed.

Command: Insert Name Start End

Name is a string that represents the name of a user. Start and End are integers that represent the user's login and logout times (measured in tenths of a second, as explained above). Your program should modify the skip list as follows. If there is already a login session for this user, then you should delete it (the easiest way to do this is to use the Delete command described below). If the skip list doesn't already contain a node whose start times are Start and End, then you'll create these nodes, assign their levels randomly as described in the book, and insert into them the appropriate information about the other users' login sessions. You'll need to insert information about the login session for Name into the appropriate nodes of the list.

Note: if you need to create nodes for both Start and End, then you'll be calling your random number generator twice. In order to get predictable behavior from your program, the first call should be for the Start node and the second one should be for the End node.

For each node created, print out a message telling the node's start time and how many levels the node contains. (For debugging purposes, you might also find it helpful to print some information about the user lists at each level of the node, but the final version of your program should not print that information.)

Output format:

Node created with start time s and l levels.

Additional note:

There are situations in which inserting a name may also require modifying the positions of the other names. Here's an example contributed by Ransom Winder. Suppose we start with an empty skip list and insert Al [1,6). This might produce the following skip list:

Header Node1      Node2
P:====>P: Lambda
       U:
P:====>P: Lambda
       U:
P:====>P: Lambda
       U:
P:====>P: ======> P: Lambda
       U: Al      U:
       S: 1       S: 6

When we insert Bob, suppose we generate 3 levels for his first node and 4 levels for his second node. Then we should get the following skip list (note that Al's position in Node 1 has changed):

Header Node1     Node2     Node3       Node4
P:====>P: ===============> P: Lambda
       U: Al               U:
P:====>P: =====> P: =====> P: Lambda
       U:        U:        U:
P:====>P: =====> P: =====> P: Lambda
       U:        U:        U:
P:====>P: =====> P: =====> P: =======> P: Lambda
       U:        U: Bob    U: Al       U:
       S: 1      S: 2      S: 4        S: 6

Command: Delete Name Start End

Name is a string that represents the name of a user, and Start and End are integers that represent the login and logout times (measured in tenths of a second, as explained above). Your program should modify the skip list as follows. First, remove all occurrences of Name from the skip list. Next, delete the node for Start if there are no users whose sessions start or end at time Start, and delete the node for End if there are no users whose sessions start or end at time End. For each node deleted, print out the following line:

Node deleted with start time s.

Command: UserTime Start Finish Name

Start and Finish are integers (representing time in tenths of a second), and Name is a string. Compute the total number of seconds S that a user named Name was logged into the computer during the time interval [Start, Finish).

Output format:

N user lists examined.
From time Start to time Finish, Name spent S seconds on the computer.

Command: MaxUsers Start Finish

Start and Finish are integers (representing time in tenths of a second). Compute the maximum number of users M logged into the system, over all time points in the interval [Start,Finish). Give those users, in sorted order.

Output format:

N user lists examined.
Between time Start and time Finish, the largest number of users is M.
The users:
Name1

Namek

Command: UsersAt p

p is an integer (representing time in tenths of a second). Tell how many people are using the computer at time p, and give their names. The Name values should be printed in the order in which they are discovered by descending the segment tree.

Output format:

N user lists examined.
The following users are logged in at time p:
Name1

Namek

Command: TotalUsers Start Finish

Start and Finish are integers (representing time in tenths of a second). Print the total number of users that were on the computer during the interval [Start,Finish). Print the Name values in sorted order for all sessions that are running during the interval [Start, Finish).

Output format:

N user lists examined.
S users were on the computer between time Start and time Finish:
Name1

Namek

Command: IsUserOn Name p

Name is a string denoting a user, and p is an integer (representing time in tenths of a second). Tell whether or not a user named Name has a session on the computer at time p.

Output (if true):

N user lists examined.
Name is on the computer at time p.

Output (if false):

N user lists examined.
Name is not on the computer at time p.

Command: IsUserOnRange Name Start Finish

Name is a string, and Start and Finish are integers (representing time in tenths of a second). Tell whether or not a user named Name has a session on the computer at any point during the interval [Start,Finish).

Output (if true):

N user lists examined.
Name is on the computer between times Start and Finish.

Output (if false):

N user lists examined.
Name is not on the computer between times Start and Finish.

Here's a note about how to compute MaxUsers and TotalUsers. Recall that a skip list corresponds to a search tree such that each node at depth d of the search tree is represented by a pointer at level MaxLevels-d of the skip list. The book discusses how to do an ordinary search on this tree. For MaxUsers and TotalUsers, you'll need to combine this search with a tree traversal, but this should be pretty similar to what you did with your segment trees in Project 1. The main difference is that in the search tree that corresponds to the skip list, the number of children at each node of the search tree is often something other than 2. However, that shouldn't make much difference for a preorder tree traversal - just visit the node, and then go down a level to visit its children.