/*
Hello again flipcoders. To compliment my recently posted array routines,
here's my assortment of useful templated list routines.
Some of these are quite basic routines, some are not, however i'm
surprised by how many people have trouble writing basic list routines.
I'm fairly sure these are also bug free, (I've tested them thoroughly)
but if you find a bug, or have other suggestions or comments, let me know.
If nothing more these should be very useful to beginners.
To use these all you need to do is have a list (any type) and
define a few operators for that data type. Allocation and deallocation
is done by the caller. Note, this code also assumes that your next-item
pointer is called 'next'.

For example given the following data type:

typedef unsigned short keyType;
typedef struct item {
	item *next;
	keyType key;
	long foo;
	char bar;
};

The routines will require that you define the following:

inline int operator <  (item &a, item &b) {return a.key < b.key;}
inline int operator == (item &a, item &b) {return a.key == b.key;}

If the key is not the entire item, also define these:

inline int operator <  (item &a, keyType b) {return a.key < b;}
inline int operator == (item &a, keyType b) {return a.key == b;}

You can then use the routines below like this:

item *myList = NULL;
for (int i=1; i<100; ++i) {
	item *addMe = new item;
	item.key = rand();
  Push(myList, addMe);
}
MergeSort(myList);

I hope the rest is mostly self-explanatory.
Written on a Mac using Symantec C++ v8.6.
Permission to use/copy/modify/distribute hereby granted.

[NZ]_i/\/\alc
(Malcolm)
*/

#ifndef MyListUtils
#define MyListUtils

//This macro is a trick of mine I've never seen used before, it provides a fake
//previous-item pointer for the head of the list, so that the special case of
//removing an item from the head of the list etc, is eliminated.
//However only prev->next actually exists. Accessing the other fields would be bad.
//T is the node type, H is the head variable, N is the name of the next ptr.
#define fakePrev(T, H, N) (T*)(((unsigned long)&H) + ((unsigned long)H) - ((unsigned long)&H->N))

//#define USE_TAIL true //Uncomment if you also wish to keep track
		//of the end of the list so that inserting at the end is faster.

// *** Utilities ***
// Returns first item, pointless yeah, but here for completeness
template <class TItem>
inline TItem *headPeek(TItem *head) {
	return head;
}

// Returns last item
template <class TItem>
TItem *tailPeek(TItem *head) {
	TItem *curr = head, *prev = NULL;
	while (curr != NULL) {
		prev = curr;
		curr = curr->next;
	}
	return prev;
}

// Returns true if the list is sorted
template <class TItem>
Boolean Sorted(TItem *head) {
	if (head != NULL) {
		item *other = head->next;
		while (other != NULL) {
			if (*other < *head) return false;
			head = other;
			other = other->next;
		}
	}
	return true;
}

// Returns the number of items in the list
template <class TItem>
inline int ListCount(TItem *head) {
	int count = 0;
	while (head != NULL) {
		++count;
		head = head->next;
	}
	return count;
}

// Reverses the list
template <class TItem>
void Reverse(TItem *&head
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
	if (head != NULL) {
#ifdef USE_TAIL
  tail = head;
#endif
		TItem *newList = head, *oldList = head->next, *temp;
		newList->next = NULL;
		while (oldList != NULL) {
			temp = oldList;
			oldList = oldList->next;
			temp->next = newList;
			newList = temp;
		}
		head = newList;
	}
}

// Insert a caller-allocated item at the head
template <class TItem>
void Push(TItem *&head, TItem *ins
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
#ifdef USE_TAIL
  if (head == NULL) tail = ins;
#endif
	ins->next = head;
	head = ins;
}

// Insert a caller-allocated item at the tail
template <class TItem>
void Put(TItem *&head, TItem *ins
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
#ifdef USE_TAIL
  if (head == NULL) {
  	head = ins;
  } else {
  	tail->next = ins;
  }
	tail = ins;
#else
	TItem *curr = head, *prev = fakePrev(TItem, head, next);//= NULL;
	while (curr != NULL) {
		prev = curr;
		curr = curr->next;
	}
	/*if (prev == NULL) //fakePrev eliminates this
		head = ins;
	else*/
		prev->next = ins;	
#endif
	ins->next = NULL;
}

// Take off item at the head - caller responsible for deallocation
template <class TItem>
TItem *Pop(TItem *&head
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
	TItem *temp = head;
	if (head != NULL)
		head = head->next;
#ifdef USE_TAIL
	if (head == NULL) tail = NULL;
#endif
	return temp;
}

