Created
December 7, 2020 18:42
-
-
Save xinyazhang/8cec0fa477aec3c52520bd39af5acc24 to your computer and use it in GitHub Desktop.
Hamming Number, C++ Template Metaprogramming
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
| /* | |
| hamming.cpp: a C++ version for calculating hamming numbers, aka regular numbers, | |
| aka ugly numbers, in compile time (using template meta programming). | |
| Copyright (C) 2008 Daniel Gutson | |
| hamming.cpp is free software: you can redistribute it and/or modify | |
| it under the terms of the GNU Affero General Public License as | |
| published by the Free Software Foundation, either version 3 of the | |
| License, or (at your option) any later version. | |
| This program is distributed in the hope that it will be useful, | |
| but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| GNU Affero General Public License for more details. | |
| You should have received a copy of the GNU Affero General Public License | |
| along with this program. If not, see <http://www.gnu.org/licenses/>. | |
| This program computes the n-th iteration of the Dijkstra algorithm | |
| provide in Wikipedia. | |
| For questions, contact me: danielgutson@gmail.com, or visit my | |
| homepage at http://danielgutson.googlepages.com/professionalinformation | |
| */ | |
| #include <iostream> | |
| using namespace std; | |
| struct NIL{}; | |
| template <int H, class T> | |
| struct List | |
| { | |
| enum { HEAD = H}; | |
| typedef T TAIL; | |
| }; | |
| enum COMP_TYPE | |
| { | |
| kEQ, | |
| kLESS, | |
| kMORE | |
| }; | |
| template <int A, int B> | |
| struct COMP | |
| { | |
| enum { val = ( A == B ? kEQ : ( A < B ? kLESS : kMORE ) ) }; | |
| }; | |
| template <class L> | |
| struct PRINTL | |
| { | |
| static void print() { cout << L::HEAD << " "; PRINTL<typename L::TAIL>::print(); } | |
| }; | |
| template <> | |
| struct PRINTL<NIL> | |
| { | |
| static void print() { cout << endl; } | |
| }; | |
| typedef List<1,NIL> START; | |
| template <class L, int MUL> | |
| struct GROW | |
| { | |
| typedef List<L::HEAD * MUL, typename GROW<typename L::TAIL, MUL>::RET > RET; | |
| }; | |
| template <int MUL> | |
| struct GROW<NIL, MUL> | |
| { | |
| typedef NIL RET; | |
| }; | |
| template <class L1, class L2, int L1_L2> struct MERGE2_; | |
| template <class L1, class L2> | |
| struct MERGE2 | |
| { | |
| typedef typename MERGE2_<L1, L2, COMP<L1::HEAD, L2::HEAD>::val >::RET RET; | |
| }; | |
| template <class L> | |
| struct MERGE2<L, NIL> | |
| { | |
| typedef L RET; | |
| }; | |
| template <class L> | |
| struct MERGE2<NIL,L> | |
| { | |
| typedef L RET; | |
| }; | |
| template <class L1, class L2, int L1_L2> // assume EQ | |
| struct MERGE2_ | |
| { | |
| typedef List<L1::HEAD, typename MERGE2<typename L1::TAIL, typename L2::TAIL>::RET > RET; | |
| }; | |
| template <class L1, class L2> | |
| struct MERGE2_<L1, L2, kLESS> // L1::HEAD < L2::HEAD | |
| { | |
| typedef List<L1::HEAD, typename MERGE2<typename L1::TAIL, L2>::RET > RET; | |
| }; | |
| template <class L1, class L2> | |
| struct MERGE2_<L1, L2, kMORE> // L1::HEAD > L2::HEAD | |
| { | |
| typedef List<L2::HEAD, typename MERGE2<L1, typename L2::TAIL>::RET > RET; | |
| }; | |
| template <class L, int IT> | |
| struct HAMMING | |
| { | |
| typedef typename | |
| HAMMING< | |
| typename MERGE2< | |
| typename MERGE2< L, typename GROW<L, 2>::RET >::RET, | |
| typename MERGE2< typename GROW<L, 3>::RET, typename GROW<L, 5>::RET>::RET | |
| >::RET, | |
| IT-1>::RET RET; | |
| }; | |
| template <class L> | |
| struct HAMMING<L, 0> | |
| { | |
| typedef L RET; | |
| }; | |
| int main() | |
| { | |
| PRINTL<HAMMING<START, 5>::RET >::print(); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment