My permute_append class.

linked_list.h

/* Joe Pea - Assignment 5 */

// FILE: linked_list.h 
// TEMPLATE CLASS PROVIDED:
//   sequence<Item> (part of the namespace CISP430_A3)
//   This is a container class for a sequence of items,
//   where each List may have a designated item called the current item).
//   The template parameter <value_type> is the data type of the items
//   in the List. It may be any of the C++ built-in types (int, char, etc.),
//   or a class with a default constructor, an assignment operator,
//   and a copy constructor.
//
// TYPEDEFS and MEMBER CONSTANTS for the sequence class:
//   sequence<Item>::value_type
//     Thisis the data type of the items in the sequence. It
//     may be any of the C++ built-in types (int, char, etc.), or a class with a
//     default constructor, an assignment operator, and a copy constructor.
//
// CONSTRUCTOR for the sequence<Item> class:
//   sequence( )
//     Postcondition: The sequence has been initialized as an empty sequence.
//
// MODIFICATION MEMBER FUNCTIONS for the sequence<Item> class:
//   void start( )
//     Postcondition: The first item on the sequence becomes the current item
//     (but if the sequence is empty, then there is no current item).
//
//   void advance( )
//     Precondition: is_item returns true.
//     Postcondition: If the current item was already the last item in the
//     sequence, then there is no longer any current item. Otherwise, the new
//     current item is the item immediately after the original current item.
//
//   void insert(const value_type& entry)
//     Postcondition: A new copy of entry has been inserted in the sequence
//     before the current item. If there was no current item, then the new entry 
//     has been inserted at the front of the sequence. In either case, the newly
//     inserted item is now the current item of the sequence.
//
//   void attach(const value_type& entry)
//     Postcondition: A new copy of entry has been inserted in the sequence after
//     the current item. If there was no current item, then the new entry has 
//     been attached to the end of the sequence. In either case, the newly
//     inserted item is now the current item of the sequence.
//
//   void remove_current( )
//     Precondition: is_item returns true.
//     Postcondition: The current item has been removed from the sequence, and
//     the item after this (if there is one) is now the new current item.
//
// CONSTANT MEMBER FUNCTIONS for the sequence<Item> class:
//   size_t size( ) const
//     Postcondition: The return value is the number of items in the sequence.
//
//   bool is_item( ) const
//     Postcondition: A true return value indicates that there is a valid
//     "current" item that may be retrieved by activating the current
//     member function (listed below). A false return value indicates that
//     there is no valid current item.
//
//   value_type current( ) const
//     Precondition: is_item( ) returns true.
//     Postcondition: The item returned is the current item in the sequence.
//
// VALUE SEMANTICS for the sequence class:
//    Assignments and the copy constructor may be used with sequence objects.

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <cstdlib>  // Provides size_t
#include <string>	// allows usage of the string type
#include "node.h"  // Provides node class
using namespace std;

namespace CISP430_A5
{
    template <typename Item>
    class linked_list
	/*TODO: * Optimize so that we don't have to iterate through each address to reach a desired position.
			  Make a "position" field for each Node object or something?
			  Or create a "last_position" variable in this class so we can iterate forward
			  or backward from the last position instead of from the beginning each time?
			* Add or modify post and pre conditions above for all the functions.
	*/
	/**
			The /*REMOVED*//*, /*STAYS THE SAME*//*, and /*ADDED*//* comments show the 
			differences in converting from the sequence class to the linked_list class.
	*/
    {
		public:
		/* TYPEDEFS and MEMBER CONSTANTS: */
			typedef Item value_type;
			
		
		
		/* CONSTRUCTORS and DESTRUCTOR: */
			linked_list( );
			linked_list(const linked_list& source);
			~linked_list( );
			
		
		
		/* MODIFICATION MEMBER FUNCTIONS */
			/*ADDED:*/
				value_type get(size_t position); // get item at position x
				void set(size_t position, const value_type& entry); // set item at position x, if past boundaries, just modify at beginning or at end.
				void add(const value_type& entry); // add to the end of list
				void insert(size_t position, const value_type& entry); // set item at position x, if past boundaries, just insert at beginning or attach at end.
				void attach(size_t position, const value_type& entry); // set item at position x, if past boundaries, just insert at beginning or attach at end.
				void remove(size_t position);
		
			/*REMOVED:*/
				/*void remove_current( );*/
				/*void start( );*/
				/*void advance( );*/
				/*void insert(const value_type& entry);*/
				/*void attach(const value_type& entry);*/
		
			/*STAYS THE SAME:*/
				void operator=(const linked_list& source);
			
		
		
		/* CONSTANT MEMBER FUNCTIONS */
			/*STAYS THE SAME:*/
				value_type current( ) const;
				size_t size( ) const { return many_nodes; }
				bool is_item( ) const { return (cursor != NULL); }

		
		
		private:
		/*PRIVATE HELPER FUNCTIONS*/
			/*ADDED:*/
				void remove_current( );
				void start( );
				void advance( );
				void insert_here(const value_type& entry); // same as insert() from sequence. insert at current position.
				void attach_here(const value_type& entry); // same as attach() from sequence. attach at current position.
		
		
		
		/*PRIVATE VARIABLES*/	
			/*STAYS THE SAME:*/
				node<Item> *cursor;
				node<Item> *precursor;
				node<Item> *head_ptr;
				node<Item> *tail_ptr;
				size_t many_nodes;
    };

	
	
	
	
	
	
	/*Linked List Tools*/
	template <typename Item>
	linked_list<Item> list_splice(linked_list<Item> &input, size_t offset, size_t length);
	template <typename Item>
	linked_list<Item> list_splice(linked_list<Item> &input, size_t offset, size_t length, Item new_item);
	template <typename Item>
	linked_list<Item> list_splice(linked_list<Item> &input, size_t offset, size_t length, linked_list<Item> new_items);
	
	/*template prefix not needed here since the second parameter names a specific type for the linked_list*/
	string charList_join(const char* glue, linked_list<char> pieces);
	
	template <typename Item>
	typename linked_list<Item>::value_type list_pop(linked_list<Item> list);
}





/* Sample usage:
int main(void) {

	linked_list items = new linked_list;
	items.attach(10);
	items.insert(30);
	items.attach(20);
	items.insert(40);

	// for each item in the list:
	for (int i=0; i<items.size(); ++i) {
		cout << items.get(i) << endl;
	}
	
	items.set(2, 50);
	// item at position 2 is now 50.
}
*/




// The implementation of a template class must be included in its header file:
#include "linked_list.template"
#endif

linked_list.template

/* Joe Pea - CISP430 Assignment 5 */

namespace CISP430_A5 {
/*I've marked lines/blocks as REMOVED or ADDED in order to tell what I changed
	from the sequence class to create my ideal linked_list class*/
/*TODO: Add previous field to Node class and remove usage of precursor.*/
			
	/* CONSTRUCTORS and DESTRUCTOR */
	
	template <typename Item>
	linked_list<Item>::linked_list() {
		head_ptr = NULL;
		tail_ptr = NULL;
		cursor = NULL;
		precursor = NULL; // no need for this if Node objects have a "previous" link field.
		many_nodes = 0;
	}
	
	template <typename Item>
	linked_list<Item>::linked_list( const linked_list& source ) { // copier
		
		int src_size = source.size(); // to replicate cursor position
		int many_til_end = 0; // to replicate cursor position
		int many_til_mid = 0; // to replicate cursor position
		node<Item> *src_cursor = source.cursor; // to replicate cursor position
		
		list_copy(source.head_ptr, head_ptr, tail_ptr);
		
		/*replicate the size value (before cursor position because functions used for that depend on many_nodes value*/
			many_nodes = source.many_nodes;
		
		/*replicate the cursor position*/
			if (src_cursor != NULL) {
				while (src_cursor != NULL) {
					++many_til_end;
					src_cursor = src_cursor->link();
				}
				many_til_mid = src_size - many_til_end; // this is how many to advance to replicate cursor position.
				start(); // put this.cursor at beginning. // DEPENDS ON VALUE OF many_nodes ABOVE
				for (int i=0; i<many_til_mid; ++i) {
					advance(); // DEPENDS ON VALUE OF many_nodes ABOVE
				}
				/* after the for loop, the new linked_list's cursor should be at the same position as the source's cursor was.*/
			}
			else {
				cursor = NULL;
				precursor = NULL;
			}
	}
	
	template <typename Item>
	linked_list<Item>::~linked_list() { // Destructor
		list_clear(head_ptr);
		head_ptr = tail_ptr = cursor = precursor = NULL;
		many_nodes = 0;
	}
			
	/* MODIFICATION MEMBER FUNCTIONS */
	
	template <typename Item>
	void linked_list<Item>::start() {
		if (many_nodes > 0) { // if at least one item exists
			cursor = head_ptr;
			precursor = NULL;
		}
	}
	
	template <typename Item>
	void linked_list<Item>::advance() {
		if (is_item()) {
			precursor = cursor;
			cursor = cursor->link();
			if ( cursor == NULL ) {
				precursor = NULL;
			}
		}
	}
	
	/*
	ADDED [
	*/
		template <typename Item>
		typename linked_list<Item>::value_type linked_list<Item>::get(size_t position) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then return item
				if (i==0)
					start();
				else
					advance();
				
