[TABLE OF CONTENTS] [BOTTOM] - [NEXT]

Author:  Rony G. Flatscher

For:     ANSI NCITS J18

Purpose: Collections and Set(like) Operations

Version: 0.9.7.1

As of:   1998-10-10

Status:  Draft

Please send comments to Rony.Flatscher@wu-wien.ac.at

Abstract This paper describes the Object Rexx collection classes, the setlike operations and the coercion of collection classes.

The previous version may be found at http://wwwi.wu-wien.ac.at/rgf/ansi.j18/collection/rgf_coll.htm. It contains supplemental information.

[TOP] [BOTTOM] - [PREVIOUS] [NEXT] Table of Contents


        1     Object Rexx Collections 
             

        1.1   Basic Collection Methods 
             

        1.2   Additional Collection Methods 
             

        2     The Role of Indices for Collections 
             

        2.1   Using Indices for Addressing Purposes Only 
             

        2.2   Functional Dependency (FD) and Multivalued Dependency (MVD)  
             

        2.2.1 Index and Item the Same Object 
                          

        2.2.2 Multiplicity of Index 
             

        3     Setlike Collection Classes and Setlike Operations 


        3.1   Definition I of Setlike Operations 


        3.2   Definition II of Setlike Operations 


        3.3   Examples for the Setlike Operations 


        4     Casting of Collections

[TOP] [TABLE OF CONTENTS] [BOTTOM] - [PREVIOUS] [NEXT]

1 Object Rexx Collections

Object Rexx collections are able to collect any number and any type of objects by using an index for storing and retrieving them.

If a collection class implements at least the setlike operations UNION and DIFFERENCE in form of appropriately named methods, then it is called a setlike collection class.

1.1 Basic Collection Methods

The collected objects are also called items or values in the OOI on-line documentation, which may lead to slight confusions. For clarity this text uses the term item only.

Collection classes collect objects via the PUT resp. []= method and allow for retrieving them in a number of ways:

via an index (using the AT resp. [] method to retrieve the associated item),
an array object (using the MAKEARRAY method to create it) or
a supplier object (using the SUPPLIER method to create it).




Hence, every collection class in Object Rexx needs to implement at
least the methods PUT(item, index) resp. 
[]=, AT(index) 
resp. [], MAKEARRAY and
SUPPLIER.





 
1.2 Additional Collection Methods
 


Typically, collection classes also implement the methods ITEMS
(returns the number of collected items), HASINDEX(index) and
REMOVE(index).

 Collections which allow for more than one item to be 
associated with a specific index like the built-in class
Relation also implement the methods HASITEM(item,
index) and REMOVEITEM(item, index).






[TOP]
[TABLE OF CONTENTS]
[BOTTOM]
-
[PREVIOUS]
[NEXT]
 
2 The Role of Indices for Collections
 


A collection class uses an index as an addressing mechanism to 
store and retrieve one ore more items, depending on the 
collection class.





 
2.1 Using Indices for Addressing Purposes Only
 


If the properties of an index are (pre-)set outside the
control of an application, then the only relationship which can be 
exploited between an index and an item is the one of
associativity.  In this case the index serves as an addressing
scheme for the associated item(s) only as there is no 
functional dependency between the values of the index 
and the item(s) properties.


This leads to the conclusion that it is not possible to use the
index outside the context of its collection class where it got
defined.  [There are no functional dependencies to its items
which could possibly get exploited.]


Such collection classes will return an array as a result of an 
MAKEARRAY message which has the collection items 
stored in it, rather than the indices of the collection.


The result of sending the SUPPLIER message yields an object
whose supplier-index properties are not guaranteed to be
the same as used in the original collection.  [E.g.  iterating over a supplier for a multidimensional
array object.] With other words the yielding
supplier-index/item pairs of the supplier can
be different in the properties of the index-part if
compared to the original collection.


OOI has three such collection classes implemented: Array, 
List and Queue.





 
2.2 Functional Dependency (FD) and Multivalued Dependency (MVD)
 


