with text_io;                           use text_io;
with Standard_Natural_Numbers;          use Standard_Natural_Numbers;
with Standard_Complex_Laurentials;      use Standard_Complex_Laurentials;
with Standard_Complex_Laur_Systems;     use Standard_Complex_Laur_Systems;
with Standard_Monomial_Maps;            use Standard_Monomial_Maps;

package Standard_Monomial_Map_Filters is

-- DESCRIPTION :
--   An irreducible decomposition of the solution set defined by a binomial
--   system consists of an array of lists of monomial maps:
--   (1) All lists in the same entry of the array have the same dimension.
--   (2) Every map corresponds to an irreducible factor.
--   (3) No map is contained in another map.
--   The tools offered by this package proceed by filtering a list of
--   monomial maps computed as contributing factors to a permanent of
--   the incidence matrix of the exponents of the binomial system.

  function Is_Pure_Dimensional
               ( maps : Monomial_Map_List ) return boolean;

  -- DESCRIPTION :
  --   Returns true if the list maps is empty or if all maps in the list
  --   have the same dimension as the first map in the list.

  function Pure_Dimensional_Maps
               ( maps : Monomial_Map_List; dim : natural32 )
               return Monomial_Map_List;

  -- DESCRIPTION :
  --   Returns those maps from the given list maps
  --   that are of the given dimension dim.

  function Pure_Dimensional_Maps
               ( maps : Monomial_Map_List )
               return Array_of_Monomial_Map_Lists;

  -- DESCRIPTION :
  --   Returns an array of range 0..Top_Dimension(maps)
  --   where the d-th entry contains all maps of dimension d.

  function Remove_Duplicates
               ( maps : Monomial_Map_List ) return Monomial_Map_List;

  -- DESCRIPTION :
  --   Returns the list maps with duplicate elements removed.

  procedure Filter_Duplicates ( maps : in out Monomial_Map_List );

  -- DESCRIPTION :
  --   Removes duplicate maps from the given list.

  procedure Filter_Duplicates ( maps : in out Array_of_Monomial_Map_Lists );

  -- DESCRIPTION :
  --   Removes duplicate maps from the given lists.

  function Is_Free ( map : Monomial_Map ) return boolean;

  -- DESCRIPTION :
  --   A monomial map is free if all coefficients are either zero or one
  --   and for all variables which have coefficient, the exponent vector
  --   is a unit vector.  A free map defines a monomial ideal.

  function Has_Zeroes ( map : Monomial_Map ) return boolean;

  -- DESCRIPTION :
  --   Returns true if the monomial map contains zeroes.

  function Is_Free_Submap ( m1,m2 : Monomial_Map ) return boolean;

  -- DESCRIPTION :
  --   For free maps m1 and m2, this function returns true if the map m1
  --   represents a submap of m2 and false otherwise.

  -- REQUIRED : Is_Free(m1) and Is_Free(m2).

  function Remove_Free_Submaps
              ( m1 : Monomial_Map_List; m2 : Monomial_Map )
              return Monomial_Map_List;

  -- DESCRIPTION :
  --   Given a free map m2, this function returns the list of maps in m1
  --   that are not free or free and not submaps of m2.

  -- REQUIRED : Is_Free(m2).

  function Remove_Free_Submaps
              ( m1,m2 : Monomial_Map_List ) return Monomial_Map_List;

  -- DESCRIPTION :
  --   Returns the maps in m1 which are not free or free and not submaps
  --   of any free map in m2.

  procedure Filter_Free_Submaps
              ( m1 : in out Monomial_Map_List;
                m2 : in Monomial_Map_List );

  -- DESCRIPTION :
  --   Removes from m1 those free maps that are submap of any free map
  --   of the list m2.

  procedure Filter_Free_Submaps
              ( maps : in out Array_of_Monomial_Map_Lists );

  -- DESCRIPTION :
  --   Given maps of dimension d in the list maps(d),
  --   free lower dimensional maps are removed if they are submaps
  --   of free maps at a higher dimension.

  function Is_Zero_Submap ( m1,m2 : Monomial_Map ) return boolean;

  -- DESCRIPTION :
  --   Returns true if for every zero in m1, there is also a zero
  --   at the same location in m2, returns false otherwise.
  --   This is a fast preprocessing criterion which is conclusive
  --   if it returns false, then m1 cannot be a submap of m2.

  function Filter ( p : Poly; map : Monomial_Map ) return Poly;

  -- DESCRIPTION :
  --   Returns those terms of p that remain after setting those variables
  --   to zero as defined by the map.

  function Filter ( p : Laur_Sys; map : Monomial_Map )
                  return Link_to_Laur_Sys;

  -- DESCRIPTION :
  --   Returns those equations of p that remain after setting those variables
  --   to zero as defined by the map.

  function Is_Generated_by_Monomials
              ( p : Poly; map : Monomial_Map ) return boolean;
 
  -- DESCRIPTION :
  --   Returns true if the polynomial is generated by the monomials
  --   in the free map that are zero.

  function Is_Generated_by_Monomials
              ( p : Laur_Sys; m1,m2 : Monomial_Map ) return boolean;

  -- DESCRIPTION :
  --   Returns true if the monomials defined by the free map m1 generate
  --   the toric map m2 and thus the m1 is a submap of m2.

  function Is_Free_of_Affine_Submap
              ( p : Laur_Sys; m1,m2 : Monomial_Map ) return boolean;

  -- DESCRIPTION :
  --   The free map m1 is a submap of the affine map m2
  --   if Is_Zero_Submap(m1,m2) and Is_Generated_by_Monomials(p,m1,m2).

  function Remove_Free_of_Affine_Submaps
              ( p : Laur_Sys; m1 : Monomial_Map_List; m2 : Monomial_Map )
              return Monomial_Map_List;

  -- DESCRIPTION :
  --   Returns the list of maps in m1 which are either not free,
  --   or which are free submaps of the map m2.

  function Remove_Free_of_Affine_Submaps
              ( p : Laur_Sys; m1,m2 : Monomial_Map_List )
              return Monomial_Map_List;

  -- DESCRIPTION :
  --   Returns the maps in m1 which are not free or free and not submaps
  --   of any affine map in m2.

  procedure Filter_Free_of_Affine_Submaps
              ( p : Laur_Sys; m1 : in out Monomial_Map_List;
                m2 : in Monomial_Map_List );

  -- DESCRIPTION :
  --   Removes from m1 those free maps that are submap of any affine map
  --   of the list m2.

  procedure Filter_Free_of_Affine_Submaps
              ( p : Laur_Sys; maps : in out Array_of_Monomial_Map_Lists );

  -- DESCRIPTION :
  --   Given maps of dimension d in the list maps(d),
  --   free lower dimensional maps are removed if they are submaps
  --   of affine maps at a higher dimension.

  function Is_Affine_Submap
              ( p : Laur_Sys; m1,m2 : Monomial_Map ) return boolean;

  -- DESCRIPTION :
  --   Returns true if the affine map m1 is a submap of the affine map m2.

  function Remove_Affine_Submaps
              ( p : Laur_Sys; m1 : Monomial_Map_List; m2 : Monomial_Map )
              return Monomial_Map_List;

  -- DESCRIPTION :
  --   Returns the list of maps in m1 which are affine submaps of m2.

  function Remove_Affine_Submaps
              ( p : Laur_Sys; m1,m2 : Monomial_Map_List )
              return Monomial_Map_List;

  -- DESCRIPTION :
  --   Returns the maps in m1 which are not affine submaps
  --   of any affine map in m2.

  procedure Filter_Affine_Submaps
              ( p : Laur_Sys; m1 : in out Monomial_Map_List;
                m2 : in Monomial_Map_List );

  -- DESCRIPTION :
  --   Removes from m1 those maps that are affine submap of any 
  --   affine map of the list m2.

  procedure Filter_Affine_Submaps
              ( p : Laur_Sys; maps : in out Array_of_Monomial_Map_Lists );

  -- DESCRIPTION :
  --   Given maps of dimension d in the list maps(d),
  --   lower dimensional maps are removed if they are affine submaps
  --   of affine maps at a higher dimension.

-- MAIN DRIVERS :

  procedure Silent_Filter
               ( p : in Laur_Sys; maps : in Monomial_Map_List;
                 c : out Link_to_Array_of_Monomial_Map_Lists );
  procedure Reporting_Filter
               ( file : in file_type;
                 p : in Laur_Sys; maps : in Monomial_Map_List;
                 c : out Link_to_Array_of_Monomial_Map_Lists );

  -- DESCRIPTION :
  --   If the maps are not pure dimensional, the lower dimensional
  --   components are filtered out if they are submaps of the higher
  --   dimensional components.
  --   The reporting filter writes diagnostics of the filtering process,
  --   while the silent filter stays mute.

end Standard_Monomial_Map_Filters;
