www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.dtl - container vs collection

reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
Here's a fun naming problem: should the "basic container interface" be 
called Container or Collection? I'm used to Collection from Java but I bet 
they used the name Collection because Container was taken by AWT to mean a 
Component that contains other Components. In D we don't have any such 
conflict so I'm seriously thinking of using Container instead of Collection. 
Thoughts?

I'm also thinking of using Enumeration (ala Java) for the interface for 
opApply and IndexedEnumeration for opApply that takes keys as well as 
values. Currently I'm calling those interfaces Sequences. Thoughts on those 
names would be appreciated, too.

So so summarize here a set of names I'm looking at:
interface Enumeration(Value) {
  int opApply( int delegate(inout Value value) dg);
}
interface IndexedEnumeration(Index,Value) : Enumeration!(Value) {
  alias Enumeration!(Value).opApply opApply;
  int opApply( int delegate(inout Index index, inout Value value) dg);
}
interface Container(Index,Value) : IndexedEnumeration!(Index,Value) {
  bool isEmpty();
  void clear();
  Container dup();
  size_t length();
  Value* lookup(Index index);
  Value opIndex(Index index);
  void opIndexAssign(Value val, Index index); // undefined if not present
  Value extract(Index index);
  void remove(Index index);
  Index[] keys();
  Value[] values();
}
interface OrderedContainer(Index,Value) : Container!(Index,Value) {
  OrderedContainer opSlice(Index a, Index b);
  OrderedContainer opSlice(OrderedContainer a, OrderedContainer b);
  OrderedContainer head();
  OrderedContainer tail();
  void next(int n = 1, int end = 0);
  int opApply(int delegate(inout OrderedContainer itr) dg);
  alias Container!(Index,Value).opApply opApply; // overload
  void remove(OrderedContainer x);
  alias Container!(Index,Value).remove remove; // overload
}
interface ListContainer(Value) : OrderedContainer!(size_t,Value) {
  void add(...);
  ListContainer opCatAssign(Value v);
  ListContainer opCat(Value v);
  ListContainer opCatAssign(OrderedContainer!(size_t,Value) v);
  ListContainer opCat(OrderedContainer!(size_t,Value) v);
  ListContainer opCat_r(Value v);
  void addTail(Value v);
  void addTail(OrderedContainer!(size_t,Value) v);
  void addHead(Value v);
  void addHead(OrderedContainer!(size_t,Value) v);
  Value removeHead();
  Value removeTail();
  void addBefore(OrderedContainer!(size_t,Value) subv, 
OrderedContainer!(size_t,Value) v);
  void addAfter(OrderedContainer!(size_t,Value) subv, 
OrderedContainer!(size_t,Value) v);
  ListContainer reverse();
}
May 09 2005
next sibling parent reply John Demme <me teqdruid.com> writes:
The only problem that I see is your dup method.  It returns Container.
What would probably be preferable is to define it for more specific
interfaces, so that casts are less likely.  That is, if I want this to
work w/o casting:
Set s = new HashSet();
Set t = s.dup();

A child class cannot override the return type.  The following code (with
DMD 0.120)
module i;
interface A {
  A dup();
}
interface B:A {
  B dup();
}
class C : B {
  B dup() {
    return null;
  }
}
void main() {
}

produces this:
$ dmd i.d
i.d(11): class i.C interface function B.dup isn't implemented

It sucks.  I've bitched about it before, and still don't understand why
it can't work, just that it doesn't.

John Demme

