Digital Mars - digitalmars.D.dtl - container vs collection

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → "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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → "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

↑ ↓ ← → "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