				if (i==position) {
					return current();
				}
			}
		}
		
		template <typename Item>
		void linked_list<Item>::set(size_t position, const value_type& entry) {
			if (is_item()) { // only set at a valid position.
			
				insert(position, entry); // insert new item to list
				
				advance();
				remove_current(); // remove old item from list.
			}
		}
		
		template <typename Item>
		void linked_list<Item>::add(const value_type& entry) {
			cursor = precursor = NULL; // remove cursor
			attach_here(entry); // <<-- attaches at end when no cursor.
		}
		
		template <typename Item>
		void linked_list<Item>::remove(size_t position) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then insert item
				if (i==0)
					start();
				else
					advance();
				
				if (i==position) {
					remove_current();
				}
			}
		}
		
		template <typename Item>
		void linked_list<Item>::insert(size_t position, const value_type& entry) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then insert item
				if (i==0)
					start();
				else
					advance();
				
				if (i==position) {
					insert_here(entry);
				}
			}
		}
	/*
	]
	*/
	
	template <typename Item>
	void linked_list<Item>::insert_here(const value_type &entry) {
	/*REMOVED*/
		// void linked_list<Item>::insert(const value_type &entry) {
		
		/*if the list is empty*/
		if (!is_item() && !many_nodes) {
			cursor = new node<Item>(entry);
			head_ptr = cursor;
			tail_ptr = cursor;
		}
		
		/*if the list is not empty and cursor points to the first item*/
		else if (is_item() && cursor == head_ptr) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr );
			head_ptr = cursor;
		}
		
		/*if the list is not empty and there is no current item*/
		else if (!is_item() && many_nodes) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr );
			head_ptr = cursor;
		}
		
		/*if the list is not empty and the cursor points somewhere in 
			the middle(including last item)*/
		else if (is_item() && cursor != head_ptr) {
			cursor = new node<Item>( entry );
			cursor->set_link( precursor->link() );
			precursor->set_link( cursor );
		}
		
		++many_nodes; //increase the node count
	}
	
	/*ADDED*/
		template <typename Item>
		void linked_list<Item>::attach(size_t position, const value_type& entry) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then attach item
				if (i==0)
					start();
				else
					advance();
				
				if (i==position) {
					attach_here(entry);
				}
			}
		}
	
	template <typename Item>
	void linked_list<Item>::attach_here(const value_type& entry) {
	/*REMOVED*/
		// void linked_list<Item>::attach(const value_type& entry) {
		
		/*if the list is empty*/
		if (!is_item() && !many_nodes) {
			cursor = new node<Item>(entry);
			head_ptr = cursor;
			tail_ptr = cursor;
			precursor = NULL;
		}
		
		/*if the list is not empty and cursor points to the first item and there's only one item*/
		else if (is_item() && many_nodes == 1) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr->link() );
			head_ptr->set_link( cursor );
			precursor = head_ptr;
			tail_ptr = cursor;
		}
		
		/*if the list is not empty and cursor points to the first item and there's more than one item*/
		else if (is_item() && many_nodes > 1 && cursor == head_ptr ) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr->link() );
			head_ptr->set_link( cursor );
			precursor = head_ptr;
		}
		
		/*if the list is not empty and there is no current item*/
		else if (!is_item() && many_nodes) {
			cursor = new node<Item>( entry );
			tail_ptr->set_link( cursor );
			precursor = tail_ptr;
			tail_ptr = cursor;
		}
		
		/*if the list is not empty and the cursor points somewhere in 
			the middle(including last item)*/
		else if (is_item() && cursor != head_ptr) {
			if (cursor != tail_ptr) { // if cursor is not at last item
				cursor = new node<Item>( entry );
			}
			else if (cursor == tail_ptr) { // if cursor is at last item
				cursor = new node<Item>( entry );
				tail_ptr = cursor;
			}
			cursor->set_link( (precursor->link())->link() );
			(precursor->link())->set_link( cursor );
			precursor = precursor->link();
		}
		
		++many_nodes; // increase the node count
	}
	
	template <typename Item>
	void linked_list<Item>::remove_current() {
		if ( is_item() ) {
			
			/*If the cursor points to an item in the middle of the list, not tail, not head:*/
			if (cursor != head_ptr && cursor != tail_ptr) {
				precursor->set_link( cursor->link() );
				delete cursor;
				cursor = precursor->link();
			}
		
			/*If the cursor points to the first item in the list and that is the only item:*/
			else if (many_nodes == 1) {
				delete cursor;
				cursor = head_ptr = tail_ptr = precursor = NULL;
			}
			
			/*If the cursor points to the first item in the list and there is more than one item:*/
			else if ( cursor == head_ptr && many_nodes > 1) {
				cursor = cursor->link();
				delete head_ptr;
				head_ptr = cursor;
			}
			
			/*If the cursor points to the last item in the list (and there is more than one item)*/
			else if ( cursor == tail_ptr && many_nodes > 1) {
				delete cursor;
				tail_ptr = precursor;
				/* #!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!# */
				tail_ptr->set_link(NULL);
				/* #!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!# */
				precursor = cursor = NULL;
			}
			
			--many_nodes;
		}
	}
	
	template <typename Item>
	void linked_list<Item>::operator =(const linked_list& source) {
		if (this != &source) {
			list_clear(head_ptr);
			head_ptr = tail_ptr = cursor = precursor = NULL;
			many_nodes = 0;
		
			int src_size = source.size(); // to replicate cursor position
			int many_til_end = 0; // to replicate cursor position
			int many_til_mid = 0; // to replicate cursor position
			node<Item> *src_cursor = source.cursor; // to replicate cursor position
			
			list_copy(source.head_ptr, head_ptr, tail_ptr);
			
			/*replicate the size value (before cursor position because functions used for that depend on many_nodes value*/
				many_nodes = source.many_nodes;
			
			/*replicate the cursor position*/
				if (src_cursor != NULL) {
					while (src_cursor != NULL) {
						++many_til_end;
						src_cursor = src_cursor->link();
					}
					many_til_mid = src_size - many_til_end; // this is how many to advance to replicate cursor position.
					start(); // put this.cursor at beginning.
					for (int i=0; i<many_til_mid; ++i) {
						advance();
					}
					/* after the for loop, the new linked_list's cursor should be at the same position as the source's cursor was.*/
				}
				else {
					cursor = NULL;
					precursor = NULL;
				}
		}
	}
			
	/* CONSTANT MEMBER FUNCTIONS */
	
	template <typename Item>
	typename linked_list<Item>::value_type linked_list<Item>::current() const {
		if ( is_item() ) {
			return cursor->data();
		}
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

	/*LINKED LIST TOOLS*/
	template <typename Item>
	linked_list<Item> list_splice(linked_list<Item> &input, size_t offset, size_t length) {
		/*removes as many items as specified by length from the input
		  list starting from the zero-based offset. Don't try a length longer
		  than the number of remaining items (yet). Input gets modified, and the return value
		  is a new linked list consisting of the that were removed from input.*/
		  
		linked_list<Item> spliced;
		
		for (int i=offset; i<offset+length; ++i) {
			spliced.add( input.get(i) );
			input.remove(i);
		}
		
		return spliced;
	}
	template <typename Item>
	linked_list<Item> list_splice(linked_list<Item> &input, size_t offset, size_t length, Item new_item) {
		/*removes as many items as specified by length from the input
		  list starting from the zero-based offset. Don't try a length longer
		  than the number of remaining items (yet). Input gets modified, and the return value
		  is a new linked list consisting of the that were removed from input.
		  Additionally, new_item has been put in place of the items that were removed.*/
		
		input.insert(offset, new_item);
		return list_splice(input, offset+1, length);
	}
	template <typename Item>
	linked_list<Item> list_splice(linked_list<Item> &input, size_t offset, size_t length, linked_list<Item> new_items) {
		/*removes as many items as specified by length from the input
		  list starting from the zero-based offset. Don't try a length longer
		  than the number of remaining items (yet). Input gets modified, and the return value
		  is a new linked list consisting of the that were removed from input.
		  Additionally, All the items contained in new_items have been put in place of the items that were removed.*/
		/*Not implemented for now...*/
		
		// input.insert(offset, new_item);
		return list_splice(input, offset+1, length);
	}
	
	/*template prefix not needed here since the second parameter names a specific type for the linked_list*/
	string charList_join(const char* glue, linked_list<char> pieces) {
		
		string joined = "";
		
		for (int i=0; i<pieces.size(); ++i) {
			if (i==0) { //only for the first piece do we not include the glue because there are one less glues than the total pieces (one glue between each piece).
				joined += pieces.get(i); //??? How do you append a char to the string variable ???
			}
			else {
				// joined += glue + pieces.get(i); //??? Does this way work instead of the two line method below? Answer: 
				joined += glue;
				joined += pieces.get(i);
			}
		}
		
		return joined;
	}

	template <typename Item>
	typename linked_list<Item>::value_type list_pop(linked_list<Item> list) {
		return (list_splice(list, list.size()-1, 1)).get(0);
	}

}

