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.
You do not have the required permissions to view the files attached to this post.