WordExclude.h

Go to the documentation of this file.
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 */

Generated on Sun Jun 8 10:56:40 2008 for GNUmifluz by  doxygen 1.5.5