Author Topic: Thoughts about Collections  (Read 10063 times)

Paolo F Cantoni

  • EA Guru
  • *****
  • Posts: 5882
  • Karma: +71/-79
  • Inconsistently correct systems DON'T EXIST!
    • View Profile
Re: Thoughts about Collections
« Reply #15 on: October 24, 2005, 05:09:08 pm »
Quote
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. ;D

Paolo


Inconsistently correct systems DON'T EXIST!
... Therefore, aim for consistency; in the expectation of achieving correctness....
-Semantica-
Helsinki Principle Rules!

jeshaw2

  • EA User
  • **
  • Posts: 701
  • Karma: +0/-0
  • I'm a Singleton, what pattern are you?
    • View Profile
Re: Thoughts about Collections
« Reply #16 on: October 24, 2005, 09:11:29 pm »
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?
Verbal Use Cases aren't worth the paper they are written upon.

jeshaw2

  • EA User
  • **
  • Posts: 701
  • Karma: +0/-0
  • I'm a Singleton, what pattern are you?
    • View Profile
Re: Thoughts about Collections
« Reply #17 on: October 24, 2005, 09:16:24 pm »
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.  :)
Verbal Use Cases aren't worth the paper they are written upon.

Paolo F Cantoni

  • EA Guru
  • *****
  • Posts: 5882
  • Karma: +71/-79
  • Inconsistently correct systems DON'T EXIST!
    • View Profile
Re: Thoughts about Collections
« Reply #18 on: October 25, 2005, 01:32:12 am »
Quote
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

Inconsistently correct systems DON'T EXIST!
... Therefore, aim for consistency; in the expectation of achieving correctness....
-Semantica-
Helsinki Principle Rules!

jeshaw2

  • EA User
  • **
  • Posts: 701
  • Karma: +0/-0
  • I'm a Singleton, what pattern are you?
    • View Profile
Re: Thoughts about Collections
« Reply #19 on: October 25, 2005, 10:18:06 am »
Just a quick note Paolo.  I must leave for work soon.

Quote
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.

Quote
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.

Verbal Use Cases aren't worth the paper they are written upon.

Paolo F Cantoni

  • EA Guru
  • *****
  • Posts: 5882
  • Karma: +71/-79
  • Inconsistently correct systems DON'T EXIST!
    • View Profile
Re: Thoughts about Collections
« Reply #20 on: October 25, 2005, 01:35:22 pm »
Quote
[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
« Last Edit: October 25, 2005, 01:37:45 pm by PaoloFCantoni »
Inconsistently correct systems DON'T EXIST!
... Therefore, aim for consistency; in the expectation of achieving correctness....
-Semantica-
Helsinki Principle Rules!

sargasso

  • EA Practitioner
  • ***
  • Posts: 1406
  • Karma: +1/-2
  • 10 COMFROM 30; 20 HALT; 30 ONSUB(50,90,10)
    • View Profile
Re: Thoughts about Collections
« Reply #21 on: October 25, 2005, 03:25:12 pm »
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
« Last Edit: October 25, 2005, 03:28:05 pm by sargasso »
"It is not so expressed, but what of that?
'Twere good you do so much for charity."

Oh I forgot, we aren't doing him are we.

Paolo F Cantoni

  • EA Guru
  • *****
  • Posts: 5882
  • Karma: +71/-79
  • Inconsistently correct systems DON'T EXIST!
    • View Profile
Re: Thoughts about Collections
« Reply #22 on: October 25, 2005, 03:41:31 pm »
Quote
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! ;D  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... ;)

Quote
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

Inconsistently correct systems DON'T EXIST!
... Therefore, aim for consistency; in the expectation of achieving correctness....
-Semantica-
Helsinki Principle Rules!

KP

  • EA Administrator
  • EA Expert
  • *****
  • Posts: 2436
  • Karma: +29/-2
    • View Profile
Re: Thoughts about Collections
« Reply #23 on: October 25, 2005, 03:59:21 pm »
Quote
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?
The Sparx Team
support@sparxsystems.com

Paolo F Cantoni

  • EA Guru
  • *****
  • Posts: 5882
  • Karma: +71/-79
  • Inconsistently correct systems DON'T EXIST!
    • View Profile
Re: Thoughts about Collections
« Reply #24 on: October 25, 2005, 04:17:39 pm »
Quote
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
« Last Edit: October 25, 2005, 04:18:16 pm by PaoloFCantoni »
Inconsistently correct systems DON'T EXIST!
... Therefore, aim for consistency; in the expectation of achieving correctness....
-Semantica-
Helsinki Principle Rules!

KP

  • EA Administrator
  • EA Expert
  • *****
  • Posts: 2436
  • Karma: +29/-2
    • View Profile
Re: Thoughts about Collections
« Reply #25 on: October 25, 2005, 04:21:49 pm »
Quote
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!
The Sparx Team
support@sparxsystems.com

jeshaw2

  • EA User
  • **
  • Posts: 701
  • Karma: +0/-0
  • I'm a Singleton, what pattern are you?
    • View Profile
Re: Thoughts about Collections
« Reply #26 on: October 25, 2005, 11:42:26 pm »
Quote
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.

Quote
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?

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?

Quote
Is Uni- versus Bi-Directional traversal merely a policy to be applied?
Yes, but applied to the association ends not the collection holonym.
Verbal Use Cases aren't worth the paper they are written upon.

Paolo F Cantoni

  • EA Guru
  • *****
  • Posts: 5882
  • Karma: +71/-79
  • Inconsistently correct systems DON'T EXIST!
    • View Profile
Re: Thoughts about Collections
« Reply #27 on: October 26, 2005, 12:08:05 am »
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.
Inconsistently correct systems DON'T EXIST!
... Therefore, aim for consistency; in the expectation of achieving correctness....
-Semantica-
Helsinki Principle Rules!

jeshaw2

  • EA User
  • **
  • Posts: 701
  • Karma: +0/-0
  • I'm a Singleton, what pattern are you?
    • View Profile
Re: Thoughts about Collections
« Reply #28 on: October 26, 2005, 04:39:43 am »
Quote
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. ;D

Need we a home for Policy & Feature Definition also?
Verbal Use Cases aren't worth the paper they are written upon.

jeshaw2

  • EA User
  • **
  • Posts: 701
  • Karma: +0/-0
  • I'm a Singleton, what pattern are you?
    • View Profile
Re: Thoughts about Collections
« Reply #29 on: October 26, 2005, 04:54:09 am »
Quote
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]
« Last Edit: October 26, 2005, 04:54:58 am by jeshaw2 »
Verbal Use Cases aren't worth the paper they are written upon.