If the values of the properties of an index are freely settable
by an application, then it is assumed that the associated item
is functional dependent (abbreviated:  "FD")
from its index.  In the case that more than one item
is functionally dependent from the same index, then the term
multivalued dependency (abbreviated:  "MVD") 
is used instead.  [These terms stem from the normalization rules for
creating normalized relational database tables.]


If a functional dependency exists between an index and an
item/items then this leads to the conclusion
that such an index semantically represents the
functional dependent item(s) which are associated with
them.  With other words, knowing the FD respectively the
MVD, it becomes possible to yield the item(s) by
merely setting the appropriate index properties.


Such collection classes will return an array as a result of a
MAKEARRAY message which has the collection indices
stored in it, which in turn may get used to retrieve the appropriate
item(s) from the original collection.


The result of sending the SUPPLIER message yields an object
whose index properties are the same as used in the original
collection.  With other words the yielding
index/item pairs of the supplier are
not different in the properties of the index-part
if compared to the original collection.


OOI has five such collection classes implemented: Bag, 
Directory, Relation, Set and 
Table.


Analyzing the validity of index/item pair(s) and the
multiplicity of indices within the same collection there are
two additional classifications of the builtin collection classes
possible.




 
2.2.1 Index and Item the Same Object
 


Bags and Sets are collection classes which
mandate that the index and the item are always the
same object.  






 
2.2.2 Multiplicity of Index 
 


A Bag and a Relation may contain duplicate
indices and hence posses the MVD property. 
Therefore these classes implement the methods HASITEM(item,
index) and REMOVEITEM(item, index), which allow for 
applications to fully qualify an index/item-pair.



In contrast, a Directory, a Set and a
Table must not contain duplicate indices.  They
possess the FD property but not the MVD property.




Hint:


     In the discussion of the setlike operations a set is 
used to specify the behaviour for all setlike classes which are 
characterized by the property that they must not contain duplicate 
indices.



     In the discussion of the setlike operations a bag is 
used to specify the behaviour for all setlike classes which may contain 
duplicate indices.












[TOP]
[TABLE OF CONTENTS]
[BOTTOM]
-
[PREVIOUS]
[NEXT]
 
3 Setlike Collection Classes and Setlike Operations 
 


A "setlike" collection class is one which possesses
the FD and possibly the MVD property and at least the
setlike methods UNION and DIFFERENCE carrying
out the appropriate setlike operations.  [With these two setlike methods all other setlike
operations can be implemented.] In this text the
receiver setlike collection is usually denoted with
A.


"Setlike operations" operate on elements. 
The collection object which gets sent as an argument to the setlike 
receiver collection is called other.  In this text the
collection other is usually denoted with B.


Before carrying out any setlike operation other gets casted to the type of the setlike
receiver collection first.  In this text the casted version
of B is denoted with B_A hence
indicating in its subscript the type it got casted to.




Hence a setlike operation s is defined as: 
    

    
    A
    s
    B 
    :==
    A
    s
    B_A 

    

where the setlike operation s is one of: 

    
UNION
    
    
    
DIFFERENCE
    
    
    
XOR
    
    
    
INTERSECTION
    
    
    
SUBSET
    




A setlike operation works on the elements of a setlike
collection. 

An element is constituted either 


by the index which represents its associated
item (due to the existence of a FD which exists in 
all setlike collections),


or by the combination of the index with its
item in the case of a
MVD-collection, which as a result fully
qualifies a particular collected item.



If a setlike operation needs to iterate over all elements of a
setlike collection a supplier object is created and
in the course of iterating over the supplier, conceptually 
the appropriate elements are created.






 
3.1 Definition I of Setlike Operations
 


The setlike operations defined in this section apply to all 
setlike collections.  The receiver must be a
setlike collection.  other is the argument of the
invoked setlike method and can be any collection; it gets
casted to the type of the receiver setlike collection
before use.


The resulting setlike collection is of type A and is
denoted as A^/. 

[Hence:
A~class==A^/~class ]


UNION

All elements of other B and of receiver A are 
put into A^/:


    
    A
    UNION
    B 
    :== 
    A
    UNION
    B_A 
    
    


DIFFERENCE (MINUS)


The resulting setlike collection A^/ is a copy of
receiver A in which all elements of other B
are removed:


    
    A
    DIFFERENCE
    B 
    :== 
    A
    DIFFERENCE
    B_A
    
    


XOR

The resulting setlike collection A^/ contains all
elements of the receiver A which are not in
other B and all elements of other B which are 
not in the receiver A:


    
    A
    XOR
    B 
    :==
    A
    XOR
    B_A 
    
    
  


    
    XOR
    
    can be defined with a combination of 

    
    UNION
    

    and

    
    DIFFERENCE:



    
    A
    XOR
    B :==

    (A
    DIFFERENCE
    B_A)
    UNION

    (B_A
    DIFFERENCE
    A)
    
    




INTERSECTION
The resulting setlike collection A^/ contains all elements which appear 
in both collections:


    
    A
    INTERSECTION
    B 
    :==
    A
    INTERSECTION
    B_A
    
    
    


    INTERSECTION
    can be defined with 
    DIFFERENCE:


    
    A
    INTERSECTION
    B 
    :==
    A
    INTERSECTION
    B_A 
    :==
    A
    DIFFERENCE
    (A
    DIFFERENCE
    B_A )
    

    

    or instead of the last term:
    


    
    B_A
    DIFFERENCE
    (B_A
    DIFFERENCE
    A)
    

    



SUBSET 

Returns .true if receiver A
contains all the elements which are contained in 
other B, .false else:


    
    A 
    SUBSET
    B
    :==
    A
    SUBSET
    B_A

    
    


    
    SUBSET
    
    can be defined with DIFFERENCE and a 
boolean comparison whether the resulting setlike collection is 
empty:


( (A DIFFERENCE B_A) 
== {} )
    








 
3.2 Definition II of Setlike Operations
 



There is a setlike collection A as the receiver and a 
collection B as other and an element 
e. B gets casted to type A and is 
denoted as B_A.


The resulting setlike collection is of type A and is
denoted as A^/.

[Hence:
A~class==A^/~class ]


n1 gives the number of times element e is
contained in A and n2 gives the number of
times element e is contained in collection
B_A:





-


n1,n2>=0




-

    In the case of a set in addition: 
    
    n1,n2<=1
    








UNION


  
  
  set:
  

   A union B: e is contained 
   max(n1,n2) times in 
   A^/

  

  bag:
  

   A union B: e is contained 
   (n1+n2) times in
   A^/
  

  



DIFFERENCE

   A difference B: e is contained 
   max(0,n1-n2) times in 
   A^/
   



XOR


   A xor B: e is contained 
   abs(n1-n2)
times in A^/



INTERSECTION

   A intersection B: e is contained 
   min(n1,n2) times in 
   A^/

   



SUBSET


   .true, if for all elements in
   A the relation n1<=n2
holds, .false else.














 
3.3 Examples for the Setlike Operations 
 



The examples in this section use Object Rexx sets and 
Object Rexx bags to demonstrate the effects of the setlike 
operations. The extensions for the receiver collections and 
for the other collections for both, sets
and bags, are given in the following table:



   
   
   
   
   
   set, i.e. unique elements only
   
   
   bag, i.e. multiple elements allowed
   
   

   
   
   A={a,b}
   

   B={b,c}
   
   
   A={a,b,b}
   

   B={b,b,c,c}
   

   
   
   
   Table 1: extensions for sets and bags.
   


The following table 2 demonstrates the content of the setlike 
collection A^/ as a result of setlike operations.





   
   
   
   

   
   setlike collection resulting from the setlike operation


   

   
   setlike operation:

   
   set (unique elements only)
   
   
   bag (multiple elements allowed)
   
   

   

    
    A
    UNION
    B 
    
   
   
   A^/={a,b,c}
   
   
   A^/={a,b,b,b,b,c,c}


   

   

    
    A
    DIFFERENCE
    B 
    

    

    
    B
    DIFFERENCE
    A 
    
   
   
   A^/={a}

   

   A^/={c}
   
   
   A^/={a}

   

   A^/={c,c}


   

   

    
    A
    XOR
    B 
    
   
   
   A^/={a,c}
   
   
   A^/={a,c,c}


   

   

    
    A
    INTERSECTION
    B 
    
   
   
   A^/={b}
   
   
   A^/={b,b}

   

   

    
    A
    SUBSET
    B 
    
   
   
   .false
   
   
   .false



   


   
   
   
   Table 2: resulting setlike collection A^/
   of setlike operations on sets and bags.

   













