OSDev.org

Code: Select all

#include "linked_array_list.h"
#include <iostream>

using namespace std;

//function main
//PRECONDITIONS: As a testing function, there is minimal error checking
//				 for valid user input so care should be taken when using
//POSTCONDITIONS: Modifies the linked_array_list object as requested 
//                until the program is exited
int main()
{
	linked_array_list mylist;
	char input = ' ';
	int tmp;
	cout << "**linked_array_list testing program**" << endl;
	while (input != 'q')
	{
		cout << endl << "Select one of the following options: " << endl;
		cout << "[i]nsert an integer value into the list" << endl;
		cout << "[d]elete an integer value from the list" << endl;
		cout << "[v]iew the current contents of the list" << endl;
		cout << "[q]uit" << endl;
		cin >> input;
		switch(input)
		{
			case 'i':
				cout << endl << "Enter a number to add to the list: ";
				cin >> tmp;
				mylist.insert_data(tmp);
				break;
			case 'd':
				cout << endl << "Enter a number to delete from the list: ";
				cin >> tmp;
				mylist.delete_data(tmp);
				break;
			case 'v':
				cout << endl << mylist << endl;
				break;
			case 'q':
				break;
			default:
				cerr << endl << "That is not a valid choice" << endl;
				break;
		}
	}
	system("PAUSE");
	return 0;
}

Code: Select all

#ifndef _LINKED_ARRAY_LIST_H
#define _LINKED_ARRAY_LIST_H

#include "array_node.h"
#include <iostream>

class linked_array_list {
public:
	//CONSTRUCTOR for the linked_array_list class
	linked_array_list();
	linked_array_list(const int& new_data);
	//DESTRUCTOR for the linked_array_list class
	~linked_array_list();
	//MEMBER FUNCTIONS for the linked_array_list class
	void insert_data(const int& new_data);
	void delete_data(const int& data_value);
	//NON-MEMBER FUNCTIONS for the linked_array_list class
	friend std::ostream& operator <<(std::ostream& output, const linked_array_list& lal);
private:
	//PRIVATE MEMBER FUNCTIONS for the linked_array_list class
	void consolidate_array_nodes();
	array_node* head_pointer;
	array_node* tail_pointer;
};

#endif

Code: Select all

#include "linked_array_list.h"

linked_array_list::linked_array_list()
{
	head_pointer = new array_node();
	tail_pointer = head_pointer;
}

linked_array_list::linked_array_list(const int& new_data)
{
	head_pointer = new array_node(new_data);
	tail_pointer = head_pointer;
}

linked_array_list::~linked_array_list()
{
	array_node* tmp;
	while(head_pointer != NULL)
	{
		tmp = head_pointer;
		head_pointer = head_pointer->get_link();
		delete tmp;
	}
}

void linked_array_list::insert_data(const int& new_data)
{
	array_node* tmp;
	//check if the data can be stored in an existing node
	for (tmp = head_pointer; tmp != NULL; tmp = tmp->get_link())
	{
		if (tmp->insert_data(new_data))
			return;
	}
	//if no free space found, create a new node to store the data
	tmp = new array_node(new_data);
	tail_pointer->set_link(tmp);
	tail_pointer = tmp;
}

void linked_array_list::delete_data(const int& data_value)
{
	array_node* tmp;
	//loop through the nodes, deleting all instances of the data_value
	for (tmp = head_pointer; tmp != NULL; tmp = tmp->get_link())
		tmp->delete_data(data_value);
	//check if any nodes can be eliminated
	consolidate_array_nodes();
}


