with Standard_Integer_Vectors; use Standard_Integer_Vectors;
with Standard_Integer_Matrices; use Standard_Integer_Matrices;
with Lists_of_Integer_Vectors; use Lists_of_Integer_Vectors;
with Arrays_of_Integer_Vector_Lists; use Arrays_of_Integer_Vector_Lists;
package Normal_Cone_Intersections is
-- DESCRIPTION :
-- This package provides a data abstraction to represent the intersections
-- of the generators of a normal cone with a tuple of normal cone complexes.
-- DATA STRUCTURE :
type Intersection_Matrix ( n,m,nc : natural ) is record
sv : Vector(1..n);
im : Matrix(0..m,1..nc);
end record;
-- The aim of an intersection matrix is to answer the question :
-- does the ith generator of the normal cone of the point x
-- belong to the normal cone of the kth point of the jth support?
-- The parameters of the three-dimensional intersection matrix are
-- n : number of supports to consider the point x to;
-- m : number of generators of the normal cone to x;
-- nc : total number of normal cones that need to be considered.
-- The data of the intersection matrix are
-- sv(1..n) a vector whose entries indicates the starting position of the
-- the supports in the matrix im, i.e., sv(i) gives the first column in
-- the matrix im that collects the data of the normal cone of the first
-- points in the ith support;
-- im(0..m,1..nc) is a matrix that contains the answers to the question:
-- im(i,sv(j)+k) equals 0 or 1, 0 when the ith generator does not belong
-- to the normal cone of the kth points in the jth support, 1 otherwise;
-- im(0,sv(j)+k) is the sum of im(i,sv(j)+k) for all i in 1..m.
-- CONSTRUCTORS :
function Number_of_Cones ( l : Array_of_Lists; i : natural ) return natural;
-- DESCRIPTION :
-- Computes the number of cones, i.e.: returns the sum of the lengths of
-- all lists of l, without consider the ith one.
-- This is an auxiliary for determining the third dimension of the
-- intersection matrix.
function Lengths ( l : Array_of_Lists; i : natural ) return Vector;
-- DESCRIPTION :
-- Returns a vector of dimension equal to l that accumulates the lengths
-- of the lists of l, without considering the ith component.
-- More precisely, the jth component of the vector on return equals
-- one plus the sum of all lengths of the lists in l(l'first..j),
-- minus the length of l(i), if i < j. So the vector on return can serve
-- as the vector sv, except for the last component that equals one plus
-- the total number of cones to consider.
function Create ( l : Array_of_Lists; g : List; i : natural )
return Intersection_Matrix;
-- DESCRIPTION :
-- Returns the intersection matrix of the list of generators of the normal
-- cone of a point that belongs to the list l(i).
-- ELEMENTARY SELECTORS :
function Is_In ( ima : Intersection_Matrix; i,j,k : natural ) return boolean;
-- DESCRIPTION :
-- Returns true when the ith generator belongs to the normal cone of the
-- kth point of the jth support list.
function Maximal_Column ( ima : Intersection_Matrix ) return natural;
-- DESCRIPTION :
-- Returns the index to the column in the intersection matrix with
-- the maximal column sum.
function Component ( ima : Intersection_Matrix; column : natural )
return natural;
-- DESCRIPTION :
-- Returns the number of the component of the intersection matrix the
-- given column index corresponds to. The number on return equals the
-- index of the support of the corresponding column.
function Length ( ima : Intersection_Matrix; i : natural ) return natural;
-- DESCRIPTION :
-- Returns the length of the ith component of the matrix, i.e., returns
-- the length of the ith support list.
function Row_Sum ( ima : Intersection_Matrix; i,j : natural ) return natural;
-- DESCRIPTION :
-- Returns the sum of the elements on the ith row, for all normal cones
-- of the points of the jth support.
-- ENUMERATING COMPLEMENTARY COLUMS :
generic
with procedure Process ( cols : in Vector; continue : out boolean );
-- DESCRIPTION :
-- This procedure is invoked each time a set of complementary columns
-- has been found. The vector on return has the following meaning:
-- cols(i) = 0 means that no normal cone of the ith component is taken,
-- cols(i) = j means that the jth normal cone of the ith component
-- belongs to the complementary columns.
-- Note that the range of cols is 1..n-1, with n = #supports.
procedure Complementary_Columns ( ima : in Intersection_Matrix );
-- DESCRIPTION :
-- This procedure enumerates all complementary columns.
-- A set of columns, at most one of each component, is said to be
-- complementary if its union contains all generators of a normal cone.
function Partition ( ima : Intersection_Matrix; cols : Vector; g : List )
return Array_of_Lists;
-- DESCRIPTION :
-- Returns a partition of the set of generators g w.r.t. the columns cols
-- in the intersection matrix ima. More precisely: the ith list on return
-- contains those generators that belong to the normal cone cols(i) of the
-- ith component.
-- If the same generator belongs to several cones, it will be contained
-- only in the list with smallest index.
-- REQUIRED : cols is a set of complementary columns.
function Partition_in_Union ( partg,points : Array_of_Lists; i : natural;
cols : Vector ) return boolean;
-- DESCRIPTION :
-- Returns true if the set of generators of a normal cones of the ith
-- component of the point lists belongs to the union of normal cones,
-- as indicated by the set of complementary columns.
function Contained_in_Union
( l : Array_of_Lists; i : natural; g : List;
ima : Intersection_Matrix; cols : Vector ) return boolean;
-- DESCRIPTION :
-- Returns true if the list of generators g is contained in the normal
-- cones to the point selected by the columns of the intersection matrix.
-- FINAL TARGET ROUTINE :
function Contained_in_Union
( l : Array_of_Lists; i : natural; g : List;
ima : Intersection_Matrix ) return boolean;
-- DESCRIPTION :
-- Enumerates all sets of complementary columns, until its union
-- contains the convex cone spanned by the list of generators,
-- until all possibilities are exhausted.
-- In the first case, true is returned, otherwise false is returned.
end Normal_Cone_Intersections;