// Insert a caller-allocated item into an ordered list
template <class TItem>
void Insert(TItem *&head, TItem *ins
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
	TItem *curr = head, *prev = fakePrev(TItem, head, next);//= NULL;
	while (curr != NULL) {
		if (*ins < *curr) break;
		prev = curr;
		curr = curr->next;
	}
	/*if (prev == NULL) //fakePrev eliminates this
		head = ins;
	else*/
		prev->next = ins;	
	ins->next = curr;
#ifdef USE_TAIL
	if (curr == NULL) tail = ins;
#endif
}

// Remove selected item - caller responsible for deallocation
template <class TItem>
void Remove(TItem *&head, TItem *rem
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
	TItem *curr = head, *after, *prev = fakePrev(TItem, head, next);//= NULL;
	while (curr != NULL) {
		after = curr->next;
		if (curr == rem) {
			/*if (prev == NULL) //fakePrev eliminates this
				head = ins;
			else*/
				prev->next = after;
#ifdef USE_TAIL
			if (head == NULL) tail = NULL;
#endif
			break;
		}
		prev = curr;
		curr = after;
	}
}

// *** Searching ***
// O(n) : sorted only
template <class TItem, class TKey>
TItem *SortedSequentialSearch(TItem *head, TKey find) {
	for (; head != NULL; head = head->next)
		if (*head < find)
			continue;
		else if (*head == find)
			return head;
		else
			return NULL;
	return NULL;
}

// O(n)
template <class TItem, class TKey>
inline TItem *SequentialSearch(TItem *head, TKey find) {
	for (; head != NULL; head = head->next)
		if (*head == find)
			return head;
	return NULL;
}

// *** Combining ***
// O(m+n) : both lists sorted only
template <class TItem>
TItem *MergeLists(TItem *head1, TItem *head2
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
	if (head1 == NULL) {
#ifdef USE_TAIL
			tail = tailPeek(head2);
#endif
		return head2;
	}
	if (head2 == NULL) {
#ifdef USE_TAIL
			tail = tailPeek(head1);
#endif
		return head1;
	}
	TItem *combined = NULL, *newTail = fakePrev(TItem, combined, next);
	do {
		if (*head1 < *head2) {
			newTail->next = head1;
			newTail = head1;
			head1 = head1->next;
			if (head1 != NULL) continue;
			newTail->next = head2;
#ifdef USE_TAIL
			tail = tailPeek(newTail);
#endif
			return combined;
		} else {
			newTail->next = head2;
			newTail = head2;
			head2 = head2->next;
			if (head2 != NULL) continue;
			newTail->next = head1;
#ifdef USE_TAIL
			tail = tailPeek(newTail);
#endif
			return combined;
		}
	} while (true);
}

// *** Sorting ***
// O(nlogn) : uses stack memory
template <class TItem>
void MergeSort(TItem *&head
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
	if (head != NULL) {
		if (head->next != NULL) { //Must be at least 2 items
			TItem *oldhead=head, *heads[2], *tails[2];
			int sortMore[2], largest, appendWhichList;
			sortMore[0] = sortMore[1] = false;
			heads[0] = tails[0] = oldhead; oldhead = oldhead->next;
			heads[1] = tails[1] = oldhead; oldhead = oldhead->next;
			largest = (*tails[1] < *tails[0] ? 0 : 1);
			while (oldhead != NULL) { //Split up old list
				if (*tails[largest] < *oldhead) {
					appendWhichList = largest;
				} else if (*oldhead < *tails[1-largest]) {
					appendWhichList = largest;
					sortMore[largest] = true;
					largest = 1-largest;
				} else {
					appendWhichList = 1-largest;
				}
				tails[appendWhichList]->next = oldhead;
				tails[appendWhichList] = oldhead;
				oldhead = oldhead->next;
			}
			tails[0]->next = NULL;
			if (sortMore[0]) MergeSort(heads[0]
#ifdef USE_TAIL
			, tails[0]
#endif
			);
			tails[1]->next = NULL;
			if (sortMore[1]) MergeSort(heads[1]
#ifdef USE_TAIL
			, tails[1]
#endif
			);
			head = MergeLists(heads[0], heads[1]
#ifdef USE_TAIL
			, tail
#endif
			);
		}
	}
}

