index.h

Go to the documentation of this file.

/*  This file is part of libDAI - http://www.libdai.org/
 *
 *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
 *
 *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
 */




#ifndef __defined_libdai_index_h
#define __defined_libdai_index_h


#include <vector>
#include <algorithm>
#include <map>
#include <dai/varset.h>


namespace dai {



class IndexFor {
    private:
        long                _index;

        std::vector<long>   _sum;

        std::vector<size_t> _state;

        std::vector<size_t> _ranges;

    public:
        IndexFor() : _index(-1) {}

        IndexFor( const VarSet& indexVars, const VarSet& forVars ) : _state( forVars.size(), 0 ) {
            long sum = 1;

            _ranges.reserve( forVars.size() );
            _sum.reserve( forVars.size() );

            VarSet::const_iterator j = forVars.begin();
            for( VarSet::const_iterator i = indexVars.begin(); i != indexVars.end(); ++i ) {
                for( ; j != forVars.end() && *j <= *i; ++j ) {
                    _ranges.push_back( j->states() );
                    _sum.push_back( (*i == *j) ? sum : 0 );
                }
                sum *= i->states();
            }
            for( ; j != forVars.end(); ++j ) {
                _ranges.push_back( j->states() );
                _sum.push_back( 0 );
            }
            _index = 0;
        }

        IndexFor& reset() {
            fill( _state.begin(), _state.end(), 0 );
            _index = 0;
            return( *this );
        }

        operator size_t() const {
            DAI_ASSERT( valid() );
            return( _index );
        }

        IndexFor& operator++ () {
            if( _index >= 0 ) {
                size_t i = 0;

                while( i < _state.size() ) {
                    _index += _sum[i];
                    if( ++_state[i] < _ranges[i] )
                        break;
                    _index -= _sum[i] * _ranges[i];
                    _state[i] = 0;
                    i++;
                }

                if( i == _state.size() )
                    _index = -1;
            }
            return( *this );
        }

        void operator++( int ) {
            operator++();
        }

        bool valid() const {
            return( _index >= 0 );
        }
};



class Permute {
    private:
        std::vector<size_t>  _ranges;
        std::vector<size_t>  _sigma;

    public:
        Permute() : _ranges(), _sigma() {}

        Permute( const std::vector<size_t> &rs, const std::vector<size_t> &sigma ) : _ranges(rs), _sigma(sigma) {
            DAI_ASSERT( _ranges.size() == _sigma.size() );
        }


        Permute( const std::vector<Var> &vars, bool reverse=false ) : _ranges(), _sigma() {
            size_t N = vars.size();

            // construct ranges
            _ranges.reserve( N );
            for( size_t i = 0; i < N; ++i )
                if( reverse )
                    _ranges.push_back( vars[N - 1 - i].states() );
                else
                    _ranges.push_back( vars[i].states() );

            // construct VarSet out of vars
            VarSet vs( vars.begin(), vars.end(), N );
            DAI_ASSERT( vs.size() == N );
            
            // construct sigma
            _sigma.reserve( N );
            for( VarSet::const_iterator vs_i = vs.begin(); vs_i != vs.end(); ++vs_i ) {
                size_t ind = find( vars.begin(), vars.end(), *vs_i ) - vars.begin();
                if( reverse )
                    _sigma.push_back( N - 1 - ind );
                else
                    _sigma.push_back( ind );
            }
        }


        size_t convertLinearIndex( size_t li ) const {
            size_t N = _ranges.size();

            // calculate vector index corresponding to linear index
            std::vector<size_t> vi;
            vi.reserve( N );
            size_t prod = 1;
            for( size_t k = 0; k < N; k++ ) {
                vi.push_back( li % _ranges[k] );
                li /= _ranges[k];
                prod *= _ranges[k];
            }

            // convert permuted vector index to corresponding linear index
            prod = 1;
            size_t sigma_li = 0;
            for( size_t k = 0; k < N; k++ ) {
                sigma_li += vi[_sigma[k]] * prod;
                prod *= _ranges[_sigma[k]];
            }

            return sigma_li;
        }

        const std::vector<size_t>& sigma() const { return _sigma; }

        std::vector<size_t>& sigma() { return _sigma; }

        const std::vector<size_t>& ranges() { return _ranges; }

