Neighbours_Rn.h

Go to the documentation of this file.

// politopix allows to make computations on polytopes such as finding vertices, intersecting, Minkowski sums, ...
//     Copyright (C) 2014-2015 : Delos Vincent
//
//     This program 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.
//
//     This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.
//
// I2M (UMR CNRS 5295 / University of Bordeaux)
 
#ifndef NEIGHBOURS_Rn
#define NEIGHBOURS_Rn
#include "HalfSpace_Rn.h"
 
 
class Neighbours_Rn {
 
public:
  Neighbours_Rn():_iterator(0) {}
 
  void addGenerator(
    const std::vector< unsigned int >& commonFacets,
    unsigned int numbergenIN,
    unsigned int numbergenOUT,
    HalfSpace_Rn::State state) {
 
    //std::cout << std::endl << "DUMP CANDIDATE:" << std::endl;
    //std::cout << "Gin candidate: " << numbergenIN << " ";
    //std::cout << ", Gout candidate: " << numbergenOUT << std::endl;
    //dump(std::cout);
    bool alreadyInsertedPair=false;
    {for (unsigned int i=0; i<_HSPerNewGenerators.size(); ++i) {
      if (_HSPerNewGenerators[i].size() > commonFacets.size()) {
        // Larger set first.
        if (std::includes(_HSPerNewGenerators[i].begin(), _HSPerNewGenerators[i].end(), commonFacets.begin(), commonFacets.end())) {
          // No need to do anything as the current generator set of
          // half-spaces is included in the set number j.
          //std::cout << "false1 (size=" << i << ")" << std::endl;
          return;
        }
      }
      else {
        if (std::includes(commonFacets.begin(), commonFacets.end(), _HSPerNewGenerators[i].begin(), _HSPerNewGenerators[i].end())) {
          // Substitute the old generator to be removed with the current one.
          if (alreadyInsertedPair == false) {
            _HSPerNewGenerators[i]  = commonFacets;
            _GeneratorsInNumber[i]  = numbergenIN;
            _GeneratorsOutNumber[i] = numbergenOUT;
            _GeneratorsState[i] = state;
            alreadyInsertedPair = true;
          }
          else {
            // This case is rare but can occur, when we need to erase two generators already
            // in the list. Take care of not inserting twice the same so shift the arrays.
            {for (unsigned int ii=i; ii<_HSPerNewGenerators.size()-1; ++ii) {
              _GeneratorsOutNumber[ii]= _GeneratorsOutNumber[ii+1];
              _HSPerNewGenerators[ii] = _HSPerNewGenerators[ii+1];
              _GeneratorsInNumber[ii] = _GeneratorsInNumber[ii+1];
              _GeneratorsState[ii] = _GeneratorsState[ii+1];
            }}
            _GeneratorsOutNumber.pop_back();
            _GeneratorsInNumber.pop_back();
            _HSPerNewGenerators.pop_back();
            _GeneratorsState.pop_back();
          }
        }
      }
    }}
    if (alreadyInsertedPair == false) {
      _GeneratorsInNumber.push_back(numbergenIN);
      _GeneratorsOutNumber.push_back(numbergenOUT);
      _HSPerNewGenerators.push_back(commonFacets);
      _GeneratorsState.push_back(state);
      //std::cout << "true (total=" << _HSPerNewGenerators.size() << std::endl;
    }
    //dump(std::cout);
  }
 
  void addGeneratorWithoutCheck(
    const std::vector< unsigned int >& commonFacets,
    unsigned int numbergenIN,
    unsigned int numbergenOUT,
    HalfSpace_Rn::State state) {
    _GeneratorsInNumber.push_back(numbergenIN);
    _GeneratorsOutNumber.push_back(numbergenOUT);
    _HSPerNewGenerators.push_back(commonFacets);
    _GeneratorsState.push_back(state);
  }
 
  void begin() {_iterator=0; checkIterator();}
 
  void next() {++_iterator; checkIterator();}
 
  void checkIterator() {
    while (_iterator!=_HSPerNewGenerators.size() && _GeneratorsState[ _iterator]==HalfSpace_Rn::hs_ON)
      ++_iterator;
  }
 
  bool end() const {return (_iterator==_HSPerNewGenerators.size());}
 
  unsigned int currentGenInNumber() const {return _GeneratorsInNumber[ _iterator];}
 
  unsigned int currentGenOutNumber() const {return _GeneratorsOutNumber[_iterator];}
 
  const std::vector< unsigned int >& commonHalfSpaces() const {return _HSPerNewGenerators[_iterator];}
 
  void dump(std::ostream &ofs) const {
    ofs << "New gen:" << std::endl;
    unsigned int i=0;
    std::vector< std::vector< unsigned int > >::const_iterator ite;
    for (ite=_HSPerNewGenerators.begin(); ite!=_HSPerNewGenerators.end(); ++ite) {
      ofs << "(Gin=  " << _GeneratorsInNumber[i]  << ",";
      ofs << " Gout= " << _GeneratorsOutNumber[i] << ") ";
      ofs << "(State=" << HalfSpace_Rn::getStateAsText(_GeneratorsState[i]) << ")" << std::endl;
      i++;
      std::copy((*ite).begin(), (*ite).end(), std::ostream_iterator< unsigned int >(ofs, " ") );
      ofs << std::endl;
    }
  }
 
protected:
  unsigned int _iterator;
  std::vector< HalfSpace_Rn::State > _GeneratorsState;
  std::vector< unsigned int > _GeneratorsInNumber;
  std::vector< unsigned int > _GeneratorsOutNumber;
  std::vector< std::vector< unsigned int > > _HSPerNewGenerators;
};
 
#endif