[Thomas Linder Puls]

Also, a few notes on your library: In many ways an interesting data structure. But ...

It seems to me that the "more" abstract data type you are "actually" implementing is something like this:

Code: Select all

interface chain{@Data}
 
predicates
    insertBefore : (@Data Reference, @Data Data).
    % plus other variations insertAfter, insertFirst, insertLast ...
 
predicates
    contains : (@Data Value) determ.
 
predicates
    tryGetNext (@Data Reference) -> @Data Value determ.
    % plus other such things tryGetPrevious, isEmpty, ....
 
predicates
    getAll_nd : () -> @Data Value nondeterm.
 
...
 
end interface chain

Some of this could naturally be inherited from setM. But notice that none of this looks map-like; there is no Key-involvement.

However, the actual implementation of this data type involves using "small" positive numbers as array indices. And in order to make the abstract version of this data type we need an efficient collision free mapping from our @Data to "small" positive numbers. (Unlike hash functions which allows collisions (though fewer collisions is better)).

The interface (mapM_chain) you provide with a @Key (called @Site in your code) seems like a relatively "uninteresting" implementation detail. And as implementation detail it is over-generalized because: @Key will always be positive.

The problem in using this data structure lies in providing the mapping from @Data to positive.

Your objIdentNumber provides one such mapping, they must however be built into the data, which limits the generality. Furthermore, the "positive" numbers can be as large as the number of objects that was alive simultaneously at some point in time.

It is a known problem (at least to me) that when generalizing a data structure, you may need a mapping from the actual interesting data to some low-level internal "thing". And the resulting data structure will not be more efficient than that mapping.

[Martin Meyer]

OK. But just to the objSetM_chain construction:

Of course a persistent data structure is one where every operation returns a new data structure but also preserves the old one. I think, you mention it because I made a mistake:

My objSetM_chain example is not appropriate. When I tried to make class objSetM_chain persistent, I realized that it cannot be done with the reversion class resp. with the undo-on-backtrack feature. Thus it is nonsense that I presented it here.

However class objSetM_chain can be made persistent with type recoverableState which is used in the stateManager class. To keep things simple, I prove the technique in a smaller example. In attached arrayP_Example modifiable type arrayM is turned into persistent one arrayP. The class arrayP has same (amortized) performance characteristics as arrayM provided one does not alternatingly access versions of the array with growing distance (for example versions 1 2 1 3 1 4 1 5 and so on).

In coding arrayP I came across another issue for which I have opened a separate topic. Please have look at that too.

Type objSetM_chain supports the setM interface (via the setM_chain interface). In my library I have also an objMapM_chain type which supports the mapM interface. I called the numbered objects 'keys', but you can denote them as well 'indexes'.

The involved positive ID numbers are always 'small' resp. dense and also free of collisions. That is because they stem from a number generator. The generator numbers the objects starting with 0 und subsequently adds 1 to the highest number generated so far or it re-uses a number from a disposed object if there exists one. 'Small' addresses the aspect that in case a single 'large' number would be inserted in underlying positiveSetM_chain, then an array buffer had to be re-sized to that large number - that would not hurt the performance claim, but would waste memory.

Yes, parameter @Site in interface mapM_chain is is over-generalized in the example because it is always positive. But in objMapM_chain (where I am using it too) it is not always positive. The construction in objMapM_chain is analogous to the example: In the example parameter @Site in setM_chain refers in one place to demoObject and in another place to positive:

Code: Select all

        DemoChain = objSetM_chain::new(),
        show("create new objSetM_chain", DemoChain),
        %--
        Chihiro = demoObject::new("Chihiro"),
        DemoChain:insert(Chihiro),

Code: Select all

interface objSetM_chain{@Site} supports setM_chain{@Site}

Code: Select all

interface positiveSetM_chain supports setM_chain{positive}

Yes, the ID numbers must be built into the data and that limits the generality. It is built in by the restriction that the member objects must support type resp. inherit class objIdentNumber. This restriction is the most severe one about the construction.

And again yes, the positive ID numbers can be as large as the number of objects that was alive simultaneously at some point in time. But they cannot be larger than that. And that is why the involved numbers, i.e. the alive numbers together with the numbers in the pool which are waiting for re-use, are always dense and consist of only (in the above mentioned sense) 'small' numbers.

Of course the fact that there is a maximal positive number also limits the construction. My performance claim assumes that arithmetic operations and thus element address calculations in arrays are in O(1). If the operating principle of setM_chain would be ported to unlimited numbers and arrays, then my performance claim could not hold anymore.

The objects to ID numbers mapping works in constant time in both directions. The direction forth is obvious since the number is a field in the object. Direction back is also in O(1) because it takes only two array look-ups. To see how it works, just step with the debugger in the example into the code at line 31:

Code: Select all

        Contains1 = toBoolean(DemoChain:contains(Kamaji)),

Hence the generalizing data structure objSetM_chain is not claimed to be more efficient than the underlying mapping from objects to ID numbers. After the needed memory has been allocated, all works in constant time.

The construction has its limits, but -at least so far- I cannot see any defect about it.