Sorted dict 1

Pull request for SortedDict and BalancedTree23 taking into account Kevin Squire's feedback from the past 12 days.
Kevin,

With regard to this point that you raise, I've studied my code and decided 
that the additional code complexity in order to accomplish the suggested 
change is not worthwhile.

In more detail, the issue is that the dummy key/value entries in the two 
sentinel nodes, as well as the dummy key entries in the tree nodes above 
them, are never used, but they are copied over in code like this:


             ## If our ascent reaches a 2-node, then we convert it to
             ## a 3-node by giving it a child3 field that is >0.
             ## Encountering a 2-node halts the ascent up the tree.

             t.tree[p1] = (cmp2(ord,oldtreenode, minkeynewchild, isleaf) == 
1)?
                 TreeNode{K}(oldtreenode.child1, newchild, 
oldtreenode.child2,
                             oldtreenode.parent,
                             minkeynewchild, oldtreenode.splitkey1) :
                 TreeNode{K}(oldtreenode.child1, oldtreenode.child2, 
newchild,
                             oldtreenode.parent,
                             oldtreenode.splitkey1, minkeynewchild)

If oldtreenode.splitkey1 were an undefined reference, then this code would 
fail, so it would need to be guarded with an "if" statement. 
Unfortunately, there are many such instances that would need to be 
guarded.

Furthermore, even if I inserted all the necessary guards, it still 
wouldn't completely solve the problem of leaving unused keys in the tree. 
For example, if the user creates a big tree and then deletes all entries, 
there are some unused keys left in the root node.  The only way to fix 
those is with additional logic in the delete routine and new partial 
constructors to the TreeNode and KDRec data items so that if this 
scenario (unused keys in the tree) is detected, the old tree nodes are 
overwritten with partially constructed tree nodes with undefined 
references.

Overall, the amount of logic required is substantial and is also difficult 
to test because it would involve many uncommon cases.

This problem is caused by some design decisions in Julia: first, there is 
no concept of 'default constructor' in Julia.  In C++, any data items that 
go into a container must have a default constructor exactly to avoid these 
problems.  Second, Julia does not allow undefined references to be copied. 
I can understand the rationale for this decision, but in this scenario it 
creates some difficulties.

-- Steve




On Tue, 23 Sep 2014, Kevin Squire wrote:

> 
> In src/balancedTree.jl:
> 
> > +    ## The following code is necessary because in the case of a
> > +    ## brand new tree, the initial tree and data entries were incompletely
> > +    ## initialized by the constructor.  In this case, the call to insert! 
> > +    ## underway carries
> > +    ## valid K and D values, so these valid values may now be
> > +    ## stored in the dummy placeholder nodes so that they no
> > +    ## longer hold undefined references.
> > +
> > +    if size(t.data,1) == 2
> > +        @assert(t.rootloc == 1 && t.depth == 1)
> > +        t.tree[1] = TreeNode{K}(t.tree[1].child1, t.tree[1].child2,
> > +                                t.tree[1].child3, t.tree[1].parent,
> > +                                k, k)
> > +        t.data[1] = KDRec{K,D}(t.data[1].parent, k, d)
> > +        t.data[2] = KDRec{K,D}(t.data[2].parent, k, d)
> > +    end
> 
> I'm wondering if the block above is necessary? It keeps things from being undefined, which can be
> good, but it also maintains references to k and d, even after these might otherwise be
> unreferenced, so they won't be garbage collected until after the tree is disposed of. This probably
> isn't a big deal most of the time, but occasionally could be surprising.
> 
> It seems that you (almost?) always check for your sentinel values before accessing the data or tree
> nodes, so I would consider removing this. If the data values here are ever accessed, it is almost
> certainly an error, and it would arguably be better if an error were thrown than to return the
> values stored here.
> 
> The only exception I can think of is when displaying a node for debugging, but even there, it would
> probably be worth just special casing the sentinel nodes.
> 
> —
> Reply to this email directly or view it onGitHub.[7881863__eyJzY29wZSI6Ik5ld3NpZXM6QmVhY29uIiwiZXhwaXJlcyI6MTcyNzA5NTY0NCwiZGF0YSI6eyJpZCI6N
> DE3MzQ5Mjl9fQ==--f61119f560eab2872a2005327ca212f660af54f4.gif]
> 
> 
>