00001 // 00002 // Part of the ht://Dig package <http://www.htdig.org/> 00003 // Copyright (c) 1999, 2000, 2001 The ht://Dig Group 00004 // For copyright details, see the file COPYING in your distribution 00005 // or the GNU General Public License version 2 or later 00006 // <http://www.gnu.org/copyleft/gpl.html> 00007 // 00008 // $Id: WordExclude_8h-source.html,v 1.1 2008年06月08日 10:13:10 sebdiaz Exp $ 00009 // 00010 // 00011 // NAME 00012 // 00013 // permute bits in bit field 00014 // 00015 // SYNOPSIS 00016 // 00017 // #include <WordExclude.h> 00018 // 00019 // #define BITS 5 00020 // 00021 // WordExclude permute; 00022 // permute.Initialize(BITS); 00023 // while(permute.Next() == WORD_EXCLUDE_OK) 00024 // ... 00025 // 00026 // DESCRIPTION 00027 // 00028 // Count from 1 to the specified maximum. A variable++ loop does the same. 00029 // The <b>WordExclude</b> class counts in a specific order. 00030 // It first step thru all the permutations containing only 1 bit set, in 00031 // increasing order. Then thru all the permutations containing 2 bits set, 00032 // in increasing order. As so forth until the maximum number is reached. 00033 // See the <b>Permute</b> method for more information. 00034 // 00035 // 00036 // END 00037 00038 #ifndef _WordExclude_h 00039 #define _WordExclude_h 00040 00041 #include <stdio.h> 00042 00043 // 00044 // WordExclude methods return values 00045 // 00046 #define WORD_EXCLUDE_OK 1 00047 #define WORD_EXCLUDE_END 2 00048 00049 // 00050 // Maximum number of bits 00051 // 00052 #define WORD_EXCLUDE_MAX (sizeof(unsigned int) * 8) 00053 00054 // 00055 // Convert a position <p> in a <l> bits mask into a bit offset (from 0) 00056 // 00057 #define WORD_EXCLUDE_POSITION2BIT(l,p) ((l) - (p) - 1) 00058 00059 class WordExclude { 00060 public: 00061 WordExclude() { 00062 mask = maxi = bits = 0; 00063 verbose = 0; 00064 } 00065 00066 //- 00067 // Reset the generator and prepare it for <b>length</b> bits generation. 00068 // The <b>length</b> cannot be greater than <i>WORD_EXCLUDE_MAX.</i> 00069 // Returns OK if no error occurs, NOTOK otherwise. 00070 // 00071 virtual int Initialize(unsigned int length, unsigned int, unsigned int, int); 00072 //- 00073 // Move to next exclude mask. Returns WORD_EXCLUDE_OK if successfull, 00074 // WORD_EXCLUDE_END if at the end of the permutations. It starts by 00075 // calling <i>Permute</i> with one bit set, then two and up to 00076 // <i>Maxi()</i> included. The last permutation only generates one 00077 // possibility since all the bits are set. 00078 // 00079 virtual int Next(); 00080 //- 00081 // Exclude bit for <b>position</b> starts at most significant bit. That is 00082 // position 0 exclude bit is most significant bit of the current mask. 00083 // Returns true if position is excluded, false otherwise. 00084 // 00085 virtual inline unsigned int Excluded(int position) const { return mask & (1 << WORD_EXCLUDE_POSITION2BIT(maxi, position)); } 00086 //- 00087 // Returns how many bits are not excluded with current mask. 00088 // 00089 virtual inline int NotExcludedCount() const { return maxi - bits; } 00090 //- 00091 // Returns how many bits are excluded with current mask. 00092 // 00093 virtual inline int ExcludedCount() const { return bits; } 00094 // 00095 // Save and restore in string 00096 // 00097 //- 00098 // Write an ascii representation of the WordExclude object in <b>buffer.</b> 00099 // Each bit is represented by the character 0 or 1. The most significant 00100 // bit is the last character in the string. For instance 00101 // 1000 is the string representation of a WordExclude object initialized 00102 // with length = 4 after the first <i>Next</i> operation. 00103 // 00104 virtual void Get(String& buffer) const; 00105 //- 00106 // Initialize the object from the string representation in <b>buffer.</b> 00107 // Returns OK on success, NOTOK on failure. 00108 // 00109 virtual int Set(const String& buffer); 00110 00111 //- 00112 // Generate all the permutations 00113 // containing <i>n</i> bits in a <b>bits</b> bit word in increasing order. 00114 // The <b>mask</b> argument is originally filled by the caller 00115 // with the <i>n</i> least significant bits set. A call to Permute 00116 // generates the next permutation immediately greater (numerically) 00117 // than the one contained in <b>mask</b>. 00118 // 00119 // Permute returns the next permutation or 0 if it reached the 00120 // maximum. 00121 // 00122 // To understand the algorithm, imagine 1 is a ball and 0 a space. 00123 // 00124 // When playing the game you start with a rack of <b>bits</b> slots filled 00125 // with <i>n</i> balls all on the left side. You end the game when all 00126 // the balls are on the right side. 00127 // 00128 // Sarting from the left, search for the first ball that has an 00129 // empty space to the right. While searching remove all the balls 00130 // you find. Place a ball in the empty space you found, at the 00131 // right of the last ball removed. Sarting from the left, fill all 00132 // empty spaces you can with the removed balls. At this point you 00133 // have a permutation. Then repeat the same steps until all balls 00134 // are to the right, meaning that you've explored all the permutations. 00135 // 00136 // Here is a sample generated by repeated calls to WordExclude::Permute: 00137 // (left most bit is least significant) 00138 // <pre> 00139 // mask = 1111100000 00140 // while(mask = WordExclude::Permute(mask, 7)) 00141 // show_bits(mask) 00142 // 00143 // 1111100000 (0x0000001f - 31) 00144 // 1111010000 (0x0000002f - 47) 00145 // 1110110000 (0x00000037 - 55) 00146 // 1101110000 (0x0000003b - 59) 00147 // 1011110000 (0x0000003d - 61) 00148 // 0111110000 (0x0000003e - 62) 00149 // 1111001000 (0x0000004f - 79) 00150 // 1110101000 (0x00000057 - 87) 00151 // 1101101000 (0x0000005b - 91) 00152 // 1011101000 (0x0000005d - 93) 00153 // 0111101000 (0x0000005e - 94) 00154 // 1110011000 (0x00000067 - 103) 00155 // 1101011000 (0x0000006b - 107) 00156 // 1011011000 (0x0000006d - 109) 00157 // 0111011000 (0x0000006e - 110) 00158 // 1100111000 (0x00000073 - 115) 00159 // 1010111000 (0x00000075 - 117) 00160 // 0110111000 (0x00000076 - 118) 00161 // 1001111000 (0x00000079 - 121) 00162 // 0101111000 (0x0000007a - 122) 00163 // 0011111000 (0x0000007c - 124) 00164 // </pre> 00165 // A recursive implementation would be: 00166 // <pre> 00167 // /* Recursive */ 00168 // void permute(unsigned int result, int bits_count, int bits_toset) 00169 // { 00170 // if(bits_toset <= 0 || bits_count <= 0) { 00171 // if(bits_toset <= 0) 00172 // do_something(result); 00173 // } else { 00174 // permute(result, bits_count - 1, bits_toset); 00175 // permute(result | (1 << (bits_count - 1)), bits_count - 1, bits_toset - 1); 00176 // } 00177 // } 00178 // </pre> 00179 // Which is more elegant but not practical at all in our case. 00180 // 00181 inline unsigned int Permute(unsigned int mask, unsigned int bits); 00182 00183 //- 00184 // Return the current bit field value. 00185 // 00186 virtual inline unsigned int Mask() const { return mask; } 00187 00188 virtual inline unsigned int Maxi() const { return maxi; } 00189 00190 virtual inline unsigned int Bits() const { return bits; } 00191 00192 inline int Verbose(int verbosity) { return verbose = verbosity; } 00193 00194 protected: 00195 unsigned int mask; 00196 unsigned int maxi; 00197 unsigned int bits; 00198 00199 int verbose; 00200 }; 00201 00202 #endif /* _WordExclude_h */