LEMGA: utility.h Source File

00001 // -*- C++ -*-
00002 #ifndef __LEMGA_UTILITY_H__
00003 #define __LEMGA_UTILITY_H__
00004 
00011 #include <vector>
00012 
00014 template<class N>
00015 bool gray_next (std::vector<N>& v, typename std::vector<N>::size_type& p) {
00016     typename std::vector<N>::size_type n = v.size();
00017     assert(n > 0);
00018 
00019     // by default we alter the last bit
00020     p = n - 1;
00021     bool more = true;
00022 
00023     // find the largest n such that v[n] == 1
00024     while (--n && v[n] == 0) /* empty */;
00025 
00026     if (n > 0) {
00027         typename std::vector<N>::size_type j = n;
00028         bool xor_sum = true;
00029         while (n--)
00030             xor_sum = xor_sum ^ (v[n] != 0);
00031         if (xor_sum) p = j - 1;
00032     } else if (v[0] != 0) {
00033         p = 0; more = false;
00034     }
00035     v[p] = (v[p] == 0);
00036     return more;
00037 }
00038 
00039 template<class N>
00040 bool gray_next (std::vector<N>& v) {
00041     typename std::vector<N>::size_type p;
00042     return gray_next(v, p);
00043 }
00044 
00045 #ifdef  __UTILITY_H__
00046 #warning "This header file may conflict with another `utility.h' file."
00047 #endif
00048 #define __UTILITY_H__
00049 #endif