main.cpp

#include <string>	// provides the string type (class)
#include <iostream>	// provides cout, etc.
#include "linked_list.h" // provides linked_list
#include "permute_append.h" // provides permute_append

using namespace std;
using namespace CISP430_A5;

/*PERMUTE_APPEND STUB TEST*/
int main(void) {
	
	permute_append tester;
	tester.do_it("skate", "board");
	cout << tester.get(4);
	
}



/*LINKED_LIST STUB TEST*/
// int main(void) {

	// linked_list<int> items;
	// items.add(10);
	// items.add(30);
	// items.add(20);
	// items.add(40);

	// /* for each item in the list:*/
	// for (int i=0; i<items.size(); ++i) {
		// cout << items.get(i) << endl;
	// }
	
// cout << "-----------------------" << endl;
	
	// items.set(2, 50);
	// /* item at position 2 is now 50. */
	// cout << items.get(2) << endl;
	
// cout << "-----------------------" << endl;
	
	// items.add(23);
	// items.add(16);
	// items.add(34);
	// items.remove(2);
	// for (int i=0; i<items.size(); ++i) {
		// cout << items.get(i) << endl;
	// }
	
// cout << "-----------------------" << endl;

	// items.remove(4);
	// for (int i=0; i<items.size(); ++i) {
		// cout << items.get(i) << endl;
	// }
// }

makefile

all: main

main: main.o permute_append.o
	g++ main.o permute_append.o -o main.exe
	
main.o: main.cpp linked_list.h linked_list.template node.h node.template
	g++ -c main.cpp
	
permute_append.o: permute_append.cpp permute_append.h linked_list.h linked_list.template node.h node.template
	g++ -c permute_append.cpp




clean:
	rm -f *.o *.gch

node.h

/* Joe Pea - Assignment 5 */

// FILE: node.h (part of the namespace CISP430_A3)
// PROVIDES: A template class for a node in a linked list, and list manipulation
// functions. The template parameter is the type of the data in each node.
// This file also defines a template class: node_iterator<Item>.
// The node_iterator is a forward iterators with two constructors:
// (1) A constructor (with a node<Item>* parameter) that attaches the iterator
// to the specified node in a linked list, and (2) a default constructor that
// creates a special iterator that marks the position that is beyond the end of a
// linked list. There is also a const_node_iterator for use with
// const node<Item>* .
//
// TYPEDEF for the node<Item> template class:
//   Each node of the list contains a piece of data and a pointer to the
//   next node. The type of the data (node<Item>::value_type) is the Item type
//   from the template parameter. The type may be any of the built-in C++ classes
//   (int, char, ...) or a class with a default constructor, an assignment
//   operator, and a test for equality (x == y).
// NOTE:
//   Many compilers require the use of the new keyword typename before using
//   the expression node<Item>::value_type. Otherwise
//   the compiler doesn't have enough information to realize that it is the
//   name of a data type.
//
// CONSTRUCTOR for the node<Item> class:
//   node(
//     const Item& init_data = Item(),
//     node* init_link = NULL
//   )
//     Postcondition: The node contains the specified data and link.
//     NOTE: The default value for the init_data is obtained from the default
//     constructor of the Item. In the ANSI/ISO standard, this notation
//     is also allowed for the built-in types, providing a default value of
//     zero. The init_link has a default value of NULL.
//
// NOTE about two versions of some functions:
//   The data function returns a reference to the data field of a node and
//   the link function returns a copy of the link field of a node.
//   Each of these functions comes in two versions: a const version and a
//   non-const version. If the function is activated by a const node, then the
//   compiler choses the const version (and the return value is const).
//   If the function is activated by a non-const node, then the compiler choses
//   the non-const version (and the return value will be non-const).
// EXAMPLES:
//    const node<int> *c;
//    c->link( ) activates the const version of link returning const node*
//    c->data( ) activates the const version of data returning const Item&
//    c->data( ) = 42; ... is forbidden
//    node<int> *p;
//    p->link( ) activates the non-const version of link returning node*
//    p->data( ) activates the non-const version of data returning Item&
//    p->data( ) = 42; ... actually changes the data in p's node
//
// MEMBER FUNCTIONS for the node<Item> class:
//   const Item& data( ) const <----- const version
//   and
//   Item& data( ) <----------------- non-const version
//   See the note (above) about the const version and non-const versions:
//     Postcondition: The return value is a reference to the  data from this node.
//
//   const node* link( ) const <----- const version
//   and
//   node* link( ) <----------------- non-const version
//   See the note (above) about the const version and non-const versions:
//     Postcondition: The return value is the link from this node.
//   
//   void set_data(const Item& new_data)
//     Postcondition: The node now contains the specified new data.
//   
//   void set_link(node* new_link)
//     Postcondition: The node now contains the specified new link.
//
// FUNCTIONS in the linked list toolkit:
//   template <class Item>
//   void list_clear(node<Item>*& head_ptr) 
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: All nodes of the list have been returned to the heap,
//     and the head_ptr is now NULL.
//
//   template <class Item>
//   void list_copy
//   (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr)
//     Precondition: source_ptr is the head pointer of a linked list.
//     Postcondition: head_ptr and tail_ptr are the head and tail pointers for
//     a new list that contains the same items as the list pointed to by
//     source_ptr. The original list is unaltered.
//
//   template <class Item>
//   void list_head_insert(node<Item>*& head_ptr, const Item& entry) 
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: A new node containing the given entry has been added at
//     the head of the linked list; head_ptr now points to the head of the new,
//     longer linked list.
//
//   template <class Item>
//   void list_head_remove(node<Item>*& head_ptr) 
//     Precondition: head_ptr is the head pointer of a linked list, with at
//     least one node.
//     Postcondition: The head node has been removed and returned to the heap;
//     head_ptr is now the head pointer of the new, shorter linked list.
//
//   template <class Item>
//   void list_insert(node<Item>* previous_ptr, const Item& entry) 
//     Precondition: previous_ptr points to a node in a linked list.
//     Postcondition: A new node containing the given entry has been added
//     after the node that previous_ptr points to.
//
//   template <class Item>
//   size_t list_length(const node<Item>* head_ptr)
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: The value returned is the number of nodes in the linked
//     list.
//
//   template <class NodePtr, class SizeType>
//   NodePtr list_locate(NodePtr head_ptr, SizeType position)
//   The NodePtr may be either node<Item>* or const node<Item>*
//     Precondition: head_ptr is the head pointer of a linked list, and
//     position > 0.
//     Postcondition: The return value is a pointer that points to the node at
//     the specified position in the list. (The head node is position 1, the
//     next node is position 2, and so on). If there is no such position, then
//     the null pointer is returned.
//
//   template <class Item>
//   void list_remove(node<Item>* previous_ptr) 
//     Precondition: previous_ptr points to a node in a linked list, and this
//     is not the tail node of the list.
//     Postcondition: The node after previous_ptr has been removed from the
//     linked list.
//
//   template <class NodePtr, class Item>
//   NodePtr list_search
//   (NodePtr head_ptr, const Item& target) 
//   The NodePtr may be either node<Item>* or const node<Item>*
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: The return value is a pointer that points to the first
//     node containing the specified target in its data member. If there is no
//     such node, the null pointer is returned.
//
// DYNAMIC MEMORY usage by the toolkit: 
//   If there is insufficient dynamic memory, then the following functions throw
//   bad_alloc: the constructor, list_head_insert, list_insert, list_copy.

