>>>
>>> Thanks Kevin for your answers. If I understand it correctly, using
>>> 'Dictionary' cannot be the source of non-determinism.
>>>
>>
>> I would say that it is unlikely. The hashing function is constant.
>>
>> At some stage as you insert elements into the dictionary the
dictionary
>> will have to increase the size of its hashtable which will reorganize
>> the keys (Dictionaries can also be compacted iflots of entries are
>> removed). It is *possible* that this is happening at different times
>> and so you are getting different orders but from a quick look at the
>> code I don't see how.
>>
>
> IIRC hashing is applied to "tagged values" some of which depend on
> items' memory location (e.g. atoms), which, in turn, is not guaranteed
> to be the same.
>
I have incorporated all the suggestions and I have the final definition
which I'm satisfied with. Also, the previous version wasn't usable if we
create a new OrderedDictionary from a child space because as soon as we
change anything, because of the shared global cell 'Counter', a runtime
error occurs saying that modification of global cell variable isn't
allowed from the local space. The attached version below gets rid of
this error as well.
Thanks everyone and hope this is useful for someone else too. Let me
know if it can be still improved/corrected.
Cheers,
-Himanshu.
--------- Final definition of OrderedDictionary.oz below ----------
functor
prepare
MyTypeMarker = {Name.new}
export
New
Is
IsEmpty
Put
Exchange
CondExchange
Get
CondGet
Keys
Entries
Items
Remove
RemoveAll
Clone
Member
ToRecord
Weak
define
fun {ByEntry _#(_#Count1) _#(_#Count2)}
Count1 < Count2
end
fun {Default P}
Dictionary.P
end
Weak = {Default weak}
fun {New}
D = {Dictionary.new}
in
{Dictionary.put D MyTypeMarker {NewCell 0}#(~1)}
D
end
fun {GetCounter D}
case {Dictionary.get D MyTypeMarker} of Item#_ then Item end
end
fun {Is D}
{Dictionary.is D} andthen {Dictionary.member D MyTypeMarker}
end
fun {IsEmpty D}
{Is D} = true %% Assert that it is of OrderedDictionary type
{List.length {Dictionary.keys D}} =< 1
end
proc {Remove D Key}
{Is D} = true %% Assert that it is of OrderedDictionary type
{Dictionary.remove D Key}
end
proc {RemoveAll D}
{Is D} = true %% Assert that it is of OrderedDictionary type
{Dictionary.removeAll D}
{Dictionary.put D MyTypeMarker {NewCell 0}#(~1)}
end
fun {Member D Key}
{Is D} = true %% Assert that it is of OrderedDictionary type
{Dictionary.member D Key}
end
fun {Clone D}
X
in
{Is D} = true %% Assert that it is of OrderedDictionary type
X = {Dictionary.clone D}
{Dictionary.put X MyTypeMarker {NewCell 0}#(~1)}
X
end
proc {Put D Key Item}
NewSeq
OldSeq
in
{Is D} = true %% Assert that it is of OrderedDictionary type
_#OldSeq = {Dictionary.condExchange D Key _#unit $ Item#NewSeq}
if OldSeq == unit then NewCounter in
%% Key is new, so set a new incremented value
%% or, NewSeq = Counter := NewCounter
{Cell.exchange {GetCounter D} NewSeq NewCounter}
NewCounter = NewSeq + 1
else
NewSeq = OldSeq
end
end
fun {Get D Key}
{Is D} = true %% Assert that it is of OrderedDictionary type
case {Dictionary.get D Key} of Item#_ then Item end
end
fun {Keys D}
{Is D} = true %% Assert that it is of OrderedDictionary type
%% Return elements in insertion order
{Map {Entries D} fun {$ Key#_} Key end}
end
fun {Items D}
{Is D} = true %% Assert that it is of OrderedDictionary type
%% Return items in insertion order
{Map {Entries D} fun {$ _#Item} Item end}
end
fun {Entries D}
SortedEntries
AllItems
in
{Is D} = true %% Assert that it is of OrderedDictionary type
SortedEntries = {Sort {Dictionary.entries D} ByEntry}
AllItems = {Map SortedEntries fun {$ Key#(Element#_)} Key#Element
end}
%% Ignore the first item that contains
MyMarkerType#(CounterCell#(~1))
{List.drop AllItems 1}
end
proc {Exchange D Key OldVal NewVal}
{Is D} = true %% Assert that it is of OrderedDictionary type
case {Dictionary.get D Key}
of OldVal#OldCount then
{Dictionary.put D Key NewVal#OldCount}
end
end
proc {CondExchange D Key DefVal OldVal NewVal}
{Is D} = true %% Assert that it is of OrderedDictionary type
if {Dictionary.member D Key} == false then
OldVal = DefVal
else
{Exchange D Key OldVal NewVal}
end
end
fun {CondGet D Key DefVal}
{Is D} = true %% Assert that it is of OrderedDictionary type
if {Dictionary.member D Key} == false then
DefVal
else
{Get D Key}
end
end
fun {ToRecord Label D}
{Is D} = true %% Assert that it is of OrderedDictionary type
{List.toRecord Label {Entries D}}
end
end
--------- Final definition of OrderedDictionary.oz above ----------
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
