#  Copyright (c) 1997-2024
#  Ewgenij Gawrilow, Michael Joswig, and the polymake team
#  Technische Universität Berlin, Germany
#  https://polymake.org
#
#  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 2, or (at your option) any
#  later version: http://www.gnu.org/licenses/gpl.txt.
#
#  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.
#-------------------------------------------------------------------------------

# @category Artificial
# Designates a sequential lattice, that is, having all nodes sorted by rank.
# This is a preferred flavor, because it allows more compact and efficient persistent storage.
declare property_type Sequential : c++(special => 'graph::lattice::Sequential', include => "polymake/graph/Decoration.h");

# @category Artificial
# Designates a non-sequential lattice, that is, having nodes in arbitrary order.
# This flavor should only be used if an algorithm creating the lattice can't guarantee node ordering by rank.
declare property_type Nonsequential : c++(special => 'graph::lattice::Nonsequential', include => "polymake/graph/Decoration.h");

# @category Combinatorics
# Mapping of lattice nodes to their ranks.
# A "rank map" for our purpose is any assignment of natural numbers to the elements of a poset such that the (total) ordering of the numbers refines the (partial) ordering of the corresponding elements.
# @tparam SeqType tag describing node order, must be [[Sequential]] or [[Nonsequential]].
declare property_type InverseRankMap<SeqType> : c++ (name=>"graph::lattice::InverseRankMap", include=>"polymake/graph/Decoration.h") {

   operator @eq : c++;
   
   # @category Combinatorics
   # @param Int r
   # @param Int n
   # Set the rank of a given node
   user_method set_rank(&, $,$) : c++;

   # @category Combinatorics
   # @param Int r
   # @return List<Int> All nodes of rank r.
   user_method nodes_of_rank($) : c++;

   # @category Combinatorics
   # @param Int r1
   # @param Int r2
   # @return List<Int> or Set<Int> All indices of rank r1 <= r <= r2
   user_method nodes_of_rank_range($,$) : c++;

   # @category Combinatorics
   # @return Map<Int, List<Int>> or Map<Int, Pair<Int, Int>>. An actual map object sorting nodes according to rank.
   # In the nonsequential case, each integer (= rank) is mapped to a list of the corresponding nodes.\
   # In the sequential case, it is mapped to the first and last index of all nodes of that rank.
   user_method get_map() : c++;

}

# @category Combinatorics
# Minimal required data associated with [[PartiallyOrderedSet]] nodes.
# @field Set<Int> face face represented by the node
# @field Int rank node rank
declare property_type BasicDecoration : c++ (name=>"graph::lattice::BasicDecoration", include=>"polymake/graph/Decoration.h");


# @category Combinatorics
# A PartiallyOrderedSet is a poset where join and meet exist for any two elements.
# It is realized as a directed graph.
# Some implementations currently restricted to ranked posets (will be fixed soon™).
# @tparam Decoration additional data associated with each node.  Should be derived from [[BasicDecoration]].
# @tparam SeqType tag describing the node ordering, should be [[Sequential]] or [[Nonsequential]].
declare object PartiallyOrderedSet<Decoration, SeqType = Nonsequential> [isa(Decoration, BasicDecoration)] : Graph<Directed> {

   # @category Combinatorics
   # This is the data associated to each node. The prototype for this is [[BasicDecoration]],
   # which consists of properties face and rank.
   # @example [application polytope] [prefer cdd] [require bundled:cdd] The following prints this property of the face lattice of the 2-simplex (triangle):
   # > print simplex(2)->HASSE_DIAGRAM->DECORATION;
   # | ({} 0)
   # | ({0} 1)
   # | ({1} 1)
   # | ({2} 1)
   # | ({1 2} 2)
   # | ({0 2} 2)
   # | ({0 1} 2)
   # | ({0 1 2} 3)
   property DECORATION : NodeMap<Directed, Decoration> : construct(ADJACENCY);

