Common Lisp Package: COM.INFORMATIMAGO.COMMON-LISP.CESARUM.BRELATION

This package implements a relation abstract data type based on an array of bset. It can represent only relations between two positive and bounded integers. (Inspired by Modula-2 cocktail-9309/reuse/src/Relations.md). See also: COM.INFORMATIMAGO.COMMON-LISP.CESARUM.BSET License: AGPL3 Copyright Pascal J. Bourguignon 2004 - 2012 This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. 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 Affero General Public License for more details. You should have received a copy of the GNU Affero General Public License along with this program. If not, see <http://www.gnu.org/licenses/>

README:

FUNCTION

Public

ASSIGN (REL1 REL2)

POST: REL1 is a copy of REL2. RETURN: REL1

ASSIGN-ELEMENT (REL E1 E2)

POST: REL contains only (E1,E2). RETURN: REL

ASSIGN-EMPTY (REL)

POST: REL is the empty relation. RETURN: REL

CARDINAL (REL)

RETURN: The number of couples in the relation REL.

CLOSURE (REL)

POST: REL is the transitive closure of the old REL. RETURN: REL

COMPLEMENT (REL)

POST: REL is the complement of old REL. RETURN: REL

DIFFERENCE (REL1 REL2)

POST: REL1 is the difference of old REL1 and REL2. RETURN: REL1

EXCLUDE (REL E1 E2)

DO: Remove (E1 E2) from the relation REL. POST: ¬ REL(E1,E2)

EXISTS (REL PROC)

DO: Calls PROC on couples of the relation REL until it returns true. PROC: A predicate of two elements. RETURN: Whether PROC returned true for at least one couple.

EXISTS-1 (REL PROC)

DO: Calls PROC on each couples of the relation REL. PROC: A predicate of two elements. RETURN: Whether PROC returned true for exactly one couple.

EXTRACT (REL)

DO: Selects a couple in the relation REL, exclude it from REL, and return it. PRE: (not (is-empty rel)) POST: ¬REL(i,j) RETURN: (values i j) such as old REL(i,j), or NIL if REL is empty.

FOR-ALL (REL PROC)

DO: Calls PROC on couples of the relation REL while it returns true. PROC: A predicate of two elements. RETURN: Whether PROC returned true for all couples.

FOR-ALL-DO (REL PROC)

DO: Calls PROC on each couple of the relation REL. PROC: A function of two elements. RETURN: REL

GET-CYCLICS (REL BSET)

RETURN: The set of elements that are in cycles.

HAS-REFLEXIVE (REL)

RETURN: ∃i∈[0,SIZE1-1], REL(i,i)

INCLUDE (REL E1 E2)

DO: Adds (E1 E2) to the relation REL. POST: REL(E1,E2)

INTERSECTION (REL1 REL2)

POST: REL1 is the intersection of old REL1 and REL2. RETURN: REL1

IS-CYCLIC (REL)

RETURN: Whether the relation REL is cyclic.

IS-ELEMENT (E1 E2 REL)

RETURN: Whether REL(E1,E2).

IS-EMPTY (REL)

RETURN: Whether REL is empty.

IS-EQUAL (REL1 REL2)

RETURN: Whether REL1 is equal to REL2.

IS-EQUIVALENCE (REL)

RETURN: Whether REL is an equivalence relation. Ie. REL is reflexive, symetric and transitive.

IS-NOT-EQUAL (REL1 REL2)

RETURN: Whether REL1 is not equal to REL2.

IS-REFLEXIVE (REL)

RETURN: Whether the relation REL is reflexive. Ie. ∀i∈[0,SIZE1-1], REL(i,i)

IS-REFLEXIVE-1 (E1 REL)

RETURN: Whether REL(E1,E1)

IS-STRICT-SUBSET (REL1 REL2)

RETURN: Whether REL1 is a strict subset of REL2.

IS-SUBSET (REL1 REL2)

