#  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.
#-------------------------------------------------------------------------------

# @topic category objects/QuotientSpace/properties/Basic properties
# Properties defining a quotient space.


# A topological quotient space obtained from a [[Polytope]] by identifying faces.
# This object will sit inside the polytope.
# @category Symmetry
declare object QuotientSpace {

# @category Basic properties
# The group encoding the quotient space.
# The faces of the space are the orbits of the faces of the polytope under the group.
property IDENTIFICATION_ACTION : group::PermutationAction;

# @category Combinatorics
# The dimension of the quotient space, defined to be the dimension of the polytope.
property DIM : Int;

# @category Combinatorics
# A simplicial complex obtained by two stellar subdivisions of the defining polytope.
property SIMPLICIAL_COMPLEX : topaz::SimplicialComplex : multiple;

# @category Combinatorics
# The faces of the quotient space, ordered by dimension. One representative of each orbit class is kept.
property FACES : Array<Set<Set<Int>>>;

# @category Combinatorics
# The orbits of faces of the quotient space, ordered by dimension.
property FACE_ORBITS : Array<Set<Set<Set<Int>>>>;

# @category Combinatorics
# Some listing of equivalence classes of faces of the quotient space, ordered by dimension.
# Analogous to FACE_ORBITS, but not necessarily coming from a group
property FACE_CLASSES : Array<Set<Set<Set<Int>>>>;

# @category Combinatorics
# The symmetry group induced by the symmetry group of the polytope on the [[FACES]] of the quotient space
property SYMMETRY_GROUP : group::Group;

# @category Combinatorics
# All simplices in the quotient space
property SIMPLICES : Array<Array<Set<Int>>>;

# @category Combinatorics
# The (//d//-1)-dimensional simplices in the interior.    
property REPRESENTATIVE_INTERIOR_RIDGE_SIMPLICES : Array<Bitset>;

# @category Combinatorics
# The interior //d//-dimensional simplices of a cone of combinatorial dimension //d//
property REPRESENTATIVE_MAX_INTERIOR_SIMPLICES : Array<Bitset>;

# @category Combinatorics
# The boundary (//d//-1)-dimensional simplices of a cone of combinatorial dimension //d//
property REPRESENTATIVE_MAX_BOUNDARY_SIMPLICES : Array<Bitset>;

# @category Combinatorics
# The simplices made from points of the quotient space (also internal simplices, not just faces)
property N_SIMPLICES : Array<Int>;

# @category Combinatorics
# An array that tells how many faces of each dimension there are
property F_VECTOR : Array<Int>;

# @category Combinatorics
# a SparseMatrix whose rows are the sum of all cocircuit equations corresponding to a fixed symmetry class of interior ridge
property COCIRCUIT_EQUATIONS : SparseMatrix;

# @category Combinatorics
# A lower bound for the number of simplices needed to triangulate the quotient space
property SIMPLEXITY_LOWER_BOUND: Int;

}

object Polytope {


# @category Geometry
# A topological quotient space obtained from a polytope by identifying faces.
property QUOTIENT_SPACE : QuotientSpace : multiple;

rule QUOTIENT_SPACE(any).DIM = COMBINATORIAL_DIM;

}

# @category Quotient spaces
# Return a 2-dimensional __cylinder__ obtained by identifying two opposite sides of a square.
# @return Polytope
# @example To obtain a topological space homeomorphic to a cylinder, type
# > $p = cylinder_2();
# > print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->GENERATORS;
# | 2 3 0 1
# > print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->ORBITS;
# | {0 2}
# | {1 3}
# Thus, vertices 0,2 and vertices 1,3 are identified.
# > print $p->QUOTIENT_SPACE->FACES;
# | {{0} {1}}
# | {{0 1} {0 2} {1 3}}
# | {{0 1 2 3}}
# Thus, after identification two vertices, three edges, and one two-dimensional face remain:
# > print $p->QUOTIENT_SPACE->F_VECTOR;
# | 2 3 1

user_function cylinder_2 {
    my $p = cube(2);
    my $g = new group::PermutationAction(GENERATORS=>[[2,3,0,1]]);
    my $qs = new QuotientSpace(IDENTIFICATION_ACTION=>$g);
    $p->QUOTIENT_SPACE = $qs;
    $p->description="2-dimensional cylinder";
    return $p; 
}

# @category Quotient spaces
# Return the 3-dimensional Euclidean manifold obtained by identifying opposite faces
# of a 3-dimensional cube by a quarter turn. After identification, two classes 
# of vertices remain.
# @return Polytope
# @example To obtain a topological space homeomorphic to the quarter turn manifold, type
# > $p = quarter_turn_manifold();
# > print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->GENERATORS;
# | 5 7 4 6 2 0 3 1
# | 6 2 1 5 7 3 0 4
# To see which vertices are identified, type
# > print $p->QUOTIENT_SPACE->IDENTIFICATION_ACTION->ORBITS;
# | {0 3 5 6}
# | {1 2 4 7}
# Thus, two classes of vertices remain, with 0 and 1 being representatives. 
# To see the faces remaining after identification, type
# > print $p->QUOTIENT_SPACE->FACES;
# | {{0} {1}}
# | {{0 1} {0 2} {0 4} {0 7}}
# | {{0 1 2 3} {0 1 4 5} {0 1 6 7}}
# | {{0 1 2 3 4 5 6 7}}
# > print $p->QUOTIENT_SPACE->F_VECTOR;
# | 2 4 3 1
user_function quarter_turn_manifold {
    my $p = cube(3);
    my $g = new group::PermutationAction(GENERATORS=>[[5,7,4,6,2,0,3,1],[6,2,1,5,7,3,0,4]]); 
    my $q = new QuotientSpace(IDENTIFICATION_ACTION=>$g);
    $q->name = "Quarter turn manifold";
    $q->description = "Quarter turn manifold obtained by identifying facets of a 3-cube";
    $p->QUOTIENT_SPACE = $q;
    return $p; 
}

# @category Quotient spaces
# For a centrally symmetric polytope, divide
# out the central symmetry, i.e, identify diametrically opposite faces.
# @param Polytope P, centrally symmetric
# @example
# > $P = cube(3);
# > cs_quotient($P);
# > print $P->CS_PERMUTATION;
# | 7 6 5 4 3 2 1 0
# The zeroth vertex gets identified with the seventh, the first with the sixth etc.

user_function cs_quotient {
    my $this = shift;
    die "cs_quotient: input not centrally symmetric" unless $this->CENTRALLY_SYMMETRIC;
    my $gen = $this->CS_PERMUTATION;
    my $arr = new Array<Array<Int>>([ $gen ]);
    my $g = new group::PermutationAction(GENERATORS=>$arr);
    my $qs = new QuotientSpace(IDENTIFICATION_ACTION=>$g);
    $qs->description = "Quotient space mod Z_2 of " . $this->description; 
    $this->QUOTIENT_SPACE = $qs;
    return $this;
}

# @category Quotient spaces
# Return the 4-dimensional hyperbolic manifold obtained by Michael Davis
# @return Polytope 
# [Proceedings of the AMS, Vol. 93, No. 2 (Feb., 1985), pp. 325-328]
# by identifying opposite faces of the 120-cell
# @example The Davis manifold is the centrally symmetric quotient of the regular 210-cell:
# > $d = davis_manifold();
# > print $d->F_VECTOR;
# | 600 1200 720 120
# > print $d->QUOTIENT_SPACE->F_VECTOR;
# | 300 600 360 60 1

user_function davis_manifold { 
    my $c120=regular_120_cell();
    return cs_quotient($c120);
}


object Polytope {

rule QUOTIENT_SPACE.FACES, QUOTIENT_SPACE.FACE_ORBITS, QUOTIENT_SPACE.SYMMETRY_GROUP.PERMUTATION_ACTION(new).GENERATORS : \
    COMBINATORIAL_DIM, N_VERTICES, \
    HASSE_DIAGRAM.ADJACENCY, HASSE_DIAGRAM.DECORATION, HASSE_DIAGRAM.INVERSE_RANK_MAP, HASSE_DIAGRAM.TOP_NODE, HASSE_DIAGRAM.BOTTOM_NODE, \
    GROUP.VERTICES_ACTION.GENERATORS, QUOTIENT_SPACE.IDENTIFICATION_ACTION.GENERATORS {
        quotient_space_faces($this);
}

rule QUOTIENT_SPACE.FACES, QUOTIENT_SPACE.FACE_ORBITS : \
    COMBINATORIAL_DIM, N_VERTICES, \
    HASSE_DIAGRAM.ADJACENCY, HASSE_DIAGRAM.DECORATION, HASSE_DIAGRAM.INVERSE_RANK_MAP, HASSE_DIAGRAM.TOP_NODE, HASSE_DIAGRAM.BOTTOM_NODE, \
    QUOTIENT_SPACE.IDENTIFICATION_ACTION.GENERATORS {
        quotient_space_faces($this);
}

rule QUOTIENT_SPACE.F_VECTOR : QUOTIENT_SPACE.FACES {
    my $cds = $this->QUOTIENT_SPACE->FACES;
    my @n_vector = map { $cds->[$_]->size } (0..$cds->size-1);
    $this->QUOTIENT_SPACE->F_VECTOR = \@n_vector;
}

rule QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).FACETS, QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).VERTEX_LABELS, \
     QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).PURE,  QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).DIM : \
     VERTICES_IN_FACETS, HASSE_DIAGRAM.ADJACENCY, HASSE_DIAGRAM.DECORATION, HASSE_DIAGRAM.INVERSE_RANK_MAP, HASSE_DIAGRAM.TOP_NODE, HASSE_DIAGRAM.BOTTOM_NODE, \
    QUOTIENT_SPACE.IDENTIFICATION_ACTION {
    $this->QUOTIENT_SPACE->SIMPLICIAL_COMPLEX = topaz::bs2quotient_by_group($this); 
}

rule QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).FACETS, QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).VERTEX_LABELS, \
     QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).PURE,  QUOTIENT_SPACE.SIMPLICIAL_COMPLEX(new).DIM : \
     VERTICES_IN_FACETS, HASSE_DIAGRAM.ADJACENCY, HASSE_DIAGRAM.DECORATION, HASSE_DIAGRAM.INVERSE_RANK_MAP, HASSE_DIAGRAM.TOP_NODE, HASSE_DIAGRAM.BOTTOM_NODE, \
     QUOTIENT_SPACE.FACE_CLASSES {
    $this->QUOTIENT_SPACE->SIMPLICIAL_COMPLEX = topaz::bs2quotient_by_equivalence($this); 
}

rule QUOTIENT_SPACE.SIMPLICES : COMBINATORIAL_DIM, VERTICES, QUOTIENT_SPACE.SYMMETRY_GROUP.PERMUTATION_ACTION.GENERATORS {
    $this->QUOTIENT_SPACE->SIMPLICES = representative_simplices($this->COMBINATORIAL_DIM, $this->VERTICES, $this->QUOTIENT_SPACE->SYMMETRY_GROUP->PERMUTATION_ACTION->GENERATORS);
}

# @category Combinatorics
# The equivalence classes of maximal-dimensional simplices in the interior and boundary under a symmetry group 
rule QUOTIENT_SPACE.REPRESENTATIVE_INTERIOR_RIDGE_SIMPLICES, QUOTIENT_SPACE.REPRESENTATIVE_MAX_BOUNDARY_SIMPLICES \
     : COMBINATORIAL_DIM, RAYS_IN_FACETS, RAYS, QUOTIENT_SPACE.SYMMETRY_GROUP.PERMUTATION_ACTION.GENERATORS {
    my $pair = representative_interior_and_boundary_ridges($this);
    $this->QUOTIENT_SPACE->REPRESENTATIVE_INTERIOR_RIDGE_SIMPLICES = $pair->first;
    $this->QUOTIENT_SPACE->REPRESENTATIVE_MAX_BOUNDARY_SIMPLICES = $pair->second;
}

# @category Combinatorics
# The equivalence classes of maximal-dimensional simplices in the boundary under a symmetry group 
rule QUOTIENT_SPACE.REPRESENTATIVE_MAX_INTERIOR_SIMPLICES : COMBINATORIAL_DIM, RAYS, QUOTIENT_SPACE.SYMMETRY_GROUP.PERMUTATION_ACTION.GENERATORS {
    $this->QUOTIENT_SPACE->REPRESENTATIVE_MAX_INTERIOR_SIMPLICES = representative_max_interior_simplices($this->COMBINATORIAL_DIM, $this->RAYS, $this->QUOTIENT_SPACE->SYMMETRY_GROUP->PERMUTATION_ACTION->GENERATORS);
}

rule QUOTIENT_SPACE.N_SIMPLICES : QUOTIENT_SPACE.SIMPLICES {
    my $cds = $this->QUOTIENT_SPACE->SIMPLICES;
    my @n_vector = map { $cds->[$_]->size } (0..$cds->size-1);
    $this->QUOTIENT_SPACE->N_SIMPLICES = \@n_vector;
}

rule QUOTIENT_SPACE.COCIRCUIT_EQUATIONS : QUOTIENT_SPACE.REPRESENTATIVE_INTERIOR_RIDGE_SIMPLICES, QUOTIENT_SPACE.REPRESENTATIVE_MAX_INTERIOR_SIMPLICES, COMBINATORIAL_DIM, RAYS, RAYS_IN_FACETS, QUOTIENT_SPACE.SYMMETRY_GROUP.PERMUTATION_ACTION.GENERATORS {
   my $d = $this->COMBINATORIAL_DIM;
   my $interior_ridge_reps = $this->QUOTIENT_SPACE->REPRESENTATIVE_INTERIOR_RIDGE_SIMPLICES;
   my $facet_reps = $this->QUOTIENT_SPACE->REPRESENTATIVE_MAX_INTERIOR_SIMPLICES;
   $this->QUOTIENT_SPACE->COCIRCUIT_EQUATIONS = symmetrized_cocircuit_equations_0($d, $this->RAYS, $this->RAYS_IN_FACETS, $this->QUOTIENT_SPACE->SYMMETRY_GROUP->PERMUTATION_ACTION->GENERATORS, $interior_ridge_reps, $facet_reps);
}

rule QUOTIENT_SPACE.SIMPLEXITY_LOWER_BOUND : COMBINATORIAL_DIM, RAYS, RAYS_IN_FACETS, QUOTIENT_SPACE.REPRESENTATIVE_MAX_BOUNDARY_SIMPLICES, QUOTIENT_SPACE.REPRESENTATIVE_MAX_INTERIOR_SIMPLICES, VOLUME, QUOTIENT_SPACE.COCIRCUIT_EQUATIONS, QUOTIENT_SPACE.SYMMETRY_GROUP.PERMUTATION_ACTION.GENERATORS, QUOTIENT_SPACE.IDENTIFICATION_ACTION.GENERATORS {
   my $d = $this->COMBINATORIAL_DIM;
   my $exterior_ridge_reps = $this->QUOTIENT_SPACE->REPRESENTATIVE_MAX_BOUNDARY_SIMPLICES;
   my $facet_reps = $this->QUOTIENT_SPACE->REPRESENTATIVE_MAX_INTERIOR_SIMPLICES;
   $this->QUOTIENT_SPACE->SIMPLEXITY_LOWER_BOUND = quotient_space_simplexity_lower_bound($d, $this->VERTICES, $this->VERTICES_IN_FACETS, $exterior_ridge_reps, $facet_reps, $this->VOLUME, $this->QUOTIENT_SPACE->COCIRCUIT_EQUATIONS, $this->QUOTIENT_SPACE->SYMMETRY_GROUP->PERMUTATION_ACTION->GENERATORS, $this->QUOTIENT_SPACE->IDENTIFICATION_ACTION->GENERATORS);
}

}

# @category Quotient spaces
# outputs a linear program whose optimal value is a lower bound for the number of simplices 
# necessary to triangulate the polytope in such a way that its symmetries respect the triangulation
# of the boundary.
user_function write_quotient_space_simplexity_ilp<Scalar>(Polytope<Scalar> $) {
    my ($q, $outfilename) = @_;
    return quotient_space_simplexity_ilp($q->COMBINATORIAL_DIM, $q->VERTICES, $q->VERTICES_IN_FACETS, $q->QUOTIENT_SPACE->REPRESENTATIVE_MAX_BOUNDARY_SIMPLICES, $q->QUOTIENT_SPACE->REPRESENTATIVE_MAX_INTERIOR_SIMPLICES, $q->VOLUME, $q->QUOTIENT_SPACE->COCIRCUIT_EQUATIONS, $q->QUOTIENT_SPACE->SYMMETRY_GROUP->PERMUTATION_ACTION->GENERATORS, $q->QUOTIENT_SPACE->IDENTIFICATION_ACTION->GENERATORS, filename => $outfilename);
}


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