Thoughts about Collections

[Paolo F Cantoni]

Paolo;

Everything made sense and I agree with everything  up to this point...
it may not need the same Attribute in each Item, but it must be there (and only one of) for the Enumerator to work.  
 I agree with what I think you said, but I'm not sure that what you think you said is what I think you said.  Can you fly a bit slower?

When I wrote it I thought it might be contentious.
I'm taking my cue from the discussion on Indexers.
It seems to me that in the simple case, homogeneous collection.  Every item has the same Attribute with the same name and the same Enumeration.  So there should be no problem applying the Enumerator.  OK?  (I think we agree on this).

Now, assume a heterogeneous collection where some items are as before and some items have no such Attribute and no such Enumeration (in any other attribute).  By definition those Items without the Enumeration can't be part of the subset.  This should be OK (from first principles)

Now, consider a third case, heterogeneous collection with some of the original Items and some others That have the same Enumeration but with a different name.  If we allow that Enumerators are defined by their signature, then the compiler can work out that this other Attribute can be used to select subset Items.

Are you happier with that?

Example, Collection of Items.  Some are Jelly Beans (Attribute: BeanColour:ConfectionColour) others are Liquorice All-Sorts (AllSortColour:ConfectionColour).

We can ask the question get me the green items and get both Jelly Beans and All-Sorts.

Now, most (if not all) languages don't (natively) support this idea.  But we are defining CIM related concepts here.

Besides, to paraphrase the old aphorism:  Define it and they will code.

Paolo

[jeshaw2]

Is it valid to say "The product of an enumeration on a bag is an ordered set"?  Similar to a SQL SELECT DISTINCT query on a database table?

[jeshaw2]

OOPS!  Didn't see your response before I posted my question.

Yes, I'm happy with your explanation on heterogeneous sets.  That's what I thought you were saying.  

[Paolo F Cantoni]

Yes, I'm happy with your explanation on heterogeneous sets.  That's what I thought you were saying.  

OK Jim,

Now, lets look at Collections in general.

What are the features the most basic collection must have?

I've already alluded to two types of collections:
Associative (Maps, Hashes etc) and Non-Associative (Lists, Vectors etc).  

It seems to me that the Collection must have an Iterator.  Indexers and Enumerators are available depending upon the Collection type.

What Features should an Iterator implement?

Paolo

[jeshaw2]

Just a quick note Paolo.  I must leave for work soon.

What are the features the most basic collection must have?

Before I can respond to this question, I need to build a specialization hierarchy of Collection classes, possibly based upon some combination their functionality and type.  Then I can abstract out common features to a generalized Collection class.  I'm exploring the idea that associative collections are a specialization of Sequential (non-associative) collections.

What Features should an Iterator implement?

Again, I see a specialization hierarchy of Iterator classes, paralleling the Collection hierarchy, to be analyzed for abstraction to the  top level of the hierarchy.

A couple of points on Iterators though:

• The iterator should provide protection against mutation of the collection during the traversal.
  
• Each client should have its own copy of the iterator to allow concurrent iterations.
  
• I think the iterators need to be thread safe.
  
• Iterators need to keep track of the iteration state.  (Not sure about this)
  
  Sorry, I gotta run...
  Be back later.
  
  

[Paolo F Cantoni]

[size=13][SNIP][/size]
I need to build a specialization hierarchy of Collection classes, possibly based upon some combination their functionality and type.  Then I can abstract out common features to a generalized Collection class.  I'm exploring the idea that associative collections are a specialization of Sequential (non-associative) collections.[size=13][SNIP][/size]

I'm having difficulty, looking at the list of Collection types from various sources, getting a good handle on the types of Collections.  In particular, which might apply to the CIM and which are more suited to the PIM and PSM or even the code itself.

Perhaps we might gainfully start by defining some named types and their functionality in a coding language neutral way?  We should resist terms like: Constant time random access is not supported or Insertion and removal in the middle take linear time.

I'll kick off with a few...

Vector:   (Non-Associative) Can be traversed in one direction only, Can add and remove from anywhere
List:   (Non-Associative) Can be traversed in both directions, Can add and remove from anywhere
Deque:   (Non-Associative) Can add and remove from either end only
Queue:   (Non-Associative) Can add at start only and remove from end only
Stack:   (Non-Associative) Can add at and remove from start only

Questions:
Traversal of Deque, Queue and Stack?
It would seem that Stack and Queue are specializations of Deque?
I've seen a definition of Deque that allows addition/removal in the middle (if so, how different from List)?
Is Uni- versus Bi-Directional traversal merely a policy to be applied?

Perhaps all we have is a matrix of policies and names to be given to specific combinations of policies?

Paolo

[sargasso]

Watch out Paolo, if you're not careful you'll invent Algol in a minute.  

Dont forget linked lists, and in particular circular lists..  oh and trees as well.

Before y'all think these are implementation level constructs, last year I was involved in building a traffic simulation to check out a couple of business level queing options (single and double section clearances).  Given the nature of the network the traffic had to traverse,  a statically linked list that modelled the network was the best design we could come up with.... had to build the link handling  by hand as I couldn't find any suitable structures in the C# collections libraries.


bruce

[Paolo F Cantoni]

Watch out Paolo, if you're not careful you'll invent Algol in a minute.  

bruce,

You've guessed I'm an old Algol68 hand!  Magic language!  The only mind expanding programming language I every used (except for Eiffel).  You thought, you wrote, it did!  I've been trying to regain that experience since...

Don't forget linked lists, and in particular circular lists..  oh and trees as well.

Before y'all think these are implementation level constructs, last year I was involved in building a traffic simulation to check out a couple of business level queueing options (single and double section clearances).  Given the nature of the network the traffic had to traverse,  a statically linked list that modelled the network was the best design we could come up with.... had to build the link handling  by hand as I couldn't find any suitable structures in the C# collections libraries.
bruce

Point taken...
However,I want to re-iterate my point... The types of Collections in the CIM (Computationally Independent Model) cannot be described n therms of their computational characteristics.  They should only be described in terms of their functionality.

Now as a consequence there may be computational effects, but they are consequences not essentials.

Paolo

[KP]

Deque:   (Non-Associative) Can add and remove from either end only

I've never seen this word before - is it pronounced "deck" and does it behave the same as a deck of cards?

[Paolo F Cantoni]

I've never seen this word before - is it pronounced "deck" and does it behave the same as a deck of cards?

As far as I know, it IS pronounced 'deck'

According to ACRONYM finder Deque stands for Double Ended Queue - which is in accord with the definition I gave.

So, it doesn't behave like a deck of cards...

HTH,
Paolo

[KP]

As far as I know, it IS pronounced 'deck'

According to ACRONYM finder Deque stands for Double Ended Queue - which is in accord with the definition I gave.

So, it doesn't behave like a deck of cards...

HTH,
Paolo

Thanks for that - my new word for the day!

[jeshaw2]

Perhaps all we have is a matrix of policies and names to be given to specific combinations of policies?

I think this is the case!  I start with Non-Associative collections and Associative collections (as a specialization of Non-Associative collections) as a base.  To that, I add the following features:

• Ordering Policy
• Collision Policy
• Enumeration Order Attribute (optional)
• Enumeration Policy
• Priority Policy
• Mutation Policy
• Equivalence function
• Ordering Function

Applying these to the two base collection types, I can generate (dare I say all?) of the other specialized collection types.

I'm hoping that most of the these features may be Interface types to minimize the number of permutations.

I'll kick off with a few...  
Vector:   (Non-Associative) Can be traversed in one direction only, Can add and remove from anywhere
List:   (Non-Associative) Can be traversed in both directions, Can add and remove from anywhere
Deque:   (Non-Associative) Can add and remove from either end only
Queue:   (Non-Associative) Can add at start only and remove from end only
Stack:   (Non-Associative) Can add at and remove from start only

To this list I would add:

• Set
• Ordered Set
• Bag
• Map (Associative) isOrdered=false, isUnique=true
• Multimap (Associative) isOrdered=true, isUnique=false
• Ordered Map (Associative)isOrdered=true, IsUnique=true
  

Some of the other comments related to trees, etc. Seem to be at lower abstraction levels.  Can something be abstracted from them and brought up to this level?

It would seem that Stack and Queue are specializations of Deque?

Yes, It would seem that way, but how would you handle sub setting the Inherited operations?

Is Uni- versus Bi-Directional traversal merely a policy to be applied?

Yes, but applied to the association ends not the collection holonym.

[Paolo F Cantoni]

Jim,

If you agree, I'll create an Excel 2000 spreadsheet to allow us to manage the matrix and load it up to the EA User site.

That way all the thoughts can eventually be put in one place and it will represent the current view (of the two of us at least).

Paolo

PS:  I'll use Excel 2000 since 1) I have it, 2) it seems to be the most widely available.

[jeshaw2]

If you agree, I'll create an Excel 2000 spreadsheet to allow us to manage the matrix and load it up to the EA User site.

Interesting!  A Collections Wiki    I agree.  I have Excel 2003, I think the two file types are the same, but you might consider *.cvs format to allow participation by those with steam-driven (and other alternatively fueled) computers.

Need we a home for Policy & Feature Definition also?

[jeshaw2]

Quote:It would seem that Stack and Queue are specializations of Deque?  
Yes, It would seem that way, but how would you handle sub setting the Inherited operations?

[onFurtherReflection]

Perhaps it is the other way around. Deque seems to have DNA from both Stack and Queue. All three of these are controlled by a Mutation Policy.  A set of specalized interfaces seems appropriate here.

[/onFurtherReflection]