Poset.h

Go to the documentation of this file.

#ifndef INCLUDE_TEMPLE_POSET_H
#define INCLUDE_TEMPLE_POSET_H

#include "boost/logic/tribool.hpp"
#include <vector>
#include <string>
#include <algorithm>
#include <stdexcept>

namespace Scine {
namespace Molassembler {
namespace Temple {

template<typename T>
class Poset {
public:
  struct Subset {
    using const_iterator = typename std::vector<T>::const_iterator;

    std::vector<T> values;
    bool ordered = false;

    Subset(T value) {
      values.push_back(std::move(value));
    }

    Subset(std::vector<T> passValues) : values(std::move(passValues)) {}

    template<typename Iter>
    Subset(Iter begin, Iter end) : values(begin, end) {}

    const_iterator begin() const {
      return std::begin(values);
    }

    const_iterator end() const {
      return std::end(values);
    }
  };

  using const_iterator = typename std::vector<Subset>::const_iterator;

  template<typename Container>
  Poset(const Container& container) {
    setUnorderedValues(
      std::begin(container),
      std::end(container)
    );
  }

  template<typename Iter>
  Poset(Iter&& begin, Iter&& end) {
    setUnorderedValues(
      std::forward<Iter>(begin),
      std::forward<Iter>(end)
    );
  }

  template<typename Iter>
  void setUnorderedValues(Iter&& begin, Iter&& end) {
    subsets.clear();
    subsets.emplace_back(std::forward<Iter>(begin), std::forward<Iter>(end));
  }

  template<typename Comparator>
  void orderUnordered(Comparator&& comparator) {
    auto lowerBoundComparator = [&comparator](const Subset& set, const T& t) -> bool {
      return comparator(set.values.front(), t);
    };

    std::vector<Subset> newSubsets;
    newSubsets.reserve(subsets.size());
    for(Subset& subset : subsets) {
      // If the subset is already ordered, move it to the newSubsets
      if(subset.ordered) {
        newSubsets.push_back(std::move(subset));
        continue;
      }

      // Unordered Subsets may split into multiple Subsets
      std::vector<Subset> splat;
      for(auto& value : subset) {
        // Find which Subset this element belongs to using binary search
        auto findIter = std::lower_bound(
          std::begin(splat),
          std::end(splat),
          value,
          lowerBoundComparator
        );

        if(findIter == std::end(splat)) {
          // This element does not belong to any existing Subset, so we create one
          splat.emplace_back(std::move(value));
          continue;
        }

        if(!comparator(value, findIter->values.front())) {
          // This element belongs to the set pointed to by findIter
          findIter->values.push_back(std::move(value));
          continue;
        }

        /* Last possibility: This element is part of a new set that should be
         * inserted before the set pointed to by findIter
         */
        splat.emplace(
          findIter,
          std::move(value)
        );
      }

      // Finalize single-element sets
      for(auto& splatSet : splat) {
        if(splatSet.values.size() == 1) {
          splatSet.ordered = true;
        }
      }

      // Move the split up sets into the new subsets
      std::move(
        std::begin(splat),
        std::end(splat),
        std::back_inserter(newSubsets)
      );
    }

    // Overwrite subsets with the new ones
    subsets = std::move(newSubsets);
  }

  void finalize() {
    for(Subset& subset : subsets) {
      subset.ordered = true;
    }
  }

  const_iterator begin() const {
    return std::begin(subsets);
  }

  const_iterator end() const {
    return std::end(subsets);
  }

  std::string toString() const {
    std::string str = "{";
    for(const Subset& subset : subsets) {
      auto it = std::begin(subset);
      while(true) {
        str += std::to_string(*it);
        if(++it != std::end(subset)) {
          str += ", ";
        } else {
          str += " | ";
          break;
        }
      }
    }
    str += "}";

    return str;
  }

  const_iterator find(const T& a) const {
    return std::find_if(
      std::begin(subsets),
      std::end(subsets),
      [&a](const Subset& subset) -> bool {
        return std::find(
          std::begin(subset),
          std::end(subset),
          a
        ) != std::end(subset);
      }
    );
  }

  boost::tribool compare(const T& a, const T& b) const {
    const auto subsetEnd = std::end(subsets);
    auto aIter = find(a);

    if(aIter == subsetEnd) {
      throw std::invalid_argument("The first argument to compare is not in the poset");
    }

    auto bIter = find(b);

    if(bIter == subsetEnd) {
      throw std::invalid_argument("The second argument to compare is not in the poset");
    }

    /* If both elements are not in the same Subset, then they are ordered by
     * their position in the list of Subsets.
     */
    if(aIter != bIter) {
      return aIter < bIter;
    }

    /* So now we know both outer iterators point to the same subset and that
     * neither of those outer iterators is the end iterator. So we can safely
     * look at the Subset pointed to by the (matching) outer iterators.
     *
     * If the subset is ordered, then the elements are equal. Otherwise, the
     * order is indeterminate.
     */
    if(aIter.first->ordered) {
      return false;
    }

    return boost::indeterminate;
  }

  std::vector<
    std::vector<T>
  > extract() {
    const unsigned N = subsets.size();
    std::vector<
      std::vector<T>
    > extracted(N);

    for(unsigned i = 0; i < N; ++i) {
      extracted[i] = std::move(subsets[i].values);
    }

    subsets.clear();
    return extracted;
  }

private:
  std::vector<Subset> subsets;
};

} // namespace Temple
} // namespace Molassembler
} // namespace Scine

#endif