Chapter 2: Basic Abstract Data Types. Problem 2.10

Problem 2.10. We wish to store a list in an array A whose cells consist of two fields,
data to store an element and position to give the (integer0 position of the element.
An integer last indicates that A[0] through A[last] are used to hold the list.
The type LIST can be defined by

type
    LIST = record
        last := integer;
        elements: array[1.. maxlength] of record
              data: elementtype;
              position: integer
        end
end;

//problem 2.10. 

#include <iostream>
#include <string>
using namespace std;

struct REC
{
    int nData;
    int nPos; //starts from 1. 
}; 

struct LIST
{
    int nLast; //points to the last element in the list.
              //size of the list = nLast+1
    REC list[10];     //Statically allocated for simplicity. 
                    //This would be replaced by a pointer to an array in a
                    //profressional program.
}; 

void CreateList(LIST* listStr); 
bool ListHasSpace(LIST* listStr); 
void PrintList(LIST* listStr); 
bool AddElementToList(LIST* listStr, int data, int pos); 
void DeleteElemAtPos(LIST* listStr); 

void main()
{
    LIST listStr; 
    memset(&listStr,0,sizeof(listStr)); //memset to set everything to 0. 
                                  //elements with 0 position are invalid as position starts with 1.
    listStr.nLast = 9; //10-1 because the list can only hold 10 objects for now

    //Create the list by taking user input
    CreateList(&listStr); 
    cout << "List created." << endl;
    PrintList(&listStr); 
    string sAns = "n"; 
    while(1)
    {
        DeleteElemAtPos(&listStr);
        PrintList(&listStr); 
        cout << "Continue with deletions (y/n)?:"; 
        cin >> sAns;  
        if( sAns[0] == 'n' || sAns[0] == 'N' )
            break;
    }
}

void CreateList(LIST* listStr)
{
    if( !listStr )
        return; 

    while( ListHasSpace(listStr) )
    {
        int data = 0;
        int pos = 0;

        PrintList(listStr); 
        
        cout << "Enter the data for element in the list:"; 
        cin >> data; 
           cout << endl; 
        cout << "Enter the position of this data item in the list:"; 
        cin >> pos;
        
        if( !AddElementToList(listStr, data, pos) )
        {
            cout << "Invalid position." << endl;
        }
    }
}

//Returns true if there are empty elements in the list. 
//Empty elements are defined by a position of 0. 
bool ListHasSpace(LIST* listStr)
{
    if( !listStr )
        return false;

    for( int n = 0; n < listStr->nLast+1; n++ )
    {
        if( listStr->list[n].nPos == 0 )
            return true; 
    }
    return false;
}

void PrintList(LIST* listStr)
{
    if( !listStr )
        return; 
    if( listStr->nLast <= 0 )
        return; 

    cout << "List --------> " << endl;
    for( int n = 0; n < listStr->nLast+1; n++ )
    {
        if( listStr->list[n].nPos == 0 )
            cout << "<Empty Element>" << endl;
        else
            cout << "Data [" << listStr->list[n].nData << "]" << " Pos [" << listStr->list[n].nPos << "]." << endl;
    }
    cout << "<----------- End of List" << endl;
}

//true if element can be successfully added - which means there is space in the list as well as position is unique
bool AddElementToList(LIST* listStr, int data, int pos)
{
    if( !listStr )
        return false;
    if( pos == 0 )
        return false;

    //first validate if this position already exists in the list or not. 
    //if it does, error out
    //and while we are traversing the list, find the next empty space too. 
    int nPositionInList = -1; 
    for( int n = 0; n < listStr->nLast+1; n++ )
    {
        if( nPositionInList == -1 && listStr->list[n].nPos == 0 )
            nPositionInList = n;
        if( listStr->list[n].nPos == pos )
        {
            //something is already there at this position. 
            return false;
        }
    }
    if( nPositionInList == -1 )
    {
        return false;
    }
    //all set to add the element
    listStr->list[nPositionInList].nData = data;
    listStr->list[nPositionInList].nPos = pos;
    return true;
}

void DeleteElemAtPos(LIST* listStr)
{
    if( !listStr )
        return;

    int pos = -1; 
    cout << "Enter position of element to delete: " << endl;
    cin >> pos;

    if( pos == 0 )
    {
        cout << "Invalid Position." << endl;
        return;
    }

    if( listStr->nLast <= 0 )
    {
        cout << "List is empty." << endl;
           return;
    }    

    //assumption: the list does not contain duplicate elements with the same position.
    int posToDelete = -1;
    //find the element that needs to be deleted.
    for( int n = 0; n < listStr->nLast+1; n++ )
    {
        if( listStr->list[n].nPos == pos )
        {
            posToDelete = n; 
            break;
        }
    }
    if( posToDelete == -1 )
    {
        cout << "Could not find element with position [" << pos << "]." << endl;
        return;
    }
    cout << "Element at position [" << pos << "] will be deleted." << endl; 
    //Delete the element at the position by overwriting this with elements after it. 
    for( int n = posToDelete; n < listStr->nLast; n++ )
    {
        listStr->list[n].nData = listStr->list[n+1].nData;
        listStr->list[n].nPos = listStr->list[n+1].nPos;
    }
    //one element less from the array. 
    listStr->nLast--; 
}