-- (c) Copyright - See License.txt

--

namespace sets

--****

-- == Sets

--

-- <>

--

-- The sets.e module defines a type for sets and provides basic tools for handling them.

--

-- Other modules may be built upon them, for instance graph handling or simple topology, finite groups etc.

--

-- Notes:

-- * A //set// is an ordered sequence in ascending order, not more, not less

-- * A //map// from setA to setB is a sequence the length of setA whose elements are indexes into setB,

-- followed by {length(setA),length(setB)}.

-- * An //operation// of E x F ==> G is a two dimensional sequence of elements of G, indexed by

-- E x F, and the triple {card(E),card(F),card(G)}.

--

include std/error.e

include std/sequence.e

-- Description: Prints an error message on stderr and abort(1)s.

-- Takes: {routine name,error message}; both are strings.

--****

-- === Types

--

--**

-- A set is a sequence in which each item is greater than the previous item.

--

-- See Also:

-- [[:compare]]

object x,y

end if

end if

end if

end type

-- Description: Returns 0 for a non integer or an out of bounds integer, else 1.

-- Takes: object to test; lower allowable bound; upper allowable bound.

-- Returns: 1 if x is an integer greater or equal to lbound and less than or

-- equal to ubound, else 0.

--

-- See Also: map, is_left_unit, is_right_unit

end if

end if

end if

end function

--**

-- Returns 1 if a sequence of integers is a valid map descriptor, else 0.

--

-- Comments:

-- A map is a sequence of indexes. Each index is between 1 and the maximum allowed for the particular map.

--

-- Actually, what is being called a ##map## is a class of maps, as the elements of the input

-- sequence, except for the last two, are ordinals rather than set elements. A map

-- contains the information required to map as expected the elements of a set, given by index,

-- to another set, where the images are indexes again. Technically, those are maps of the

-- category of finite sets quotiented by equality of cardinal.

--

-- The objects that map.e handle are completely unrelated to these.

--

-- Example 1:

--

-- sequence s0 = {2, 3, 4, 1, 4, 2, 6, 4}

-- ? map(s0) -- prints out 1.

--

--

-- See Also:

-- [[:define_map]], [[:fiber_over]], [[:restrict]], [[:direct_map]], [[:reverse_map]],

-- [[:is_injective]], [[:is_surjective]], [[:is_bijective]]

object p,q

end if

end if

-- The 2nd last element contains the number of items in the map.

end if

end if

-- The last element contains the upper boundary for element values.

end if

end if

-- Check that each element is within the boundaries.

end if

end type

--**

-- Returns 1 if the data represents a map from the product of two sets to a third one.

--

-- Comments:

--

-- An operation from FxG to H is defined as a sequence of mappings from G to H, plus the

-- cardinals of the sets F, G and H. If the input data is consistent with this description,

-- 1 is returned, else 0.

--

-- Example 1:

--

-- sequence s = {{{2, 3}, {3, 1}, {1, 2}, {2, 3}, {3, 1}}, {5,2,3}}

-- -- s represents the addition modulo 3 from {0, 1, 2, 3, 4} x {1, 2} to {0, 1, 2}

-- ? operation(s) -- prints out 1.

--

sequence u

end if

end if

end if

end if

end if

end type

--****

-- === Inclusion and belonging.

--

integer r,c

end if

end if

else

end if

else

end if

else

end if

end function

include std/sort.e

include std/sequence.e

--**

-- Makes a set out of a sequence by sorting it and removing duplicate elements.

--

-- Parameters:

-- # ##s## : the sequence to transform.

--

-- Returns:

--

-- A **set**, which is the ordered list of distinct elements in ##s##.

--

-- Example 1:

--

-- sequence s0 = {1,3,7,5,7,4,1}

-- set s1 = sequence_to_set(s0) -- s1 is now {1,3,4,5,7}

--

--

-- See Also:

-- [[:set]]

end function

--**

-- Return the cardinal of a set

--

-- Parameters:

-- # ##S## : the set being queried.

--

-- Returns:

--

-- An **integer**, the count of elements in S.

--

-- See Also:

-- [[:set]]

end function

--**

-- Decide whether an object is in a set.

--

-- Parameters:

-- # ##x## : the object inquired about

-- # ##S## : the set being queried

--

-- Returns:

--

-- An **integer**, 1 if ##x## is in ##S##, else 0.

--

-- Example 1:

--

-- set s0 = {1,3,5,7}

-- ?belongs_to(2,s) -- prints out 0