        size_t operator[]( size_t i ) const {
#ifdef DAI_DEBUG
            return _sigma.at(i);
#else
            return _sigma[i];
#endif
        }

        Permute inverse() const {
            size_t N = _ranges.size();
            std::vector<size_t> invRanges( N, 0 );
            std::vector<size_t> invSigma( N, 0 );
            for( size_t i = 0; i < N; i++ ) {
                invSigma[_sigma[i]] = i;
                invRanges[i] = _ranges[_sigma[i]];
            }
            return Permute( invRanges, invSigma );
        }
};



class multifor {
    private:
        std::vector<size_t>  _ranges;
        std::vector<size_t>  _indices;
        long                 _linear_index;

    public:
        multifor() : _ranges(), _indices(), _linear_index(0) {}

        multifor( const std::vector<size_t> &d ) : _ranges(d), _indices(d.size(),0), _linear_index(0) {}

        operator size_t() const {
            DAI_DEBASSERT( valid() );
            return( _linear_index );
        }

        size_t operator[]( size_t k ) const {
            DAI_DEBASSERT( valid() );
            DAI_DEBASSERT( k < _indices.size() );
            return _indices[k];
        }

        multifor & operator++() {
            if( valid() ) {
                _linear_index++;
                size_t i;
                for( i = 0; i != _indices.size(); i++ ) {
                    if( ++(_indices[i]) < _ranges[i] )
                        break;
                    _indices[i] = 0;
                }
                if( i == _indices.size() )
                    _linear_index = -1;
            }
            return *this;
        }

        void operator++( int ) {
            operator++();
        }

        multifor& reset() {
            fill( _indices.begin(), _indices.end(), 0 );
            _linear_index = 0;
            return( *this );
        }

        bool valid() const {
            return( _linear_index >= 0 );
        }
};



class State {
    private:
        typedef std::map<Var, size_t> states_type;

        BigInt                        state;

        states_type                   states;

    public:
        State() : state(0), states() {}

        State( const VarSet &vs, BigInt linearState=0 ) : state(linearState), states() {
            if( linearState == 0 )
                for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ )
                    states[*v] = 0;
            else {
                for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ ) {
                    states[*v] = BigInt_size_t( linearState % (BigInt)v->states() );
                    linearState /= (BigInt)v->states();
                }
                DAI_ASSERT( linearState == 0 );
            }
        }

        State( const std::map<Var, size_t> &s ) : state(0), states() {
            insert( s.begin(), s.end() );
        }

        typedef states_type::const_iterator const_iterator;

        const_iterator begin() const { return states.begin(); }

        const_iterator end() const { return states.end(); }

        operator size_t() const {
            DAI_ASSERT( valid() );
            return( BigInt_size_t( state ) );
        }

        template<typename InputIterator>
        void insert( InputIterator b, InputIterator e ) {
            states.insert( b, e );
            VarSet vars;
            for( const_iterator it = begin(); it != end(); it++ )
                vars |= it->first;
            state = 0;
            state = this->operator()( vars );
        }

        const std::map<Var,size_t>& get() const { return states; }

        operator const std::map<Var,size_t>& () const { return states; }

        size_t operator() ( const Var &v ) const {
            states_type::const_iterator entry = states.find( v );
            if( entry == states.end() )
                return 0;
            else
                return entry->second;
        }

        BigInt operator() ( const VarSet &vs ) const {
            BigInt vs_state = 0;
            BigInt prod = 1;
            for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ ) {
                states_type::const_iterator entry = states.find( *v );
                if( entry != states.end() )
                    vs_state += (BigInt)entry->second * prod;
                prod *= (BigInt)v->states();
            }
            return vs_state;
        }

        void operator++( ) {
            if( valid() ) {
                state++;
                states_type::iterator entry = states.begin();
                while( entry != states.end() ) {
                    if( ++(entry->second) < entry->first.states() )
                        break;
                    entry->second = 0;
                    entry++;
                }
                if( entry == states.end() )
                    state = -1;
            }
        }

        void operator++( int ) {
            operator++();
        }

        bool valid() const {
            return( state >= 0 );
        }

        void reset() {
            state = 0;
            for( states_type::iterator s = states.begin(); s != states.end(); s++ )
                s->second = 0;
        }
};


} // end of namespace dai


#endif