#ifndef NODE_H  
#define NODE_H

#include <cstdlib>   // Provides NULL and size_t
#include <iterator>  // Provides iterator and forward_iterator_tag

namespace CISP430_A5
{
    template <class Item>
    class node
    {
		public:
			// TYPEDEF
			typedef Item value_type;
			// CONSTRUCTOR
			node(const Item& init_data=Item( ), node* init_link=NULL) {
				data_field = init_data; link_field = init_link;
			}
			// MODIFICATION MEMBER FUNCTIONS
			Item& data( ) { return data_field; }
			node* link( ) { return link_field; }
			void set_data(const Item& new_data) { data_field = new_data; }
			void set_link(node* new_link) { link_field = new_link; }
			// CONST MEMBER FUNCTIONS
			const Item& data( ) const { return data_field; }
			const node* link( ) const { return link_field; }
		private:
			Item data_field;
			node *link_field;
    };

    // FUNCTIONS to manipulate a linked list:
    template <class Item>
    void list_clear(node<Item>*& head_ptr);

    template <class Item>
    void list_copy
        (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);

    template <class Item>
    void list_head_insert(node<Item>*& head_ptr, const Item& entry); 

    template <class Item>
    void list_head_remove(node<Item>*& head_ptr);

    template <class Item>
    void list_insert(node<Item>* previous_ptr, const Item& entry);
 
    template <class Item>
	size_t list_length(const node<Item>* head_ptr);

    template <class NodePtr, class SizeType>
    NodePtr list_locate(NodePtr head_ptr, SizeType position);

    template <class Item>
    void list_remove(node<Item>* previous_ptr);
   
    template <class NodePtr, class Item>
    NodePtr list_search(NodePtr head_ptr, const Item& target);

    // FORWARD ITERATORS to step through the nodes of a linked list
    // A node_iterator of can change the underlying linked list through the
    // * operator, so it may not be used with a const node. The
    // node_const_iterator cannot change the underlying linked list
    // through the * operator, so it may be used with a const node.
    // WARNING:
    // This classes use std::iterator as its base class;
    // Older compilers that do not support the std::iterator class can
    // delete everything after the word iterator in the second line:

    template <class Item>
    class node_iterator
	// : public std::iterator<std::forward_iterator_tag, Item>
    {
		public:
			node_iterator(node<Item>* initial = NULL) {
				current = initial;
			}
			Item& operator *( ) const { return current->data( ); }
			node_iterator& operator ++( ) { // Prefix ++
				current = current->link( );
				return *this;
			}
			node_iterator operator ++(int) { // Postfix ++
				node_iterator original(current);
				current = current->link( );
				return original;      	  
			}
			bool operator ==(const node_iterator other) const {
				return current == other.current;
			}
			bool operator !=(const node_iterator other) const {
				return current != other.current;
			}
		private:
			node<Item>* current;
    };

    template <class Item>
    class const_node_iterator
	// : public std::iterator<std::forward_iterator_tag, const Item>
    {
		public:
			const_node_iterator(const node<Item>* initial = NULL) { current = initial; }
			const Item& operator *( ) const { return current->data( ); }
			const_node_iterator& operator ++( ) { // Prefix ++
				current = current->link( );
				return *this;
			}
			const_node_iterator operator ++(int) { // Postfix ++
				const_node_iterator original(current);
				current = current->link( );
				return original;
			}
			bool operator ==(const const_node_iterator other) const {
				return current == other.current;
			}
			bool operator !=(const const_node_iterator other) const {
				return current != other.current;
			}
		private:
			const node<Item>* current;
    };

}

#include "node.template"
#endif

node.template

/* Joe Pea - Assignment 5 */

// FILE: node.template
// IMPLEMENTS: The functions of the node template class and the
// linked list toolkit (see node2.h for documentation).
//
// NOTE:
//   Since node is a template class, this file is included in node2.h.
//   Therefore, we should not put any using directives in this file.
//
// INVARIANT for the node class:
//   The data of a node is stored in data_field, and the link in link_field.

#include <cassert>    // Provides assert
#include <cstdlib>    // Provides NULL and size_t

namespace CISP430_A5
{
    template <class Item>
    void list_clear(node<Item>*& head_ptr)
    // Library facilities used: cstdlib
    {
		while (head_ptr != NULL)
			list_head_remove(head_ptr);
    }

    template <class Item>
    void list_copy(
		const node<Item>* source_ptr,
		node<Item>*& head_ptr,
		node<Item>*& tail_ptr
	) 
    // Library facilities used: cstdlib
    {
		head_ptr = NULL;
		tail_ptr = NULL;
		// Handle the case of the empty list
		if (source_ptr == NULL)
			return;	

		// Make the head node for the newly created list, and put data in it
		list_head_insert(head_ptr, source_ptr->data( ));
		tail_ptr = head_ptr; 
		
		// Copy rest of the nodes one at a time, adding at the tail of new list
		source_ptr = source_ptr->link( );
		while (source_ptr != NULL)
		{
			list_insert(tail_ptr, source_ptr->data( ));
			tail_ptr = tail_ptr->link( );
			source_ptr = source_ptr->link( );
		}
    }
    
    template <class Item>
    void list_head_insert(node<Item>*& head_ptr, const Item& entry)
    {
		head_ptr = new node<Item>(entry, head_ptr);
    }

    template <class Item>
    void list_head_remove(node<Item>*& head_ptr)
    {
		node<Item> *remove_ptr;

		remove_ptr = head_ptr;
		head_ptr = head_ptr->link( );
		delete remove_ptr;
    }

    template <class Item>
    void list_insert(node<Item>* previous_ptr, const Item& entry)
    {
		node<Item> *insert_ptr;
		insert_ptr = new node<Item>(entry, previous_ptr->link( ));
		previous_ptr->set_link(insert_ptr);
    }

    template <class Item>
    size_t list_length(const node<Item>* head_ptr)
    // Library facilities used: cstdlib
    {
		const node<Item> *cursor;
		std::size_t answer;
		
		answer = 0;
		for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
			++answer;
		
		return answer;
    }

    template <class NodePtr, class SizeType>
    NodePtr list_locate(NodePtr head_ptr, SizeType position) 
    // Library facilities used: cassert, cstdlib
    {
		NodePtr cursor;
		SizeType i;
		
		assert(0 < position);
		cursor = head_ptr;
		for (i = 1; (i < position) && (cursor != NULL); ++i)
			cursor = cursor->link( );
		return cursor;
    }

    template <class Item>
    void list_remove(node<Item>* previous_ptr)
    {
		node<Item> *remove_ptr;

		remove_ptr = previous_ptr->link( );
		previous_ptr->set_link(remove_ptr->link( ));
		delete remove_ptr;
    }

    template <class NodePtr, class Item>
    NodePtr list_search(NodePtr head_ptr, const Item& target)
    // Library facilities used: cstdlib
    {
		NodePtr cursor;
		
		for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
			if (target == cursor->data( ))
			return cursor;
		return NULL;
    }
}

permute_append.cpp

// #include <cstdlib>  // Provides size_t // included in permute_append.h
// #include <sstream>	// provides the << operator for string concatenation. // not using
//#include <string>	//provides string type //included in permute_append.h
#include "permute_append.h"

namespace CISP430_A5 {

	/*CONSTRUCTORS, DECONSTRUCTOR*/
		permute_append::permute_append() {
			firstString = "x"; // x is just a default value
			secondString = "x"; // x is just a default value
			total = 0;
		}
		permute_append::permute_append(const char* first, const char* second) {
			firstString = first;
			secondString = second;
			
			total = 1; // at least one permutation
			for (int i=firstString.length(); i>0; --i) { // number of permutations is equal to factorial of the number of characters in firstString
				total *= i;
			}
			
			/*Turn string into linked list of chars*/
			for (int i=0; i<firstString.length(); ++i) {
				permute_me.add(firstString[i]);
			}
		}
		permute_append::permute_append(const permute_append &source) {
			firstString = source.firstString;
			secondString = source.secondString;
			total = source.total;
			permute_me = source.permute_me;
			result_list = source.result_list;
		}
		permute_append::~permute_append() {
			total = 0;
			firstString = "";
			secondString = "";
			/*so I guess we don't need to delete the linked_list object manually*/
			// delete permute_me;
			// delete result_list;
		}
	
	
	
	
	linked_list<string> permute_append::permute(linked_list<char> charList) { // permute the characters in the array (n items, n at a time)
	/*Returns a linked_list of strings, each string a permutation of the chars in charList.*/
		static linked_list<string> perms; static linked_list<char> usedChars;
		linked_list<char> character;
		for (int i = 0; i < charList.size(); ++i) {
			character = list_splice(charList, i, 1); //??? How do we pass charList to list_splice so list_splice modifies charList directly? Answer: just like I did.
			usedChars.add( character.get(0) );
			if (charList.size() == 0) perms.add( charList_join("", usedChars) ); //??? Is charList_join() working? I believe so.
			permute(charList);
			list_splice( charList, i, 0, character.get(0) );
			list_pop( usedChars );
		}
		return perms;
	}
	/*My PHP version of permute:*/
	// function permute(linked_list<char> charArray) { // permute the characters in the array (n items, n at a time)
		// static $perms = array(); static $usedChars = array();
		// for ($i = 0; $i < sizeof($charArray); $i++) {
			// $char = array_splice($charArray, $i, 1);
			// $usedChars[] = $char[0];
			// if (sizeof($charArray) == 0) $perms[] = implode("", $usedChars);
			// permute($charArray);
			// array_splice($charArray, $i, 0, $char[0]);
			// array_pop($usedChars);
		// }
		// return $perms;
	// }
	
	
			
	string permute_append::do_it() {
	// appends secondString to each permutation of firstString and stores each result in result_list
		linked_list<string> perms( permute(permute_me) ); // ??? How do you point to the returned linked_list properly?
		// string result = "";
		
		for (size_t i=0; i<perms.size(); ++i) {
			// result = "";
			// result << perms.get(i) << secondString;
			result_list.add(perms.get(i) + secondString);
		}
	}
	
	string permute_append::do_it(const char* first, const char* second) {
	// set firstString and secondString then appends secondString to each permutation of firstString and stores each result in result_list
		firstString = first; secondString = second;
		do_it();
	}
			
	string permute_append::get(size_t position) { // get a result
	/*Get the item at position position from result_list */
		return result_list.get(position);
	}


}

permute_append.h

#include <cstdlib>  // Provides size_t
#include <string>	// provides string type (C++ class)
#include "linked_list.h" // provides linked_list
using namespace std;


namespace CISP430_A5 {
	
	class permute_append {
		
		public:
			
			/*CONSTRUCTORS, DESTRUCTOR*/
				permute_append();
				permute_append(const char* first, const char* second);
				permute_append(const permute_append &source);
				~permute_append();
				
			
			
			
			
			
			
			
			
			
			/*Returns a linked_list of string items, each item a permutation of the chars in the charList argument*/
			linked_list<string> permute(linked_list<char> charList); // permute the characters in charList (n items, n at a time)
			
			string do_it();
			// appends secondString to each permutation of firstString and stores each result in result_list
			
			string do_it(const char* first, const char* second);
			// set firstString and secondString then appends secondString to each permutation of firstString and stores each result in result_list
			
			string get(size_t position);
			/*Get the item at position position from result_list*/
			

		private:
			size_t total;
			string firstString;
			string secondString;
			linked_list<char> permute_me;
			linked_list<string> result_list;
		
	};
	
}