CSE 321 Lab 1

Objective
Overview
Materials Provided
Set Up
Swap/Compare Two Array Elements
Using the Test Driver
What To Submit

Objective

The objective for this assignment is to implement the Sorting_Machine component.

Overview

You will be implementing the Sorting_Machine component using the heapsort algorithm discussed in class.

Materials Provided

The set up instructions will provide you with a user catalog containing the following components and auxiliary items:

Sorting_Machine_Kernel
Sorting_Machine_Kernel_2
Sorting_Machine_Test.cpp

You will need to do the following:

In Sorting_Machine_Kernel_2, add headers for any private operations that are needed. Note: When you add any private operations, you must include requires and ensures clauses with each operation header. You may write the requires and ensures clauses in English, but be as precise as possible.
In Sorting_Machine_Kernel_2, fill in the bodies of all operations.

Important! Note that it is a requirement of this lab that you use the heapsort algorithm described in class. Essentially any variation on that algorithm is either going to be less efficient or simply not heapsort. And neither of these options is acceptable.

To use a demonstration version of the test driver, just execute the command 321_Sorting_Machine_Demo.

Set Up

Copy the lab1 course catalog to your group project directory (/project/c321axnn, where "x" is your section letter and "nn" is your team number):
```
cp -r /class/sce/now/321/labs/catalogs/lab1 /project/c321axnn
```
Make sure that the new catalog will be accessible to your partner. Perform this action now and as your last act whenever you finish a working session. Note that 'l' in the chmod command is the letter 'l' ("el"), as in "lock":
```
cd /project/c321axnn/lab1

chmod -R g-l,g+rwX .

set-group-ID .
```
Look around the new user catalog to familiarize yourself with its contents.

Swap/Compare Two Array Elements

To avoid violating the repeated argument rule, you must use the Array_Exchange_At and Array_Are_In_Order_At Array extensions to swap and compare two array elements, respectively. In other words, to swap elements i and j in array a, use a.Exchange_At (i, j), and to compare elements i and j in array a, use a.Are_In_Order_At (i, j).

Using the Test Driver

The test driver initializes an array from 0 through 9 of sorting machines. When using the driver, it will ask for the number of the sorting machine to which you would like to apply an operation. You should always respond with a value in the range 0 through 9. Also, the test driver instantiates sorting machines with Text for Item. Here is an example:

Run in interactive mode (y/n)? y


Command: s [Swap]
         p [Put_To]
         i [Insert]
         f [Remove_First]
         a [Remove_Any]
         c [Change_To_Extraction_Phase]
         x [Is_In_Extraction_Phase]
         z [Size]
         C [Clear]
         q [Quit]: i
Insert into which Sorting Machine? 3
  ... x value? Sorting machines are cool!

--------------------------------------------
                   |    x = Sorting machines are cool!
--------------------------------------------
m3.Insert (x);  |
--------------------------------------------
                   |    x =
--------------------------------------------

Command: s [Swap]
         p [Put_To]
         i [Insert]
         f [Remove_First]
         a [Remove_Any]
         c [Change_To_Extraction_Phase]
         x [Is_In_Extraction_Phase]
         z [Size]
         C [Clear]
         q [Quit]: p
Put which Sorting Machine? 3

--------------------------------------------
m3 =
(
  true,
  {
    Sorting machines are cool!
  }
)
--------------------------------------------

Command: s [Swap]
         p [Put_To]
         i [Insert]
         f [Remove_First]
         a [Remove_Any]
         c [Change_To_Extraction_Phase]
         x [Is_In_Extraction_Phase]
         z [Size]
         C [Clear]
         q [Quit]: q

What To Submit

Once you and your partner are convinced that all implementations are working correctly, get into your group's lab1 directory /project/c321axnn/lab1 in an xterm window and use the rcpp-submit command to submit your solution as follows (noting that you will need to use the appropriate suffix in place of ?? in this command, as posted next to your instructor's name on the CSE 321 Home Page):

rcpp-submit c321?? lab1

If you get an error message rather than a confirmation of success, please read the message; it contains useful information! Do not just run the same command again. Save the e-mail you get as a receipt of submission, just in case.