//TODO: This code is still problematic
//some corrupted data sometimes finds its way into the nodes 
void linked_array_list::consolidate_array_nodes()
{
	//if only one node exists, there is no need to consolidate
	if (head_pointer == tail_pointer)
		return;
	//loop through the nodes, looking for half-empty nodes
	array_node* tmp_node = head_pointer;
	for (; tmp_node != NULL; tmp_node = tmp_node->get_link())
	{
		//a half-empty node found
		if (tmp_node->get_no_free() >= tmp_node->get_no_used())
		{
			//check for adequate free space in other nodes
			size_t free_spaces = 0;
			array_node* tmp_node2 = head_pointer;
			for (; tmp_node2 != NULL; tmp_node2 = tmp_node2->get_link())
			{
				if (tmp_node2 != tmp_node)
					free_spaces += tmp_node2->get_no_free();
			}
			if (free_spaces >= tmp_node->get_no_used())
			{
				//we need to break the node from the list
				if (tmp_node != head_pointer)
				{
					tmp_node2 = head_pointer;
					for (; tmp_node2->get_link() != tmp_node; tmp_node2 = tmp_node2->get_link());
					tmp_node2->set_link(tmp_node->get_link());
					if (tmp_node == tail_pointer)
						tail_pointer = tmp_node2;
				}
				else
					head_pointer = tmp_node->get_link();
				//redistribute the node's data
				unsigned i = 0;
				int* tmp_data = tmp_node->get_data();
				tmp_node2 = head_pointer;
				for (; i < tmp_node->get_no_used(); tmp_node2 = tmp_node2->get_link())
				{
					while (tmp_node2->insert_data(tmp_data[i]))
						++i;
				}
				//a little housekeeping here
				array_node* tmp_delete = tmp_node;
				int* tmp_delete_data = tmp_data;
				tmp_node = head_pointer;
				delete tmp_delete;
				delete tmp_delete_data;
			}
		}
	}
}

std::ostream& operator <<(std::ostream& output, const linked_array_list& lal)
{
	unsigned i = 1;
	array_node* tmp = lal.head_pointer;
	//loop through the nodes, adding its data to the ostream
	for (; tmp != NULL; tmp = tmp->get_link())
	{
		output << "Node " << i << std::endl;
		output << *tmp << std::endl;
		++i;
	}
	return output;
}

Code: Select all

#ifndef _ARRAY_NODE_H
#define _ARRAY_NODE_H

#include <bitset>
#include <iostream>

class array_node{
public:
	//CONSTRUCTOR for the array_node class
	array_node();
	array_node(const int& initial_data);
	//ACCESSORS for the array_node class
	void set_link(array_node* new_link);
	array_node* get_link();
	//MEMBER FUNCTIONS for the array_node class
	bool insert_data(const int& new_data);
	void delete_data(const int& data_value);
	int* get_data();
	size_t get_no_free();
	size_t get_no_used();
	//NON-MEMBER FUNCTIONS for the array_node class
	friend std::ostream& operator <<(std::ostream& output, const array_node& anode);
private:
	static const size_t MAX_SIZE = 5;
	int data[MAX_SIZE];
	array_node* link;
	std::bitset<MAX_SIZE> elements_used;
};

#endif

Code: Select all

#include "array_node.h"

array_node::array_node()
:link(NULL)
{}

array_node::array_node(const int& initial_data)
:link(NULL)
{
	data[0] = initial_data;
	elements_used.flip(0);
}

void array_node::set_link(array_node* new_link)
{
	link = new_link;
}

array_node* array_node::get_link()
{
	return link;
}

bool array_node::insert_data(const int& new_data)
{
	//if true, no free array spots available
	if (elements_used.count() == MAX_SIZE)
		return false;
	//else, look for a free spot to insert the data
	size_t i;
	for (i = 0; i < MAX_SIZE; ++i)
	{
		if (!elements_used[i])
		{
			data[i] = new_data;
			elements_used.flip(i);
			return true;
		}
	}
	//this line should never be reached
	return false;
}

void array_node::delete_data(const int& data_value)
{
	//search for data matching data_value
	//if found, free it's space
	size_t i;
	for (i = 0; i < MAX_SIZE; ++i)
	{
		if (data[i] == data_value)
			elements_used.flip(i);
	}
}

int* array_node::get_data()
{
	//set up a container array
	int* data_array = new int[elements_used.count()];
	//fill the temp array with node values
	size_t i, j = 0;
	for (i = 0; i < MAX_SIZE; ++i)
	{
		if (elements_used[i])
		{
			data_array[j] = data[i];
			++j;
		}
	}
	return data_array;
}

size_t array_node::get_no_free()
{
	return MAX_SIZE - elements_used.count();
}

size_t array_node::get_no_used()
{
	return elements_used.count();
}

std::ostream& operator <<(std::ostream& output, const array_node& anode)
{
	size_t i;
	//fill up the ostream in the same manner
	//as the array with get_data()
	for (i = 0; i < array_node::MAX_SIZE; ++i)
	{
		if (anode.elements_used[i])
			output << anode.data[i] << " ";
	}
	output << std::endl;
	return output;
}