ChangeSorter.cpp #5

// ChangeSorter.cpp: implementation of the ChangeSorter class.
//
//////////////////////////////////////////////////////////////////////

#include "stdhdrs.h"
#include "strbuf.h"
#include "changesorter.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

ChangeSorter::ChangeSorter()
{
	head = NULL;
	seek = NULL;
	tail = NULL;
	counter = 0;
	size = 0;
}

ChangeSorter::~ChangeSorter()
{
	if (head != NULL) delete head;
}

void ChangeSorter::AddChange(StrBuf input)
{
	if (head == NULL) //empty list?
	{
		head = new ChangeNode(input);
		seek = head;
		tail = head;
		counter = 1;
		size = 1;
		return;
	} 
	if ((input == head->change) || (input == seek->change) || (input == tail->change)) 
		return; //value is already in the list, so add nothing

	ChangeNode* newnode = new ChangeNode(input);
	
	bool fwd;
	int n = newnode->value;
	int h = head->value;
	int s = seek->value;
	int t = tail->value;

	if (n < h)  // new node is before head
	{
		newnode->next = head;
		head->prev = newnode;
		head = newnode;
		counter++;
		size++;
		return;
	}
	else if (t < n) // new node is after tail
	{
		newnode->prev = tail;
		tail->next = newnode;
		tail = newnode;
		size++;
		return;
	}
	else if (n < s) //new node is between head and seek
	{
		if ( (n - h) > (s - n) ) //closer to seek
		{
			fwd = false;
		}
		else					//closer to head
		{
			seek = head;
			counter = 1;
			fwd = true;
		}
	}
	else if (s < n) // new node is between seek and tail
	{
		if ( (n - s) > (t - n) ) //closer to tail
		{
			fwd = false;
			seek = tail;
			counter = size;
		}
		else					//closer to seek
		{
			fwd = true;
		}
	}
	else exit(1);  // ChangeSorter invariant violated!

	if (fwd) // new node goes somewhere after seek
	{
		while (seek)
		{
			if (seek->value == n) return;
			else if (n < seek->value) //insert before seek
			{
				newnode->prev = seek->prev;
				newnode->next = seek;
				newnode->prev->next = newnode;
				newnode->next->prev = newnode;
				counter++;
				size++;
				return;
			}
			else
			{
				seek = seek->next;
				counter++;
			}
		}
	}
	else   // new node goes somewhere before seek
	{
		while (seek)
		{
			if (seek->value == n) return;
			else if (seek->value < n) //insert after seek
			{
				newnode->prev = seek;
				newnode->next = seek->next;
				newnode->prev->next = newnode;
				newnode->next->prev = newnode;
				size++;
				return;
			}
			else
			{
				seek = seek->prev;
				counter--;
			}
		}
	}
}

int ChangeSorter::GetPos(StrBuf input)
{
	if ((head == NULL) || (seek == NULL) || (tail == NULL)) return 0;

	int n = atoi((const char*) input.Text());
	int h = head->value;
	int s = seek->value;
	int t = tail->value;

	if (n == h) return 1;
	if (n == s) return counter;
	if (n == t) return size;
	if ((n < h) || (t < n)) return 0;

	bool fwd;

	if (n < s) //before seek
	{
		if ( (n - h) < (s - n) ) //closer to head
		{
			seek = head;
			counter = 1;
			fwd = true;
		}
		else					//closer to seek
		{
			fwd = false;
		}
	}
	else	//after seek
	{
		if ( (n - s) < (t - n) ) //closer to seek
		{
			fwd = true;
		}
		else					//closer to tail
		{
			seek = tail;
			counter = size;
			fwd = false;
		}
	}

	if (fwd) //node being sought is somewhere after seek
	{
		while (seek)
		{
			if (seek->value == n) return counter;
			else if (n < seek->value) return 0; //not here
			else
			{
				seek = seek->next;
				counter++;
			}
		}
	}
	else //node being sought is before seek
	{
		while (seek)
		{
			if (seek->value == n) return counter;
			else if (seek->value < n) return 0; //not here
			else
			{
				seek = seek->prev;
				counter--;
			}
		}
	}
	return 0; //default case, shouldn't ever happen
}

StrBuf ChangeSorter::GetChange(int pos)
{
	if ((head == NULL) || (seek == NULL) || (tail == NULL)) return StrBuf();
	if ((pos < 1) || (pos > size)) return StrBuf();

	if (pos == 1) return head->change;
	if (pos == size) return tail->change;
	if (pos == counter) return seek->change;

	bool fwd;

	if (pos < counter) //before seek
	{
		if ( (pos - 1) < (counter - pos) ) //closer to head
		{
			seek = head;
			counter = 1;
			fwd = true;
		}
		else					//closer to seek
		{
			fwd = false;
		}
	}
	else	//after seek
	{
		if ( (pos - counter) < (size - pos) ) //closer to seek
		{
			fwd = true;
		}
		else					//closer to tail
		{
			seek = tail;
			counter = size;
			fwd = false;
		}
	}

	if (fwd) //node being sought is somewhere after seek
	{
		while (seek)
		{
			if (counter == pos) return seek->change;
			else if (pos < counter) return StrBuf(); //not here
			else
			{
				seek = seek->next;
				counter++;
			}
		}
	}
	else //node being sought is before seek
	{
		while (seek)
		{
			if (counter == pos) return seek->change;
			else if (counter < pos) return StrBuf(); //not here
			else
			{
				seek = seek->prev;
				counter--;
			}
		}
	}
	return StrBuf(); //default case, shouldn't ever happen
}