relations.hh

// This file is a part of Aurelia.
// Copyright (C) 2010  Valentin David
// Copyright (C) 2010  University of Bergen
//
// 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/>.
#ifndef __RELATIONS_HH
# define __RELATIONS_HH

#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <iostream>

namespace aurelia {

template <typename T>
struct set: std::unordered_set<T> {
public:
  set() {}

  explicit set(const T& t): std::unordered_set<T>() {
    this->insert(t);
  }

  set(const set&) = default;
  set(set&&) = default;
  set& operator=(const set&) = default;
  set& operator=(set&& other) = default;

  set operator|(const set& other) const {
    set ret = *this;
    ret.insert(other.begin(), other.end());
    return ret;
  }

  set& operator|=(const set& other) {
    this->insert(other.begin(), other.end());
    return *this;
  }

  bool has(const T& t) const {
    return this->find(t) != this->end();
  }
};

template <typename T, typename U = T>
struct rel_set: public std::unordered_multimap<T,U> {
public:
  rel_set() {}
  explicit rel_set(const std::pair<T,U>& t)
    : std::unordered_multimap<T,U>() {
    this->insert(t);
  }

  rel_set(const rel_set&) = default;
  rel_set(rel_set&&) = default;
  rel_set& operator=(const rel_set&) = default;
  rel_set& operator=(rel_set&& other) = default;

  typename std::unordered_multimap<T,U>::iterator
  insert(const typename std::unordered_multimap<T,U>::value_type& v) {
    typename std::unordered_multimap<T,U>::iterator i = this->find(v.first);
    if (i == this->end())
      return this->std::unordered_multimap<T,U>::insert(v);
    for (;i != this->end(); ++i) {
      if ((*i).first != v.first)
        return this->std::unordered_multimap<T,U>::insert(v);
      if ((*i).second == v.second)
        return i;
    }
    return this->std::unordered_multimap<T,U>::insert(v);
  }

  typename std::unordered_multimap<T,U>::iterator
  insert(const typename std::unordered_multimap<T,U>::const_iterator&,
         const typename std::unordered_multimap<T,U>::value_type& v) {
    return this->insert(v);
  }

  template <typename Iterator>
  void insert(Iterator begin, Iterator end) {
    for (; begin != end; ++begin) {
      this->insert(*begin);
    }
  }

  rel_set operator|(const rel_set& other) const {
    rel_set ret = *this;
    ret.insert(other.begin(), other.end());
    return ret;
  }

  rel_set& operator|=(const rel_set& other) {
    this->insert(other.begin(), other.end());
    return *this;
  }

  set<U> operator[](const T& key) const {
    set<U> ret;
    for (typename std::unordered_multimap<T,U>::const_iterator i =
           this->find(key);
         i != this->end(); ++i) {
      if ((*i).first != key)
        break ;
      ret.insert((*i).second);
    }
    return ret;
  }

  rel_set operator*() const {
    rel_set<T> ret = *this;
    bool once_more = true;
    while (once_more) {
      once_more = false;
      rel_set<T> tmp = ret;
      for (typename rel_set<T>::iterator i = ret.begin();
           i != ret.end(); ++i) {
        for (typename rel_set<T>::iterator j =
               ret.find((*i).second);
             j != ret.end(); ++j) {
          if ((*j).first != (*i).second)
            break ;
          typename rel_set<T>::iterator k =
            ret.find((*i).first);
          for (; k != ret.end(); ++k) {
            if ((*k).first != (*i).first)
              break ;
            if ((*k).second == (*j).second)
              break ;
          }
          bool notfound = (k == ret.end());
          if (!notfound)
            notfound = ((*k).first != (*i).first);
          if (notfound) {
            tmp.insert(std::pair<T,T>((*i).first, (*j).second));
            once_more = true;
          }
        }
      }
      ret = tmp;
    }
    return ret;
  }
};

template <typename T>
set<T> carrier(const rel_set<T>& m) {
  set<T> ret;
  std::for_each(m.begin(), m.end(),
                [&ret](const std::pair<T,T>& in) {
                  ret.insert(in.first);
                  ret.insert(in.second);
                });
  return std::move(ret);
}

template <typename Stream, typename T, typename U>
Stream& operator<<(Stream& s, const std::pair<T, U>& p) {
  s << "<" << p.first << "," << p.second << ">";
  return s;
}

template <typename Stream, typename T, typename U>
Stream& operator<<(Stream& s, const rel_set<T, U>& m) {
  bool first = true;
  s << "{";
  std::for_each(m.begin(), m.end(),
                [&s, &first](const std::pair<T, U>& in) {
                  if (first) first = false;
                  else s << ",";
                  s << in;
                });
  s << "}";
  return s;
}

template <typename Stream, typename T>
Stream& operator<<(Stream& s, const set<T>& m) {
  bool first = true;
  s << "{";
  std::for_each(m.begin(), m.end(),
                [&s, &first](const T& in) {
                  if (first) first = false;
                  else s << ",";
                  s << in;
                });
  s << "}";
  return s;
}

template <typename T>
set<T> top(const rel_set<T>& m) {
  set<T> ret;
  std::for_each(m.begin(), m.end(),
                [&ret](const std::pair<T, T>& in) {
                  ret.insert(in.first);
                });
  std::for_each(m.begin(), m.end(),
                [&ret](const std::pair<T, T>& in) {
                  ret.erase(in.second);
                });
  return std::move(ret);
}

template <typename T>
set<T> bottom(const rel_set<T>& m) {
  set<T> ret;
  std::for_each(m.begin(), m.end(),
                [&m, &ret](const std::pair<T, T>& in) {
                  if (m.find(in.second) == m.end())
                    ret.insert(in.second);
                });
  return std::move(ret);
}

template <typename T, typename U, typename V>
rel_set<T, V> operator*(const rel_set<T, U>& a, const rel_set<U, V>& b) {
  rel_set<T, V> ret;

  for (typename rel_set<T, U>::const_iterator i = a.begin();
       i != a.end(); ++i) {
    for (typename rel_set<U, V>::const_iterator j =
           b.find((*i).second);
         j != b.end(); ++j) {
      if ((*j).first != (*i).second)
        break ;
      ret.insert(std::pair<T,V>((*i).first, (*j).second));
    }
  }

  return std::move(ret);
}

template <typename T, typename U>
rel_set<T, U> operator*(const set<T>& a, const set<U>& b) {
  rel_set<T, U> ret;

  for (typename set<T>::const_iterator i = a.begin();
       i != a.end(); ++i) {
    for (typename set<U>::const_iterator j = b.begin();
         j != b.end(); ++j) {
      ret.insert(std::pair<T,U>((*i), (*j)));
    }
  }

  return std::move(ret);
}

template <typename T, typename U>
set<T> domain(const rel_set<T, U>& a) {
  set<T> ret;
  std::for_each(a.begin(), a.end(),
                [&ret](const std::pair<T, U>& p) {
                  ret.insert(p.first);
                });
  return std::move(ret);
}

template <typename T>
set<T> operator-(const set<T>& a, const set<T>& b) {
  set<T> ret;
  std::for_each(a.begin(), a.end(),
                [&b, &ret](const T& t) {
                  if (b.find(t) == b.end())
                    ret.insert(t);
                });
  return std::move(ret);
}

template <typename T>
set<T> reachX(const rel_set<T>& G, const set<T>& Start, const set<T>& Excl) {
  if (Start.empty())
    return Start;
  set<T> direct_reach;
  std::for_each(Start.begin(), Start.end(),
                [&direct_reach, &G, &Excl](const T& in) {
                  direct_reach |= G[in] - Excl;
                });
  return Start | reachX(G, std::move(direct_reach), Excl | Start);
}

}

#endif