Class Demo: Sorted List Implemented as an array in C++
Interface (Header) File defining the list class
//---------------------------------------------------------------
// File: ToDoList.h
// Purpose: Interface file for the demonstration ToDoList class
// Author: Dr. Rick Coleman
//---------------------------------------------------------------
#ifndef TODOLIST_H
#define TODOLIST_H
#include <iostream>
using namespace std;
// Define a structure to use as the list item
struct ToDoItem
{
int priority; // Task priority and key
char theTask[128]; // Task string;
};
#define MAX_SIZE 50 // Define maximum number of tasks in list
// Class definition
class ToDoList
{
private:
ToDoItem taskList[MAX_SIZE]; // List implemented as an array
int lastIdx; // Index where last item was inserted
public:
ToDoList(); // Class constructor
~ToDoList(); // Class destructor
void ClearList(); // Remove all items from the list
void Insert(char *task, int priority); // Add a task to the list
void Delete(char *task); // Delete given a task string
void Delete(int priority); // Delete given a priority
char *Search(int priority); // Search given a priority
int ListLength(); // Return number of items in list
bool isEmpty(); // Return true if list is empty
bool isFull(); // Return true if list is full
char *GetNextTask(); // Return the next task
void PrintList(); // Print all items in the list
};
#endif // End class definition
Implementation (.cpp) File defining the list class
//---------------------------------------------------------------
// File: ToDoList.cpp
// Purpose: Implementation file for the ToDoList class
// Author: Dr. Rick Coleman
// Date: January 2002
//---------------------------------------------------------------
#include <cstdlib> // To get access to malloc()
#include <string.h>
#include "ToDoList.h"
//--------------------------------------------
// Function: ToDoList()
// Purpose: Class constructor
// Returns: N/A
//--------------------------------------------
ToDoList::ToDoList()
{
lastIdx = -1;
}
//--------------------------------------------
// Function: ~ToDoList()
// Purpose: Class destructor
// Returns: N/A
//--------------------------------------------
ToDoList::~ToDoList()
{
// Nothing to do. All memory automatically
// cleared when class is destroyed
}
//--------------------------------------------
// Function: ClearList()
// Purpose: Remove all items from the list
// Returns: void
//--------------------------------------------
void ToDoList::ClearList()
{
lastIdx = -1; // Just reset count
}
//--------------------------------------------
// Function: Insert()
// Purpose: Insert a task into the list in
// the correct order.
// Returns: void
//--------------------------------------------
void ToDoList::Insert(char *task, int priority)
{
int index;
if(isFull())
{
cout << "Cannot add the task: " << task;
cout << "\n to the list. List full.\n";
return;
}
// Increment lastIdx
lastIdx++;
// Move all items in the list down by 1 until
// the appropriate location is found
index = lastIdx;
while((index > 0) && (taskList[index-1].priority > priority))
{
// Move this one down one
taskList[index] = taskList[index-1];
index--;
}
// When we get here we will have one of the following cases
// index == 0 because we are inserting the first task
// index == 0 because all other tasks have been moved down one
// so we are inserting a new first priority task
// index == n because all other tasks have been moved down one
// index == lastIdx because this task has a larger priority than
// any others already in the list
// In each case we insert the new task into the list at index
taskList[index].priority = priority;
strcpy(taskList[index].theTask, task);
}
//--------------------------------------------
// Function: Delete()
// Purpose: Delete a task from the list.
// Returns: void
//--------------------------------------------
void ToDoList::Delete(char *task)
{
int i, d = 0;
while((d <= lastIdx) && (strcmp(taskList[d].theTask, task) != 0))
{
d++;
}
if(d > lastIdx)
{
cout << "Cannot find task to delete.\n";
}
else
{
// Move all other tasks toward the front of the array
// This also overwrites and "deletes" the task searched for
for(i = d; i < lastIdx; i++)
{
taskList[i] = taskList[i+1];
}
lastIdx--; // Reset lastIdx
}
}
//--------------------------------------------
// Function: Delete()
// Purpose: Delete a task from the list given
// its priority. Assumes priority is unique.
// Returns: void
//--------------------------------------------
void ToDoList::Delete(int priority)
{
int i, d = 0;
while((d <= lastIdx) && (taskList[d].priority != priority))
{
d++;
}
if(d > lastIdx)
{
cout << "Cannot find task to delete.\n";
}
else
{
// Move all other tasks toward the front of the array
// This also overwrites and "deletes" the task searched for
for(i = d; i < lastIdx; i++)
{
taskList[i] = taskList[i+1];
}
lastIdx--; // Reset lastIdx
}
}
//--------------------------------------------
// Function: Search()
// Purpose: Search for a task by priority and
// return a copy of the task string.
// Note the dynamic creation of a string.
// Returns: Char pointer pointing to a new
// string containing a copy of the task.
//--------------------------------------------
char *ToDoList::Search(int priority)
{
int s = 0;
char *returnStr;
while((s <= lastIdx) && (taskList[s].priority != priority))
{
s++;
}
if(s > lastIdx)
{
cout << "Task not found.\n\n";
return ""; // could not find the task
}
else
{
// Copy the task
returnStr = (char *)malloc(strlen(taskList[s].theTask) + 1);
strcpy(returnStr, taskList[s].theTask);
return returnStr;
}
}
//--------------------------------------------
// Function: ListLength()
// Purpose: Return the number of items in the
// list.
// Returns: Number of items in list
//--------------------------------------------
int ToDoList::ListLength()
{
return lastIdx+1;
}
//--------------------------------------------
// Function: isEmpty()
// Purpose: Return true if the list is empty
// Returns: True if empty, otherwise false
//--------------------------------------------
bool ToDoList::isEmpty()
{
return (lastIdx == -1);
}
//--------------------------------------------
// Function: isFull()
// Purpose: Return true if the list is full
// Returns: True if full, otherwise false
//--------------------------------------------
bool ToDoList::isFull()
{
return (lastIdx >= MAX_SIZE);
}
//--------------------------------------------
// Function: GetNextTask()
// Purpose: Return the task string of the task
// at the head of the list.
// Note the dynamic creation of a string.
// Returns: Char pointer pointing to a new
// string containing a copy of the task.
//--------------------------------------------
char *ToDoList::GetNextTask()
{
int i = 0;
char *returnStr;
// Copy the task
if(isEmpty())
{
cout << "List is empty.\n\n";
return "";
}
else
{
returnStr = (char *)malloc(strlen(taskList[0].theTask) + 1);
strcpy(returnStr, taskList[0].theTask);
// Move all other tasks up
while(i < lastIdx)
{
taskList[i] = taskList[i+1];
i++;
}
lastIdx--; // Decrement index
return returnStr;
}
}
//--------------------------------------------
// Function: PrintList()
// Purpose: Print all tasks in the list with
// their priority.
// Returns: void
//--------------------------------------------
void ToDoList::PrintList()
{
int i;
cout << "\n\nTasks in the List\n";
cout << "-----------------------------------------------------------\n";
cout << "Priority\t\tTask\n";
cout << "-----------------------------------------------------------\n";
for(i=0; i<=lastIdx; i++)
{
cout << taskList[i].priority << "\t\t" << taskList[i].theTask << "\n";
}
cout << "-----------------------------------------------------------\n\n";
}
Main file used to test the list class
//---------------------------------------------------------------
// File: ListMain.cpp
// Purpose: Demonstrate use of the ToDoList class
// Author: Dr. Rick Coleman
// Date: December, 2001
//---------------------------------------------------------------
#include <iostream>
#include "ToDoList.h"
#include <string.h>
using namespace std;
int main(int argc, char **argv)
{
ToDoList *theList;
cout << "Simple List Demonstration\n";
cout << "(List implemented as an Array - Do not try this at home)\n\n";
cout << "Create a list and add a few tasks to the list";
theList = new ToDoList();
theList->Insert("This is task 1", 5);
theList->Insert("This is task 2", 1);
theList->Insert("This is task 3", 3);
theList->Insert("This is task 4", 2);
theList->Insert("This is task 5", 4);
// Show what is in the list
theList->PrintList();
// Test the list length function
cout << "\nList now contains " << theList->ListLength() << " items.\n\n";
// Test delete function 1
cout << "Testing delete function 1.\n";
theList->Delete("This is task 4");
theList->PrintList();
// Test delete function 2
cout << "Testing delete function 2.\n";
theList->Delete(5);
theList->PrintList();
// Test both delete functions with a know failure argument
cout << "Testing failure in delete function 1.\n";
theList->Delete("This is task 4");
cout << "\n";
cout << "Testing failure in delete function 2.\n";
theList->Delete(5);
cout << "\n";
// Test search
cout << "Testing Search function\n";
cout << "Search result: " << theList->Search(4) << "\n\n";
// Testing get next task
cout << theList->GetNextTask();
cout << "\n";
cout << theList->GetNextTask();
cout << "\n";
cout << theList->GetNextTask();
cout << "\n";
cout << theList->GetNextTask();
cout << "\n";
cout << "\n\nEnd list demonstration...";
return 0;
}