template <class TItem>
TItem *QuickSortAux(TItem *&head) {
	TItem *curr = head->next;
	if (curr != NULL) {
		TItem *center = head, *less = NULL, *greater = NULL;
		do {
			TItem *after = curr->next;
			if (*curr < *center) {
				curr->next = less;
				less = curr;
			} else {
				curr->next = greater;
				greater = curr;
			}
			curr = after;
		} while (curr != NULL);
		if (less != NULL) {
			TItem *last = QuickSortAux(less);
			last->next = center;
			head = less;
		} else {
			head = center;
		}
		if (greater != NULL) {
			TItem *last = QuickSortAux(greater);
			center->next = greater;
			return last;
		} else {
			center->next = NULL;
			return center;
		}
	}
	return head;
}
// O(nlogn) .. O(n^2) : uses stack memory
template <class TItem>
inline void QuickSort(TItem *&head
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
#ifndef USE_TAIL
  TItem *tail;
#endif
	if (head != NULL) 
		tail = QuickSortAux(head);
}

// O(n) .. O(n^2) : Stable
template <class TItem>
void InsertionSort(TItem *&head
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
	TItem *newList = NULL, *oldList = head, *temp, *curr, *prev;
	while (oldList != NULL) {
		temp = oldList;
		oldList = oldList->next;		
		curr = newList, prev = fakePrev(TItem, newList, next);
		while (curr != NULL) {
			if (*temp < *curr) break;
			prev = curr;
			curr = curr->next;
		}
		prev->next = temp;	
		temp->next = curr;
#ifdef USE_TAIL
		if (curr == NULL) tail = temp;
#endif
	}
	head = newList;
}

// O(n^2) : Stable
template <class TItem>
void DualSelectionSort(TItem *&head
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
	TItem *unsortedhead=head, *curr, *prev;
	TItem *highhead=NULL, *hightail=NULL, *currhighprev, *movehigh;
	TItem *lowhead=NULL, *lowtail=NULL, *currlowprev, *movelow;
	while (unsortedhead != NULL) {
		curr = unsortedhead;
		currlowprev = currhighprev = prev = fakePrev(TItem, unsortedhead, next);
		do {
			if (*curr < *currlowprev->next)
				currlowprev = prev;
			//if (*currhighprev->next < *curr) //Faster, non-stable
			if (!(*curr < *currhighprev->next)) //Slower, Stable
				currhighprev = prev;
			prev = curr;
			curr = curr->next;
		} while (curr != NULL);		
		if (currlowprev == currhighprev)
			break;
		movehigh = currhighprev->next;
		movelow = currlowprev->next;
		if (movehigh == currlowprev)
			currlowprev = currhighprev;
		currhighprev->next = movehigh->next;
		currlowprev->next = movelow->next;
		if (highhead == NULL) hightail = movehigh;
		movehigh->next = highhead;
		highhead = movehigh;
		if (lowhead == NULL) {
			lowhead = movelow;
		} else {
			lowtail->next = movelow;
		}
		lowtail = movelow;
	}
	if (lowhead != NULL) {
		head = lowhead;
		if (unsortedhead != NULL) {
			lowtail->next = unsortedhead;
			prev->next = highhead;
		} else {
			lowtail->next = highhead;
		}
	#ifdef USE_TAIL
		tail = hightail;
	#endif
	}
}

// O(n^2) : Stable
template <class TItem>
void SelectionSort(TItem *&head
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
	TItem *unsortedhead=head, *curr, *prev;
	TItem *lowhead=NULL, *lowtail=NULL, *currlowprev, *movelow;
	while (unsortedhead != NULL) {
		curr = unsortedhead;
		currlowprev = prev = fakePrev(TItem, unsortedhead, next);
		do {
			if (*curr < *currlowprev->next)
				currlowprev = prev;
			prev = curr;
			curr = curr->next;
		} while (curr != NULL);		
		movelow = currlowprev->next;
		currlowprev->next = movelow->next;
		if (lowhead == NULL)
			lowhead = movelow;
		else
			lowtail->next = movelow;
		lowtail = movelow;
	}
	head = lowhead;
#ifdef USE_TAIL
	tail = lowtail;
#endif
}

// O(n^2) : Stable
template <class TItem>
void BubbleSort(TItem *&head
#ifdef USE_TAIL
  , TItem *&tail
#endif
) {
	TItem *stophere = NULL;
	while (head != stophere) {
		TItem *curr = head, *prev = fakePrev(TItem, head, next);
		TItem *after = curr->next;
		while (after != stophere) {
			if (*after < *curr) {
				curr->next = after->next;
				prev->next = after;
				after->next = curr;
			}
			prev = curr;
			curr = after;
			after = after->next;
		}
#ifdef USE_TAIL
		if (stophere == NULL) tail = curr;
#endif
		stophere = curr;
	}
}

#endif