Created
October 13, 2012 04:42
-
-
Save okaram/3883253 to your computer and use it in GitHub Desktop.
cons lists in C++
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
template<typename T> | |
struct ConsNode { | |
public: | |
ConsNode(T car=T(), ConsList<T> cdr=ConsList<T>()):_car(car),_cdr(cdr) {} | |
private: | |
T _car; | |
ConsList<T> _cdr; | |
friend T car<>(const ConsList<T> &l); | |
friend const ConsList<T>& cdr<>(const ConsList<T> &l); | |
}; |
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
template <typename T> | |
using ConsList= std::shared_ptr<ConsNode <T> >; |
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
template<typename T> | |
ConsList<T> cons(T car, const ConsList<T>& cdr=ConsList<T>()) { | |
return std::make_shared<ConsNode<T> > (car,cdr); | |
} |
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
template<typename T> | |
T car(const ConsList<T>&l) | |
{ | |
return l->_car; | |
} | |
template<typename T> | |
const ConsList<T>& cdr(const ConsList<T>&l) | |
{ | |
return l->_cdr; | |
} | |
template<class T> | |
bool isEmpty(const ConsList<T>&l) | |
{ | |
return !l; | |
} | |
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
int main(void) | |
{ | |
ConsList<int> l=cons(3,cons(4,cons(7))); | |
ConsList<int> l2=cons(9,cons(5,l)); // l2 shares the last 3 elements with l | |
ConsList<int> l3=cons(11,cdr(l2)); // l3 shares with l2, and also with l | |
cout << car(l) << " " << car(cdr(l)) << endl; | |
cout << len(l2) << " " << sum(l2) << endl; | |
cout << l2 << endl; | |
cout << l3 << 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
template<class T> | |
std::ostream& operator<<(std::ostream& o, const ConsList<T>&l) | |
{ | |
if(!isEmpty(l)) | |
o << car(l) << " " << cdr(l); | |
return o; | |
} |
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
template<class T> | |
std::ostream& operator<<(std::ostream& o, const ConsList<T>&l) | |
{ | |
if(l) | |
o << car(l) << " " << cdr(l); | |
return o; | |
} |
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
template<typename T> | |
unsigned len(const ConsList<T>&l) | |
{ | |
if(!isEmpty(l)) | |
return 0; | |
return 1+len(cdr(l)); | |
} | |
template<typename T> | |
T sum(const ConsList<T>& l) | |
{ | |
if(isEmpty(l)) | |
return 0; | |
return car(l)+sum(cdr(l)); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment