I haven't thought about that yet, besides that it should be something with either a "`" or a "_" first (for the lfuns, that is). ADT.set_order and ADT.get_order seems like reasonable names for the global functions, and then the lfuns would be _set_order and _get_order. Would that do?
The ordering function is a less-than operation and not a three-way comparator (i.e. like strcmp(3)). My reasons for that are:
o It's simpler to make a less-than function. o It's actually not that often one can use the extra information given by a three-way comparator to save calls, at least in binary trees. o It can be slightly less work to do a less-than operation. o The issue of equality is not connected to the order; in a three-way comparator it's easier to make the mistake that it should return 0 only when the operands are equal, and not when they are orderwise unrelated (i.e. the order is partial).
I was thinking about the name _set_comparator or _set_orderer but that was for a 3-way comparator, I should probably call a less-than simply _set_less_than then it's quite obvious from the name what the function is expected to do. A less-than should likely be enough I'll try to dream up a scenario where it wouldn't be.
Not the algorithm itself, only the functions it needs. The algorithms are inherently dependent on the properties of the collections they can work with, and those properties are more than this. I believe that the need by an algorithm for certain functions is an accurate way of expressing which properties it needs(*). Since all the functions are adequately abstracted and don't touch on the implementations in improper ways, it's also an abstract way.
In this view, you're saying that you wish to oversimplify the interface just to be able to make a simple rule that an algorithm that work on one collection will work on all (or on one of a few subsets). The backside is that you then also completely rule out both algorithms and types of collections that can be very useful on various subsets of each other.
Note that you can exploit the looks-like philosophy of the Pike type system to accurately check if a certain collection fits a certain algorithm, since it checks identifier by identifier that the class of the actual argument is compatible with the class of the formal argument.
I still believe it's better to have a few relatively limited interfaces that include the 90% most used types instead of having a lot that include 100%. Otherwise it will end up in a vast number of different types that only works with a few algorithms each because the one who made them just had a those algorithms in mind when the type was done. But you're right that the current way to categorise the ADTs might have been totally wrong and may be a better way to try to look at possible algorithms and try to see what they need and make a few interfaces, one for each type of algorithm, just try to keep it down to four or five interfaces, ten maximum. Still keep the collection, set, map and the others, but declaring most of the methods optional and put the restriction in the interfaces. Let try it out and see what it result in.
/ Peta, jo det är jag
Previous text:
2002-11-13 02:46: Subject: More about ADTs
No I think I keep it as it is, then you have the possibility to insert and replace if exist with '[]= and insert but do not replace with insert. /.../
That's a valid point. Don't really know when the second variety would be useful, but still.
and by returning the value belonging to the key you can make a choice if you want to replace the value or not.
The return value should then be UNDEFINED and not 0 if the insert is successful.
(Besides, global functions for setting and getting the `< function is necessary in the new multisets, so these will probably be candidates for lfuns too.)
What is the name and syntax you have planned for them?
I haven't thought about that yet, besides that it should be something with either a "`" or a "_" first (for the lfuns, that is). ADT.set_order and ADT.get_order seems like reasonable names for the global functions, and then the lfuns would be _set_order and _get_order. Would that do?
The ordering function is a less-than operation and not a three-way comparator (i.e. like strcmp(3)). My reasons for that are:
o It's simpler to make a less-than function. o It's actually not that often one can use the extra information given by a three-way comparator to save calls, at least in binary trees. o It can be slightly less work to do a less-than operation. o The issue of equality is not connected to the order; in a three-way comparator it's easier to make the mistake that it should return 0 only when the operands are equal, and not when they are orderwise unrelated (i.e. the order is partial).
With "if the there hasn't been any changes in the collection", I did not mean that the iterator would not work, I mean that the iterator will not traverse the elements in the same order.
Yes, well, you stated a premise that an iterator on both ordered and unordered collections should be able to fulfill. I wanted to point out that additional conditions can be added to an iterator on an ordered collection.
The main goal I had in mind when creating the collection interfaces was that you could write an algorithm that take a collection and then later reuse it with any other collection. By declaring a lot of methods optional this will spoil the abstractness of the whole thing because then you has to know the implementation of the algorithm before you know if your collection will work anyway.
Not the algorithm itself, only the functions it needs. The algorithms are inherently dependent on the properties of the collections they can work with, and those properties are more than this. I believe that the need by an algorithm for certain functions is an accurate way of expressing which properties it needs(*). Since all the functions are adequately abstracted and don't touch on the implementations in improper ways, it's also an abstract way.
In this view, you're saying that you wish to oversimplify the interface just to be able to make a simple rule that an algorithm that work on one collection will work on all (or on one of a few subsets). The backside is that you then also completely rule out both algorithms and types of collections that can be very useful on various subsets of each other.
Note that you can exploit the looks-like philosophy of the Pike type system to accurately check if a certain collection fits a certain algorithm, since it checks identifier by identifier that the class of the actual argument is compatible with the class of the formal argument.
*) In some cases the same property might be expressed through several functions. Then it's of course not appropriate for a collection implementation to arbitrarily define some of them and leaving out others. Such dependencies should also be part of the documented interface, e.g. by making those functions mandatory in an interface class that itself is optional.
/ Martin Stjernholm, Roxen IS