binary_linear_space.hpp

Go to the documentation of this file.

#pragma once
 
#include <vector>
 
#include "permutations.hpp"
 
namespace tu
{
 
  class binary_linear_space
  {
  public:
 
    typedef std::vector <bool> vector_type;
 
    explicit binary_linear_space(size_t length)
    {
      _length = length;
      _dimension = 0;
      _vectors.push_back(vector_type(length, false));
    }
 
    binary_linear_space(const binary_linear_space& other)
    {
      _length = other._length;
      _dimension = other._dimension;
      _vectors.clear();
      _vectors.reserve(other.vectors());
      std::copy(other._vectors.begin(), other._vectors.end(), std::back_inserter(_vectors));
    }
 
    const vector_type& operator[](size_t index) const
    {
      return _vectors[index];
    }
 
    inline size_t length() const
    {
      return _length;
    }
 
    inline size_t vectors() const
    {
      return _vectors.size();
    }
 
    inline size_t dimension() const
    {
      return _dimension;
    }
 
    inline bool insert_checked(const vector_type& vector)
    {
      assert (vector.size() == length());
 
      if (is_spanned(vector))
        return false;
 
      insert(vector);
      return true;
    }
 
    void insert(const vector_type& vector)
    {
      assert (vector.size() == length());
 
      size_t begin = 1 << _dimension;
      ++_dimension;
      size_t end = 1 << _dimension;
      _vectors.resize(end, vector);
      for (size_t current = begin + 1; current < end; current++)
        vector_sum(vector, _vectors[current - begin], _vectors[current]);
    }
 
    int find(const vector_type& vector) const
    {
      assert (vector.size() == length());
 
      for (size_t j = 0; j < _vectors.size(); ++j)
      {
        const vector_type& current_vector = _vectors[j];
        bool same = true;
        for (size_t i = 0; i < _length; ++i)
        {
          if (current_vector[i] ? !vector[i] : vector[i])
          {
            same = false;
            break;
          }
        }
        if (same)
          return j;
      }
      return -1;
    }
 
    inline bool is_spanned(const vector_type& vector) const
    {
      assert (vector.size() == length());
 
      return find(vector) >= 0;
    }
 
  protected:
 
    static void vector_sum(const vector_type& first, const vector_type& second, vector_type& result)
    {
      assert (first.size() == second.size());
      assert (first.size() == result.size());
 
      for (size_t i = 0; i < first.size(); ++i)
      {
        result[i] = first[i] ? !second[i] : second[i];
      }
    }
 
  private:
    size_t _length;
    size_t _dimension;
    std::vector <vector_type> _vectors;
  };
 
  inline std::ostream& operator<<(std::ostream& stream, const binary_linear_space& space)
  {
    for (size_t i = 0; i < space.vectors(); ++i)
    {
      for (size_t j = 0; j < space.length(); ++j)
      {
        stream << ' ' << (space[i][j] ? '1' : '0');
      }
      stream << '\n';
    }
    return stream;
  }
 
} /* namespace tu */