   # @category Combinatorics
   # This property provides an efficient way to enumerate all nodes of a given rank.
   # Internally these are realized differently, depending on whether the PartiallyOrderedSet
   # is [[Sequential]] or [[Nonsequential]].
   # Both provide the same user methods though.
   # Notice that this function is necessary for technical reasons (for any PartiallyOrderedSet, even if it has maximal chains of various lengths).
   # In fact, a "rank map" for our purpose is any assignment of natural numbers to the elements of a poset such that the (total) ordering of the numbers refines the (partial) ordering of the corresponding elements.
   # @example [application polytope] [prefer cdd] [require bundled:cdd] The following prints this property of the face lattice of the 2-simplex (triangle), where the tuples represent the ranges of nodes belonging to a specific rank:
   # > print simplex(2)->HASSE_DIAGRAM->INVERSE_RANK_MAP;
   # | {(0 (0 0)) (1 (1 3)) (2 (4 6)) (3 (7 7))}
   property INVERSE_RANK_MAP : InverseRankMap<SeqType>;

   rule INVERSE_RANK_MAP : ADJACENCY, DECORATION {
     my $irm = new InverseRankMap<SeqType>();
     for my $i (@{nodes($this->ADJACENCY)}) { $irm->set_rank($i, $this->DECORATION->[$i]->rank) }
     $this->INVERSE_RANK_MAP = $irm;
   }

   # @category Combinatorics
   # The index of the top node
   # @example [application polytope] The following prints the top node of the face lattice of the 2-simplex (triangle):
   # > print simplex(2)->HASSE_DIAGRAM->TOP_NODE;
   # | 7
   property TOP_NODE : Int;

   # @category Combinatorics
   # The index of the bottom node
   # @example [application polytope] [prefer cdd] [require bundled:cdd] The following prints the bottom node of the face lattice of the 2-simplex (triangle):
   # > print simplex(2)->HASSE_DIAGRAM->BOTTOM_NODE;
   # | 0
   property BOTTOM_NODE : Int;

   # @category Combinatorics
   # The face of each node, realized as a NodeMap.
   # This property is kept for two reasons: As a convenient way to access only the face part
   # of the decoration (in this case the property is temporary) and
   # for reasons of backwards compatibility.
   # @example [application polytope] [prefer cdd] [require bundled:cdd] The following prints the faces of the face lattice of the 2-simplex (triangle):
   # > print simplex(2)->HASSE_DIAGRAM->FACES;
   # | {}
   # | {0}
   # | {1}
   # | {2}
   # | {1 2}
   # | {0 2}
   # | {0 1}
   # | {0 1 2}
   property FACES : NodeMap<Directed, Set > : construct(ADJACENCY);

   # @category Combinatorics
   # Kept only for backwards compatibility. Basically encodes the [[INVERSE_RANK_MAP]] in
   # FaceLattice objects prior to 3.0.7
   property DIMS : Array<Int>;

   # @category Combinatorics
   # Maximal chains
   property MAXIMAL_CHAINS : Array<Set<Int>>;

   rule MAXIMAL_CHAINS : ADJACENCY, DECORATION, INVERSE_RANK_MAP {
     $this->MAXIMAL_CHAINS = lattice_maximal_chains($this);
   }

   # @category Combinatorics
   # An edge signals the comparability among poset elements (without top and bottom).
   # Index shift by -1 since bottom and top are missing.
   # This is required per specification of the GraphAdjacency class
   property COMPARABILITY_GRAPH : GraphAdjacency<Undirected>;

   rule COMPARABILITY_GRAPH : ADJACENCY, DECORATION, MAXIMAL_CHAINS {
     $this->COMPARABILITY_GRAPH = lattice_comparability_graph($this);
   }
   
   # @category Combinatorics
   # Maximal anti-chains
   property MAXIMAL_ANTI_CHAINS : Array<Set<Int>>;

