Thoughts about Collections

[jeshaw2]

Here are my thoughts on the Enumeration Order Policy I mentioned earlier in this thread.  This is a derivtive work based on a literature search across the internet.

Enumeration Order Policy

Collections may be designated as enumeratable or notEnumeratable.  enumeratable presupposes the existence of an object that traverses the collection in some specified manner.  In the context of this policy, the traversal may be performed by an Enumerator, Iterator, or an Indexer.

Enumeration Order Policies are specified in terms of operations used to derive new collections from existing collections. This policy does not address issues of collection containment, persistence, nor anything else beyond the ordering of Items within the derived collection.

There are usually three players to keep track of, for which I use the following terminology:

   newCollection := existingCollection.derivationOp (proposedContent)

A newCollection is derived from a subset of the existingCollection plus the addition of any proposedContent.  The existingCollection may, or may not, be a null collection and the subset may include zero to all of the existing items in the existingCollection.  The proposedContent may, or may not, be null, but it is fully included (not subsetted) in the newCollection. Collisions resulting from this merging of Items from two sources are resolved by the Collision Policy for the collection.

The default Enumeration Order for unsorted collections is based on where items were inserted to the existingCollection.  The default Enumeration Order for ordered collections is based upon the ordering function of the existingCollection.

Two, of the many other, Enumeration Order Policies are LIFO (specific to Stacks) and FIFO (specific to Queues and Priority Queues).

• FIFO means that, in deriving a newCollection from an existing one, that the contents of the newCollection that are taken from the existingCollection appear first and in the same relative order.  When a derivation operation proposes new contents, the contents of the newCollection taken from the proposedContents appear after the contents from the existingCollection, and in the same relative order as presented in the proposedContent.
• With LIFO the contents taken from the proposedContent appear first in the newCollection, followed by the contents taken from the existingCollection.  The contents taken from the existingCollection appear in the same relative order in which they appeared in the existingCollection.  The contents taken from the proposedContent appear in reverse order to the way they are presented in the proposedContent.  Deriving a Queue from a Stack or a Stack from a Queue reverses the order of the items.
  
  The Enumeration Orders for trees are the same as the traversal orders offered by the tree.  Well known traversal orders include, but are not limited to,  Pre-order, In-order, Post-order, Depth-first, and Breadth-first.  A tree may offer a variety of traversal orders and may, therefore, provide a variety of Enumeration Orders.
  
  
  Your thoughts?

[Paolo F Cantoni]

 Can you expand on what Ordinal manipulation might entail?

BTW, I just made indexed lists immutable.

I just meant access via the integer Indexer.

I just say Indexer any more can I?  

In the light of our discussions in this Thread, what do you mean by Indexed List?  And why is it immutable?

Paolo

[Paolo F Cantoni]

Paolo
Actually, I was hoping you'd talk me out of it; because now, what is the difference between a set and a map    Is it that a map has an explicit key and a set has a derived key (derived from the item's position)?  :-/

A Set is a Collection whose Items are just values (for example, an Enumeration is an Ordered Set of EnumerationLiterals).  A Map is a Collection whose items consist of two parts, a Name and a Value (or Object).

Perhaps the Indexer is an object that derives a map, which is associative, from an existing set which is non-associative?   :-/

It's unfortunate that due to natural language constraints, we get confusion due to the Index homonym.  (I'm subject to it too...)

For my own work (and in my models, designs and documentation) I make a strict distinction between Keys and Indexes.  A Key is a uniqueness constraint which is (typically) supported by an underlying unique Index.  Thus I no longer use the phrase Unique Index, just Key.  Indexes aid access, Keys provide Referential Integrity.

In the context of the Collections and situations we are dealing with here, I don't think we need to directly expose any Indexes (in the DBMS sense).

An Indexer does not require an Index to provide Ordinal access to a Collection.
Interestingly, we haven't discussed if an Indexer can return more than one Item from the Collection (for example: give me every third Item).

An Indexer can be defined for non-Ordinal access (using some attribute value of the items).  Here, again, it may return more than one Item (for example, give me the "Blue" Items).  Indexes may be used to assist in returning these items, but that is an internal implementation issue.  Not a part of the definition.

In the case of {unique} collections, then Keys are involved.

In the case of Mapped Collections, the Name is used to access the Item.  In the case of a Map, the Name is unique (identifies exactly one item), in the case of the Multi-Map, there may be more than one Item with that Name.

As far as I can determine, an Unordered Map is a Hash.  Thus, notwithstanding that a unique Name is a precondition, you can't get an Ordered Iterator.  An Ordered Map provides the Ordered Iterator.

I have to admit I'm having difficulty comparing apples with apples in looking up stuff on Collections on the Net as they seem all to be language specific and sometimes the same word means slightly different things, depending on the language involved.

Paolo

[jeshaw2]

In the light of our discussions in this Thread, what do you mean by Indexed List?  And why is it immutable?

Given your last post, my meaning may change  Here is what I meant at that time and allow me the fun of developing  a telephone book example that I'm contemplating for use with my students:

List: an unordered, disarrayed, not unique, un-contained, unaddressable collection of values.  For example, I cut the phone numbers out of my phone book.  I made sure each phone number individually appeared, with no other information, on its own little piece of confetti.  I blew the confetti through a fan and let the pieces fall where they may.  That gave me a list of phone numbers.  (I can't use the term set here, but if I swept them in to an envelope would I than have a bag )

Indexed list: a list where the values are arranged in sequence (not necessarily in an order) so that they may be referenced by their position in the sequence.  For example:  I brought in the neighborhood kids and had them arrange the phone number confetti in a long, single row down the sidewalk.  Thus, I could reference a phone number by its position (i) in the row -- fromHead(i) or fromTail(i). Now, needing the phone number located at Row.fromTail(1,234,592), I may send out a child to count back from the tail of the collection to the phone number desired and bring what they discover at that position back to me for use.  I refer to i as the index.

Why immutable? Well, technically it is mutable.  However, I find it difficult to carry the indexed phone list with me on trips out of town (too hard to get it past airport security and makes it difficult to maintain by the folks on the home front too), but I can remember my home phone number.  

When on a trip, I normally need access to a subset of the phone book (clients, friends, etc.), so I maintain a very small pocket phone book, on a preprinted, shiny, white plastic <<show-off in the pub>> reference card, containing the names of interesting individuals, but instead of including their phone numbers, I keep  the index to their number in the Row collection thus assuring that I'm in quasi-third normal form *feeling proud now".

When I need to call an associate, I first call my daughter at home and give her the index to the number I need.  She runs out, counts down to the referenced location, and calls me back (albeit a few days later) with the needed number.  

Imagine my dismay when I discover that several phone numbers have been removed from the list (I didn't even know those individuals either) and now all of the index numbers on my pre-printed, shiny, white plastic <<show off in the pub>> card are useless!!!  You can bet that when I got home, I made the Row collection immutable; problem fixed!  *Really feeling proud now!*

Well, my problem solution set my neighbor (Paolo)'s head to wagging and he posted something about indexes, keys, and such.  Let me read on and see what that's all about...

[jkorman]

Given your last post, my meaning may change  Here is what I meant at that time and allow me the fun of developing  a telephone book example that I'm contemplating for use with my students:

List: an unordered, disarrayed, not unique, un-contained, unaddressable collection of values.  For example, I cut the phone numbers out of my phone book.  I made sure each phone number individually appeared, with no other information, on its own little piece of confetti.  I blew the confetti through a fan and let the pieces fall where they may.  That gave me a list of phone numbers.  (I can't use the term set here, but if I swept them in to an envelope would I than have a bag )

Jim, You lost me here. I was under the assumption that a list had order! Given your example of the phone list
As I see it, your phone book is a list of phone numbers. Each page, an arbitrarily sized sub-list.  Once you cut each entry from the other, you no longer have a list. Especially after spreading the confetti about the room.  

Side note : I am enjoying these discussions. I'm looking forward to a compilation in more readable form.

Jim

[jeshaw2]

In my search on the INTERNET, bag is shown as a synonym of list  :-/  Paolo said in the thread isUnique isOrdered a bag is un-orded and not unique.  I perceive a phone book (uncut) as an Ordered Map of phone numbers, given that it is associative between the phone numbers and the individual's names.  

I suspect there is a nuance of a difference between a list and a bag, but it is beyond any metrics I've come across so far.

Side note : I am enjoying these discussions. I'm looking forward to a compilation in more readable form.

Thanks...it is in my mind to do so.

[jeshaw2]

Paolo;

A Set is a Collection whose Items are just values (for example, an Enumeration is an Ordered Set of EnumerationLiterals). A Map is a Collection whose items consist of two parts, a Name and a Value (or Object).

I agree with your assertions here, but I'm suspicious of the example  But no matter, I get your point.  BTW: Would you apply this portion of a set's definition to a vector, list, and bag? Further, do these collection types appear at the CIM level?

A Key is a uniqueness constraint which is (typically) supported by an underlying unique Index. Thus I no longer use the phrase Unique Index, just Key. Indexes aid access, Keys provide Referential Integrity.

In the context of the Collections and situations we are dealing with here, I don't think we need to directly expose any Indexes (in the DBMS sense).

This is a bit of a stretch for me, but I think I understand and can provisionally accept for now.  I need time to internalize this.  I'm sure you are correct for modeling this at the CIM level.  One 'Gunga Din' patch for your vest here!

An Indexer does not require an Index to provide Ordinal access to a Collection.

Agreed.

Interestingly, we haven't discussed if an Indexer can return more than one Item from the Collection (for example: give me every third Item).

An Indexer can be defined for non-Ordinal access (using some attribute value of the items). Here, again, it may return more than one Item (for example, give me the "Blue" Items). Indexes may be used to assist in returning these items, but that is an internal implementation issue. Not a part of the definition.

You seem to be blurring the distinctions you made earlier between Indexer and Iterator.

In the case of {unique} collections, then Keys are involved.

 I disagree with this.  I can allow this for maps, but for sets the item's value is used for the equivalence test.  (Ref; my thoughts on Collision Policy above.)

As far as I can determine, an Unordered Map is a Hash.

 If by this, you mean a hash table, then I would want it to be immutable also!

Thus, notwithstanding that a unique Name is a precondition, you can't get an Ordered Iterator. An Ordered Map provides the Ordered Iterator.

 Got lost here. Can you provide more words?  BTW: In my thinking, Indexers, Iterators, and enumerators (if available for a given collection) are objects nested within the collection object.  

I have to admit I'm having difficulty comparing apples with apples in looking up stuff on Collections on the Net as they seem all to be language specific and sometimes the same word means slightly different things, depending on the language involved.

 Agreed in spades.  A lot of that static shows up in my classes as quoted authorities (how dare I disagree with all those sources?) making me look like a heretic.   The reasonings we are going through here are helping to deal with that in a more dignified manner.

And just to be clear:  Sets are essentially non-associative collections?  But they can be made to look associative? (this is where I'm at now.)

[Paolo F Cantoni]

[size=16]STOP PRESS!  Important edit[/size]
Jim,
I made the original post, but I had a lingering concern over my response to your question regarding Sets being non-associative.  I've now found the problem with my (original response).  I now believe my highest level categorisation of Collections into Associative and non-Associative is incorrect.  The Items in the categorisations, I still believe are correct.  That is, Sets go with Maps.  But the naming of the categorisation is incorrect.  What I called Associative Collections should now be called Value Based.   This means that Each Item in the collection is a Value, not an Object.  In the Object based collection, the items are objects.

In the case of Maps, we have an Associative collection since we associate something with the Value Item (an object, another value).  Value based collections can thus entertain the concepts of Ordering and/or Uniqueness

So, if you substitute the term Value Based for Associative and Object based for non-Associative everything I've said so far is still valid (I think) - I just named them incorrectly!

Paolo
A Set is a Collection whose Items are just values (for example, an Enumeration is an Ordered Set of EnumerationLiterals). A Map is a Collection whose items consist of two parts, a Name and a Value (or Object).
I agree with your assertions here, but I'm suspicious of the example   But no matter, I get your point.  BTW: Would you apply this portion of a set's definition to a vector, list, and bag?

No, because these are not Value based, they have no concept of uniqueness.  BTW, See below, I now understand an Enumeration is a Set (It doesn't have to be an OrderedSet).

Further, do these collection types appear at the CIM level?

Yes, I think so.

A Key is a uniqueness constraint which is (typically) supported by an underlying unique Index. Thus I no longer use the phrase Unique Index, just Key. Indexes aid access, Keys provide Referential Integrity.
In the context of the Collections and situations we are dealing with here, I don't think we need to directly expose any Indexes (in the DBMS sense).
This is a bit of a stretch for me, but I think I understand and can provisionally accept for now.  I need time to internalize this.  I'm sure you are correct for modeling this at the CIM level.  One 'Gunga Din' patch for your vest here!

The explanations above should have helped clarify this.

An Indexer does not require an Index to provide Ordinal access to a Collection.
Agreed.
Interestingly, we haven't discussed if an Indexer can return more than one Item from the Collection (for example: give me every third Item).
An Indexer can be defined for non-Ordinal access (using some attribute value of the items). Here, again, it may return more than one Item (for example, give me the "Blue" Items). Indexes may be used to assist in returning these items, but that is an internal implementation issue. Not a part of the definition.
You seem to be blurring the distinctions you made earlier between Indexer and Iterator.

I don't think so.  The iterator always returns one value (at a time) by applying some constant function to the collection - I said elsewhere in this thread that I felt that the Iterator was essentially procedural.  The Indexer and Enumerator are essentially declarative.  Consequently, they behave more like an SQL SELECT.  Therefore, we should allow the possibility that an Indexer could return several items.  Remember a non-ordinal Indexer uses the attributes of the Item to determine whether to return it or not.

In the case of {unique} collections, then Keys are involved.
I disagree with this.  I can allow this for maps, but for sets the item's value is used for the equivalence test.  (Ref; my thoughts on Collision Policy above.)

Having re-read the Collision Policy, I believe you are mistaken in discussing Uniqueness for an non-Value Based Collection.  As I discuss above, there is nothing to hang the uniqueness hat on.  I stand by my original statement,.  Hopefully, my clarifications may have helped convert you.

As far as I can determine, an Unordered Map is a Hash.
If by this, you mean a hash table, then I would want it to be immutable also!

Do we have to introduce immutability at this point?  In the case of CIM level stuff, it may be moot.  Anyways, I'd like to clarify other stuff before attacking immutability (if that's OK with you).

Thus, notwithstanding that a unique Name is a precondition, you can't get an Ordered Iterator. An Ordered Map provides the Ordered Iterator.
Got lost here. Can you provide more words?  BTW: In my thinking, Indexers, Iterators, and Enumerators (if available for a given collection) are objects nested within the collection object.

They're surely Features.  In my view, behavioural features.  I'm not sure they're objects, they'd be more like the Properties we discussed earlier - not well handled by UML at present.
Back to the Hash - as I understand a Hash, there is no implied ordering.  You supply the key, you get the item.  If you iterate (or ordinally index) over  the Collection, the names will come out in no particular order.  In fact, I'm not sure that the same order is guaranteed between runs on an unchanged Collection.  To provide consistent ordering, you have to apply the Constraint: IsOrdered to the Map.  Good enough?

I have to admit I'm having difficulty comparing apples with apples in looking up stuff on Collections on the Net as they seem all to be language specific and sometimes the same word means slightly different things, depending on the language involved.
Agreed in spades.  A lot of that static shows up in my classes as quoted authorities (how dare I disagree with all those sources?) making me look like a heretic.   The reasonings we are going through here are helping to deal with that in a more dignified manner.

Well, we can easily dare to disagree since they disagree among themselves!  Remember my tag line and signature...

Anyway, we have no particular axe to grind, other than trying to bring clarity and consistency to our understanding - for the purposes of creating better models - a noble endeavour!

And just to be clear:  Sets are essentially non-associative collections?  But they can be made to look associative? (this is where I'm at now.)

OK< Jim.  Assuming you were using my previous definition of Associative, then I'll reply in the negative, but use the new definitions. Sets are Value Based because they involve a Value (Name) corresponding to (associated with) the Item.  Elsewhere I said an Enumeration is an Ordered Set, this was incorrect! All Sets are Enumerations, if the set of values (the literals not the integers - remember in the CIM the only thing we have are the literals) is ordered then we have an OrderedSet or OrderedEnumeration.  OrderedEnumeration is of no real consequence to us in normal usage - it's just an Enumeration.
The UML 2 [size=13]Superstructure[/size] Specification   7.3.44 Property (from Kernel, AssociationClasses) has a nice little table specifying how isOrdered and IsUnique interact - but in the context of the values...
isOrdered isUnique Collection type
false............true..............Set
true.............true........OrderedSet
false........... false.............Bag
true............ false..........Sequence

Apologies to all for not having thought carefully enough... But I think we're getting there.

Paolo

[Paolo F Cantoni]

Given your last post, my meaning may change  Here is what I meant at that time and allow me the fun of developing  a telephone book example that I'm contemplating for use with my students:

Do we agree that the original phone book is a Multi-Map (valueBased, associative, ordered, nonUnique).  If not, then the rest of my response may clarify why you should agree...  It's valueBased because each name has a number (and other information associated with it).

List: an unordered, disarrayed, not unique, un-contained, unaddressable collection of values.  For example, I cut the phone numbers out of my phone book.  I made sure each phone number individually appeared, with no other information, on its own little piece of confetti.  I blew the confetti through a fan and let the pieces fall where they may.  That gave me a list of phone numbers.  (I can't use the term set here, but if I swept them in to an envelope would I than have a bag )

According to UML 2 you have a bag (objectBased, unOrdered, nonUnique).  Now for some clarification.  You have a list of Items - you DON'T have a list of Values.  Each Item has a value but it ISN'T a value (in the valueBased Collection sense).  I think that's where confusion has crept in (even for me, I'm improving my mental metaCIM as I type!).  Jim Korman was saying something similar, I think.

Indexed list: a list where the values are arranged in sequence (not necessarily in an order) so that they may be referenced by their position in the sequence.  For example:  I brought in the neighborhood kids and had them arrange the phone number confetti in a long, single row down the sidewalk.  Thus, I could reference a phone number by its position (i) in the row -- fromHead(i) or fromTail(i). Now, needing the phone number located at Row.fromTail(1,234,592), I may send out a child to count back from the tail of the collection to the phone number desired and bring what they discover at that position back to me for use.  I refer to i as the index.

I don't think there's any point in distinguishing a List from an Indexed List.  All Collections have an Indexer (ordinal), I think.  According to UML 2 7.3.44 (mentioned in the previous post) Sequences are Ordered.  (They're OrderedBags).  That's why they only mention the isOrdered and isUnique properties.  Since the numbers are the Items, you can ask the kid to bring you "555-5555" but they will be behaving like an Indexer.

Why immutable? Well, technically it is mutable.  However, I find it difficult to carry the indexed phone list with me on trips out of town (too hard to get it past airport security and makes it difficult to maintain by the folks on the home front too), but I can remember my home phone number.

When on a trip, I normally need access to a subset of the phone book (clients, friends, etc.), so I maintain a very small pocket phone book, on a preprinted, shiny, white plastic <<show-off in the pub>> reference card, containing the names of interesting individuals, but instead of including their phone numbers, I keep  the index to their number in the Row collection thus assuring that I'm in quasi-third normal form *feeling proud now".

Your card is a ValueBased, Associative Collection - another (multi-)Map - you put in the Name and get a number.

When I need to call an associate, I first call my daughter at home and give her the index to the number I need.  She runs out, counts down to the referenced location, and calls me back (albeit a few days later) with the needed number.

What you have at home is a Bag.  Your daughter is the Indexer (ordinal).  Your call supllies the ordinal value to be looked up.

Imagine my dismay when I discover that several phone numbers have been removed from the list (I didn't even know those individuals either) and now all of the index numbers on my pre-printed, shiny, white plastic <<show off in the pub>> card are useless!!!  You can bet that when I got home, I made the Row collection immutable; problem fixed!  *Really feeling proud now!*

You got a number because the Bag still had an n^th element.  You only know it was the wrong number because the person you contacted wasn't the person you expected.

The immutability is not a requirement of the Collections, but in the interface (you have created) between the two collections.  Because you have two collections, but the wrong way round!  If at home you kept the multi-map (phone book) you would only need to keep a list of names on your card (non-valueBased, ordered (as you will), possibly unique).  Your call would now be:  "Honey, can you look up Paolo's number and give it to me?"  So long as Paolo was in the book, she'd give it to you, regardless of where his ordinal position was.

Well, my problem solution set my neighbor (Paolo)'s head to wagging and he posted something about indexes, keys, and such.  Let me read on and see what that's all about...

Paolo

[jeshaw2]

Paolo;
Just a quick note.  There is a lot of stuff here to consider, but the wife just handed me a "honey-do" list.

What I called Associative Collections should now be called Value Based. This means that Each Item in the collection is a Value, not an Object. In the Object based collection, the items are objects.

In the case of Maps, we have an Associative collection since we associate something with the Value Item (an object, another value). Value based collections can thus entertain the concepts of Ordering and/or Uniqueness

So, if you substitute the term Value Based for Associative and Object based for non-Associative everything I've said so far is still valid (I think) - I just named them incorrectly!

I came across a reference that seems to mirror this Typology.  

A few threads back, I used the term Sequential to refer to non-Associative collections.  It was this reference that led me into that.  Take a look, if you will, and let me know if this is helpful, or not, to our discussion.

C++ Lecture Notes, Steven J. Zeil, Dept CompSci, Old Dominion Univ.
His use of Containers is similar to our use of Collections.  These references are:

Sequential & Associative  Can we use these names or must they be abstracted to a higher level and renamed?

Quick Reference for STL Containers (Presents an interesting thought on Adapters.)

Another Typology I've seen is Vectors, Arrays, and Collections.  Vectors & Arrays hold values;  Collections hold objects.

Is there a way we can reconcile / unify all of this?

Do we agree that the original phone book is a Multi-Map (valueBased, associative, ordered, nonUnique).

Yes I agree.  I picked up on the non unique property after I posted.  

[Paolo F Cantoni]

Jim,

Here's an attempt to reconcile / unify the discussions so far:

What we're attempting to do is to define a set of Collection types, suitable for use in a CIM (Computationally Independent Model).
Accordingly, we focus only on their functionality, not any considerations of computational methods.  We will attempt to define a set of properties, functionalities, capabilities, constraints and operations whereby any given combination will produce a unique name for the Collection type.  Our set of Collection Types therefore will attempt to be Canonical.

In addition, where appropriate, we will apply the UML denotations regarding collections to be found in the [size=13]Superstructure[/size] Specification   7.3.44 Property (from Kernel, AssociationClasses)

In order for the notions of isOrdered an/or isUnique to be applicable, each item in the collection must expose or provide or be associated with a Tag for this purpose.  We can liken the tag to those boards carried by advertisers on the street (such as "the End is Nigh" or "Eat at Joes")  Essentially, the Tag is visible outside the Item (to the Collector - the Collection holonym).

We can thus separate Collection types into two basic categorisations:

unTagged - We can only see the Item as Opaque.
Tagged - Each opaque Item also has a visible Tag.

I'll tackle the latter one first.


[size=16]Tagged Collections[/size][/b]

Tagged Collections have Items with a Tag visible to the Collector.

Sometimes, for whatever reason, the Item is the Tag.  "The Tag, the whole Tag and nothing but the Tag".  Predominantly, however,you have a Tag and the associated Item.  These latter are denoted Associative Collections (for the obvious reason).  Thus a Tagged Collection may be either Associative or nonAssociative.  Associative Collections are also known as Maps

Since we have determined that isUnique and isOrdered required Tags and the UML section only discusses their interaction, then the section applies ONLY to Tagged Collections.  NOTE: the UML section doesn't say anything about the Collection being Associative or not, thus the terms apply equally to both.

Once we have Tags, if the there can only be unique Tags in the Collection, then the Tag acts as a Key (uniqueness constraint).   Such Collections are known as Enumerations.

Where you do not have ordering, you can also have all the operations of unTagged Collections (see below).

The Tagged Collection Types are known as:
Set:    (unOrdered, unique)
OrderedSet:    (ordered, unique)
Bag:    (unOrdered, nonUnique)
Sequence:    (ordered, nonUnique)


[size=16]unTagged Collections[/size][/b]

UnTagged Collections have Items that are Opaque to the Collector.

We can ONLY describe (identify?) each Item by their ordinal position in the Collection.  Operations such as insertion and deletion can only be carried out at certain points in the Collection:
Add to start   (addToStart)
Add in middle    (addInMiddle)
Add to end    (addToEnd)
Remove from start    (i]removeFromStart[/i])
Remove from middle    (removeFromMiddle)
Remove from end    (removeFromEnd)

If all six operations are not available, then we have a Restricted Access Collection.

The unTagged Collection Types are known as:
List:   (addToStart,addInMiddle,addToEnd,RemoveFromStart,removeFromMiddle,removeFromEnd)
Deque:   (addToStart,addToEnd,removeFromStart,removeFromEnd)
Queue:   (addToStart,removeFromEnd)
Stack:   (addToStart,removeFromStart)


[size=16]Collection Features[/size][/b]

All collection types have two features:
Iterator:   Retrieves one item at a time by applying a function over the ordinal position of the current Item.
Indexer:   Retrieves one or more items at a time by applying a function some property of the Items.  NOTE: an Indexer can provide similar functionality to the Tag in a Tagged Collection.  The difference is that in the Tagged Collection the Collector provides a standard Indexer operation, in an unTagged collection, if no indexer is provided, then one will not exist.
In addition, where the Item contains an attribute whose values are an Enumeration one can define an:
Enumerator:   Retrieves one or more items at a time by applying a filter on an Enumerable property of the Items.

The Iterator is essentially procedural.  Indexer and Enumerator are essentially declarative.

Multiple Iterators, Indexers and Enumerators may be defined for a Collection, but they must vary in their signatures.


As far as I can tell, these are the ONLY Collection types available at the CIM level.  All others are either:
PIM (Platform Independent Model)
PSM (Platform Specific Model)
applicable due to some computational or logistical internals.

HTH,
Paolo

BTW: I've uploaded a new version of the Abstractions document, consistent with these definitions.

[size=0]©2005 Paolo Cantoni, -Semantica-[/size]

[jeshaw2]

Paolo;

This means that Each Item in the collection is a Value, not an Object.  In the Object based collection, the items are objects.
 
In the case of Maps, we have an Associative collection since we associate something with the Value Item (an object, another value).  Value based collections can thus entertain the concepts of Ordering and/or Uniqueness

I need some help with this.  Can you  provide a real-word example from each of the two collection types including some represetnative data?

[Paolo F Cantoni]

Paolo;

I need some help with this.  Can you  provide a real-word example from each of the two collection types including some representative data?

Does my new Unified Theory help?  If not, let me know and I'll provide examples...

Paolo  (going off to his "honey-do" list...)

[jeshaw2]

Paolo!  Nice piece of work!  I think I understand this!  However, lets make sure I understand this by paraphrasing in a less formal language..

What we're attempting to do is to define a set of Collection types, suitable for use in a CIM (Computationally Independent Model).
Accordingly, we focus only on their functionality, not any considerations of computational methods. We will attempt to define a set of properties, functionalities, capabilities, constraints and operations whereby any given combination will produce a unique name for the Collection type. Our set of Collection Types therefore will attempt to be Canonical.

 There is a whole bunch of stuff we can do at the PIM, PSM and coding levels that we won't recognize as being available or existing at the CIM level.  We shall speak only of the real-world essence of things in our domain, what is to be done with them, and not how it will be done, or how it could be done when we develop the software.

In addition, where appropriate, we will apply the UML denotations regarding collections to be found in the Superstructure Specification 7.3.44 Property (from Kernel, AssociationClasses)

Specifically, collection properties and collection classification in to collection types.

In order for the notions of isOrdered an/or isUnique to be applicable, each item in the collection must expose or provide or be associated with a Tag for this purpose.

The collection association properties isOrdered=true|false and isUnique=true|false are constraints on the association.  Their evaluation requires information about the Items, from somewhere, to work against.  What ever the source of that information, we shall refer to it as the Item's Tag.

We can liken the tag to those boards carried by advertisers on the street (such as "the End is Nigh" or "Eat at Joes") Essentially, the Tag is visible outside the Item (to the Collector - the Collection holonym).

Our practice of Data hiding would normally prevent  the Collector object  (the one representing the whole collection) from accessing the collected Item's attributes.  At the CIM level, however, we trust that the needed information will (some how and in some way) be made available when needed, and for the present, we are content to simply give a name to this information so that we may make reference to it within or CIM level discussions and documentation.

We can thus separate Collection types into two basic categorizations:

unTagged - We can only see the Item as Opaque.
Tagged - Each opaque Item also has a visible Tag.

If we are able to evaluate isOrdered and isUnique the collection is of one type, if not it is of the other type.  Further, we shall proceed as if the Collector can not see any of the Item's attributes except for the Tag information which may be exposed to the collector.

Tagged Collections

Tagged Collections have Items with a Tag visible to the Collector.

By our own definition this is true.

Sometimes, for whatever reason, the Item is the Tag. "The Tag, the whole Tag and nothing but the Tag".

An atomic piece of data like my phone number confetti chips.

Predominantly, however, you have a Tag and the associated Item.

My phone number confetti chips would not qualify for this case.  Even though the phone number could  be associated with an individual, there is nothing on or within the confetti chips themselves to make that association.  To qualify, information about the individual would need to be present, but not necessarily visible, on or within the chip.

These latter are denoted Associative Collections (for the obvious reason).
 Thus a Tagged Collection may be either Associative or nonAssociative. Associative Collections are also known as Maps

Collections having Items similar to my confetti chips with out the information about the individual are nonAssociative.  Collections having Items similar to my confetti chips with the information about the individual are Associative.

Since we have determined that isUnique and isOrdered required Tags and the UML section only discusses their interaction,

In terms of collection types.

then the section applies ONLY to Tagged Collections. NOTE: the UML section doesn't say anything about the Collection being Associative or not, thus the terms apply equally to both.

If mom didn't tell me to "keep out of it", the cookie jar was fair game.

Once we have Tags, if the there can only be unique Tags in the Collection, then the Tag acts as a Key (uniqueness constraint).

Not to be confused with a DBMS type "key"...its a constraint, not a piece of data.  Also, we may say a similar thing about ordered collections.

Such Collections are known as Enumerations.

Huh Enumerations must be unique?  I'm not sure about that yet, I need more thought about this.

Where you do not have ordering, you can also have all the operations of unTagged Collections (see below).

Gee! Can't I, at least, have some of them? Wondering if the uniqueness impacts their availability?

The Tagged Collection Types are known as:
Set: (unOrdered, unique)
OrderedSet: (ordered, unique)
Bag: (unOrdered, nonUnique)
Sequence: (ordered, nonUnique)

The number of these types are doubled when you take non- and Associative collections in to consideration.  [looking askance] at the naming conventions used in our spread sheet. [/looking askance]

unTagged Collections

UnTagged Collections have Items that are Opaque to the Collector.

We can ONLY describe (identify?) each Item by their ordinal position in the Collection. Operations such as insertion and deletion can only be carried out at certain points in the Collection:
Add to start (addToStart)
Add in middle (addInMiddle)
Add to end (addToEnd)
Remove from start (i]removeFromStart[/i])
Remove from middle (removeFromMiddle)
Remove from end (removeFromEnd)

If all six operations are not available, then we have a Restricted Access Collection.

The unTagged Collection Types are known as:
List: (addToStart,addInMiddle,addToEnd,RemoveFromStart,removeFromMiddle,removeFro mEnd)
Deque: (addToStart,addToEnd,removeFromStart,removeFromEnd)
Queue: (addToStart,removeFromEnd)
Stack: (addToStart,removeFromStart)

This is intuitively easy to understand.

Collection Features

All collection types have two features:
Iterator: Retrieves one item at a time by applying a function over the ordinal position of the current Item.
Indexer: Retrieves one or more items at a time by applying a function over ? some property of the Items.

True if that property is non-opaque to the indexer.

NOTE: an Indexer can provide similar functionality to the Tag in a Tagged Collection. The difference is that in the Tagged Collection the Collector provides a standard Indexer operation, in an unTagged collection, if no indexer is provided, then one will not exist.
In addition, where the Item contains an attribute whose values are an Enumeration one can define an:
Enumerator: Retrieves one or more items at a time by applying a filter on an Enumerable property of the Items.

Again, True if that property is non-opaque to the Enumerator.

The Iterator is essentially procedural. Indexer and Enumerator are essentially declarative.

For the benefit of the "greater unwashed", more words on procedural and declarative would be nice to have.

Multiple Iterators, Indexers and Enumerators may be defined for a Collection, but they must vary in their signatures.

This is an important point; and, not a problem to understand.

As far as I can tell, these are the ONLY Collection types available at the CIM level.

Might I suggest Priority Queues?

Well, I'm still up in the air about Enumerations being unique.  Well, how did I do?

[Paolo F Cantoni]

Paolo!  Nice piece of work!  I think I understand this!  However, lets make sure I understand this by paraphrasing in a less formal language..

Yes, very good move Jim.  And an excellent job!

[size=13][SNIP][/size]
Our practice of Data hiding would normally prevent  the Collector object  (the one representing the whole collection) from accessing the collected Item's attributes.  At the CIM level, however, we trust that the needed information will (some how and in some way) be made available when needed, and for the present, we are content to simply give a name to this information so that we may make reference to it within or CIM level discussions and documentation.

Well, technically the Tag is not the Item, so it can come from anywhere.  It's not even the function of the Collector to find the Tag, they just have to accept it.  The object asking to add the Item provides the Tag.  How it got it is its business.

If we are able to evaluate isOrdered and isUnique the collection is of one type, if not it is of the other type.  Further, we shall proceed as if the Collector can not see any of the Item's attributes except for the Tag information which may be exposed to the collector.

Yes, I think this point is fundamental. I didn't get to this point until I started writing the previous post.  See also the regarding the Features below...

[size=13][SNIP][/size]
Not to be confused with a DBMS type "key"...its a constraint, not a piece of data.  Also, we may say a similar thing about ordered collections.

My use of Key in both places is identical.  A Key uniquely identifies the Row in the Table, the Item in the Collection.  While a Key is not required to enforce uniqueness, it does enforce uniqueness.  (In another post I make the clear distinction between Key and DBMS Index)

Huh Enumerations must be unique?  I'm not sure about that yet, I need more thought about this.

The UML 2 [size=13]Superstructure[/size] Specification
7.3.16 Enumeration (from Kernel)
An enumeration is a data type whose values are enumerated in the model as enumeration literals.
7.3.17 EnumerationLiteral (from Kernel)
An EnumerationLiteral has a name that can be used to identify it within its enumeration datatype. The enumeration literal
name is scoped within and must be unique within its enumeration. Enumeration literal names are not global and must be
qualified for general use.
(emphasis mine)

[size=10][SNIP][/size]
Gee! Can't I, at least, have some of them? Wondering if the uniqueness impacts their availability?

Yes, that was exactly my assessment, uniqueness robs you of their availability.

The number of these types are doubled when you take non- and Associative collections in to consideration.  [looking askance] at the naming conventions used in our spread sheet. [/looking askance]

Yes, I agree, but I couldn't see any way around it.

[size=13][SNIP][/size]
For the benefit of the "greater unwashed", more words on procedural and declarative would be nice to have.

procedural   concerned with how to manipulate symbols, concepts, and rules to accomplish a task or solve a problem
declarative    concerned with the recall of facts and events
In a declarative request, I ask the system to return me some result.  The System figures out how to do it.
In a procedural request, I have to tell the system how to return me the result.  You can better appreciate the difference by comparing a DBMS stored procedure to a DBMS select statement.

[size=10][SNIP][/size]
Might I suggest Priority Queues?

Yeah, I looked at them before I moved them out.  I couldn't see how they differed from sufficiently from a normal queue to warrant their own type.  They are certainly a specialization of Queue.  Do we have a new Feature... Prioritiser?

Well, I'm still up in the air about Enumerations being unique.  Well, how did I do?

Enumerations should be sealed by now...  You done good!

Paolo