poset.h

Go to the documentation of this file.

/*
  Copyright (C) 2004,2005 Fokko du Cloux
  part of the Atlas of Lie Groups and Representations

  For license information see the LICENSE file
*/

#ifndef POSET_H  /* guard against multiple inclusions */
#define POSET_H

#include <vector>

#include "bitmap.h"
#include "tags.h"

#include "poset_fwd.h"
#include "graph_fwd.h"


namespace atlas {

namespace poset {



/******** type definitions **************************************************/

class Poset {
  std::vector<bitmap::BitMap> d_below;

  void new_cover(unsigned long  x,unsigned long y) // add $x<y$, $y$ maximal
  { (d_below[y] |= d_below[x]).insert(x); }


 public:

// constructors and destructors
  Poset() : d_below() {}

  explicit Poset(size_t n); // poset without any (nontrivial) comparabilities

  template<typename C> // |C| is some container of |set::Elt|
  explicit Poset(const std::vector<C>& hasse);

  Poset(size_t n,const std::vector<Link>&);

  Poset(const Poset& p, tags::DualTag);

  ~Poset() {}

// swap
  void swap(Poset& other) {
    d_below.swap(other.d_below);
  }

// accessors

  bool lesseq(set::Elt i, set::Elt j) const
  { return i<j ? d_below[j].isMember(i) : i==j; }

  bool operator==(const Poset& other) const;

  size_t size() const { return d_below.size(); }

  const bitmap::BitMap& below(set::Elt y)const { return d_below[y]; }
  bitmap::BitMap above(set::Elt x) const;

  set::EltList maxima(const bitmap::BitMap&) const;
  set::EltList minima(const bitmap::BitMap&) const;

  set::EltList covered_by(set::Elt y) const { return maxima(d_below[y]); }
  set::EltList covers_of(set::Elt x) const;

  graph::OrientedGraph hasseDiagram() const; // full Hasse diagram
  graph::OrientedGraph hasseDiagram(set::Elt max) const; // part |<=max|

  unsigned long n_comparable() const;

// manipulators
  void resize(unsigned long);

  void extend(const std::vector<Link>& lks)
  {
    for (size_t i=0; i<lks.size(); ++i)
      new_cover(lks[i].first,lks[i].second);
  }

  // add a new maximal element, comparable with elements in |container|
  template<typename C> void new_max(C container)
  {
    size_t y=d_below.size();
    d_below.push_back(bitmap::BitMap(y));

    for (typename C::const_iterator
       it=container.begin(); it!=container.end(); ++it)
      new_cover(*it,y);
  }

}; // class Poset


/* ********************** Function(s) *****************************/

// memory-efficient version of |Poset(hasse).n_comparable()|
unsigned long n_comparable_from_Hasse
  (const std::vector<set::EltList>& hasse);

template<typename C>
Poset::Poset(const std::vector<C>& hasse)
: d_below(hasse.size())
{
  for (size_t i=0; i<hasse.size(); ++i)
  {
    d_below[i].set_capacity(i);
    for (typename C::const_iterator
       it=hasse[i].begin(); it!=hasse[i].end(); ++it)
      new_cover(*it,i);
  }
}


} // |namespace poset|

} // |namespace atlas|

#endif