   rule MAXIMAL_ANTI_CHAINS : COMPARABILITY_GRAPH {
     # FIXME: the following should replace the first two lines
     #   $mc = max_independent_sets($this->COMPARABILITY_GRAPH);
     my $CG = new Graph<Undirected>(ADJACENCY=>$this->COMPARABILITY_GRAPH);
     my $mc = new Array<Set<Int>>(max_cliques(complement_graph($CG)->ADJACENCY));
     my $n = $mc->size();
     for (my $i=0; $i<$n; ++$i) {
       my $this_set = new Set<Int>();
       for (my $e=entire($mc->[$i]); $e; ++$e) {
         $this_set += ($$e);
       }
       $mc->[$i] = $this_set;
     }
     $this->MAXIMAL_ANTI_CHAINS = $mc;
   }
   
   # @category Combinatorics
   # @param Int r
   # @return List<Int> All indices of nodes of rank r
   # @example [application polytope] The following prints the nodes of rank 1 of the face lattice of the 2-simplex (triangle):
   # > print simplex(2)->HASSE_DIAGRAM->nodes_of_rank(1);
   # | {1 2 3}
   user_method nodes_of_rank($) : INVERSE_RANK_MAP {
      my ($this,$d) = @_;
      return $this->INVERSE_RANK_MAP->nodes_of_rank($d);
   }

   # @category Combinatorics
   # @param Int r1
   # @param Int r2
   # @return List<Int> or Set<Int> All indices of rank r1 <= r <= r2
   # @example [application polytope] The following prints the nodes with rank between 1 and 2 of the face lattice of the 2-simplex (triangle):
   # > print simplex(2)->HASSE_DIAGRAM->nodes_of_rank_range(1,2);
   # | {1 2 3 4 5 6}
   user_method nodes_of_rank_range($,$) : INVERSE_RANK_MAP {
      my ($this,$d1,$d2) = @_;
      return $this->INVERSE_RANK_MAP->nodes_of_rank_range($d1,$d2);
   }

   # @category Combinatorics
   # @return Int The rank of the [[TOP_NODE]]
   # @example [application polytope] The following prints the rank of the top node of the face lattice of the 2-simplex (triangle):
   # > print simplex(2)->HASSE_DIAGRAM->rank();
   # | 3
   user_method rank() : DECORATION, TOP_NODE {
      my $this = shift;
      return $this->DECORATION->[$this->TOP_NODE]->rank;
   }

   # @category Combinatorics
   # @return Array<Set<Int> > For each node, contains the indices of maximal nodes it lies below.
   # @example [application polytope] [prefer cdd] [require bundled:cdd] The following prints the dual faces of the face lattice of the 2-simplex (triangle):
   # > print simplex(2)->HASSE_DIAGRAM->dual_faces();
   # | {0 1 2}
   # | {1 2}
   # | {0 2}
   # | {0 1}
   # | {0}
   # | {1}
   # | {2}
   # | {}
   user_method dual_faces() {
      return lattice_dual_faces(shift);
   }

   rule FACES : ADJACENCY, DECORATION {
      $this->FACES(temporary) = faces_map_from_decoration($this->ADJACENCY, $this->DECORATION);
   }
   weight 1.10;

}

# @category Combinatorics
# Backwards compatibility alias for [[PartiallyOrderedSet]]
declare object Lattice = PartiallyOrderedSet;

# A [[PartiallyOrderedSet]] with a [[BasicDecoration]], which corresponds to the legacy HasseDiagram type
declare object_specialization Basic<SeqType> = PartiallyOrderedSet<BasicDecoration, SeqType> {

   rule DECORATION, INVERSE_RANK_MAP, TOP_NODE, BOTTOM_NODE : FACES, DIMS, ADJACENCY {
      #Backwards compatibility rule
      migrate_hasse_properties($this);
      $this->remove("DIMS");
      $this->remove("FACES"); #FIXME This has currently no effect - why?
   }
   weight 1.10;
}

# Local Variables:
# mode: perl
# cperl-indent-level:3
# indent-tabs-mode:nil
# End: