// tsil by student name, CSCI 2170-sec, Due: mm/dd/yy
// PROGRAM ID: arlist.cpp / Array-based linked list example w/tsil
// AUTHOR: student name
// REMARKS: This version of "arlist" uses a dummy header node
#include <iostream>
#include "arlist.h"

using namespace std;

// Reverse the linked list
void tsil(tNode list[])
//        INOUT
{
	// ... replace this with your implementation code ...
	return;
}


// Traverse and print the contents of the linked list
void traverse(const tNode list[])
//            IN
{
	int current = list[0].next;   // index of node under current consideration

	while ( current != NONE )
	{
		cout << list[current].item << endl;
		current = list[current].next;
	}
	return;
}


// Insert an item, in non-descending sorted order, into the linked list
bool insert(tItemType newitem, tNode list[], int& n, int& avail)
//          IN                 INOUT         INOUT   INOUT
{
	int freeSpot;          // index of a node available for storage
	int current;           // index of node under current consideration
	int previous = 0;      // index of prior node; dummy header has index 0

	freeSpot = PopAvail(list, avail);
	if (freeSpot == NONE)
		return false;
	else
	{
		// insert new item into array
		list[freeSpot].item = newitem;
		// traverse the list
		current = list[previous].next;
		while ( current != NONE  &&  list[current].item < newitem )
		{
			previous = current;
			current = list[current].next;
		}
		// update the "next" values
		list[freeSpot].next = list[previous].next;
		list[previous].next = freeSpot;
		++n;
		return true;
	}
}


// Remove specified target, if it exists, from the linked list
bool remove(tItemType target, tNode list[], int& n, int& avail)
//          IN                INOUT         INOUT   INOUT
{
	int current;           // index of node under current consideration
	int previous = 0;      // index of prior node; dummy header has index 0

	current = list[0].next;
	while ( current != NONE  &&  list[current].item < target )
	{
		previous = current;
		current = list[current].next;
	}
	if (n>0 && list[current].item == target)
	{
		list[previous].next = list[current].next;
		PushAvail(list, current, avail);
		--n;
		return true;
	}
	else
	{
		return false;
	}
}


// Initialize the array's free space (avail) entries
void init(tNode list[], int& n, int& avail, int capacity)
//        OUT           OUT     OUT         IN
{
	// Initialize dummy node to show empty storage list
	list[0].next = NONE;
	n = 0;

	// Link all the nodes into a "free" list
	avail = 1;
	for (int i=avail; i<capacity; ++i)
		list[i].next = i+1;
	list[capacity].next = NONE;
}


// Return the next available free spot in the array
int  PopAvail(tNode list[], int& avail)
//            INOUT         INOUT
{
	int freeSpot = avail;
	avail = list[avail].next;
	return freeSpot;
}

// Release a node in the array and make it a free spot
void PushAvail(tNode list[], int pos, int& avail)
//             INOUT         IN       INOUT
{
	list[pos].next = avail;
	avail = pos;
}