Created
February 29, 2020 01:43
-
-
Save chronologicaldot/0184c29a55d7e597996e19a106cc0ceb to your computer and use it in GitHub Desktop.
Open linked list (meaning you can pull it apart; useful for big data that means manual organization)
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
/* | |
Name: Linus Listor for C++ | |
(Linus Listor C Plus / Linus Listor Cp ) | |
(C) Nic Anderson | |
Date: June 15, 2011 | |
See LinusListorCp.h for copyright details. | |
Desc: This is a simple linked list for C++ programs. | |
*/ | |
#ifndef _LLISTOR_ | |
#define _LLISTOR_ | |
// include the header | |
#include "LinusListorCp.h" | |
namespace Linus | |
{ | |
template<class Unk> | |
LListor<Unk>::LListor() | |
{ | |
// indicate this link has neither prior nor post links | |
possession_state = s_none; | |
} | |
// for the item being stored | |
template<class Unk> | |
Unk* LListor<Unk>::getThisItemAddress() | |
{ | |
return &ThisItem; | |
} | |
template<class Unk> | |
Unk LListor<Unk>::getThisItemCopy() | |
{ | |
return ThisItem; | |
} | |
template<class Unk> | |
void LListor<Unk>::setThisItem(Unk newItem) | |
{ | |
ThisItem = newItem; | |
} | |
// for the prior and post links | |
template<class Unk> | |
LListor<Unk>* LListor<Unk>::getPriorLink() | |
{ | |
if ( possession_state == s_prior || possession_state == s_both ) | |
return PriorLink; | |
else return 0; | |
} | |
template<class Unk> | |
void LListor<Unk>::setPriorLink( LListor<Unk>* newPrior ) | |
{ | |
// set the new link (NOTE: Does not delete the old one in case it is needed) | |
PriorLink = newPrior; | |
// adjust the possession state if necessary | |
switch ( possession_state ) | |
{ | |
case s_none: possession_state = s_prior; break; | |
case s_prior: break; | |
case s_post: possession_state = s_both; break; | |
case s_both: break; | |
} | |
} | |
template<class Unk> | |
LListor<Unk>* LListor<Unk>::getPostLink() | |
{ | |
if ( possession_state == s_post || possession_state == s_both ) | |
return PostLink; | |
else return 0; | |
} | |
template<class Unk> | |
void LListor<Unk>::setPostLink( LListor<Unk>* newPost ) | |
{ | |
// set the new link (NOTE: Does not delete the old one in case it is needed) | |
PostLink = newPost; | |
// adjust the possession state if necessary | |
switch ( possession_state ) | |
{ | |
case s_none: possession_state = s_post; break; | |
case s_prior: possession_state = s_both; break; | |
case s_post: break; | |
case s_both: break; | |
} | |
} | |
// possession state | |
template<class Unk> | |
si32 LListor<Unk>::hasWhat() | |
{ | |
switch ( possession_state ) | |
{ | |
case s_none: return 0; | |
case s_prior: return 1; | |
case s_post: return 2; | |
case s_both: return 3; | |
} | |
} | |
// for adding on new links onto the chain | |
template<class Unk> | |
LListor<Unk>* LListor<Unk>::addNewLink( Unk item , bool head ) | |
{ | |
// save the location of the new link, based on whether it is the prior or post | |
if (head) // prior | |
{ | |
// determine if this link has a prior link already | |
switch ( possession_state ) | |
{ | |
case s_none: | |
// create a new link - use "new" to ensure it isn't deleted from the stack | |
PriorLink = new LListor<Unk>; | |
// assign it the new item | |
PriorLink->setThisItem(item); | |
// indicate the prior link now has a post link | |
PriorLink->setPostLink(this); | |
// indicate that this now has a prior link | |
possession_state = s_prior; | |
break; | |
case s_prior: | |
// considering this has a prior, send the item to that link to be added | |
return PriorLink->addNewLink( item, true ); | |
//break; - unnecessary after a "return" statement | |
case s_post: | |
// create a new link - use "new" to ensure it isn't deleted from the stack | |
PriorLink = new LListor<Unk>; | |
// assign it the new item | |
PriorLink->setThisItem(item); | |
// indicate the prior link now has a post link | |
PriorLink->setPostLink(this); | |
// indicate this link now has both links | |
possession_state = s_both; | |
break; | |
case s_both: | |
// considering this has a prior, send the item to that link to be added | |
return PriorLink->addNewLink( item, true ); | |
//break; - unnecessary after a return statement | |
} | |
// return the pointer to the link of the new object | |
return PriorLink; | |
} else { | |
// indicate that this link now has a new post link | |
switch ( possession_state ) | |
{ | |
case s_none: | |
// create a new link - use "new" to ensure it isn't deleted from the stack | |
PostLink = new LListor<Unk>; | |
// assign it the new item | |
PostLink->setThisItem(item); | |
// indicate the post link now has a prior link | |
PostLink->setPriorLink(this); | |
// indicate this link now has a post link | |
possession_state = s_post; | |
break; | |
case s_prior: | |
// create a new link - use "new" to ensure it isn't deleted from the stack | |
PostLink = new LListor<Unk>; | |
// assign it the new item | |
PostLink->setThisItem(item); | |
// indicate the post link now has a prior link | |
PostLink->setPriorLink(this); | |
// indicate this link now has both links | |
possession_state = s_both; | |
break; | |
case s_post: | |
// considering this has a post, send the item to that link to be added | |
return PostLink->addNewLink( item, false ); | |
//break; - unnecessary after a return statement | |
case s_both: | |
// considering this has a post, send the item to that link to be added | |
return PostLink->addNewLink( item, false ); | |
//break; - unnecessary after a return statement | |
} | |
// return the pointer to the link of the new object | |
return PostLink; | |
} | |
} | |
// for removing the current link from its current chain without deleting it | |
template<class Unk> | |
void LListor<Unk>::extractCurrLink() const | |
{ | |
// check for whether this link has a prior and a post link | |
if ( possession_state == s_both ) | |
{ | |
PriorLink->setPostLink( PostLink ); | |
PostLink->setPriorLink( PriorLink ); | |
} | |
switch( possession_state ) | |
{ | |
case s_prior: | |
switch ( PriorLink->possession_state ) | |
{ | |
case s_post: PriorLink->possession_state = s_none; break; | |
case s_both: PriorLink->possession_state = s_prior; break; | |
default: break; | |
} | |
break; | |
case s_post: // flag that the prior link has been dropped | |
switch ( PostLink->possession_state ) | |
{ | |
case s_prior: PostLink->possession_state = s_none; break; | |
case s_both: PostLink->possession_state = s_post; break; | |
default: break; | |
} | |
break; | |
case s_both: // bridge the chain | |
PriorLink->setPostLink( PostLink ); | |
PostLink->setPriorLink( PriorLink ); | |
break; | |
default: break; | |
} | |
} | |
// for properly deleting the current link in the chain | |
template<class Unk> | |
void LListor<Unk>::delCurrLink() const | |
{ | |
// check for whether this link has a prior and a post link | |
extractCurrLink(); | |
// finally, delete this link | |
delete this; | |
} | |
// for scanning the chain | |
template<class Unk> | |
LListor<Unk>* LListor<Unk>::getFirstLink() | |
{ | |
// if this link itself has a prior link, call it | |
if ( possession_state == s_prior || possession_state == s_both ) | |
return PriorLink->getFirstLink(); | |
else | |
return this; // otherwise, this (the current) link is the one to return | |
} | |
template<class Unk> | |
LListor<Unk>* LListor<Unk>::getLastLink() | |
{ | |
// if this link itself has a prior link, call it | |
if ( possession_state == s_post || possession_state == s_both ) | |
return PostLink->getLastLink(); | |
else | |
return this; // otherwise, this (the current) link is the one to return | |
} | |
} | |
#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
/* | |
This is the header file for LinusListorCp.cpp | |
(C) Nic Anderson | |
Date: June 15, 2011 | |
This software is provided 'as-is', without any express or implied | |
warranty. In no event will the authors be held liable for any damages | |
arising from the use of this software. | |
Permission is granted to anyone to use this software for any purpose, | |
including commercial applications, and to alter it and redistribute it | |
freely, subject to the following restrictions: | |
1. The origin of this software must not be misrepresented; you must not | |
claim that you wrote the original software. If you use this software | |
in a product, an acknowledgment in the product documentation would be | |
appreciated but is not required. | |
2. Altered source versions must be plainly marked as such, and must not be | |
misrepresented as being the original software. | |
3. This notice may not be removed or altered from any source distribution. | |
*/ | |
// don't double define this | |
// if "_Linus_INCLUDED" is not defined... | |
#ifndef _Linus_INCLUDED_ | |
// ... define it (and define the namespace as well) | |
#define _Linus_INCLUDED_ | |
// simple definitions for usage with this list | |
#ifdef _MSC_VER | |
typedef __int32 si32; | |
#else | |
typedef signed int si32; | |
#endif | |
namespace Linus | |
{ | |
// The main class in Linus - the actual linked list | |
template<class Unk> | |
class LListor | |
{ | |
private: | |
// pointers to the prior link and post link (links before and after this one) | |
LListor<Unk>* PriorLink; | |
LListor<Unk>* PostLink; | |
/* indicates the posession state: | |
if this link has a link before it, after it, or both */ | |
enum { | |
s_none = 0, | |
s_prior, | |
s_post, | |
s_both | |
} possession_state; | |
public: | |
// object being pointed to | |
Unk ThisItem; | |
//! Default constructor | |
/** Sets the possession state to zero, indicating this link | |
has neither a link that preceeds it nor one that follows. */ | |
LListor(); | |
// Dealing with the user's item being stored in the list | |
//! Return item address | |
/** This returns the address of the item/object | |
being pointed to by this class's pointer. */ | |
virtual Unk* getThisItemAddress(); | |
//! Return item copy | |
/** This returns a copy of the item/object | |
being pointed to by this class's pointer. */ | |
virtual Unk getThisItemCopy(); | |
//! Set/replace item | |
/** This sets a new item for this pointer or | |
replaces the current one. */ | |
virtual void setThisItem(Unk newItem); | |
// Dealing with the chain | |
//! Return prior link | |
/** This returns a pointer to the link that | |
comes before this one in the chain. */ | |
virtual LListor<Unk>* getPriorLink(); | |
//! Set prior link | |
/** This sets a pointer to the link that is | |
now to precede this one. */ | |
virtual void setPriorLink( LListor<Unk>* newPrior ); | |
//! Return post link | |
/** This returns a pointer to the link that | |
follows this one in the chain. */ | |
virtual LListor<Unk>* getPostLink(); | |
//! Set post link | |
/** This sets a pointer to the link that is | |
now to follow this one. */ | |
virtual void setPostLink( LListor<Unk>* newPost ); | |
//! Get possession state | |
/** This returns one of four values, indicating what links | |
it has: | |
0 if it has neither a preceeding/prior link nor a following/post, | |
1 if it has a prior link, | |
2 if it has a post link, | |
3 if it has both a prior and a post link. */ | |
virtual si32 hasWhat(); | |
//! Add new link | |
/** Generate an entirely new link, assign it | |
the given object, and append it to this link. | |
\param item = new object being added | |
\param head = if this link is the new prior */ | |
virtual LListor<Unk>* addNewLink( Unk item , bool head ); | |
//! Extract the current link | |
/** Takes a link out of the chain it currently belongs to | |
without deleting it. The gap in the old chain is linked | |
by the linking of the former post and prior links of the | |
extracted link. */ | |
virtual void extractCurrLink() const; | |
//! Delete the current link | |
/** Removes the current link in the chain by assigning | |
the post link and previous link to each other, returning | |
one of the two (post takes precedence over prior) if | |
available. The removed link is then deleted. */ | |
virtual void delCurrLink() const; | |
//! Delete the next link | |
/** Removes the next link in the chain, if it exists, | |
and by calling delCurrLink() on its post link. */ | |
void delPostLink() const | |
{ | |
if ( possession_state == s_post || possession_state == s_both ) | |
{ | |
this->getPostLink()->delCurrLink(); | |
} | |
} | |
//! Delete the previous link | |
/** Removes the previous link in the chain, if it exists, | |
and by calling delCurrLink() on its post link. */ | |
void delPriorLink() const | |
{ | |
if ( possession_state == s_prior || possession_state == s_both ) | |
{ | |
this->getPriorLink()->delCurrLink(); | |
} | |
} | |
//! Get the first link in the chain | |
/** This returns the first link whose possession state | |
indicates it does not have a prior link. */ | |
virtual LListor<Unk>* getFirstLink(); | |
//! Get the last link in the chain | |
/** This returns the last link whose possession state | |
indicates it does not have a post link. */ | |
virtual LListor<Unk>* getLastLink(); | |
//! Compare items | |
/** Apply greater-than comparison operation to the | |
items pointed to by the links. */ | |
void operator> ( LListor<Unk>* ll_out ) | |
{ | |
return ( ThisItem > ll_out->getThisItemCopy() ); | |
} | |
//! Compare items | |
/** Apply less-than comparison operation to the | |
items pointed to by the links. */ | |
void operator< ( LListor<Unk>* ll_out ) | |
{ | |
return ( ThisItem < ll_out->getThisItemCopy() ); | |
} | |
//! Compare items | |
/** Apply greater-than-or-equal-to comparison operation | |
to the items pointed to by the links. */ | |
void operator>= ( LListor<Unk>* ll_out ) | |
{ | |
return ( ThisItem >= ll_out->getThisItemCopy() ); | |
} | |
//! Compare items | |
/** Apply less-than-or-equal-to comparison operation | |
to the items pointed to by the links. */ | |
void operator<= ( LListor<Unk>* ll_out ) | |
{ | |
return ( ThisItem <= ll_out->getThisItemCopy() ); | |
} | |
//! Compare items | |
/** Apply not-equal-to comparison operation to the | |
items pointed to by the links. */ | |
void operator!= ( LListor<Unk>* ll_out ) | |
{ | |
return ( ThisItem != ll_out->getThisItemCopy() ); | |
} | |
//! Compare items | |
/** Apply the equal-to comparison operations to the | |
items pointed to by the links. */ | |
void operator== ( LListor<Unk>* ll_out ) | |
{ | |
return ( ThisItem == ll_out->getThisItemCopy() ); | |
} | |
}; | |
// type definitions (essentially just shortcuts) | |
//typedef LListor<int> LLii; | |
//typedef LListor<float> LLif; | |
} | |
// end the definition | |
#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
/* | |
Test program for testing Linus Listor for C++ | |
Author: Nic Anderson | |
Date: June 15, 2011 | |
*/ | |
#include <iostream> // search the system directory for iostream and add it | |
#include <string> | |
#include "LinusListorCp.cpp" // search the locale directory for LinusListorCp.cpp and add it | |
using namespace std; | |
using namespace Linus; | |
void main() | |
{ | |
cout << "\nThis program is meant to test a linked list program."; | |
// user input | |
string answer; | |
// the start of the linked list | |
LListor<string> lls; | |
LListor<string> * lsp; | |
lls.setThisItem( "List start" ); | |
do { | |
// Request user input | |
cout << "\nPlease enter a value: "; | |
cin >> answer; | |
// add a new link to the linked list | |
lsp = lls.addNewLink( answer, false ); | |
// ask if the user wants to continue inputting values to be added to the list | |
cout << "\nContinue? (y/n): "; | |
cin >> answer; | |
} while ( answer == "y" ); | |
// output the final list | |
cout << "\n\nFinal List:\n"; | |
int count = 0; | |
LListor<string> * lsi; | |
// start at this address - point to the list with the pointer "lsi" | |
lsi = &lls; | |
lsp = lls.getLastLink(); | |
// get the first link | |
lsi = lsi->getFirstLink(); | |
do { | |
// obtain the string | |
answer = lsi->getThisItemCopy(); | |
// print the contents | |
cout << count << ") " << answer << endl; | |
count++; | |
// if possible, get the post link | |
if ( lsi->hasWhat() == 2 || lsi->hasWhat() == 3 ) | |
lsi = lsi->getPostLink(); | |
else break; | |
} while ( 1 ); | |
// For debug | |
cout << "\nlsp copy = " << ( lsp->getThisItemCopy() ) | |
<< "\nlsp addr = " << ( lsp->getThisItemAddress() ) | |
<< "\nlls copy = " << ( lls.getThisItemCopy() ) << endl; | |
// get the first link | |
lsi = lsi->getFirstLink(); | |
// remove from the chain and delete the last link | |
//lsp->extractCurrLink(); | |
//delete lsp; | |
// delete the last link | |
lsp->delCurrLink(); | |
do { | |
// obtain the string | |
answer = lsi->getThisItemCopy(); | |
// print the contents | |
cout << count << ") " << answer << endl; | |
count++; | |
// if possible, get the post link | |
if ( lsi->hasWhat() == 2 || lsi->hasWhat() == 3 ) | |
lsi = lsi->getPostLink(); | |
else break; | |
} while ( 1 ); | |
// prevent closing | |
cin >> answer; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment