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 hidden or 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 hidden or 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 hidden or 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 hidden or 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 hidden or 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 hidden or 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 hidden or 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 hidden or 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