Optimizer.h

Go to the documentation of this file.

// ---------------------------------------------------------------------------
// $Id: Optimizer.h 232 2008-08-15 18:19:35Z daaugusto $
//
//   Optimizer.h (created on Thu Nov 17 18:25:35 BRT 2005)
// 
//   Genetic Algorithm File Fitter (gaffitter)
//
//   Copyright (C) 2005-2008 Douglas A. Augusto
// 
// This file is part of gaffitter.
// 
// gaffitter is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3 of the License, or (at
// your option) any later version.
// 
// gaffitter 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
// General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with gaffitter; if not, see <http://www.gnu.org/licenses/>.
//
// ---------------------------------------------------------------------------

#ifndef Optimizer_hh
#define Optimizer_hh

#include "Input.h"
#include "Params.h"
#include "util/Exception.h"

#include <vector>
#include <iostream>

#include <cmath>

// ---------------------------------------------------------------------------
#define ROUND( x ) (x < 0 ? std::ceil( (x) - 0.5 ) : std::floor( (x) + 0.5 ))

const Params::Size_t EPSILON = 0.000001;

// ---------------------------------------------------------------------------
class Optimizer;
class BinSet;

static bool AlmostEqual( double u, double v )
{
   return std::fabs( u - v ) <= EPSILON * std::fabs( u ) &&
          std::fabs( u - v ) <= EPSILON * std::fabs( v );
}

// ---------------------------------------------------------------------------
class Bin {
public:
   Bin( Params::Size_t capacity ): 
        m_sum_sizes( 0.0 ), m_capacity( capacity ) {}

   Bin( const std::vector<const SizeName*>& sn ) 
   { 
      for( unsigned i = 0; i < sn.size(); ++i ) AddItem( sn[i] );
      m_capacity = Used();
   }

   unsigned Count() const { return m_items.size(); }

   const SizeName* Item( int i ) const { return m_items[i]; }

   std::vector<const SizeName*>& Items() { return m_items; }
   const std::vector<const SizeName*>& Items() const { return m_items; }

   Params::Size_t Used() const { return m_sum_sizes; }

   Params::Size_t Free() const { return Capacity() - Used(); }
   Params::Size_t Capacity() const { return m_capacity; }

   void AddItem( const SizeName* i ) 
   { 
      //Assert (i->Size() <= Free());
      m_items.push_back(i); 
      m_sum_sizes += i->Size();
   }

   void ReplaceItem( int i, const SizeName* item )
   {
      m_sum_sizes += ( item->Size() - m_items[i]->Size() );
      m_items[i] = item;
   }

   void DelItem( int i ) 
   { 
      //Assert(m_items[i]->Size() <= Used());
      m_sum_sizes -= m_items[i]->Size(); 
      m_items.erase( m_items.begin() + i );
   }

   void AddAllItems( Bin& b )
   {
      for( unsigned i = 0; i < b.Count(); ++i ) AddItem( b[i] );
   }

   void DelAllItems() { m_items.clear(); m_sum_sizes = 0.0; }

   const SizeName* operator[](int i) const { return m_items[i]; }

   bool operator<( const Bin& bin ) const 
   {
      if ( Free() < bin.Free() ) return true;
      if ( Free() == bin.Free() ) return Count() < bin.Count();

      return false;
   }

   bool operator==( const Bin& bin ) const 
   {
      return ( AlmostEqual( bin.Free(), Free() ) && bin.Count() == Count() );
   }

   std::vector<const SizeName*>::iterator begin()  { return m_items.begin(); }
   std::vector<const SizeName*>::iterator end()  { return m_items.end(); }

   friend bool Intersect( Bin& a, std::vector<Bin>::iterator g1, 
                                  std::vector<Bin>::iterator g2, 
                                  std::vector<const SizeName*>& unassigned );
private:
   std::vector<const SizeName*> m_items; 
   Params::Size_t m_sum_sizes; 
   Params::Size_t m_capacity; 
};

// ---------------------------------------------------------------------------
class BinSet {
public:
   Bin& operator[]( int i ) { return m_bins[i]; }
   const Bin& operator[]( int i ) const { return m_bins[i]; }

   Bin& AddBin( Params::Size_t capacity ) 
   { 
      m_bins.push_back( Bin( capacity ) );
      return m_bins.back(); 
   }
   Bin& AddBin(const Bin& b) { m_bins.push_back(b); return m_bins.back(); }

   std::vector<Bin>::iterator begin() { return m_bins.begin(); }
   std::vector<Bin>::iterator end() { return m_bins.end(); }

   void DelBin( int i ) { m_bins.erase( m_bins.begin() + i ); }
   void DelAllBins() { m_bins.clear(); }

   unsigned int Count() const { return m_bins.size(); }

   bool operator!=( const BinSet& bs ) const { return !( *this == bs ); }
   bool operator==( const BinSet& bs ) const 
   {
      if( Count() != bs.Count() ) return false;
      std::vector<Bin>::const_iterator i = m_bins.begin(), j = bs.m_bins.begin();

      while( i != m_bins.end() ) if( !(*i++ == *j++) ) return false;

      return true;
   }

private:
   std::vector<Bin> m_bins; 
};

// ---------------------------------------------------------------------------
class Optimizer {
public:
   Optimizer( Input& i ): m_files( i.m_files ), m_params( i.m_params ), 
                          m_total_size( i.m_total_size ), m_solution( 0 )
   {
      /* The correct way to calculate m_bin_theo. A problematic scenario
       * occurs, for instance, when the total size is 2000 and the bin
       * capacity (target) is 100, and unfortunately the division
       * 2000/100 is represented as 20.000001 rather than the exact
       * 20.0; so, ceil( 20.000001) is 21 instead of giving 20 as the
       * theoretical minimum number of bin. */
      if( !m_params.m_bins_theo ) // if not given calculate it!
      {
         const Params::Size_t div = m_total_size / m_params.m_target;
         if( div > ROUND( div ) && div - ROUND( div ) < EPSILON )
            m_params.m_bins_theo = static_cast<unsigned>( ROUND( div ) );
         else
            m_params.m_bins_theo = static_cast<unsigned>( ceil( div ) );
      }

      if( m_params.m_verbose ) std::cout << "> Searching... " 
                                         << std::flush << std::endl;
   }

   virtual ~Optimizer() {};

private:
   Optimizer( const Optimizer& );
   Optimizer& operator=( const Optimizer& );

public:
   virtual void Evolve() = 0;
   void Output();
   friend std::ostream& operator<<( std::ostream&, const Optimizer& );

protected:
   virtual std::ostream& Write( std::ostream& s ) const
   {
      s << "> Target: " << m_params.PrettySize(m_params.m_target)
        << "\n> Input size: " << m_files.size()
        << "\n> Theoretical minimum number of bins: " << m_params.m_bins_theo
        << std::endl;

      return s;
   }

protected:
   Params::Size_t Evaluate( const BinSet& bs ) const;
   std::vector<const SizeName*>& m_files; 
   Params& m_params; 
   const Params::Size_t m_total_size; 
protected:
   BinSet* m_solution; 
};

// ----------------------------------------------------------------------------
inline std::ostream& operator<<( std::ostream& s, const Optimizer& optimizer )
{
   return optimizer.Write( s );
}

// ----------------------------------------------------------------------------
#endif