New release of the C Containers Library (CCL)

[jacob navia]

Hi

The new release contains a significant innovation: generic containers.

Generic containers are like virtual classes in the sense that you have
no creation function, i.e. you can never create a generic container,
only a specific kind of container (list, array, hash table, etc)

The iGenericContainer interface allows to treat all containers for
specific general functions the same. For instance

iGenericContainer.GetSize(someContainer);

will always return a size_t with the number of elements in the
container, no matter which container it is that is passed as argument.

The general container interface has no functions to add an element
however, since the syntax for sequential or associative elements
differ.

A further classification then, allows for those 2 branches:

Sequential containers (lists, arrays, string-arrays, bitststrings, etc)
and associative containers (hash-tables, trees) share with the generic
containers all the generic interface, adding some functions of their own.

This allows for writing of powerful completely general functions like
this "append" function (that is part of the generic sequential
containers interface):

static int Append(SequentialContainer *g1,SequentialContainer *g2)
{
int r;
void *element;
Iterator *it1 = newIterator((GenericContainer *)g2);
for (element = it1->GetFirst(it1);
element != NULL;
element = it1->GetNext(it1)) {
r = iGenericContainer.Add(g1,element);
if (r <=0) {
return r;
}

}
return 1;
}

This function will append to the first container the second one, no
matter what the exact types of g1 or g2 are.

Note that the iterators are part of the generic interface, not the
sequential one.

All of this is completely extensible and will work with ANY future
container that agrees to respect the defined protocol.

jacob

 

[MartinBroadhurst]

Hi

The new release contains a significant innovation: generic containers.

Generic containers are like virtual classes in the sense that you have
no creation function, i.e. you can never create a generic container,
only a specific kind of container (list, array, hash table, etc)

The iGenericContainer interface allows to treat all containers for
specific general functions the same. For instance

iGenericContainer.GetSize(someContainer);

will always return a size_t with the number of elements in the
container, no matter which container it is that is passed as argument.

The general container interface has no functions to add an element
however, since the syntax for sequential or associative elements
differ.

A further classification then, allows for those 2 branches:

Sequential containers (lists, arrays, string-arrays, bitststrings, etc)
and associative containers (hash-tables, trees) share with the generic
containers all the generic interface, adding some functions of their own.

This allows for writing of powerful completely general functions like
this "append" function (that is part of the generic sequential
containers interface):

static int Append(SequentialContainer *g1,SequentialContainer *g2)
{
         int r;
         void *element;
         Iterator *it1 = newIterator((GenericContainer *)g2);
         for (element = it1->GetFirst(it1);
                    element != NULL;
                    element = it1->GetNext(it1)) {
                 r = iGenericContainer.Add(g1,element);
                 if (r <=0) {
                         return r;
                 }

         }
         return 1;

}

This function will append to the first container the second one, no
matter what the exact types of g1 or g2 are.

Note that the iterators are part of the generic interface, not the
sequential one.

All of this is completely extensible and will work with ANY future
container that agrees to respect the defined protocol.

jacob

Surely Append would be more general, and more consise, it it took an
Iterator * as its first argument rather than a SequentialContainer *?

Martin

 

[MartinBroadhurst]

Surely Append would be more general, and more consise, it it took an
Iterator * as its first argument rather than a SequentialContainer *?

Martin

Sorry, I meant the *second* argument.

Martin

 

[Anders Koeln]

<snip>

Martin

Please do not reply to spammers. Thank You.

 

[BartC]

The new release contains a significant innovation: generic containers.

This allows for writing of powerful completely general functions like
this "append" function (that is part of the generic sequential containers
interface):

static int Append(SequentialContainer *g1,SequentialContainer *g2)
{
int r;
void *element;
Iterator *it1 = newIterator((GenericContainer *)g2);
for (element = it1->GetFirst(it1);
element != NULL;
element = it1->GetNext(it1)) {
r = iGenericContainer.Add(g1,element);
if (r <=0) {
return r;
}

}
return 1;
}