On Mon, 2005-05-09 at 18:54 -0400, Ben Hinkle wrote:
 Here's a fun naming problem: should the "basic container interface" be 
 called Container or Collection? I'm used to Collection from Java but I bet 
 they used the name Collection because Container was taken by AWT to mean a 
 Component that contains other Components. In D we don't have any such 
 conflict so I'm seriously thinking of using Container instead of Collection. 
 Thoughts?
 
 I'm also thinking of using Enumeration (ala Java) for the interface for 
 opApply and IndexedEnumeration for opApply that takes keys as well as 
 values. Currently I'm calling those interfaces Sequences. Thoughts on those 
 names would be appreciated, too.
 
 So so summarize here a set of names I'm looking at:
 interface Enumeration(Value) {
   int opApply( int delegate(inout Value value) dg);
 }
 interface IndexedEnumeration(Index,Value) : Enumeration!(Value) {
   alias Enumeration!(Value).opApply opApply;
   int opApply( int delegate(inout Index index, inout Value value) dg);
 }
 interface Container(Index,Value) : IndexedEnumeration!(Index,Value) {
   bool isEmpty();
   void clear();
   Container dup();
   size_t length();
   Value* lookup(Index index);
   Value opIndex(Index index);
   void opIndexAssign(Value val, Index index); // undefined if not present
   Value extract(Index index);
   void remove(Index index);
   Index[] keys();
   Value[] values();
 }
 interface OrderedContainer(Index,Value) : Container!(Index,Value) {
   OrderedContainer opSlice(Index a, Index b);
   OrderedContainer opSlice(OrderedContainer a, OrderedContainer b);
   OrderedContainer head();
   OrderedContainer tail();
   void next(int n = 1, int end = 0);
   int opApply(int delegate(inout OrderedContainer itr) dg);
   alias Container!(Index,Value).opApply opApply; // overload
   void remove(OrderedContainer x);
   alias Container!(Index,Value).remove remove; // overload
 }
 interface ListContainer(Value) : OrderedContainer!(size_t,Value) {
   void add(...);
   ListContainer opCatAssign(Value v);
   ListContainer opCat(Value v);
   ListContainer opCatAssign(OrderedContainer!(size_t,Value) v);
   ListContainer opCat(OrderedContainer!(size_t,Value) v);
   ListContainer opCat_r(Value v);
   void addTail(Value v);
   void addTail(OrderedContainer!(size_t,Value) v);
   void addHead(Value v);
   void addHead(OrderedContainer!(size_t,Value) v);
   Value removeHead();
   Value removeTail();
   void addBefore(OrderedContainer!(size_t,Value) subv, 
 OrderedContainer!(size_t,Value) v);
   void addAfter(OrderedContainer!(size_t,Value) subv, 
 OrderedContainer!(size_t,Value) v);
   ListContainer reverse();
 }
 
 
 

May 09 2005
next sibling parent "Ben Hinkle" <ben.hinkle gmail.com> writes:
"John Demme" <me teqdruid.com> wrote in message 
news:1115681750.17438.9.camel localhost.localdomain...
 The only problem that I see is your dup method.  It returns Container.
 What would probably be preferable is to define it for more specific
 interfaces, so that casts are less likely.  That is, if I want this to
 work w/o casting:
 Set s = new HashSet();
 Set t = s.dup();

Correct. This is the downside of interfaces. When I took the unittests for the structs and converted them to classes I had to change two things: the "new CList" etc and the dup casting. Everything else just worked. One solution to avoid the cast is to use the dup on the implementation: Set t = new HashSet(s.impl.dup); since my classes have an "impl" member that is the struct that actually implements the container. In fact the definition of HashSet.dup (or the equivalent for my containers) is exactly "return new <class>(impl.dup)". Most functions in the classes are a light wrapper around the struct implementations (together with some casting to get to the impl member).
 A child class cannot override the return type.  The following code (with
 DMD 0.120)
 module i;
 interface A {
  A dup();
 }
 interface B:A {
  B dup();
 }
 class C : B {
  B dup() {
    return null;
  }
 }
 void main() {
 }

 produces this:
 $ dmd i.d
 i.d(11): class i.C interface function B.dup isn't implemented

 It sucks.  I've bitched about it before, and still don't understand why
 it can't work, just that it doesn't.

I don't really know but I'm guessing the reason is due to the following. When an object is cast to an interface the "this" pointer is adjusted by an offset specific to the class and interface. Two different interfaces have two different offsets. So if dup() returns an interface A and then you try to return an interface B the offset for A and B are different and so there is no way to implicitly consider every B as also an A. For classes a subclass does not have any offset so it becomes possible to consider every "this" pointer for a class to also be "this" for the super-class.
May 09 2005
prev sibling next sibling parent "Ben Hinkle" <bhinkle mathworks.com> writes:
"John Demme" <me teqdruid.com> wrote in message 
news:1115681750.17438.9.camel localhost.localdomain...
 The only problem that I see is your dup method.  It returns Container.
 What would probably be preferable is to define it for more specific
 interfaces, so that casts are less likely.

I've been getting annoyed with the casting, too, actually. So I've been experimenting with smushing the interfaces into one and defining aliases for those "sub-interfaces" that implement more and more of the super-interface. So basically most of the Container interface is optional, which isn't very OO but removed lots of casts as long as you declare your variables as one of the interfaces. interface Enumeration(Value) { int opApply( int delegate(inout Value value) dg); } interface IndexedEnumeration(Index,Value) : Enumeration!(Value) { alias Enumeration!(Value).opApply opApply; int opApply( int delegate(inout Index index, inout Value value) dg); } interface Container(Index,Value) : IndexedEnumeration!(Index,Value) { bool isEmpty(); void clear(); Container dup(); size_t length(); Value* lookup(Index index); Value opIndex(Index index); void opIndexAssign(Value val, Index index); // undefined if not present Value extract(Index index); void remove(Index index); Index[] keys(); Value[] values(); void remove(Container x); void add(...); // OrderedContainer members Container opSlice(Index a, Index b); //optional Container opSlice(Container a, Container b); //optional Container head(); //optional Container tail(); //optional Index key(); //optional Value value(); //optional void next(int n = 1, int end = 0); //optional int opApply(int delegate(inout Container itr) dg); //optional // List members Container opCatAssign(Value v); //optional Container opCat(Value v); //optional Container opCatAssign(Container v); //optional Container opCat(Container v); //optional Container opCat_r(Value v); //optional void addTail(Value v); //optional void addTail(Container v); //optional void addHead(Value v); //optional void addHead(Container v); //optional Value removeHead(); //optional Value removeTail(); //optional void addBefore(Container subv, Container v); //optional void addAfter(Container subv, Container v); //optional Container reverse(); //optional } alias Container OrderedContainer; template IList(Value) { alias Container!(size_t,Value) IList; } template IStack(Value) { alias Container!(size_t,Value) IStack; } template IQueue(Value) { alias Container!(size_t,Value) IQueue; } template AssocContainer(Key,Value) { alias Container!(Key,Value) AssocContainer; }
May 11 2005
prev sibling parent "Ben Hinkle" <bhinkle mathworks.com> writes:
"John Demme" <me teqdruid.com> wrote in message 
news:1115681750.17438.9.camel localhost.localdomain...
 The only problem that I see is your dup method.  It returns Container.
 What would probably be preferable is to define it for more specific
 interfaces, so that casts are less likely.

It just occurred to me that covariance would work with abstract classes instead of interfaces. Making Container and friends abstract classes would lose some of the flexibility of interfaces but I can't really imagine a container that would implement "interface Container" that would also be able to subclass "abstract class Container". I'll try that out before going ahead with the "smushed interface" API. The smushed API should be a last resort.
May 11 2005
prev sibling next sibling parent reply Derek Parnell <derek psych.ward> writes:
On Mon, 9 May 2005 18:54:50 -0400, Ben Hinkle wrote:

 Here's a fun naming problem: should the "basic container interface" be 
 called Container or Collection? 

Can such a thing be empty? If so, then I'd use Container. An empty collection is an oxymoron, because if its empty it is not a collection of anything. However, if it can never be empty, then Collection is probably a better term. -- Derek Parnell Melbourne, Australia 10/05/2005 9:44:15 AM
May 09 2005
parent "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Derek Parnell" <derek psych.ward> wrote in message 
news:1k98whbt5s248$.8uyoosdg6m2.dlg 40tude.net...
 On Mon, 9 May 2005 18:54:50 -0400, Ben Hinkle wrote:

 Here's a fun naming problem: should the "basic container interface" be
 called Container or Collection?

Can such a thing be empty? If so, then I'd use Container. An empty collection is an oxymoron, because if its empty it is not a collection of anything. However, if it can never be empty, then Collection is probably a better term.

They can be empty, so that would be an argument for Container.
May 09 2005
prev sibling next sibling parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
IMHO, Container is a bit different than Collection

Container - contains.
Collection - holds.

Containtment presumes 1-to-n relationship . Collection does not have such
limitation - the same element can participate in different collections.

Containment frequently have geometrical/physical meaning (at least in GUI).
Element can be placed in container and referenced in many collections.

IMHO, as usual.

And is it possible to rename ArrayList to something different?
It is an oxymoron, isn't it?

Andrew.



"Ben Hinkle" <ben.hinkle gmail.com> wrote in message 
news:d5opnt$21m$1 digitaldaemon.com...
 Here's a fun naming problem: should the "basic container interface" be 
 called Container or Collection? I'm used to Collection from Java but I bet 
 they used the name Collection because Container was taken by AWT to mean a 
 Component that contains other Components. In D we don't have any such 
 conflict so I'm seriously thinking of using Container instead of 
 Collection. Thoughts?

 I'm also thinking of using Enumeration (ala Java) for the interface for 
 opApply and IndexedEnumeration for opApply that takes keys as well as 
 values. Currently I'm calling those interfaces Sequences. Thoughts on 
 those names would be appreciated, too.

 So so summarize here a set of names I'm looking at:
 interface Enumeration(Value) {
  int opApply( int delegate(inout Value value) dg);
 }
 interface IndexedEnumeration(Index,Value) : Enumeration!(Value) {
  alias Enumeration!(Value).opApply opApply;
  int opApply( int delegate(inout Index index, inout Value value) dg);
 }
 interface Container(Index,Value) : IndexedEnumeration!(Index,Value) {
  bool isEmpty();
  void clear();
  Container dup();
  size_t length();
  Value* lookup(Index index);
  Value opIndex(Index index);
  void opIndexAssign(Value val, Index index); // undefined if not present
  Value extract(Index index);
  void remove(Index index);
  Index[] keys();
  Value[] values();
 }
 interface OrderedContainer(Index,Value) : Container!(Index,Value) {
  OrderedContainer opSlice(Index a, Index b);
  OrderedContainer opSlice(OrderedContainer a, OrderedContainer b);
  OrderedContainer head();
  OrderedContainer tail();
  void next(int n = 1, int end = 0);
  int opApply(int delegate(inout OrderedContainer itr) dg);
  alias Container!(Index,Value).opApply opApply; // overload
  void remove(OrderedContainer x);
  alias Container!(Index,Value).remove remove; // overload
 }
 interface ListContainer(Value) : OrderedContainer!(size_t,Value) {
  void add(...);
  ListContainer opCatAssign(Value v);
  ListContainer opCat(Value v);
  ListContainer opCatAssign(OrderedContainer!(size_t,Value) v);
  ListContainer opCat(OrderedContainer!(size_t,Value) v);
  ListContainer opCat_r(Value v);
  void addTail(Value v);
  void addTail(OrderedContainer!(size_t,Value) v);
  void addHead(Value v);
  void addHead(OrderedContainer!(size_t,Value) v);
  Value removeHead();
  Value removeTail();
  void addBefore(OrderedContainer!(size_t,Value) subv, 
 OrderedContainer!(size_t,Value) v);
  void addAfter(OrderedContainer!(size_t,Value) subv, 
 OrderedContainer!(size_t,Value) v);
  ListContainer reverse();
 }


 

May 09 2005
next sibling parent Derek Parnell <derek psych.ward> writes:
On Mon, 9 May 2005 22:47:28 -0700, Andrew Fedoniouk wrote:


[snip]
 
 And is it possible to rename ArrayList to something different?
 It is an oxymoron, isn't it?

No, it's a tautology - sort of ... ;-) -- Derek Melbourne, Australia 10/05/2005 4:21:44 PM
May 09 2005
prev sibling parent "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Andrew Fedoniouk" <news terrainformatica.com> wrote in message 
news:d5phpo$esl$1 digitaldaemon.com...
 IMHO, Container is a bit different than Collection

 Container - contains.
 Collection - holds.

 Containtment presumes 1-to-n relationship . Collection does not have such
 limitation - the same element can participate in different collections.

 Containment frequently have geometrical/physical meaning (at least in 
 GUI).
 Element can be placed in container and referenced in many collections.

ok - it sounds like a vote for Collection
 IMHO, as usual.

 And is it possible to rename ArrayList to something different?
 It is an oxymoron, isn't it?

The idea is that it is a list backed by an array. Calling it "Array" wouldn't distinguish it from builtin arrays and calling it "List" would conflict with calling linked-list "List". Calling it "Vector" is an option to mimic C++/Java but to me (my silly math background) a Vector is a point in space to be used in a math context. Sure an instance of an array can be considered a point in some huge space of all possible memory contents but so can any other data structure. Plus the name ArrayList fits well with ArrayHeap (a heap backed by an array) and the aliases ArrayQueue and ArrayStack.
May 10 2005
prev sibling next sibling parent Dejan Lekic <leka entropy.tmok.com> writes:
+1 for Container . :)

-- 
...........
Dejan Lekic
  http://dejan.lekic.org
  
May 12 2005
prev sibling parent Benji Smith <dlanguage xxagg.com> writes:
I vote for Collection.

To me, a Container is a GUI-oriented concept.

But I suppose I could live with either.

--BenjiSmith
May 12 2005