WordExclude.h

Go to the documentation of this file.

//
// Part of the ht://Dig package   <http://www.htdig.org/>
// Copyright (c) 1999, 2000, 2001 The ht://Dig Group
// For copyright details, see the file COPYING in your distribution
// or the GNU General Public License version 2 or later
// <http://www.gnu.org/copyleft/gpl.html>
//
// $Id: WordExclude_8h-source.html,v 1.1 2008/06/08 10:13:10 sebdiaz Exp $
//
//
// NAME
// 
// permute bits in bit field
//
// SYNOPSIS
//
// #include <WordExclude.h>
//
// #define BITS 5
//
// WordExclude permute;
// permute.Initialize(BITS);
// while(permute.Next() == WORD_EXCLUDE_OK)
//    ...
//
// DESCRIPTION
//
// Count from 1 to the specified maximum. A variable++ loop does the same.
// The <b>WordExclude</b> class counts in a specific order.
// It first step thru all the permutations containing only 1 bit set, in
// increasing order. Then thru all the permutations containing 2 bits set,
// in increasing order. As so forth until the maximum number is reached.
// See the <b>Permute</b> method for more information.
//
//
// END

#ifndef _WordExclude_h
#define _WordExclude_h

#include <stdio.h>

//
// WordExclude methods return values
//
#define WORD_EXCLUDE_OK         1
#define WORD_EXCLUDE_END        2

//
// Maximum number of bits
//
#define WORD_EXCLUDE_MAX        (sizeof(unsigned int) * 8)

//
// Convert a position <p> in a <l> bits mask into a bit offset (from 0)
//
#define WORD_EXCLUDE_POSITION2BIT(l,p) ((l) - (p) - 1)

class WordExclude {
public:
  WordExclude() {
    mask = maxi = bits = 0;
    verbose = 0;
  }
  
  //-
  // Reset the generator and prepare it for <b>length</b> bits generation.
  // The <b>length</b> cannot be greater than <i>WORD_EXCLUDE_MAX.</i>
  // Returns OK if no error occurs, NOTOK otherwise.
  //
  virtual int Initialize(unsigned int length, unsigned int, unsigned int, int);
  //-
  // Move to next exclude mask. Returns WORD_EXCLUDE_OK if successfull,
  // WORD_EXCLUDE_END if at the end of the permutations. It starts by
  // calling <i>Permute</i> with one bit set, then two and up to 
  // <i>Maxi()</i> included. The last permutation only generates one
  // possibility since all the bits are set.
  //
  virtual int Next();
  //-
  // Exclude bit for <b>position</b> starts at most significant bit. That is
  // position 0 exclude bit is most significant bit of the current mask.
  // Returns true if position is excluded, false otherwise.
  //
  virtual inline unsigned int Excluded(int position) const { return mask & (1 << WORD_EXCLUDE_POSITION2BIT(maxi, position)); }
  //-
  // Returns how many bits are not excluded with current mask.
  //
  virtual inline int NotExcludedCount() const { return maxi - bits; }
  //-
  // Returns how many bits are excluded with current mask.
  //
  virtual inline int ExcludedCount() const { return bits; }
  //
  // Save and restore in string
  //
  //-
  // Write an ascii representation of the WordExclude object in <b>buffer.</b>
  // Each bit is represented by the character 0 or 1. The most significant
  // bit is the last character in the string. For instance
  // 1000 is the string representation of a WordExclude object initialized
  // with length = 4 after the first <i>Next</i> operation.
  //
  virtual void Get(String& buffer) const;
  //-
  // Initialize the object from the string representation in <b>buffer.</b>
  // Returns OK on success, NOTOK on failure.
  //
  virtual int Set(const String& buffer);

  //-
  // Generate all the permutations
  // containing <i>n</i> bits in a <b>bits</b> bit word in increasing order.
  // The <b>mask</b> argument is originally filled by the caller
  // with the <i>n</i> least significant bits set. A call to Permute
  // generates the next permutation immediately greater (numerically)
  // than the one contained in <b>mask</b>.
  // 
  // Permute returns the next permutation or 0 if it reached the
  // maximum.
  //
  // To understand the algorithm, imagine 1 is a ball and 0 a space.
  // 
  // When playing the game you start with a rack of <b>bits</b> slots filled
  // with <i>n</i> balls all on the left side. You end the game when all
  // the balls are on the right side.
  //
  // Sarting from the left, search for the first ball that has an
  // empty space to the right. While searching remove all the balls
  // you find.  Place a ball in the empty space you found, at the
  // right of the last ball removed. Sarting from the left, fill all
  // empty spaces you can with the removed balls. At this point you
  // have a permutation. Then repeat the same steps until all balls
  // are to the right, meaning that you've explored all the permutations.
  // 
  // Here is a sample generated by repeated calls to WordExclude::Permute:
  // (left most bit is least significant)
  // <pre>
  // mask = 1111100000 
  // while(mask = WordExclude::Permute(mask, 7))
  //    show_bits(mask)
  //
  // 1111100000 (0x0000001f -              31)
  // 1111010000 (0x0000002f -              47)
  // 1110110000 (0x00000037 -              55)
  // 1101110000 (0x0000003b -              59)
  // 1011110000 (0x0000003d -              61)
  // 0111110000 (0x0000003e -              62)
  // 1111001000 (0x0000004f -              79)
  // 1110101000 (0x00000057 -              87)
  // 1101101000 (0x0000005b -              91)
  // 1011101000 (0x0000005d -              93)
  // 0111101000 (0x0000005e -              94)
  // 1110011000 (0x00000067 -             103)
  // 1101011000 (0x0000006b -             107)
  // 1011011000 (0x0000006d -             109)
  // 0111011000 (0x0000006e -             110)
  // 1100111000 (0x00000073 -             115)
  // 1010111000 (0x00000075 -             117)
  // 0110111000 (0x00000076 -             118)
  // 1001111000 (0x00000079 -             121)
  // 0101111000 (0x0000007a -             122)
  // 0011111000 (0x0000007c -             124)
  // </pre>
  // A recursive implementation would be:
  // <pre>
  // /* Recursive */
  // void permute(unsigned int result, int bits_count, int bits_toset)
  // {
  //  if(bits_toset <= 0 || bits_count <= 0) {
  //    if(bits_toset <= 0)
  //      do_something(result);
  //  } else {
  //    permute(result, bits_count - 1, bits_toset);
  //    permute(result | (1 << (bits_count - 1)), bits_count - 1, bits_toset - 1);
  //  }
  // }
  // </pre>
  // Which is more elegant but not practical at all in our case. 
  //
  inline unsigned int Permute(unsigned int mask, unsigned int bits);
  
  //-
  // Return the current bit field value.
  //
  virtual inline unsigned int Mask() const { return mask; }

  virtual inline unsigned int Maxi() const { return maxi; }

  virtual inline unsigned int Bits() const { return bits; }

  inline int Verbose(int verbosity) { return verbose = verbosity; }

protected:
  unsigned int mask;
  unsigned int maxi;
  unsigned int bits;

  int verbose;
};

#endif /* _WordExclude_h */

---