That looks more like a 'Concatenate' function.

'Append' would add the second argument as a single extra element at the end
of g1.

This function will append to the first container the second one, no matter
what the exact types of g1 or g2 are.

Do g1 and g2 have to be compatible types (in terms of what elements they
contain)?

 

[Anders Koeln]

Please do not reply to spammers. Thank You.

 

[Keith Thompson]

Please do not reply to spammers. Thank You.

He didn't. Please do not abuse the word "spammers" by applying it
to people who clearly are not spammers. Thank you.

 

[MartinBroadhurst]

He didn't.  Please do not abuse the word "spammers" by applying it
to people who clearly are not spammers.  Thank you.

There's something a bit fishy about "Anders Koeln". He doesn't appear
to be human. He may even be a fish. I shouldn't worry about what he
says.

Martin

 

[Seebs]

Please do not reply to spammers. Thank You.

Jacob Navia is not a spammer. He's a regular participant and people have
previously talked about the design of this library here.

-s

 

[Kenny McCormack]

Please do not reply to spammers. Thank You.

We should spend all of our time telling each other who to respond to and
who not to. Good use of our time.

--
"The anti-regulation business ethos is based on the charmingly naive notion
that people will not do unspeakable things for money." - Dana Carpender

Quoted by Paul Ciszek (pciszek at panix dot com). But what I want to know
is why is this diet/low-carb food author doing making pithy political/economic
statements?

Nevertheless, the above quote is dead-on, because, the thing is - business
in one breath tells us they don't need to be regulated (which is to say:
that they can morally self-regulate), then in the next breath tells us that
corporations are amoral entities which have no obligations to anyone except
their officers and shareholders, then in the next breath they tell us they
don't need to be regulated (that they can morally self-regulate) ...

 

[jacob navia]

Le 31/10/10 22:01, MartinBroadhurst a écrit :

Hi

[snip]

static int Append(SequentialContainer *g1,SequentialContainer *g2)
{
int r;
void *element;
Iterator *it1 = newIterator((GenericContainer *)g2);
for (element = it1->GetFirst(it1);
element != NULL;
element = it1->GetNext(it1)) {
r = iGenericContainer.Add(g1,element);
if (r<=0) {
return r;
}

}
return 1;

}

This function will append to the first container the second one, no
matter what the exact types of g1 or g2 are.

Note that the iterators are part of the generic interface, not the
sequential one.

All of this is completely extensible and will work with ANY future
container that agrees to respect the defined protocol.

jacob

Surely Append would be more general, and more consise, it it took an
Iterator * as its first argument rather than a SequentialContainer *?

Martin

You are right, I just did not think about that possibility.

Sorry about the delay answering but for *some* reason, all answers
appeared today (Nov, 1st) in my news reader.

 

[jacob navia]

Le 31/10/10 22:48, BartC a écrit :

That looks more like a 'Concatenate' function.

'Append' would add the second argument as a single extra element at the
end of g1.

I run a search about append in /usr/share/man and the only place where
it is used is in curl_slist_append, that adds a string to a list of
strings. That supports your idea.

The other is that "strcat" (probably from string conCATenate) does the
equivalent for strings

Do g1 and g2 have to be compatible types (in terms of what elements they
contain)?

True, I did not test for that .

jacob

P.S.
Sorry about the delay answering but for *some* reason, all answers
appeared today (Nov, 1st) in my news reader.

 

[Malcolm McLean]

He didn't.  Please do not abuse the word "spammers" by applying it
to people who clearly are not spammers.  Thank you.

If you want to see real spam, the default Google interface to this
group is full of it. Shift to topic list view, and the legitimate
threads come to the top and most of the spam drops off. (That's one
reason why replying to spam is a bad idea). However, as you say, Jacob
is clearly not a spammer.

 

[Malcolm McLean]

The iGenericContainer interface allows to treat all containers for
specific general functions the same. For instance

iGenericContainer.GetSize(someContainer);

Object orientation. It's seductive, but it often turns out to be a
trap.

 

[jacob navia]

Le 01/11/10 11:26, Malcolm McLean a écrit :

Object orientation. It's seductive, but it often turns out to be a
trap.

In this context it means that a pointer to a container can be treated
(using a cast) as a pointer to an abstract entity that doesn't really
exist called "Generic container".

This entity has some functionality that is universally present in all
containers the library is going to cover:

o The number of elements a container holds
o The size of those
o ... and several other stuff like having an iterator, etc.

This allows to write algorithms that use ANY kind of container without
bothering into any details. This is posible in the more concrete
"classes" like SequentialContainer and AssociativeContainers.

Are those "classes" derived, in the old sense of a "is a"?

Yes, both associative and sequential containers ARE containers...

The implementation is very simple. All VTables start with the same
functions at the same place, what allows to call a generic container's
'GetSize' function without any

switch (containertype)
case TABLE:
...
case LIST:


etc.

What is more important is that ANY new container that is introduced by
some future user to extend this library will automatically work if they
respect this protocol, and all code that uses generic sequential
containers for instance will automatically work with any new container.

I do not know if you can do this in C++. In Objective C you can.

jacob

 

[Malcolm McLean]

I do not know if you can do this in C++. In Objective C you can.

In C++ you make "Container" a virtual base class, that is to say, you
give it pure virtual functions set to " = 0 ". The functions must be
overridden in derived classes that are instantiated.
What C++ forgot and Java remembered was the "interface". You can
achieve nearly the same thing with multiple inheritance, but that
leads into all sorts of difficulties.

 

[jacob navia]

Le 01/11/10 11:49, Malcolm McLean a écrit :

In C++ you make "Container" a virtual base class, that is to say, you
give it pure virtual functions set to " = 0 ". The functions must be
overridden in derived classes that are instantiated.

Interesting...

In my implementation, the generic functions aren't virtual really
since they call the container specific function. This costs an
indirection and an indirect function call in C.

I would be interested to know what the cost of virtual base classes is
in C++ (if any)


For instance to call the generic function "newIterator":

Iterator *newIterator(GenericContainer *gen)
{
return gen->VTable->newIterator(gen);
}

You see?

If you write
Iterator *n = iList.newIterator(container);

You call directly the right function, but then you have to know
that your container is a list.

It costs a function call + indirection + indirect function call.

I haven't found any way to avoid that extra call.

 

[MartinBroadhurst]

In C++ you make "Container" a virtual base class, that is to say, you
give it pure virtual functions set to " = 0 ".

No, a virtual base class is one that can be inherited more than once
without duplication of members.
You are talking about an abstract base class.

What C++ forgot and Java remembered was the "interface". You can
achieve nearly the same thing with multiple inheritance, but that
leads into all sorts of difficulties.

No it doesn't because you are inheriting from abstract base classes.
The problems with multiple inheritance manifest themselves when you
inherit from multiple concrete classes - hence the need for virtual
base classes.

Martin

 

[jacob navia]

Le 01/11/10 12:12, MartinBroadhurst a écrit :

No, a virtual base class is one that can be inherited more than once
without duplication of members.
You are talking about an abstract base class.

But in C++ you cannot use an abstract class as a parameter type, a
function return type, or the type of an explicit conversion

In my implementation you CAN use a generic container as a parameter or a
result of a function of course...

The interface proposed doesn't allow for a creation function: you can't
create an object "GenericContainer", but once you create any container
it can be used as a generic container anywhere.

 

[MartinBroadhurst]

But in C++ you cannot use an abstract class as a parameter type, a
function return type, or the type of an explicit conversion

You would use a *pointer* to an abstract base class, just as we're
using pointers here in C.

Martin