scs

Superclass:	cs<ELEM_TYPE>
Declared In:	Spatial Constraint System
See Also:	https://hal.archives-ouvertes.fr/hal-00761116/document

Introduction

The Spatial Constraint System class.

Discussion

Derived constraint systems inherit the functionality of this class. It implements spatial functions with property-checking on them. (Note: Function indexes are positive non-zero numbers).

Member Functions

f_properties: Checks whether a function satisfies a certain property.
print_func: Generic printer for an STL map structure.
print_sfunc: Prints (on std::cout) the space function i using elements' ID's.
s: Gets the image of element c in the space function i.
s_inv: Gets the inverse image of element c in the space function i.
s_map: sᵢ(elems) = image.
s_properties: Checks whether the space function i satisfies certain property.
scs(const cs &, unsigned int): Constructor.
scs(const scs &): Copy Constructor.
~scs: Destructor.

f_properties

Checks whether a function satisfies a certain property.

protected

bool f_properties(
    unsigned int i,
    std::string name,
    std::map<ELEM_TYPE, ELEM_TYPE> map,
    FUNCTION_PROPERTY property );

Parameters

i: the index of the function.
name: the name (for message output purposes) of the function.
map: the function as a map structure.
property: one of FUNCTION_PROPERTY.

Return Value

true if the function satisfies the property, false otherwise.

Complexity

O(n) if property = FP_TOTAL and O(n²) otherwise.

print_func

Generic printer for an STL map structure.

protected

void print_func(
    unsigned int i,
    std::string name,
    std::map<ELEM_TYPE, ELEM_TYPE> map );

Parameters

i: the index of the function.
name: the name (for message output purposes) of the function.
map: the function as a map structure.

Complexity

O(n) where n is the number of elements of the CS.

print_sfunc

Prints (on std::cout) the space function i using elements' ID's.

protected

void print_sfunc(
    unsigned int i );

Parameters

i: the index of the space function.

Complexity

O(n) where n is the number of elements of the CS.

s

Gets the image of element c in the space function i.

public

ELEM_TYPE s(
    unsigned int i,
    ELEM_TYPE c );

Parameters

i: index of the space function.
c: element to retrieve its image.

Return Value

sᵢ(c)

Complexity

Constant.

s_inv

Gets the inverse image of element c in the space function i.

public

std::vector<ELEM_TYPE> s_inv(
    unsigned int i,
    ELEM_TYPE c );

Parameters

i: index of the space function startin
c: element to retrieve its fiber.

Return Value

sᵢ^-1(c)

Complexity

O(n) where n is the number of elements of the CS.

s_map

sᵢ(elems) = image.

public

void s_map(
    unsigned int i,
    std::vector<ELEM_TYPE> elems,
    ELEM_TYPE image );

Parameters

i: index of the space function.
elems: elements to map.
image: image to map elements to.

Discussion

The function will do nothing if the elements or the image are not in the elements of the CS.

Complexity

O(n) where n is the number of elements to map.

s_properties

Checks whether the space function i satisfies certain property.

protected

bool s_properties(
    unsigned int i,
    S_FUNCTION_PROPERTY property );

Parameters

i: the index of the space function.
property: one of S_FUNCTION_PROPERTY.

Return Value

true if the space function satisfies the property, false otherwise. Prints to std::cerr the troublesome elements' ID's.

Complexity

O(n) if property = SP_TOTAL and O(n²) otherwise.

scs(const cs &, unsigned int)

Constructor.

public

scs (
    const cs<ELEM_TYPE>& CS,
    unsigned int n = 1 );

Parameters

CS: a CS
n: number of space functions

Discussion

This constructor will automatically map the global infima to itself in all space functions. This means that the axiom of emptiness S.1 will be automtically satisfied at creation.

Complexity

Constant.

scs(const scs &)

Copy Constructor.

public

scs (
    const scs<ELEM_TYPE>& SCS );

Parameters

SCS: already instantiated SCS.

Complexity

Constant.

~scs

Destructor.

public

~scs(
    void );

Complexity

Constant.

Typedefs

FUNCTION_PROPERTY: Enumeration of possible properties of a function.
S_FUNCTION_PROPERTY: Enumeration of possible properties of a space function.

FUNCTION_PROPERTY

Enumeration of possible properties of a function.

protected

enum class FUNCTION_PROPERTY {
    FP_TOTAL,
    FP_SURJECTIVE,
    FP_INJECTIVE,
    FP_BIJECTIVE,
    FP_JOIN_DISTRIBUTIVE,
    FP_MEET_DISTRIBUTIVE 
};

Discussion

can be

- FP_TOTAL: function is total (i.e. every domain element is mapped).

- FP_SURJECTIVE: function is surjective (i.e. every codomain element is mapped to, also called onto).

- FP_INJECTIVE: function is injective (i.e. at most one element of the domain is mapped to an element of the codamin, also called a one-to-one function).

- FP_BIJECTIVE: function is bijective (i.e. function is injective and surjective, a one-to-one correspondence).

- FP_JOIN_DISTRIBUTIVE: function distributes over finite joins (i.e. it satisfies S.2).

- FP_MEET_DISTRIBUTIVE: function distributes over finite meets (i.e. it satisfies sᵢ(c ⨅ d) = sᵢ(c) ⨅ sᵢ(d) for every element c and d of the CS).

S_FUNCTION_PROPERTY

Enumeration of possible properties of a space function.

public

enum class S_FUNCTION_PROPERTY {
    SP_TOTAL,
    SP_SURJECTIVE,
    SP_INJECTIVE,
    SP_BIJECTIVE,
    SP_JOIN_DISTRIBUTIVE,
    SP_MEET_DISTRIBUTIVE 
};

Discussion

each property has a one-on-one correspondance with the properties specified in FUNCTION_PROPERTY

Member Data

s_func

s_func

protected

std::vector< std::map<ELEM_TYPE, ELEM_TYPE> > s_func;

Discussion

Vector containing the space functions of the CS.

Last Updated: Wednesday, March 16, 2016