--

--

-- See Also:

-- [[:is_subset]] , [[:intersection]], [[:difference]]

else

end if

end function

integer p

end if

end if

end function

--**

-- Add an object to a set.

--

-- Parameters:

-- # ##x## : the object to add

-- # ##S## : the set to augment

--

-- Returns:

--

-- A **set**, which is a **copy** of ##S##, with the addition of ##x## if it was not there already.

--

-- Example 1:

--

-- set s0 = {1,3,5,7}

-- s0=add_to(2,s) -- s0 is now {1,2,3,5,7}

--

--

-- See Also:

-- [[:remove_from]], [[:belongs_to]], [[:union]]

end function

integer p

end if

else

end if

end function

--**

-- Remove an object from a set.

--

-- Parameters:

-- # ##x## : the object to add

-- # ##S## : the set to remove from

--

-- Returns:

--

--A **set**, which is a **copy** of ##S##, with ##x## removed if it was there.

--

-- Example 1:

--

-- set s0 = {1,2,3,5,7}

-- s0=remove_from(2,s0) -- s0 is now {1,3,5,7}

--

--

-- See Also:

-- [[:remove_from]], [[:belongs_to]], [[:union]]

end function

-- Returns: {1,2,...,count}, or "" if count is not greater than 0.

sequence result

end if

end function

integer p,q,ls1

sequence result

end if

end if

end if

end if

else

end if

else

end if

else

else

end if

end if

else

else

end if

end if

end function

--**

-- Checks whether a set is a subset of another.

--

-- Parameters:

-- # ##small## : the set to test

-- # ##large## : the supposedly larger set.

--

-- Returns:

--

-- An **integer**, 1 if ##small## is a subset of ##large##, else 0.

--

-- Example 1:

--

-- set s0 = {1,3,5,7}

-- ? is_subset({3,5},s0) -- prints out 1

--

--

-- See Also:

-- [[:subsets]], [[:belongs_to]], [[:difference]], [[:embedding]], [[:embed_union]]

end function

--**

-- Returns the set of indexes of the elements of a set in a larger set, or 0 if not applicable

--

-- Parameters:

-- # ##small## : the set to embed

-- # ##large## : the supposedly larger set

--

-- Returns:

--

-- A **set**, of indexes if ##small## [[:is_subset]]() ##large##, else 0. Each element

-- is the index in ##large## of the corresponding element of ##small##. Its length is ##

-- length(small)## and the values range from 1 to ##length(large)##.

--

-- Example 1:

--

-- set s0 = {1,3,5,7}

-- set s = embedding({3,5},s0) -- s is now {2,3}

--

--

-- See Also:

-- [[:subsets]], [[:belongs_to]], [[:difference]], [[:is_subset]]

--

end function

-- Description: Returns the absolute value of p.

else

end if

end function

-- Description: Wrapped by embed_union so as to avoid some type checks.

integer p,q,q_1,ls1

sequence result,temp

end if

else

end if

else

end if

end if

end if

else

end if

else

end if

else

else

end if

end if

end function

--**

-- Returns the embedding of a set into its union with another.

--

-- Parameters:

-- # ##S1## : the set to embed

-- # ##S2## : the other set

--

-- Returns:

--

-- A **set**, of indexes representing S1 inside ##union(S1,S2)##. Its length is ##length(S1)##, and the values range from 1 to ##length(S1) + length(S2)##.

--

-- Example 1:

--

-- set s1 = {2, 5, 7}, s2 = {1, 3, 4}

-- sequence s = embed_union(s1,s2) -- s is now {2, 5, 6}

--

--

-- See Also:

-- [[:embedding]], [[:union]]

end function

--**

-- Returns the list of all subsets of the input set.

--

-- Parameters:

-- # ##s## : the set to enumerate the subsets of.

--

-- Returns:

-- A **sequence**, containing all the subsets of the input set.

--

-- Comments:

--

-- ##s## must not have more than 29 elements, as the length of the output sequence is

-- ##power(2,length(s))##, which rapidly grows out of integer range.

-- The order in which the subsets are output is implementation dependent.

--

-- Example 1:

--

-- set s0 = {1,3,5,7}

-- s0 = subsets(s0) -- s0 is now:

-- {{},{1},{3},{5},{7},{1,3},{1,5},{1,7},{3,5},{3,7},{5,7},{1,3,5},{1,3,7},{1,5,7},{3,5,7},{1,3,5,7}}

--

--

-- See Also:

