#  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 property_types/Set Types
# In this category you find all property types related to sets, such as Set, Map, HashMap, IncidenceMatrix, ...

# @topic category functions/Set Operations
# This category contains functions performing operations on [[Set|Sets]].

# @category Set Types
# A type for ordered sets containing elements of type //Element//.
#
# @example
# You can for example create a new Set by:
# > $s1 = new Set(2, 3, 5, 7);
# > $s2 = new Set(4, 5);
# You can perform set theoretic operations:
# union
# > print $s1 + $s2;
# | {2 3 4 5 7}
# intersection
# > print $s1 * $s2;
# | {5}
# difference
# > print $s1 - $s2;
# | {2 3 7}
# symmetric difference
# > print $s1 ^ $s2;
# | {2 3 4 7}
# @tparam Element default: [[Int]]
declare property_type Set<Element=Int> : c++ (include => "polymake/Set.h") {

   operator @sets @compare : c++;

   operator ~ (*&& const) : c++;

   # a shortcut for single element set construction, not allowed in C++
   method construct(Element) {
       my $proto=shift;
       Core::CPlusPlus::std_parsing_constructor($proto, \@_);
   }

   # Check if e is contained in the set.
   # @param Element e element check for
   # @return Bool
   user_method contains {
      my ($self, $key)=@_;
      exists $self->{$key};
   }

   # The cardinality of the set.
   # @return Int
   user_method size() : c++;

   # The first element of the set, that is, the smallest element
   # @return Int
   user_method front() : c++;

   # The last element of the set, that is, the largest element
   # @return Int
   user_method back() : c++;

   # Add to the set, report true if existed formerly.
   # @param Element e element to insert into the set
   # @return Bool
   user_method collect(&, *) : c++;
}

# @category Set Operations
# Analyze the inclusion relation of two sets.
# @param Set s1
# @param Set s2
# @return Int 	0	if s1 = s2,
#		-1 	if s1 ⊂ s2,
#		1	if s1 ⊃ s2,
#		2	otherwise.
# @example
# > $s1 = new Set(1,2,3);
# > $s2 = $s1 - 1;
# > print incl($s1, $s2);
# | 1
# > print incl($s2, $s1);
# | -1
# > print incl($s1, $s1);
# | 0
# > print incl($s2, $s1-$s2);
# | 2

user_function incl(Set,Set) : c++ (include => "polymake/Set.h");


# @category Set Operations
# Create the [[Set]] {//a//, //a//+1, ..., //b//-1, //b//} for //a// ≤ //b//. See also: sequence
# @param Int a minimal element of the set
# @param Int b maximal element of the set
# @return Set<Int>
# @example
# > print range(23,27);
# | {23 24 25 26 27}

user_function range(Int,Int) : c++ (include => "polymake/Set.h") {
   if ($_[0] > $_[1]) {
      croak( "invalid range: minimal element > maximal element" );
   }
}

# @category Set Operations
# Create an index range starting at //a//, the last index is implied by the context.
# To be used with minor, slice, and similar methods selecting a subset of elements.
# @param Int a start index
# @return Set<Int>
# @example
# > $v=new Vector<Int>(10,20,30,40);
# > print $v->slice(range_from(2));
# | 30 40

user_function range_from(Int) : c++ (include => "polymake/Set.h");

# @category Set Operations
# Create the [[Set]] {//a//, //a//+1, ..., //a//+//c//-1}. See also: range
# @param Int a the smallest element
# @param Int c the cardinality
# @return Set<Int>
# @example
# > print sequence(23,6);
# | {23 24 25 26 27 28}

user_function sequence(Int,Int) : c++ (include => "polymake/Set.h") {
   if ($_[1] < 0) {
      croak( "invalid sequence: negative size" );
   }
}

# @category Set Operations
# Returns the subset of //s// given by the //indices//.
# @param Set s
# @param Set<Int> indices
# @return Set
# @example
# > $s = new Set<Int>(23,42,666,789);
# > $ind = new Set<Int>(0,2);
# > $su = select_subset($s,$ind);
# > print $su;
# | {23 666}

user_function select_subset(*:wary&&, *&& const) : c++ (name => 'select', include => "polymake/IndexedSubset.h");

# @category Set Operations
# Returns the singleton set {//s//}.
# @param __Scalar__ s
# @return Set<__Scalar__>
# @example
# > print scalar2set(23);
# | {23}

user_function scalar2set(*&& const) : c++ (include => "polymake/Set.h");

# @category Set Types
# Container class for dense sets of integers.
#
# A special class optimized for representation of a constrained range of
# non-negative integer numbers.
declare property_type Bitset : Set<Int> : c++ (include => "polymake/Bitset.h", default_constructor => 'Deserializing');

# allow to write ~[0,1,2] in contexts where a Set<Int> is expected
sub construct_set_from_anonlist {
   my ($arr)=@_;
   if (@$arr > 1) {
      ~(new Set($arr));
   } elsif ($arr->[0]==0) {
      range_from(1);
   } else {
      ~scalar2set($arr->[0]);
   }
}

namespaces::intercept_operation(undef, '~', \&construct_set_from_anonlist);

# @category Set Operations
# Returns all subsets of size k of a given container as perl-array.
# @param Any c any container type, e.g. [[Set]] or [[Array]]
# @return Array<Array<Any>>
user_function all_subsets(*&& const) : c++ (include => "polymake/PowerSet.h") : returns(Container<Container>);

# @category Set Operations
# Returns all subsets of size k of a given container as perl-array.
# @param Any c any container type, e.g. [[Set]] or [[Array]]
# @param Int k size of the subsets
# @return Array<Array<Any>>
user_function all_subsets_of_k(*&& const, $) : c++ (include => "polymake/PowerSet.h") : returns(Container<Container>);

##################################################################################

# @category Set Types
# A FacetList is a collection of sets of integral numbers from a closed contiguous range [0..n-1].
# The contained sets usually encode facets of a simplicial complex,
# with set elements corresponding to vertices of a complex, therefore the name.
#
# From the structural perspective, FacetList is interchangeable with [[IncidenceMatrix]],
# but they significantly differ in supported operations and their performance.
# IncidenceMatrix offers fast random access to elements, while FacetList is optimized
# for finding, inserting, and deleting facets fulfilling certain conditions like
# all subsets or supersets of a given vertex set.
#
# On perl side, FacetList behaves like a sequence of [[Set<Int>]] without random access to facets.
# Facets are visited in chronological order.
# Each facet has a unique integral ID generated at the moment of insertion.
# The IDs can be obtained via call to index() of iterators created by find() methods.
declare property_type FacetList : c++ (include => "polymake/FacetList.h") {

   # construct an empty collection
   method construct() : c++;

   # Construct an empty collection with some internal data structures pre-allocated
   # for the given initial number of vertices.
   # This is a pure optimization, FacetList grows dynamically as well.
   # @param Int n_vertices
   method construct(Int) : c++;

   # construct from a sequence of facets
   method construct(Set+) : c++;

   # construct from a sequence of facets
   # @param Int n_vertices for optional pre-allocation of some internal data structures
   method construct(Int, Set+) : c++;

   # construct from rows of an [[IncidenceMatrix]]
   method construct(IncidenceMatrix) : c++;

   # The number of facets in the list.
   # @return Int
   user_method size() : c++;

   # The number of vertices
   # @return Int
   user_method n_vertices() : c++;

   # Look up a facet.
   # @param Set f facet to find
   # @return Iterator pointing to the facet or in an invalid state
   user_method find(Set) : c++ : returns(Iterator);

   # Add a new facet.  It may be a proper subset or a proper superset of existing facets.
   # It must not be empty or coincide with any existing facet.
   # @param Set f facet to add.
   user_method insert(&, Set) : c++ : returns(Iterator);

   # Remove a facet.
   # @param Set f facet to remove
   # @return Bool whether a facet existed before
   user_method erase(&, Set) : c++;

   # Find all supersets of a given set.
   # @param Set s
   # @return Iterator all facets equal to or including //s//, visited in reverse chronological order
   user_method findSupersets(Set) : c++ : returns(Iterator);

   # Find all subsets of a given set.
   # @param Set s
   # @return Iterator all facets equal to or included in //s//, visited in lexicographical order
   user_method findSubsets(Set) : c++ : returns(Iterator);

   # Add a new facet if and only if there are no facets including it.
   # If this holds, remove all facets that are included in the new one.
   # @return Bool whether the new facet was really included.
   # @param Set f facet to add
   user_method insertMax(&, Set) : c++;

   # Add a new facet if and only if there are no facets included in it.
   # If this holds, remove all facets including the new facet.
   # @param Set f facet to add
   # @return Bool whether the new facet was really included.
   user_method insertMin(&, Set) : c++;

   # Remove all supersets of a given set
   # @param Set s filter for removal
   # @return Int number of removed facets
   user_method eraseSupersets(&, Set) : c++;

   # Remove all subsets of a given set
   # @param Set s filter for removal
   # @return Int number of removed facets
   user_method eraseSubsets(&, Set) : c++;

}

# @category Data Conversion
# Visit the facets of //f// sorted lexicographically.
# @param FacetList f
# @return Set<Set<Int>>
# @example
# > $f = new FacetList(polytope::cube(2)->VERTICES_IN_FACETS);
# > print lex_ordered($f);
# | {{0 1} {0 2} {1 3} {2 3}}

user_function lex_ordered(FacetList:anchor) : c++ (include => "polymake/PowerSet.h");  # TODO: try to get rid of this #include

##################################################################################

# @category Artificial
# Labels a [[Matrix]] or an [[IncidenceMatrix]] as __symmetric__.
declare property_type Symmetric : c++ (special => 'Symmetric', include => "polymake/IncidenceMatrix.h");

# @category Artificial
# Labels a [[Matrix]] or an [[IncidenceMatrix]] as __non-symmetric__.
declare property_type NonSymmetric : upgrades(Symmetric) : c++ (special => 'NonSymmetric', include => "polymake/IncidenceMatrix.h");

# @category Set Types
# A 0/1 incidence matrix.
# @tparam Sym one of [[Symmetric]] or [[NonSymmetric]], default: [[NonSymmetric]]
declare property_type IncidenceMatrix<Sym=NonSymmetric> : c++ (include => "polymake/IncidenceMatrix.h") {

   # Construct a matrix from a given sequence of rows.
   # @param Set sets representing the rows
   # @param Int c number of columns
   method construct(Set+, Int) : c++;

   # Construct a matrix of given dimensions, all elements implicitly initialized to `false'.
   # @param Int r number of rows
   # @param Int c number of columns
   method construct(Int, Int) : c++;

   operator @sets @compare (*:wary, *) : c++;

   operator ~ (*&& const) : c++;

   operator / | /= |= (*:wary&& const, *&& const) : c++;

   # Returns the number of rows.
   # @return Int
   user_method rows() : c++;

   # Returns the number of columns.
   # @return Int
   user_method cols() : c++;

   # Returns the //i//-th row.
   # @param Int i
   # @return SparseVector<Int>
   user_method row(:wary&&, $) : c++ : returns(lvalue);

   # Returns the //i//-th column.
   # @param Int i
   # @return SparseVector<Int>
   user_method col(:wary&&, $) : c++ : returns(lvalue);

   # Returns a __minor__ of the matrix containing the rows in //r// and the columns in //c//.
   # You can pass [[all_rows_or_cols|All]] if you want all rows or columns and ~ for the complement of a set.
   # @example
   # For example,
   # > print polytope::cube(2)->VERTICES_IN_FACETS->minor(All, ~[0]);
   # | {1}
   # | {0 2}
   # | {0}
   # | {1 2}
   # will give you the minor of a matrix containing all rows and all but the 0-th column.
   # @param Set r the rows
   # @param Set c the columns
   # @return IncidenceMatrix
   user_method minor(:wary&&, *&& const, *&& const) : c++ : returns(lvalue);

   # Returns an element of the matrix as a boolean value.
   # The return value is an `lvalue', that is, it can be assigned to, flipped, etc. if the matrix object is mutable.
   # @param Int r the row index
   # @param Int c the column index
   # @return Bool
   user_method elem(:wary&&, $$) : c++(name => '()') : returns(lvalue);

   # Removes empty rows and columns.
   # The remaining rows and columns are renumbered without gaps.
   user_method squeeze(&) : c++;

   # Removes empty rows.
   # The remaining rows are renumbered without gaps.
   user_method squeeze_rows(&) : c++;

   # Removes empty columns.
   # The remaining columns are renumbered without gaps.
   user_method squeeze_cols(&) : c++;
}

user_function rows(IncidenceMatrix:anchor) : c++ : returns(Container);

user_function cols(IncidenceMatrix:anchor) : c++ : returns(Container);


# @category Linear Algebra
# Computes the __transpose__ //A//<sup>T</sup> of an incidence matrix //A//, i.e., (a<sup>T</sup>)<sub>ij</sub> = a<sub>ji</sub>.
# @param IncidenceMatrix A
# @return IncidenceMatrix
user_function transpose(IncidenceMatrix:anchor) : c++ (name => 'T');


##################################################################################

# @category Set Types
# Maps are sorted associative containers that contain unique key/value pairs.
# Maps are sorted by their keys.
#
# Accessing or inserting a value needs logarithmic time O(log n), where n is the size of the map.
#
# @example
# You can create a new Map mapping Ints to Strings by
# > $mymap = new Map<Int, String>([1, "Monday"], [2, "Tuesday"]);
# On the perl side Maps are treated like hashrefs.
# You can add a new key/value pair by
# > $mymap->{3} = "Wednesday";
# (If the key is already contained in the Map, the corresponding value is replaced by the new one.)
# or ask for the value of a key by
# > print $mymap->{1};
# | Monday
# @tparam Key type of the key values
# @tparam Value	type of the mapped value
declare property_type Map<Key,Value> : c++ (include => "polymake/Map.h") {

   operator @eq : c++;

   type_method equal {
      my ($proto, $m1, $m2)=@_;
      return 0 unless keys(%$m1) == keys(%$m2);
      my ($pk, $pv)=@{$proto->params};
      while (my ($k1, $v1, $k2, $v2)=(each(%$m1), each(%$m2))) {
         return 0 unless $pk->equal->($k1,$k2) && $pv->equal->($v1,$v2);
      }
      1
   }
}

##################################################################################

# @category Set Types
# An unordered set of elements based on a hash table.
# Can be traversed as a normal container, but the order of elements is not stable across polymake sessions,
# even if the set is restored from the same data file every time.
# @tparam Element
declare property_type HashSet<Element> : c++ (name => 'hash_set', include => "polymake/hash_set") {

   operator += -= ^= @eq : c++;

   method contains {
      my ($self, $key)=@_;
      exists $self->{$key};
   }

   # The cardinality of the set.
   # @return Int
   user_method size() : c++;
}

# @category Set Types
# An unordered map based on a hash table.  Its interface is similar to that of [[Map]],
# but the order of elements is not stable across polymake sessions and does not correlate with key values.
#
# Accessing and inserting a value by its key works in constant time O(1).
#
# On the perl side HashMaps are treated like hashrefs.
# You can work with a HashMap like you work with a [[Map]] (keeping in mind differences in performance
# and memory demand).
# @example
# You can create a new HashMap mapping Ints to Strings by
# > $myhashmap = new HashMap<Int, String>([1, "Monday"], [2, "Tuesday"]);
# @tparam Key type of the key values
# @tparam Value	type of the mapped value
declare property_type HashMap<Key,Value> : c++ (name => 'hash_map', include => "polymake/hash_map") {

   operator @eq : c++;

   # Size of the map
   # @return Int
   user_method size() : c++;
}

##################################################################################

# @category Set Types
# A specialization of Sets containing elements of type //Element//,
# but where equality is enforced only up to a global epsilon.
#
# @example 
# You can for example create a new ApproximateSet with two elements by:
# > $s = new ApproximateSet(1.1, 1.2, 1.200000001);
#
# @tparam Element default: [[Float]]
declare property_type ApproximateSet<Element=Float> : Set<Element> : c++ (include => "polymake/ApproximateSet.h");


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