[TOP]
[TABLE OF CONTENTS]
[BOTTOM]
-
[PREVIOUS]
[NEXT]
 
4 Casting of Collections 
 


If collections are used as an argument (other) for invoking
a setlike operation, then the argument is first casted to the type of 
the setlike receiver collection. 


The casting is carried out by first creating an instance of the type of
the receiver and then puting all collected
objects of other into it.  According to the role an
index plays there is an important difference implied in
whether the other-collection is setlike or not:


Setlike collections:

The index plays an important role as it carries
FD- or MVD-semantics.  Therefore the put
operation uses the supplier-index and the
supplier-item for the purpose of this operation.


 If the target collection is index-only (e.g.  a Bag),
i.e.  the index and the item must be the same
object, then the supplier-index is used for both, 
the target-index and the target-item. 




all other collections:

The index is used merely for addressing purposes and 
does not imply a specific item to be associated
with it.  Hence no FD/MVD-semantics apply.


Therefore the put operation uses the
supplier-item only.  As a result both the
target-index and the target-item are set to
reference the supplier-item.  This way such collections are
dealt with as if they were bags of items.





A possible algorithm to carry out the casting operation as defined in
this section may look like:



 /* 98-10-09, ---rgf;
    return a collection of type "target" which collected all
    item/index pairs of the argument "other"                          */
 
 :: ROUTINE cast PUBLIC
    USE ARG target, other
 
    SIGNAL ON SYNTAX
    
    tmpColl = target~CLASS~NEW /* create an instance of type target   */
    tmpSupp = other~SUPPLIER   /* get a supplier from other           */
    
         /* is "other" a setlike collection ?  */
    bOtherIsSetlike = (other~HASMETHOD("UNION") & other~HASMETHOD("DIFFERENCE"))
 
         /* syntax-error, if index and item must have the same value, e.g. for sets/bags */
    SIGNAL ON SYNTAX NAME INDEX_ONLY   
    target~CLASS~NEW~PUT(1, 2) /* test, if target-type is index-only  */
 
    SIGNAL ON SYNTAX
    DO WHILE tmpSupp~AVAILABLE
       IF bOtherIsSetlike THEN tmpColl[ tmpSupp~INDEX ] = tmpSupp~ITEM
                          ELSE tmpColl[ tmpSupp~ITEM  ] = tmpSupp~ITEM
       tmpSupp~NEXT
    END
    RETURN tmpColl
 
 
 INDEX_ONLY :    /* this is for index-only collections (e.g. sets, bags) */
    SIGNAL ON SYNTAX
    DO WHILE tmpSupp~AVAILABLE
       IF bOtherIsSetlike THEN tmpColl[ tmpSupp~INDEX ] = tmpSupp~INDEX
                          ELSE tmpColl[ tmpSupp~ITEM  ] = tmpSupp~ITEM
       tmpSupp~NEXT
    END
    RETURN tmpColl
 
 SYNTAX: RAISE PROPAGATE       /* raise error in caller               */















Please send comments to Rony.Flatscher@wu-wien.ac.at


[TOP]
[TABLE OF CONTENTS]
-
[PREVIOUS]

`set`, i.e. unique elements only	`bag`, i.e. multiple elements allowed
`A={a,b}` `B={b,c}`	`A={a,b,b}` `B={b,b,c,c}`

setlike collection resulting from the setlike operation
setlike operation:	`set` (unique elements only)	`bag` (multiple elements allowed)
`A UNION B`	`A^/={a,b,c}`	`A^/={a,b,b,b,b,c,c}`
`A DIFFERENCE B` `B DIFFERENCE A`	`A^/={a}` `A^/={c}`	`A^/={a}` `A^/={c,c}`
`A XOR B`	`A^/={a,c}`	`A^/={a,c,c}`
`A INTERSECTION B`	`A^/={b}`	`A^/={b,b}`
`A SUBSET B`	`.false`	`.false`