-- [[:is_subset]]

integer p,k,L

sequence result,s1,s2,x

else

end if

else

end if

end function

--****

-- === Basic set-theoretic operations.

--

-- Description: Wrapped by intersection() so as to avoid some type checks.

integer k1,k2,k,c,ls1,ls2

sequence result

else

end if

end if

else

end if

else

end if

else

else

end if

end if

end function

--**

-- Returns the set of elements belonging to both s1 and s2.

--

-- Parameters:

-- # ##S1## : One of the sets to intersect

-- # ##S2## : the other set.

--

-- Returns:

--

-- A **set**, made of all elements belonging to both ##S1## and ##S2##.

--

-- Example 1:

--

-- set s0,s1,s2

-- s1={1,3,5,7} s2={-1,2,3,7,11}

-- s0=intersection(s1,s2) -- s0 is now {3,7}.

--

--

-- See Also:

-- [[:is_subset]], [[:subsets]], [[:belongs_to]]

end function

-- Description: Wrapped by union() and delta() to avoid type checking.

-- mode=1 for union and 0 for delta (union=intersection+delta)

integer k1,k2,k,c,k0

sequence result

end if

else

end if

else

end if

else

else

end if

end if

else

end if

end function

integer ls1,ls2

end if

end function

--**

-- Returns the set of elements belonging to any of two sets.

--

-- Parameters:

-- # ##S1##: one of the sets to merge

-- # ##S2##: the other set.

--

-- Returns:

--

-- The **set** of all elements belonging to ##S1## or ##S2##, and possibly to both.

--

-- Example 1:

--

-- set s0,s1,s2

-- s1={1,3,5,7} s2={-1,2,3,7,11}

-- s0=union(s1,s2) -- s0 is now {-1,1,2,3,5,7,11}.

--

--

-- See Also:

-- [[:is_subset]], [[:subsets]], [[:belongs_to]]

--

end function

--**

-- Returns the set of elements belonging to either of two sets.

--

-- Parameters:

-- # ##s1## : One of the sets to take a symmetrical difference with

-- # ##s2## : the other set.

--

-- Returns:

--

-- The **set**, of all elements belonging to either ##s1## or ##s2##.

--

-- Example 1:

--

-- set s0,s1,s2

-- s1={1,3,5,7} s2={-1,2,3,7,11}

-- s0=delta(s1,s2) -- s0 is now {-1,1,2,5,11}.

--

--

-- See Also:

-- [[:intersection]], [[:union]], [[:difference]]

--

integer ls1,ls2

end if

end function

--**

-- Returns the set of elements belonging to some set and not to another.

--

-- Parameters:

-- # ##base## : the set from which a difference is to be taken

-- # ##removed## : the set of elements to remove from ##base##.

--

-- Returns:

--

-- The **set**, of elements belonging to ##base## but not to ##removed##.

--

-- Example 1:

--

-- set s0,s1,s2

-- s1={1,3,5,7} s2={-1,2,3,7,11}

-- s0=difference(s1,s2) -- s0 is now {1,5}.

--

--

-- See Also:

-- [[:remove_from]], [[:is_subset]], [[:delta]]

--

integer k1,k2,k,c,ls1,ls2,k0

sequence result

else

end if

end if

else

end if

else

end if

else

else

end if

end if

else

end if

end function

-- Description: Wrapped by product() to skip type checking

sequence result

integer ls1,ls2,k

object x

end if

end function

--**

-- Returns the set of all pairs made of an element of a set and an element of another set.

--

-- Parameters:

-- # ##S1## : The set where the first coordinate lives

-- # ##S2## : The set where the second coordinate lives

--

-- Returns:

--

-- The **set**, of all pairs made of an element of ##S1## and an element of ##S2##.

--

-- Example 1:

--

-- set s0,s1,s2

-- s1 = {1, 3, 5, 7} s2 = {-1, 3}

-- s0 = product(s1, s2) -- s0 is now {{1, -1}, {1, 3}, {3, -1}, {3, 3}, {5, -1}, {5, 3}, {7, -1}, {7, 3}}

--

--

-- See Also:

-- [[:product_map]], [[:amalgamated_sum]], [[:fiber_product]]

end function

--****

-- === Maps between sets.

--**

-- Returns a map which sends each element of its source set to the corresponding

-- one in a list.

--

-- Parameters:

-- # ##mapping## : the sequence mapped to

-- # ##target## : the target set that contains the elements ##mapping## refers to by index

--

-- Returns:

--

-- The requested **map**, descriptor.

--

-- Example 1:

--

-- sequence s0 = {2, 3, 4, 1, 4, 2}

-- set s1 = {-1, 1, 2, 3, 4}

-- map f = define_map(s0,s1)

-- -- As a sequence, f is {3, 4, 5, 2, 5, 3, 6, 5}

--

--

-- See Also:

-- [[:map]], [[:sequences_to_map]], [[:direct_map]]

sequence result

integer lt

end function

--**

-- Returns a map which sends each element of some sequence to the corresponding one in another sequence.

--

-- Parameters:

-- # ##mapped## : the source sequence

-- # ##mapped_to## : the sequence it must map to.

-- # ##mode## : an integer, nonzero to also return the minimal sets the result map maps.

--

-- Returns:

-- A **sequence**,

-- * If ##mode## is 0, a map which maps ##mapped## to ##mapped_to##, between the smallest possible sets.

-- * If mode is not zero, the sequence has length 3. The first element is the map above. The other two elements are the sets derived from the input sequences.

--

-- Comments:

--

-- Elements in excess in ##mapped_to## are discarded.

--

-- If an element is repeated in ##mapped##, only the mapping of the last occurrence is retained.

--

-- Example 1:

--

-- sequence s0, s1

-- s0 = {2, 3, 4, 1, 4}

-- s1 = {"aba", "aac", 3, "def"}

--

-- map f = sequences_to_map(s0,s1)

-- -- As a sequence, f is {3,2,1,4,4,4}

--

--

-- See Also:

-- [[:map]], [[:define_map]]

sequence result

set sorted,sorted_to

integer ls,lm_to,lm

end if

else

end if

end function

--**

-- If an object is in some input set, returns how it is mapped to a set.

--

-- Parameters:

-- # ##f## : the map to apply

-- # ##x## : the object to apply ##f## to

-- # ##input## : the source set

-- # ##output## : the target set.

--

-- Returns:

-- An **object**, f(x) if it can be reckoned.

--

-- Errors:

--

-- ##x## must belong to ##input## for ##f(x) ##to be computed.

-- ##f## must not map to sets larger than ##output##; otherwise, it cannot be defined from ##input## to ##output##.

--

-- Example 1:

--

-- map f={3,1,2,2,4,3}

-- set s1,s2

-- s1={"Albert","Beatrix","Conrad","Doris"} s2={13,17,19}

-- object x = image(f,"Conrad",s1,s2}

-- -- x is now 17.

--

--

-- See Also:

-- [[:direct_map]]

integer p

end if

else

end if

end function

--**

-- Returns the set of all values taken by a map in some output set.

--

-- Parameters:

-- # ##f## : the map to inspect

-- # ##set## : the output set

--

-- Returns:

--

-- The **set**, of all ##f(x)##.

--

-- Example 1:

--

-- map f = {3, 2, 5, 2, 4, 6}

-- set s = {"Albert", "Beatrix", "Conrad", "Doris", "Eugene", "Fabiola"}

-- set s1 = range(f, s)

-- -- s1 is now {"Beatrix", "Conrad", "Eugene"}

--

--

-- See Also:

-- [[:direct_map]], [[:image]]

sequence result

end function

--**

-- Returns the image of a list by a map, given the input and output sets.

--

-- Parameters:

-- # ##f## : the map to apply

-- # ##input## : the source set

-- # ##elements## : the sequence to map

-- # ##output## : the target set.

--

-- Returns:

-- A **sequence**, of elements of ##output## obtained by applying ##f## to the corresponding

-- element of ##input##.

--

-- Errors:

-- This function errors out if ##f## cannot map ##input## to ##output##.

--

-- Comments:

--

-- If ##elements## has items which are not on ##input##, they are ignored. Items may appear in any order any number of times.

--

-- Example:

--

-- sequence s0 = {2,3,4,1,4}

-- set t1,t2

-- t1={1,2,2.5,3,4} t2={11,13,17,19,23,29}

-- map f = {3,1,4,5,3,5,5}

-- sequence s2 = direct_map(f,t1,s0,t2)

-- -- s2 is now {11,29,17,17,17}.

--

--

-- See Also:

-- [[:reverse_map]]

sequence result

integer k,p

end if

end if

end function

--**

-- Restricts f to the intersection of an input set and another set

--

-- Parameters:

-- # ##f## : the map to restrict

-- # ##source## : the initial source set for ##f##

-- # ##restriction## : the set which will help forming a restricted source set.

--

-- Returns:

--

-- A **map**, defined on ##difference(source,restriction)## which agrees with ##f##.

--

-- Example 1:

--

-- set s1 = {1,3,5,7,9,11,13,17,19,23}}

-- map f = [3,7,1,4,5,2,7,1,6,2,10,7}

-- set s0 = {3,11,13,19,29}

-- map f0 = restrict(f,s1,s0)

-- f0 is now: {7,2,7,6,4,7}

--

--

-- See Also:

-- [[:is_subset]], [[:direct_map]], [[:difference]]

--

end if

end function

-- Description: Wrapped by change_target() to avoid some type checks.

sequence result,done

integer p,fi

else

else

end if

end if

end function

--**

-- Converts a map by changing its output set.

--

-- Parameters:

-- # ##f## : the map to retarget

-- # ##old_target## : the initial target set for ##f##

-- # ##new_target## : the new target set.

--

-- Returns:

--

-- A **map**, which agrees with ##f## and has values in ##new_target## instead of ##

-- old_target##, or "" if ##f## hits something outside ##new_target##.

--

-- Example 1:

--

-- set s1,s2

-- s1={1,3,5,7,9,11} s2={1,3,7,11,17,19,23}

-- map f = {2,1,4,6,2,6,6,6}

-- map f0 = change_target(f,s1,s2)

-- f0 is now: {2,1,3,4,2,4,6,7}

--

--

-- See Also:

-- [[:restrict]], [[:direct_map]]

end function

--**

-- Combines two maps into one defined from the union of source sets to the union

-- of target sets.

--

-- Parameters:

-- # ##f1## : the first map

-- # ##source1## : its source set

-- # ##target1## : its target set

-- # ##f2## : the second map

-- # ##source2## : its source set

-- # ##target2## : its target set

--

-- Returns:

-- A **map**, from ##union(source1,source2)## to ##union(target1,target2)##

-- which agrees with ##f1## and ##f2##, or "" if ##f1##

-- and ##f2## disagree at any point of ##intersection(s11,s21)##.

--

-- Errors:

-- If f1 and f2 are both defined for some point, they must have the

-- same value at this point..

--

-- Example 1:

--

-- set s11,s12,s21,s22

-- s11={2,3,5,7,11,13,17,19} s21={7,13,19,23,29}

-- s12={-1,0,1,4} s22={-2,0,1,2,6}

-- map f1,f2

-- f1={2,1,3,3,2,3,1,2,8,4} f2={3,3,2,4,5,5,5}

-- map f = combine_maps(f1,s11,s12,f2,s21,s22)

-- -- f is now: {3,2,4,4,3,4,2,3,5,7,10,7}.

--

--

-- See Also:

-- [[:restrict]], [[:direct_map]]

integer len_result,p

set s

sequence result

"Maps disagree at some point where they are both defined."})

else

end if

else

end if

end function

-- Description: Wrapped by compose_map(), so as to avoid some type checks.

sequence result

end if

end function

--**

-- Creates a new map using elements from ##f2##, mapped against ##f1##

--

-- Parameters:

-- # ##f1## : the map containing indexes into ##f2##

-- # ##f2## : the map containing elements used to build the resulting map.

--

-- Returns:

-- A **map**, ##f## defined by ##f(x)=f2(f1(x))## for all ##x##

--

-- Comments:

-- Each element in ##f1## is an index into the elements of ##f2##. So if

-- ##f1## contains {3,2,1} the result map contains the 3rd, 2nd and 1st element

-- from ##f2## in that order.

--

-- Errors:

-- Every element of ##f1## must be a valid index into ##f2##.

--

-- Example 1:

--

-- map f1,f2,f

-- f1={2,3,1,1,2,5,3}

-- f2={4,8,1,2,6,7,6,9}

-- f=compose_map(f1,f2)

-- -- f is now: {8,1,4,4,8,5,9}

--

--

-- See Also:

-- [[:diagram_commutes]]

--

end function

--**

-- Decide whether taking two different paths along a square map diagrams results in the same map.

--

-- Parameters:

-- # ##from_base_path_1## : the outgoing map along path 1

-- # ##from_base_path_2## : the outgoing map along path 2

-- # ##to_target_path_1## : the incoming map along path 1

-- # ##to_target_path_2## : the incoming map along path 2

--

-- Returns:

--

-- An **integer**, either 1 if to_target_path_1 o from_base_path_1 = to_target_path_2 o from_base_path_2.

--