This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 

  Templated List Routines
  Submitted by



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)


Download Associated File: ListUtils.h (12,193 bytes)

/*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'msurprised 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) anddefine a few operators for that data type. Allocation and deallocationis done by the caller. Note, this code also assumes that your next-itempointer 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 completenesstemplate <class TItem>inline TItem *headPeek(TItem *head) {	return head;}// Returns last itemtemplate <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 sortedtemplate <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 listtemplate <class TItem>inline int ListCount(TItem *head) {	int count = 0;	while (head != NULL) {		++count;		head = head->next;	}	return count;}// Reverses the listtemplate <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 headtemplate <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 tailtemplate <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 deallocationtemplate <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 listtemplate <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 deallocationtemplate <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 onlytemplate <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 onlytemplate <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 memorytemplate <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 memorytemplate <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) : Stabletemplate <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) : Stabletemplate <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) : Stabletemplate <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) : Stabletemplate <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 

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.