Created
November 5, 2011 00:33
-
-
Save trusktr/1340872 to your computer and use it in GitHub Desktop.
My permute_append class.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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 | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
// } | |
// } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// #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); | |
} | |
} | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
}; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment