DN569122583

Subject: ANNOUNCE: dictionary - DN [1]

Frederic BONNET <frederic.bonnet@ciril.fr> - 06 Jan 2000 - comp.lang.tcl

 Dictionary: a new Tcl object type
 =================================

 Copyright (c) 1999-2000 Frédéric BONNET <frederic.bonnet@ciril.fr>

 Please read the file license.txt

 This piece of software implements a new Tcl object type called "dictionary". I
 decided to create it after a discussion in comp.lang.tcl, when I issued a RFC on
 arrays as first class object. The primary purpose was to turn arrays into
 objects so that they can be used everywhere Tcl objects are expected: as proc
 arguments or inside other objects. In the current implementation, arrays have no
 existence outside of their variable; one could see arrays as a collection of
 variables, and not as a data structure like lists. The only means of passing
 arrays to a proc is by reference and not by value. Dictionaries are an attempt
 to define an alternative to lists as a data structure, with array semantics.

 Dictionaries can be seen as a hybrid between arrays and lists. They look like
 lists, can be used as lists (thanks to the "everything is a string" Tcl
 paradigm), but their internals are closer to arrays in the sense that they use
 hash tables to store data. Some form of dictionary already exists in Tcl: the
 result of "array get" (also used as argument in "array set") has an external
 representation which is the same as a dictionary: an even-sized list whose even
 elements are keys and odd elements are values. The idea behind dictionaries is
 to give these pairlists an internal representation, rather than use the plain
 list representation. That way, the internal hash table never gets lost, and
 dictionaries can be used as arrays without performance hit. This is the main
 difference with other solutions such as TclX's keyed list, which don't use hash
 tables and then yields O(n) performances on element access. Arrays and
 dictionaries yeld nearly-O(1) performances on element access.

 A quick comparison between the different data structures:
 ---------------------------------------------------------

 =============================================================================
            Access        First-class  Order         Variable    Immutable
            performances     object       Preservation  operations    operations
 =============================================================================
 List        O(1)         Yes          Yes           Yes         Yes

 Keyedlist   O(n)         Yes          Yes           Yes         No

 Array       O(1)         No           No (via       Yes         No (variable)
                                       "array get")

 Dictionary  O(1)         Yes          No            Yes         Yes
 =============================================================================

 Here "Immutable operations" mean operations on pure values that affect no
 variable or other objects, such as "lreplace". "Variable operations" are
 operations that affect variables, such as "lappend".

 Arrays have no immutable operation since they are only implemented as variables.
 Keyedlists are regular Tcl objects but their interface define no immutable
 operation, only variable operation. There is no mean to use anonymous (ie as
 value) keyedlists. Lists only define "list" and "lappend" as variable
 operations, others are all immutable operations (lreplace, lrange...).
 Dictionaries provide both variable and immutable "write" operations (such as
 set/create, unset/substract, add/merge), and immutable "read" operations (get,
 size, exists...). So dictionaries can be used as arrays with variable ops, and
 as lists with immutable ops.

 Order preservation is only useful for those who want to interchange objects with
 lists. Keyedlists preserve the order in which elements are set. Arrays aren't
 objects so this notion hardly applies, but "array get" returns a Tcl list from
 an array, and the  elements order is undefined (it depends on the order in which
 elements are stored in the hash table). Dictionary follows array semantics in
 the sense that their external representation looks like a list, but the list
 elements are also undefined, only the key-value associations are considered
 meaningful.

 Where to get it
 ---------------

 The dictionary source archive can be found there:

     http://www.purl.org/net/bonnet/pub/dictionary.tar.gz

 It contains sources, a Visual C++ makefile for Windows and TEA-compatible (well,
 I hope so :) configure scripts.

 Version
 -------

 The current version of the package is 1.0a1. The a1 suffix means that this is
 the first alpha release of the package version 1.0. In the case of this
 package, alpha means "feature incomplete", ie some features are likely to be
 added before the final release. There may also be some bugs lurking around.
 However it is already useable as is.

 It is intended to be used with Tcl8.2 or above.

 Building the package
 --------------------

 On Windows:

     the provided makefile.vc is a MS Visual C++ -compatible makefile.
     Simply edit it then run nmake on it.

 On TEA-compatible architectures: Unix, Windows with Cygwin:

     To make type:

       ./configure
       make
       make install

     The configure script will deduce $PREFIX from the tcl installation.
     The generated Makefile uses the file $PREFIX/lib/tclConfig.sh that was left
     by the make of tcl for most of its configuration parameters.

     The Makefile generates pkgIndex.tcl files that are compatible with
     tcl7.6.   If you are using tcl7.5 then you will need to edit
     $PREFIX/lib/pkgIndex.tcl by hand.

 Using the package
 -----------------

 To use the package, simply add "package require dictionary" to your scripts. It
 will register a new command "::dictionary" in the global namespace. This command
 in turn provides a number of subcommands that operates on dictionary variables
 and objects.

 List of subcommands
 ----------------

     "add",       "array",          "create",      "exists",
     "get",       "merge",          "names",       "set",
     "size",      "substract",      "unset"

 Dictionary creation
 They build new dictionary objects.

     ::dictionary create ?list?
     ::dictionary create ?key value ...?

     Return a new dictionary initialized with the specified
     arguments, either inline:

         set d [dictionary create 1 foo 2 bar]

     or as one even-sized list:

         set d [dictionary create [list 1 foo 2 bar]]

     Dictionaries can be used as an even-sized list:

         set d2 [dictionary create $d]

     But in this case it is faster to do:

         set d2 $d

     "dictionary create" is similar to the "list" command.

 Dictionary value access
 These are immutable methods and thus return new objects from existing ones,
 like concat or lrange.

     ::dictionary size dict

     Query size of dictionary.

     ::dictionary get dict pattern

     Return a new dictionary from selected elements of another one.

     ::dictionary exists dict keyName

     Return whether the given key exists in the dictionary.

     ::dictionary names dict ?pattern?

     Return a list of keys that match the given pattern. If no pattern
     is specified, return all the keys.

     ::dictionary merge dict dict
     ::dictionary merge dict ?key value ...?

     Return a new dictionary made of the union of both dictionaries

     ::dictionary substract dict dict
     ::dictionary substract dict ?key value ...?

     Return a new dictionary made of the first dictionary elements
     minus the second's

 Dictionary variable access
 These are similar to set or lappend in the sense that they alter the value
 of a variable.

     ::dictionary set varName keyName ?newValue?

     Query or set the value of an element named keyName in
     dictionary variable varName.

     ::dictionary unset varName keyName ?keyName ...?

     Unset elements with the given key names in dictionary variable
     varName .

     ::dictionary add varName key value ?key value...?
     ::dictionary add varName list

     Add specified elements to dictionary variable varName.
     Here list can also be a dictionary.

 Dictionary interface to arrays
 These 2 methods don't provide extra functionality over existing array get/set
 methods, but the binary extension will provide optimizations given that
 array methods expect lists and thus may create object type shimmering.
 Dictionary methods won't create shimmering.

     ::dictionary array get arrayName ?pattern?

     Return a new dictionary with elements of array arrayName.
     An optional pattern is used to restrict elements by key.

     ::dictionary array set arrayName dict
     ::dictionary array new arrayName dict

     Fill array arrayName with dictionary dict's elements. The
     "new" form unsets any existing variable first.

 --
 Frédéric BONNET                        frederic.bonnet@ciril.fr
 ---------------------------------------------------------------
 "Theory may inform, but Practice convinces"
                                                     George Bain