RETURN: Whether REL1 is a subset of REL2.

IS-SYMMETRIC (REL)

RETURN: Whether the relation REL is symetric. Ie. ∀(i,j)∈[0,SIZE1-1]², REL(i,j) ⇒ REL(j,i)

IS-TRANSITIVE (REL)

RETURN: Whether the relation REL is transitive. Ie. ∀(i,j,k)∈[0,SIZE1-1]³, REL(i,j) ∧ REL(j,k) ⇒ REL(i,k)

IS-TRANSITIVE-1 (E1 E2 E3 REL)

RETURN: Whether (REL(E1,E2) ∧ REL(E2,E3)) ⇒ REL(E1,E3) NOTE: Tests the transitivity of the relation REL only on the elements E1, E2, and E3. This doesn't mean the relation REL is transitive (but it's a necessary condition).

MAKE-BRELATION (SIZE-1 SIZE-2)

RETURN: A new BRELATION between sets of sizes SIZE-1 and SIZE-2.

PROJECT-1 (REL E1 BSET)

POST: BSET is the set of all elements I that are in relation REL(I,E2). RETURN: BSET

PROJECT-2 (REL E1 BSET)

POST: BSET is the set of all elements E2 that are in relation REL(E1,E2). RETURN: BSET

READ-BRELATION (STREAM REL)

DO: Read a relation from the STREAM. POST: REL is the relation read. RETURN: REL. NOTE: The serialization format is that of a list of adjacency lists. ((1 (2 3)) (2 (3)) (4)) = ({1 2 3 4} {(1 2) (1 3) (2 3)})

SELECT (REL)

RETURN: (values i j) such as REL(i,j), or NIL if REL is empty.

SYM-DIFF (REL1 REL2)

POST: REL1 is the symetric difference of old REL1 and REL2. RETURN: REL1

UNION (REL1 REL2)

POST: REL1 is the union of old REL1 and REL2. RETURN: REL1

WRITE-BRELATION (STREAM REL)

DO: Write the relation REL to the STREAM. RETURN: REL.

Private

BRELATION-ADJSETS (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BRELATION-SIZE-1 (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

BRELATION-SIZE-2 (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

IS-SYMMETRIC-1 (E1 E2 REL)

RETURN: Whether REL(E1,E2) ∧ REL(E2,E1)

VECTOR-INIT (VECTOR CONSTRUCTOR)

DO: Sets all the slots in vector to the successive results of the function CONSTRUCTOR called with integers from 0 up to the dimension of the VECTOR. RETURN: VECTOR

Undocumented

%MAKE-BRELATION (&KEY ((ADJSETS DUM0) (MAKE-ARRAY '(0) ELEMENT-TYPE 'BSET INITIAL-ELEMENT (MAKE-BSET 0))) ((SIZE-1 DUM1) 0) ((SIZE-2 DUM2) 0))

SETFBRELATION-ADJSETS (NEW-VALUE INSTANCE)

BRELATION-P (OBJECT)

SETFBRELATION-SIZE-1 (NEW-VALUE INSTANCE)

SETFBRELATION-SIZE-2 (NEW-VALUE INSTANCE)

COPY-BRELATION (INSTANCE)

MACRO

Private

FOR ((VAR FIRST LAST . REST) &BODY BODY)

For loop. DO: Repeat BODY with VAR bound to successive integer values from FIRST to LAST inclusive. If the optional STEP argument is abstent, then it is taken as 1 or -1 depending on the order of FIRST and LAST. VAR is incremented by STEP and it stops when VAR goes above or below LAST depending on the sign of STEP.

IMPLY (P Q)

RETURN: P ⇒ Q NOTE: This short circuits the evaluation of Q if P is false.

Undocumented

ADJREF (REL I)

UNTIL (CONDITION &BODY BODY)

CLASS

Public

BRELATION

The Binary Relation Class.