Re: C++ templates?

The Q signature is a module signature, and ListQueue and TreeQueue are the concrete implementations. In C++ terms, Q would be a fully abstract base class, and ListQueue and TreeQueue would be the distinct roots of concrete implementation hierarchies that each have Q as a superclass.

ListQueue and TreeQueue would also be template classes, with the template parameter controlling the element type. There would also have to be a method to compare different elements, either as part of the Queue implementation or the element implementation. (This is what the functor argument Elt : ORD means; it says that elements have to have a comparison operation.)

I'd appreciate it if you could post your C++ translations. The last time I wrote any C++ was ~5 years ago, so while I can read it I can't write it anymore. :)

Actually, I suspect that STL is just such a translation. map versus set versus multimap is about the same as your queue implementations.

>>>>>>>
There would also have to be a method to compare different elements, either as part of the Queue implementation or the element implementation. (This is what the functor argument Elt : ORD means; it says that elements have to have a comparison operation.)
<<<<<<<<

And therein lies an error. The comparison does not have to be a member in either queue or element. It can be another template parameter.

So, you'd have something like

template <class Element>
class less
{
/*operator () is used for lots of things in STL, ini this context it's just a comparison function */
bool operator()(const Element &e1, const Element &e2) {
return e1 < e2;
}
}

template <class Element>
class more
bool operator()(const Element &e1, const Element &e2) {
return e1 > e2;
}
}

class customCompare
{
bool operator()(const MyVeryOwnType &e1, const MyVeryOwnType &e2) {
return e1.field1 < e2.field1;
}
}

template <class Element, class Comparison>
class set
{

set() {};

/* use this constructor when comparison depends on external data (almost never) */
set(Comparison &comp) : less(comp) {}

/* here in the set I can use less(e1, e2) (which is actually less.operator()(e1, e2) */

Comparison less;
}

typedef set <int, less<int> > ascendingSet

typedef set <int, more<int> > descendingSet

typedef set <MyVeryOwnType, customCompare> customSortedSet

Welcome to IWETHEY!