CMSC 420, Data Structures - Section 0101, Fall 2002

Project 1

Updates:

Oct 8, 5:50pm. Fixed a "≥" sign that wasn't showing up correctly in some web browsers.
Oct 8, 5:40pm. Changed the due dates as discussed in class. Also, here is a link to Ransom Winder's message on how to submit the project.
Oct 1, 4:30pm. The changes are minor: I alphabetized the names in the example, and made the time units more explicit in the command descriptions. All changes are shown in red.

Due on October 15 (was Oct 13) at 11pm.
Late date (10 points off): October 16 (was Oct 15) at 11pm.
Write the program in C++ or Java.
The grading criteria will include correctness, your algorithms and data structures, programming style, and documentation.
Your programs are to be submitted electronically. Later we'll post information about how.

Suppose that over the course of one day, users log in and out of sessions on a computer. At various times of the day, any number of sessions can be running - but to simplify things, we will assume that each user has at most one session per day. If the start and end times for a session are s and t, then we'll consider the time interval for the session to be the open-closed interval [s,t) = {x : s ≤ x < t}.

Our goal is to be able to organize all of the sessions into a data structure called a segment tree, so we can ask questions about the users and the state of the computer at various times of the day. Mathematically, a segment tree is a binary search tree in which each node represents a time interval, and all leaf nodes are at the same level. More specifically:

First, take the starting and ending times for all of the sessions, sort them, and remove duplicates. This gives us a sequence of time points T = {t₁, …, t_j}. The height of the tree is the smallest h such that 2^h ≥ j-1.
Going from left to right at depth h of the tree, there are j-1 leaf nodes that represent the time intervals [t₁, t₂), [t₂, t₃), …, [t_j-1,t_j).
Each non-leaf node with two children represents a time interval consisting of the union of its children’s time intervals.
Each non-leaf node n with one child will have a left child representing some interval [a,b). In this case, n represents the interval [a,oo).
Each node is labeled with its time interval. In addition, each node is labeled with the names of one or more users, as follows. Let n be a node, let [t,u) be the time interval represented by n, and let [v,w) be the time interval represented by n’s parent. For every session S=[x,y) such that [t,u) is a subset of [x,y) and [v,w) is not a subset of [x,y), n is labeled with S. If a node has more than one label, then these are stored in sorted order.

As an example, suppose that the sessions are as follows:

Jean logs in at 1:00 and logs out at 5:00;
John logs in at 2:00 and logs out at 7:00;
Joan logs in at 5:00 and logs out at 10:00;
June logs in at 6:00 and logs out at 9:00;
Jane logs in at 1:00 and logs out at 9:00.

Then the segment tree is:

                       [1,oo) 
                      /      \
                     /        \
                    /          \
                   /            \
                  /              \
             [1,7)               [7,oo)
              Jane                 /
              / \                 /
             /   \               /
            /     \             /
       [1,5)       [5,7)      [7,10)
        Jean        Joan       Joan
        / \         John        / \
       /   \        /  \       /   \
      /     \      /    \     /     \
    [1,2) [2,5) [5,6) [6,7) [7,9) [9,10)
          John        June  Jane
                            June

For this project you will need to write a program to create a segment tree and answer several different queries on the tree. 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.

There will be two input files. The first one is named "intervals". It will contain the information about the sessions. Each line of this file will have the format

Name Start End

where 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). No user name will appear more than once. When your program starts, it should read the "intervals" file, construct the segment tree, and print out the tree’s height h, number of nodes n, and number of leaf nodes v. Output format:

Segment tree has height h and contains n nodes, of which v are leaves.

The second file is named “commands”. 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: 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 nodes 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 nodes examined.
Between time Start and time Finish, the largest number of users is M.
The users:
Name₁
…
Name_k

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 nodes examined.
The following users are logged in at time p:
Name₁
…
Name_k

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 nodes examined.
S users were on the computer between time Start and time Finish:
Name₁
…
Name_k

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 nodes examined.
Name is on the computer at time p.

Output (if false):

N nodes 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 nodes examined.
Name is on the computer between times Start and Finish.

Output (if false):

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