tcllib-devel

[Tcllib-devel] key order problem for dict

[KATO K. <k.k...@gm...>]

You know that Tcl interpreter doesn't ensure that dict key ordering.

That is not matter for almost cases.

But when we write test cases,
how to compare between program result and booked value?

Especially, it is difficult problem for multi rank dict.


Thoughts?



I wrote a proc, and replaced from [dict create $key_duplicated_dict].
(yaml.tcl)

# remove duplications with saving key order
proc ::yaml::_remove_duplication {dict} {
    array set tmp $dict
    array set tmp2 {}
    foreach {key nop} $dict {
        if [info exists tmp2($key)] continue
        lappend result $key $tmp($key)
        set tmp2($key) 1
    }
    return $result
}

Re: [Tcllib-devel] key order problem for dict

[Jeff H. <je...@ac...>]

KATO Kanryu wrote:
> You know that Tcl interpreter doesn't ensure that dict key ordering.
> 
> That is not matter for almost cases.
> 
> But when we write test cases,
> how to compare between program result and booked value?

dicts are order-preserving, but that doesn't help you here.  I would 
look at the 8.5 dict.test for how it does it, using a [getOrder] proc 
that ensures a known order.

Jeff

Re: [Tcllib-devel] key order problem for dict

[KATO K. <k.k...@gm...>]

> I would look at the 8.5 dict.test for how it does it,
> using a [getOrder] proc that ensures a known order.

Is it the test of the dict itself?
It is likely to become helpful.

Thanks.

However, since he did not necessarily want to test the action of dict
itself, it decided to rewrite immediate values for the moment.
For a while, the test passed by building the data for comparison
dynamically using [list/dict create] commands.

Re: [Tcllib-devel] key order problem for dict

[Jeff H. <je...@ac...>]

KATO Kanryu wrote:
>> I would look at the 8.5 dict.test for how it does it,
>> using a [getOrder] proc that ensures a known order.
> 
> Is it the test of the dict itself?
> It is likely to become helpful.

Yes, tcl8.5/tests/dict.test, look for use of "getOrder".

Jeff

Re: [Tcllib-devel] key order problem for dict

[Andreas K. <and...@ac...>]

> You know that Tcl interpreter doesn't ensure that dict key ordering.

If you are talking about Tcl 8.5's dict structre and command, then no, IIRC
the ordering of keys is preserved by them (append order).
If you are talking about the result of [array get], then yes, the order is
'random', based on the hashtable internals.

Tcllib's testsuite support code contains a command 'dictsort' which sorts a
dictionary by keys

The definition is in Tcllib's file  modules/devtools/testutilities.tcl,
and modules/uri/uri.test,
modules/mime/mime.test are examples of using it.


> That is not matter for almost cases.
>
> But when we write test cases,
> how to compare between program result and booked value?

> Especially, it is difficult problem for multi rank dict.

>
> Thoughts?
>
>
>
> I wrote a proc, and replaced from [dict create $key_duplicated_dict].
> (yaml.tcl)
>
> # remove duplications with saving key order
> proc ::yaml::_remove_duplication {dict} {
>     array set tmp $dict
>     array set tmp2 {}
>     foreach {key nop} $dict {
>         if [info exists tmp2($key)] continue
>         lappend result $key $tmp($key)

lappend result $key $nop
and the array 'tmp' is not required.

>         set tmp2($key) 1
>     }
>     return $result
> }

--
	Andreas Kupries <and...@Ac...>
	Developer @ http://www.ActiveState.com
	Tel: +1 778-786-1122

Re: [Tcllib-devel] key order problem for dict

[KATO K. <k.k...@gm...>]

2008/5/27, Jeff Hobbs:
> Yes, tcl8.5/tests/dict.test, look for use of "getOrder".

(1)sorted a dict order by argment, and [lappend [dict size $dict].

2008/5/27, Andreas Kupries:
> Tcllib's testsuite support code contains a command 'dictsort' which sorts a
> dictionary by keys
>
> The definition is in Tcllib's file  modules/devtools/testutilities.tcl,

(2)sorted a dict order by alphabetical one.


1,2, All could be used for evaluation of a value by a future test.
Thank you for teaching.

By for the moment, although the difference is absorbed reflecting the
action of [dict create] in all values, it may be one with better using
these helpers in fact.




> If you are talking about Tcl 8.5's dict structre and command, then no, IIRC
> the ordering of keys is preserved by them (append order).

To be sure, such an action was able to be checked.
It did not know that it was decided as specification.
However, dict-extension in Tcl8.4 has not adopted such how to move.

> > # remove duplications with saving key order
> > proc ::yaml::_remove_duplication {dict} {
> >     array set tmp $dict
> >     array set tmp2 {}
> >     foreach {key nop} $dict {
> >         if [info exists tmp2($key)] continue
> >         lappend result $key $tmp($key)
>
> lappend result $key $nop
> and the array 'tmp' is not required.
>
> >         set tmp2($key) 1
> >     }
> >     return $result
> > }

Then, it does not become operation whose intention it has.
'key' is the given order and 'value' wants to evaluate the last thing.

Re: [Tcllib-devel] key order problem for dict

[KATO K. <k.k...@gm...>]

I made a procedure based on "dictsort" for testcases.
Currently, I use this in modules/yaml/yaml.test

There is upward compatibility between dictsort2 and dictsort.
If dictsort2's 2nd argument is not given, as the same work of dictsort.


proc dictsort2 {dict {pattern d}} {
    set cur  [lindex $pattern 0]
    set subs [lrange $pattern 1 end]
    set out {}
    if {$cur eq "l"} {
        foreach {node} $dict {
            if {$subs ne ""} {set node [dictsort2 $node $subs]}
            lappend out $node
        }
        return $out
    }
    if {$cur ne "d"} {array set msubs $cur}
    array set map $dict
    foreach key [lsort [array names map]] {
        set node $map($key)
        if {$cur eq "d"} {
            if {$subs ne ""} {set node [dictsort2 $node $subs]}
        } else {
            if [array exists msubs($key)] {
                set node [dictsort2 $node $msubs($key)]]
            }
        }
        lappend out $key $node
    }
    return $out
}

# Working Sample
% set dict {bb {h1 g1 d1 s1} aa {y2 t2 r2 e2}}
bb {h1 g1 d1 s1} aa {y2 t2 r2 e2}

# sorting only top
% dictsort2 $dict
aa {y2 t2 r2 e2} bb {h1 g1 d1 s1}

# sorting 2 ranks
% dictsort2 $dict {d d}
aa {r2 e2 y2 t2} bb {d1 s1 h1 g1}

# sorting only "aa"
% dictsort2 $dict {{aa d}}
aa {y2 t2 r2 e2} bb {h1 g1 d1 s1}

# sorting dict in list
% dictsort2 {{c1 d1 b1 a1} {j2 l2 a2 d2}} {l d}
{b1 a1 c1 d1} {a2 d2 j2 l2}