SE 598, Data Structures and Algorithms

STL Dequeue Programming Assignment, due 5:00 p.m. Wednesday, 5 July

Introduction

Because dequeues are similar to vectors, this assignment will be more of a generic algorithm assignment than a dequeue assignment; that is, you should be looking to cram your code full of generic algorithms rather than dequeues (although, of course, a dequeue or two wouldn't hurt).

In the previous assignment you implemented a program called readmbox, which responded to two commands: a message number n, which printed message n if it exists, and the quit command q, which quit the program. In this assignment you'll add the order command to readmbox's command repertoire.

The order command re-orders the sequence of messages presented to the readmbox user. The order command format is

order [ field word ]

where [ a ] means a is optional. field is a word with no interpretation placed on it.

The pair field word is called a search pattern. A search pattern matches a header field if the header field has field as its label and word as a word in its text-line. For example, the search pattern "Subject Urgent" matches the header field

Subject: Ugent!! Read at once!!

but matches neither of the header fields

Subject: About your last bill...

because the text-line doesn't contain "Urgent" nor

Disposition: Urgent

because the label isn't "Subject". A search pattern matches a message if it matches at least one of the header fields in the message.

The command

order field word

re-orders the message list so that messages which match the search pattern are presented to the user before messages which don't match the search pattern. For example, suppose the current state of the message list in readmbox is

1 2* 3 4* 5* 6

where each number is a message number and an asterisk (*) represents a message which matches the search pattern. Then order would re-order the message list to

2* 4* 5* 1 3 6

so that what was the second message becomes the first message, what was the fourth message becomes the second message and so on. Notice that the previous message-list order is preserved within each group of matching or non-matching messages. For example, order would be incorrect if it re-ordered the message list as

4* 2* 5* 6 3 1

such sorts are known as stable sorts.

The command

order

resets the message list to the order it had when readmbox was started.

This page last modified on 4 July 2000.