CSc 335

Objectives

• To start getting used to C++, if you're not familiar with it already
• To remember good coding practices like thorough testing

Introduction

Your Mission

Part 1: Java

public class DLList
{
    private DLLElement first;  //pointer to first node
    private DLLElement last;   //pointer to last node

    /**
     * Creates an empty sorted doubly-linked list.
     */ 
    public DLList()
    {
    }

    /**
     * Add item to the head of the list, setting the key for the new
     * head element to min_key - 1, where min_key is the smallest key
     * in the list (which should be located in the first node.)
     * If no nodes exist yet, the key will be zero.
     */
    public void prepend(Object item)
    {
    }

    /**
     * Removes the head of the list and returns the data item stored in
     * it.  Returns null if no nodes exist.
     */
    public Object removeHead()
    {
    }

    /**
     * Returns true if the list is empty.  Otherwise, false.
     */
    public boolean isEmpty()
    {
    }

    /**
     * Inserts item into the list in sorted order according to sortKey.
     */
    public void insert(Object item, Integer sortKey)
    {
    }

    /**
     * Print the list for debugging only.  The "which" parameter is
     * just a label you should print before the list so you know
     * which printing this is.  Example: 
     * PRINTING #1:
     */
    public void printList(int which)
    {
    }

    // the node class (inner class)
    private class DLLElement
    {
        private DLLElement next; 
        private DLLElement prev;
        private int key;
        private Object data;

        public DLLElement(Object item, int sortKey)
        {
        }
    }
}

Notes:

1. Do NOT import any classes or packages. You are taking care of all the pointer manipulation yourself.

2. You'll notice something in the code that you may not have seen before in Java: a private inner class. This lets DLList objects access the private DLLElement (node) instance variables as if they were public. So in DLList, you can say first.next and that would be ok.

3. You will need to create a separate class for your main() method which should test the methods above. I recommend using Strings as your data items. Watch out for special cases!

4. You may use any development environment you wish.

Part 2: C++

1. DLList.h for your declarations
2. DLList.cc for the list implementation
3. main.cc for your main() function, which will simply test your list functions

To help you out, here is starter code for DLList.h:

#ifndef DLLIST_H
#define DLLIST_H

class DLLElement 
{
  public:
    DLLElement(void *item, int sortKey);
    DLLElement *next; 
    DLLElement *prev;

    int key;
    void *data;
};

class DLList
{
  public:
    DLList();     // constructor
    ~DLList();    // destructor

    // Add item to the head of the list, setting the key for the new
    // head element to min_key - 1, where min_key is the smallest key
    // in the list (which should be located in the first node.)
    // If no nodes exist yet, the key will be zero.
    void Prepend(void *item);

    // Sets sortKey to the key of the head element and removes the head
    // of the list.
    //
    // Returns the data stored at the head of the list.  If no nodes 
    // exist, returns null and sortKey will be left undefined.
    void *RemoveHead(int *sortKey);

    // Returns true if the list is empty.  Otherwise, false.
    bool IsEmpty();

    // Inserts item into the list in sorted order according to sortKey.
    void Insert(void *item, int sortKey);

    // Print the list for debugging only.  The "which" parameter should be
    // printed before the list so you know which printing this is.
    void PrintList(int which);

  private:
    DLLElement *first;
    DLLElement *last;
};

#endif

Notes:

• The RemoveHead() function has changed slightly in the C++ version. It now takes a single int parameter called sortKey. The RemoveHead() function will set sortKey to be the key of the head of the list, remove the first node, and then return the associated data item. This demonstrates C++'s ability to explicitly return multiple items from a subroutine: one via the return type, and one via the parameter.

• Don't use cin and cout for I/O. Nachos doesn't play well with those. (And you're going to use your linked list in Nachos in the next project.) Use printf for output instead.

• For this part, please use chars as data objects instead of strings. Strings may give you some headaches since C and C++ each has a different way of defining them.

• Read the C++ FAQ. The answer you need may be there.

Compiling and Running programs on antipasto

g++ <file1> <file2> ...

where the files are all of your *.cc files. To make your compiled code traceable by the gdb debugger, use the -g option:

g++ -g <file1> <file2> ...

Remember that a link to the gdb debugger manual can be found on our web page.

Once you have removed all compiler errors, a file named a.out will be produced. This is the binary executable. To run it, just type

a.out

You may have to type ./a.out if your path variable does not include the current directory.

Makefiles

• name it Makefile (note capital M)
• name your executable DLL. You can change the name of the executable from the default a.out by using the -o option. See the tutorial for examples.
• use macros where you can to get the hang of them.
• include a clean target that will clean up object (*.o) and executable files.

make DLL

For this small project, a makefile is really overkill, but (1) they're lifesavers for really big projects and (2) Nachos is big enough that it uses makefiles. So understanding them now will help you understand what Nachos is doing in the future.

Finally...

• AddN(). This function will take a DLList * (pointer to a DLList) and an int (call it n) as parameters. This function will add n elements to the given DLList. You may create random keys and data items for the nodes or else hard code specific keys and data items to make debugging easier.

• RemoveN(). This function takes a DLList * and an int n as parameters. It removes and prints n elements from the head of the given DLList.

How to turn this in

/home/csc335pub/submit csc335 <full path to directory>

where <full path to directory> is the complete path to the directory you want to submit. (Use the "pwd" command to find out the full path to your current directory). So, for example, if I kept all of my relevant files in a directory named proj0, I would submit it with

/home/csc335pub/submit csc335 /home/fernandc/proj0

You should also turn in your code on paper (for both parts). Include your output tests with your paper copy.

Grading

Having trouble? Don't wait until the last minute! Come see me and get your $80 worth.

Administrative statement