ActiveTreeModel (Beta)

Hello Forum,

Well, I suppose this is my first contribution, if it wouldn't be
considered presumptuous to call it that.  As I said in a previous post,
criticism is welcome.

The package below will add two classes to the framework: ActiveTreeModel
and ActiveTreeNode.  They extend the behavior of TreeModel and TreeNode
(from which they subclass, respectively) to allow more robust
manipulation of the children in a node.  I explain in the class comments
what "active" means.  A full explanation can be found in the book
Reusable Software, by Bertrand Meyer, or the book Object-Oriented
Software Construction by the same author.

I tested the classes for about an hour, albeit not with TestCase<s> as I
don't know how to use SUnit yet within Dolphin (although after having
read Kent Beck's tutorial, it seems pretty straightforward).

Please bear in mind that I only just started with Dolphin and Smalltalk
about five weeks ago, so the grammar is probably a bit crude.  Also, you
will see methods such as #moveChild:toBefore: that probably could have
been named simply #move:toBefore, in retrospect.  That's the Eiffel
convention coming out.

Both ActiveTreeModel and ActiveTreeNode should be non-breaking if they
were to be substituted everywhere one is using TreeModel and TreeNode.
In ActiveTreeModel, I override #nodeClass, and in ActiveTreeNode, I
override #size.  Overriding #size might not have been warranted: again,
in Eiffel, the method, count, includes the count of the node's children
_and_ the node's object, or in other words, <(children size) + 1>.  A
more efficient approach to counting nodes might be to maintain the count
dynamically, so that #size would simply return a value immediately.
Indeed OA's comments in TreeModel even encourage a more efficient
counting implementation.

I hope this little extension proves useful.  If anything, it could be
something to build on.

Cheers,

Eric

========================================================================
=
| package |
package := Package name: 'EST Framework Extensions'.
package paxVersion: 1;
        basicComment: ''.


package classNames
        add: #ActiveTreeModel;
        add: #ActiveTreeNode;
        yourself.

package binaryGlobalNames: (Set new
        yourself).

package globalAliases: (Set new
        yourself).

package setPrerequisites: (IdentitySet new
        add: '..\Object Arts\Dolphin\MVP\Models\Tree\Dolphin Tree
Models';
        yourself).

package!

"Class Definitions"!

TreeModel subclass: #ActiveTreeModel
        instanceVariableNames: ''
        classVariableNames: ''
        poolDictionaries: ''
        classInstanceVariableNames: ''!
TreeNode subclass: #ActiveTreeNode
        instanceVariableNames: ''
        classVariableNames: ''
        poolDictionaries: ''
        classInstanceVariableNames: ''!

"Global Aliases"!


"Loose Methods"!

"End of package definition"!

"Source Globals"!

"Classes"!

ActiveTreeModel guid: (GUID fromString:
'{35807D61-53DC-4DDF-9F30-F28A495D2057}')!
ActiveTreeModel comment: 'One of the limitations of TreeModel is that
children of a node cannot be manipulated explicitly except in the most
basic way: adding at the end, removing, or moving to end of the children
of a different parent.  Manipulation beyond this can only be done on a
copy in the form of an ordered collection, a bag, a set, etc.
ActiveTreeModel builds on TreeModel by overcoming this limitation and
exploiting the fact that children are stored in an OrderedCollection.
Nodes can be added to children after or before another child node, or
altogether replaced by another node*.  ActiveTreeModel opens the door to
creating a fully active tree structure**.

The node class of an ActiveTreeModel is an ActiveTreeNode.

*Note that, when replacing node, no attempt is made to preserve the
children of the node being replaced.  Further, it is node itself that is
replaced, not the node''s object.

**Active structures are those data structures that encapsulate some
notion of cursor.  The cursor may be implied (the simple manipulation of
items by an index), or explicitly defined as a new behavior.  Indeed, a
cursor can be quite complicated and contain a great deal more
information beyond position alone.  An active tree structure normally
provides two types of cursors: a cursor for addressing the parent nodes
of the tree (global cursor), and a cursor for addressing children (child
cursor).  In other words, whereas nodes are unaware of their position in
a tree (unable, for example, to answer "I am the 4th node in the 3rd
level" or "I am the 3rd child of the 5th node in the 6th level"), an
active tree provides for a meta-awareness of the relative positions of
its nodes.

'!
!ActiveTreeModel categoriesForClass!MVP-Models! !
!ActiveTreeModel methodsFor!

add: leafObject asChildOf: parentObject after: anotherLeafObject
        "Adds the <Object>, leafObject, to the receiver as a child of
the <Object>, parentObject,
        and after the <Object>, anotherLeafObject, answering the new
leaf. If the parent is nil
        then leaf is added as a root of the tree. If leaf already exists
in the tree, then answer the
        existing node which is left in place (i.e. it is not an error to
attempt to add an equivalent
        node twice, and the existing node is not overwritten with the
new object). If the parent node
        does not exist, raise a <NotFoundError>.  If anotherLeafObject
does not exist, raise a
        <NotFoundError>.  Otherwise, answer the leaf object added."

        | parentNode childNode targetNode |
        childNode := self getNodeFor: leafObject ifAbsent: [].
        childNode notNil ifTrue: [^childNode object].
        parentNode := parentObject isNil ifTrue: [anchorNode] ifFalse:
[self getNodeFor: parentObject].
        targetNode := self getNodeFor: anotherLeafObject.
        self
                addChild: leafObject
                parentNode: parentNode
                after: targetNode.
        self
                trigger: #item:addedInParent:
                with: leafObject
                with: parentObject.
        ^leafObject!

add: leafObject asChildOf: parentObject before: anotherLeafObject
        "Adds the <Object>, leafObject, to the receiver as a child of
the <Object>, parentObject,
        and before the <Object>, anotherLeafObject, answering the new
leaf. If the parent is nil
        then leaf is added as a root of the tree. If leaf already exists
in the tree, then answer the
        existing node which is left in place (i.e. it is not an error to
attempt to add an equivalent
        node twice, and the existing node is not overwritten with the
new object). If the parent node
        does not exist, raise a <NotFoundError>.  If anotherLeafObject
does not exist, raise a
        <NotFoundError>.  Otherwise, answer the leaf object added."

        | parentNode childNode targetNode |
        childNode := self getNodeFor: leafObject ifAbsent: [].
        childNode notNil ifTrue: [^childNode object].
        parentNode := parentObject isNil ifTrue: [anchorNode] ifFalse:
[self getNodeFor: parentObject].
        targetNode := self getNodeFor: anotherLeafObject.
        self
                addChild: leafObject
                parentNode: parentNode
                before: targetNode.
        self
                trigger: #item:addedInParent:
                with: leafObject
                with: parentObject.
        ^leafObject!

addChild: anObject parentNode: parentNode after: anActiveTreeNode
        "Private - Create a child leaf and add under the specified
parent node
        and after the target node, anActiveTreeNode.  Answer the new
child node."

        | childNode |
        childNode := self newNode: anObject.
        objectNodeMap at: anObject put: childNode.
        parentNode addChildNode: childNode after: anActiveTreeNode.
        ^childNode!

addChild: anObject parentNode: parentNode before: anActiveTreeNode
        "Private - Create a child leaf and add under the specified
parent node
        and before the target node, anActiveTreeNode.  Answer the new
child node."

        | childNode |
        childNode := self newNode: anObject.
        objectNodeMap at: anObject put: childNode.
        parentNode addChildNode: childNode before: anActiveTreeNode.
        ^childNode!

atChild: anObject put: replacementObject
        "Replace the <Object>, anObject, with the <Object>,
replacementObject.
        If the target of the replacement not found, raise a
<NotFoundError>.  Otherwise,
        answer the replacement object."

        | targetNode |
        targetNode := self getNodeFor: anObject ifAbsent: [].
        self atChildNode: targetNode put: replacementObject.
        self
                trigger: #item:replacedInChildrenWith:
                with: anObject
                with: replacementObject.
        ^replacementObject!

atChildNode: anActiveTreeNode put: replacementObject
        "Private - Replace anActiveTreeNode with a new node for
replacementObject. Answer the replacement node.
        Note that this uses the private method #changeKey:to: of
LookupTable.  If the key is not changed, then the
        replacement node is not accessible even though the lookup table
contains it."

        | replacementNode parentNode |
        replacementNode := self newNode: replacementObject.
        objectNodeMap at: anActiveTreeNode object put: replacementNode.
        objectNodeMap changeKey: anActiveTreeNode object to:
replacementNode object.
        parentNode := anActiveTreeNode parent isNil ifTrue: [anchorNode]
ifFalse: [anActiveTreeNode parent].
        parentNode atChildNode: anActiveTreeNode put: replacementNode.
        ^replacementNode!

childAfterOrNil: leafObject

        | childNode parentNode nodeAfter |
        childNode := self getNodeFor: leafObject ifAbsent: [].
        parentNode := childNode parent isNil ifTrue: [anchorNode]
ifFalse: [childNode parent].
        (nodeAfter := parentNode childNodeAfterOrNil: childNode) isNil
ifTrue: [^nil].
        ^nodeAfter object!

childAt: anInteger inParent: parentObject
        "Answers the child located at the index, anInteger, within the
parentObject's collection
        of children."

        | parentNode |
        parentNode := self getNodeFor: parentObject ifAbsent: [].
        ^(parentNode childNodeAt: anInteger) object!

childBeforeOrNil: leafObject

        | childNode parentNode nodeBefore |
        childNode := self getNodeFor: leafObject ifAbsent: [].
        parentNode := childNode parent isNil ifTrue: [anchorNode]
ifFalse: [childNode parent].
        (nodeBefore := parentNode childNodeBeforeOrNil: childNode) isNil
ifTrue: [^nil].
        ^nodeBefore object!

firstChildOrNil: parentObject

        | parentNode |
        parentNode := self getNodeFor: parentObject ifAbsent: [].
        ^parentNode firstChildNodeOrNil object.!

indexOfChild: leafObject
        "Answers the index of the child within the collection of its
parent's children.  In other words,
        this is a local index."

        | childNode parentNode |
        childNode := self getNodeFor: leafObject ifAbsent: [].
        parentNode := childNode parent isNil ifTrue: [anchorNode]
ifFalse: [childNode parent].
        ^parentNode indexOfChildNode: childNode!

lastChildOrNil: parentObject

        | parentNode |
        parentNode := self getNodeFor: parentObject ifAbsent: [].
        ^parentNode lastChildNodeOrNil object.!

moveChild: leafObject downBy: anInteger
        "Overshooting the last child does not generate an error; the
move simply takes on
        the behavior of #moveChildToBottom:."

        | parentNode childNode |
        childNode := self getNodeFor: leafObject ifAbsent: [].
        parentNode := childNode parent isNil ifTrue: [anchorNode]
ifFalse: [childNode parent].
        self
                moveChildNode: childNode
                parentNode: parentNode
                downBy: anInteger;
                notifyMoved: leafObject inParent: parentNode object.
        ^leafObject!

moveChild: leafObject toAfter: anotherLeafObject

        | parentNode childNode targetNode |
        childNode := self getNodeFor: leafObject ifAbsent: [].
        parentNode := childNode parent isNil ifTrue: [anchorNode]
ifFalse: [childNode parent].
        targetNode := self getNodeFor: anotherLeafObject ifAbsent: [].
        self
                moveChildNode: childNode
                parentNode: parentNode
                toAfter: targetNode;
                notifyMoved: leafObject inParent: parentNode object.
        ^leafObject!

moveChild: leafObject toBefore: anotherLeafObject

        | parentNode childNode targetNode |
        childNode := self getNodeFor: leafObject ifAbsent: [].
        parentNode := childNode parent isNil ifTrue: [anchorNode]
ifFalse: [childNode parent].
        targetNode := self getNodeFor: anotherLeafObject ifAbsent: [].
        self
                moveChildNode: childNode
                parentNode: parentNode
                toBefore: targetNode;
                notifyMoved: leafObject inParent: parentNode object.
        ^leafObject!

moveChild: leafObject upBy: anInteger
        "Overshooting the first child does not generate an error; the
move simply takes on
        the behavior of #moveChildToTop:."

        | parentNode childNode |
        childNode := self getNodeFor: leafObject ifAbsent: [].
        parentNode := childNode parent isNil ifTrue: [anchorNode]
ifFalse: [childNode parent].
        self
                moveChildNode: childNode
                parentNode: parentNode
                upBy: anInteger;
                notifyMoved: leafObject inParent: parentNode object.
        ^leafObject
!

moveChildDown: leafObject

        ^self moveChild: leafObject downBy: 1!

moveChildNode: childNode parentNode: parentNode downBy: anInteger
        "Private"

        ^parentNode moveChildNode: childNode downBy: anInteger
        !

moveChildNode: childNode parentNode: parentNode toAfter: targetNode
        "Private"

        ^parentNode moveChildNode: childNode toAfter: targetNode
        !

moveChildNode: childNode parentNode: parentNode toBefore: targetNode
        "Private"

        ^parentNode moveChildNode: childNode toBefore: targetNode
        !

moveChildNode: childNode parentNode: parentNode upBy: anInteger
        "Private"

        ^parentNode moveChildNode: childNode upBy: anInteger
        !

moveChildNodeToBottom: childNode parentNode: parentNode
        "Private"

        ^parentNode moveChildNodeToBottom: childNode!

moveChildNodeToTop: childNode parentNode: parentNode
        "Private"
       
        ^parentNode moveChildNodeToTop: childNode!

moveChildToBottom: leafObject

        | parentNode childNode |
        childNode := self getNodeFor: leafObject ifAbsent: [].
        parentNode := childNode parent isNil ifTrue: [anchorNode]
ifFalse: [childNode parent].
        self
                moveChildNodeToBottom: childNode
                parentNode: parentNode;
                notifyMoved: leafObject inParent: parentNode object.
        ^leafObject!

moveChildToTop: leafObject

        | parentNode childNode |
        childNode := self getNodeFor: leafObject ifAbsent: [].
        parentNode := childNode parent isNil ifTrue: [anchorNode]
ifFalse: [childNode parent].
        self
                moveChildNodeToTop: childNode
                parentNode: parentNode;
                notifyMoved: leafObject inParent: parentNode object.
        ^leafObject!

moveChildUp: leafObject

        ^self moveChild: leafObject upBy: 1!

nodeClass

        ^ActiveTreeNode!

notifyMoved: leafObject inParent: parentObject
        "Private - All moves, however they are carried out, are treated
as the same."

        self
                trigger: #item:movedInParent:
                with: leafObject
                with: parentObject!

sizeOfChildrenIn: parentObject
        "Answer the number of child nodes in the parent (does not
include the node object itself)."

        ^(self sizeOfNodeFor: parentObject ) - 1!

sizeOfNodeFor: parentObject
        "Private - answer the number of child nodes in the parent, plus
the node itself."

        ^(self getNodeFor: parentObject ifAbsent: []) size

        ! !
!ActiveTreeModel categoriesFor: #add:asChildOf:after:!adding!public! !
!ActiveTreeModel categoriesFor: #add:asChildOf:before:!adding!public! !
!ActiveTreeModel categoriesFor:
#addChild:parentNode:after:!adding!private! !
!ActiveTreeModel categoriesFor:
#addChild:parentNode:before:!adding!private! !
!ActiveTreeModel categoriesFor: #atChild:put:!public!replacing! !
!ActiveTreeModel categoriesFor: #atChildNode:put:!private!replacing! !
!ActiveTreeModel categoriesFor: #childAfterOrNil:!enquiries!public! !
!ActiveTreeModel categoriesFor: #childAt:inParent:!enquiries!public! !
!ActiveTreeModel categoriesFor: #childBeforeOrNil:!enquiries!public! !
!ActiveTreeModel categoriesFor: #firstChildOrNil:!enquiries!public! !
!ActiveTreeModel categoriesFor: #indexOfChild:!enquiries!public! !
!ActiveTreeModel categoriesFor: #lastChildOrNil:!enquiries!public! !
!ActiveTreeModel categoriesFor: #moveChild:downBy:!public!updating! !
!ActiveTreeModel categoriesFor: #moveChild:toAfter:!public!updating! !
!ActiveTreeModel categoriesFor: #moveChild:toBefore:!public!updating! !
!ActiveTreeModel categoriesFor: #moveChild:upBy:!public!updating! !
!ActiveTreeModel categoriesFor: #moveChildDown:!public!updating! !
!ActiveTreeModel categoriesFor:
#moveChildNode:parentNode:downBy:!private!updating! !
!ActiveTreeModel categoriesFor:
#moveChildNode:parentNode:toAfter:!private!updating! !
!ActiveTreeModel categoriesFor:
#moveChildNode:parentNode:toBefore:!private!updating! !
!ActiveTreeModel categoriesFor:
#moveChildNode:parentNode:upBy:!private!updating! !
!ActiveTreeModel categoriesFor:
#moveChildNodeToBottom:parentNode:!private!updating! !
!ActiveTreeModel categoriesFor:
#moveChildNodeToTop:parentNode:!private!updating! !
!ActiveTreeModel categoriesFor: #moveChildToBottom:!public!updating! !
!ActiveTreeModel categoriesFor: #moveChildToTop:!public!updating! !
!ActiveTreeModel categoriesFor: #moveChildUp:!public!updating! !
!ActiveTreeModel categoriesFor: #nodeClass!constants!public! !
!ActiveTreeModel categoriesFor: #notifyMoved:inParent:!events!private! !
!ActiveTreeModel categoriesFor: #sizeOfChildrenIn:!operations!public! !
!ActiveTreeModel categoriesFor: #sizeOfNodeFor:!operations!private! !

ActiveTreeNode guid: (GUID fromString:
'{365D0D0C-869E-4C81-BE51-6328B5998F39}')!
ActiveTreeNode comment: 'ActiveTreeNode represents a node of a tree in
an <ActiveTreeModel> hierarchy.  It builds on <TreeNode> by providing
the ability to manipulate its children in a more robust manner.'!
!ActiveTreeNode categoriesForClass!MVP-Models-Support! !
!ActiveTreeNode methodsFor!

addChildNode: anActiveTreeNode after: anotherActiveTreeNode
        "Adds anActiveTreeNode as a child of the receiver, after
anotherActiveTreeNode.
        If anotherActiveTreeNode not found, raise a <NotFoundError>.
Otherwise, answer the node added."

        self children isEmpty ifTrue: [^nil].
        anActiveTreeNode = anotherActiveTreeNode ifTrue:
[^anActiveTreeNode].
        children add: anActiveTreeNode after: anotherActiveTreeNode.
        anActiveTreeNode parent: anotherActiveTreeNode parent.
        ^anActiveTreeNode!

addChildNode: anActiveTreeNode before: anotherActiveTreeNode
        "Adds anActiveTreeNode as a child of the receiver, before
anotherActiveTreeNode.  
        If anotherActiveTreeNode not found, raise a <NotFoundError>.
Otherwise, answer the node added."

        self children isEmpty ifTrue: [^nil].
        anActiveTreeNode = anotherActiveTreeNode ifTrue:
[^anActiveTreeNode].
        children add: anActiveTreeNode before: anotherActiveTreeNode.
        anActiveTreeNode parent: anotherActiveTreeNode parent.
        ^anActiveTreeNode!

atChildNode: anActiveTreeNode put: replacementNode
        "Replace anActiveTreeNode in the receiver's children.  If
several of the children are
        equal to anActiveTreeNode, only the first is replaced. If
anActiveTreeNode does not
        exist, raise <NotFoundError>.  Otherwise, answer the replacement
node."

        self children isEmpty ifTrue: [^nil].
        children at: (self indexOfChildNode: anActiveTreeNode)
                put: replacementNode.
        replacementNode parent: self.
        ^replacementNode!

childNodeAfterOrNil: anActiveTreeNode
        "Answers the child node that comes after anActiveTreeNode.  If
anActiveTreeNode does
        not exist, raise a <NotFoundError>.  If the node is childless,
or anActiveTreeNode is the
        last node, answers nil."

        self children isEmpty ifTrue: [^nil].
        children last = anActiveTreeNode ifTrue: [^nil].
        ^children after: anActiveTreeNode!

childNodeAt: anInteger
        "Answers the child node at index anInteger.  Coerce anInteger
into being bounds-correct.
        Should never fail."
       
        self children isEmpty ifTrue: [^nil].
        ^children at: (anInteger < 1
                                ifTrue: [1]
                                ifFalse: [anInteger > children size
                                        ifTrue: [children size]
                                        ifFalse: [anInteger]])!

childNodeBeforeOrNil: anActiveTreeNode
        "Answers the child node that comes before anActiveTreeNode.  If
anActiveTreeNode does
        not exist, raise a <NotFoundError>.  If the node is childless,
or anActiveTreeNode is the first
        node, answers nil."

        self children isEmpty ifTrue: [^nil].
        children first = anActiveTreeNode ifTrue: [^nil].
        ^children before: anActiveTreeNode!

firstChildNodeOrNil
        "Answer the first node,or nil if the node is childless."

        self children isEmpty ifTrue: [^nil].
        ^children first!

indexOfChildNode: anActiveTreeNode
        "Answers the index of the child node anActiveTreeNode.  If the
node is childless,
        answers 0.  If anActiveTreeNode does not exist, raise a
<NotFoundError>."

        self children isEmpty ifTrue: [^0].
        ^children indexOf: anActiveTreeNode ifAbsent: [self
errorNotFound: anActiveTreeNode]!

lastChildNodeOrNil
        "Answer the last node,or nil if the node is childless."

        self children isEmpty ifTrue: [^nil].
        ^children last!

moveChildNode: anActiveTreeNode downBy: anInteger
        "Moves anActiveTreeNode down anInteger times.  Answers the node
being moved,
        or nil if the node is childless.  If anActiveTreeNode does not
exist, raise a <NotFoundError>."

        ^self moveChildNode: anActiveTreeNode
                toAfter: (self childNodeAt: (anInteger + (self
indexOfChildNode: anActiveTreeNode)))!

moveChildNode: anActiveTreeNode toAfter: anotherActiveTreeNode

        (self children isEmpty or: [anotherActiveTreeNode isNil])
ifTrue: [^nil].
        anActiveTreeNode = anotherActiveTreeNode ifTrue:
[^anActiveTreeNode].
        self
                removeChildNode: anActiveTreeNode;
                addChildNode: anActiveTreeNode after:
anotherActiveTreeNode.
        ^anActiveTreeNode!

moveChildNode: anActiveTreeNode toBefore: anotherActiveTreeNode

        (self children isEmpty or: [anotherActiveTreeNode isNil])
ifTrue: [^nil].
        anActiveTreeNode = anotherActiveTreeNode ifTrue:
[^anActiveTreeNode].
        self
                removeChildNode: anActiveTreeNode;
                addChildNode: anActiveTreeNode before:
anotherActiveTreeNode.
        ^anActiveTreeNode!

moveChildNode: anActiveTreeNode upBy: anInteger
        "Moves anActiveTreeNode up anInteger times.  Answers the node
being moved,
        or nil if the node is childless. If anActiveTreeNode does not
exist, raise a <NotFoundError>."

        ^self moveChildNode: anActiveTreeNode
                toBefore: (self childNodeAt: (anInteger negated + (self
indexOfChildNode: anActiveTreeNode)))!

moveChildNodeDown: anActiveTreeNode
        "Moves the child node, anActiveTreeNode, down one.  If the node
is already
        at the end, then simply answers the node.  Otherwise, answers
the node being
        moved, or nil if the node is childless.  If anActiveTreeNode
does not exist,
        raise a <NotFoundError>."

        ^self moveChildNode: anActiveTreeNode downBy: 1

        !

moveChildNodeToBottom: anActiveTreeNode

        ^self moveChildNode: anActiveTreeNode toAfter: children last!

moveChildNodeToTop: anActiveTreeNode

        ^self moveChildNode: anActiveTreeNode toBefore: children first!

moveChildNodeUp: anActiveTreeNode
        "Moves the child node, anActiveTreeNode, up one.  If the node is
already
        at the beginning, then simply answers the node.  Otherwise,
answers the
        node being moved, or nil if the node is childless.  If
anActiveTreeNode does
        not exist, raise a <NotFoundError>."

        ^self moveChildNode: anActiveTreeNode upBy: 1!

size
        "Answers the number of elements in the node: the number of
children
        plus itself."

        ^children size + 1! !
!ActiveTreeNode categoriesFor: #addChildNode:after:!adding!public! !
!ActiveTreeNode categoriesFor: #addChildNode:before:!adding!public! !
!ActiveTreeNode categoriesFor: #atChildNode:put:!public!replacing! !
!ActiveTreeNode categoriesFor: #childNodeAfterOrNil:!enquiries!public! !
!ActiveTreeNode categoriesFor: #childNodeAt:!enquiries!public! !
!ActiveTreeNode categoriesFor: #childNodeBeforeOrNil:!enquiries!public!
!
!ActiveTreeNode categoriesFor: #firstChildNodeOrNil!enquiries!public! !
!ActiveTreeNode categoriesFor: #indexOfChildNode:!public! !
!ActiveTreeNode categoriesFor: #lastChildNodeOrNil!enquiries!public! !
!ActiveTreeNode categoriesFor: #moveChildNode:downBy:!public!updating! !
!ActiveTreeNode categoriesFor: #moveChildNode:toAfter:!public!updating!
!
!ActiveTreeNode categoriesFor: #moveChildNode:toBefore:!public!updating!
!
!ActiveTreeNode categoriesFor: #moveChildNode:upBy:!public!updating! !
!ActiveTreeNode categoriesFor: #moveChildNodeDown:!public!updating! !
!ActiveTreeNode categoriesFor: #moveChildNodeToBottom:!public!updating!
!
!ActiveTreeNode categoriesFor: #moveChildNodeToTop:!public!updating! !
!ActiveTreeNode categoriesFor: #moveChildNodeUp:!public!updating! !
!ActiveTreeNode categoriesFor: #size!operations!public! !

"Binary Globals"!

========================================================================
===

If anyone is having trouble installing Eric's package [1] then reading the
following might help.  Note (especially Eric) that it's not a problem with
the package itself but caused by the way that it is being distributed.

If I cut/paste Eric's code into a text file, rename it with a pac extension
and file it into Dolphin using the PackageBrowser then nothing happens - no
errors and the code is not installed into the image.  I tracked it down to
the following (located very early on in the file)

package setPrerequisites: (IdentitySet new
 add: '..\Object Arts\Dolphin\MVP\Models\Tree\Dolphin Tree
Models';
 yourself).

Either my newsreader or Eric's has wrapped the text half way through the
file name and, helpfully, removed the trailing space.  Dolphin just reads
the text from the file and you end up with a filename with an embedded crlf
sequence.  Edit the pac file to read as below and the PB should install it
correctly.

package setPrerequisites: (IdentitySet new
add: '..\Object Arts\Dolphin\MVP\Models\Tree\Dolphin Tree Models';
yourself).

I'm a bit surprised the Dolphin didn't throw _some_ sort of error though.

[1] If you copy the original code into a Dolphin workspace, highlight it all
and the "File It In" from the workspace menu then the code does install.  As
a rule I tend not to use this method as it means you have to manually
recreate the package.

--
Ian

Use the Reply-To address to contact me (limited validity).
Mail sent to the From address is ignored.

Eric,

> Well, I suppose this is my first contribution, if it wouldn't be
> considered presumptuous to call it that.  As I said in a previous post,
> criticism is welcome.

Thanks for posting this.  I do have a couple of criticisms, so I hope you
really meant that ;-)

But first a few observations.

One is that (with one exception) you don't override any of the existing
behaviour, nor extend the state of the objects themselves (add instvars).  So
(with that one exception) you could have chosen to package this as loose
methods to add to TreeModel and TreeNode.  I'm not saying it /should/ be
packaged like that, just mentioning that you /could/.  That possibility might
not have occurred to your Eiffel-trained mind.  The exception is
ActiveTreeNode>>size -- but I'm not sure what value that is supposed to add; I
could understand it answering how many children it had (non-recursive), or how
many nodes it stood for including itself (recursive), but the actual
implementation seems a little odd for a method called #size.  I would be
tempted to rename it to something that doesn't "interfere" with the general
method #size.  In which case all the methods could (only "could", mind) move up
to TreeNode, and then ActiveTreeModel wouldn't need its override of #nodeClass,
and so again it would be /possible/ to promote the new behaviour to TreeModel
itself.

Another observation -- you mentioned that you are not completely happy with the
naming conventions.  I didn't see anything which struck me as non-idiomatic for
Smalltalk.  Or rather, there is one small exception,
ActiveTreeModel>>atChild:put:.  Normally the #at:put: pattern is used for some
sort of keyed container (or where an object has a keyed-container-like role).
In this case there isn't a key (compare Sets vs. Dictionaries) so the name I
would expect to see is something like #replace:with:

Still, I think that as a matter of good naming (as opposed to idiomatic
naming), the "Child" part of several of the ActiveTreeModel methods is
inappropriate -- the object are not children of the tree (any more than the
elements of an Array are children of the array).  If they are children at all
then they are children of other objects in the tree (or may be root objects --
and so are not children at all).

A question: the name ActiveTreeModel (and the class comment) suggest that they
are active in the Eiffel sense.  I'm a bit puzzled by that since I can't see
anything "active" (in that sense) in this implementation.  Maybe I'm just
misunderstanding the meaning you give to the term ?

Anyway, the criticism.  It's about the events you trigger.

First a minor point: it's conventional for a class to include (on the
class-side) a #publishedEventsOfInstances to say what (public) events its
instances trigger.  See for instance TreeModel
class>publishedEventsOfInstances.  Nothing breaks if you forget to do that, but
it does mean that a useful browsing/documentation option is lost.  (And it also
breaks one of my tools, but I doubt if you care much about that ;-)

The more important point is that ActiveTreeModel breaks the contract that it
appears to inherit.  It's a subclass of TreeModel and doesn't indicate that it
can't be used as a TreeModel, but in fact will break when used with a standard
TreePresenter and one of the normal tree views.   The class doesn't generate
the necessary update events.  It's OK to change the event you trigger if the
new class isn't intended to use used in a TreePresenter-based triad (but I
don't think that's the case here).  It's also OK to generate new events which
the existing components don't know about (perhaps you have an extended
implementation in mind which does know about them).  But it isn't OK, not to
generate the events which a vanilla tree view expects to see, or it will fail
to update correctly.  So I think that you have to trigger #treeChanged:
notifications whenever a child is moved or replaced (the argument should be the
parent node or nil for a root item).

As I mentioned before, that will cause the exiting TreeView implementation to
collapse the changed part of the tree, which may not be what you want to
happen, but that's a problem with TreeView and should be fixed there, not by
breaking the model's contract.  In any case, not all tree view implementations
suffer from that problem.

BTW, I think you may have a bug in ActiveTreeModel>>firstChildOrNil: where it
#sends #object to the result of (parentNode firstChildOrNil).  I think that'll
break if the parent has no children.  I think there are few other places where
#object can be sent to nil.

That's It.  I hope it didn't come across as too negative.

    -- chris

Hello Chris,

>I do have a couple of criticisms, so I hope you really meant that ;-)

I did, only at this early stage they're more like lessons than
criticisms.

>One is that (with one exception) you don't override any of the existing
>behaviour, nor extend the state of the objects themselves...

This will change as the two classes mature.  I haven't yet provided the
"active" part of the structure, which will require an extension of state
and behavior (see below).

>The exception is ActiveTreeNode>>size -- but I'm not sure what value
that >is supposed to add...

Upon reconsideration, it offers no value.  It should be removed, along
with its encapsulation in ActiveTreeModel.

>Or rather, there is one small exception, ActiveTreeModel>>atChild:put:

I missed this one.  Originally I thought the argument of #at: expected
an index, but I can see now in the framework that it is polymorphic on a
number of types of arguments.

>In this case there isn't a key (compare Sets vs. Dictionaries) so the
name
>I would expect to see is something like #replace:with:...

I originally had #replace:with:, but I changed it to #atChild:put:.  But
<objectNodeMap> in TreeModel is a PluggableLookupTable, so would
#at:put: still be acceptable?

>...the objects are not children of the tree...

Coming from Eiffel, this is where I'm a little confused by the
implementation of TreeModel.  Formally, there's only ever _one_ root of
a tree.  TreeModel automatically sets up an anchorNode, which to me is
the root.  I'm puzzled by #addRoot:, which to me should be #addToRoot:
or #addAtRoot, since adding roots would contradict the one-root
invariant.  With anchorNode automatically created, it would seem that
all we're ever adding to TreeModel is children.  So I would agree with
you when you say that the use of "child" is inappropriate in the
selectors, although we might be coming to accord from two different
perspectives.

>A question: the name ActiveTreeModel (and the class comment) suggest
that
>they are active in the Eiffel sense.  I'm a bit puzzled by that since I
>can't see anything "active" (in that sense) in this implementation.
Maybe >I'm just misunderstanding the meaning you give to the term ?

There's no misunderstanding on your part.  In the class comment of
ActiveTreeModel I indicated that I was simply opening the door to adding
this behavior.  Your reply to my post affirms the reason I decided to
clip the development of these two classes: I wanted first to establish a
solid foundation, get the kinks out, as they say.  From your post I
would say that I have a little work to do.  So, very little of what I've
done falls under "active."  As you noticed, there is no notion of
cursor, implicit or explicit, local or global, or otherwise.  Also,
ActiveTreeNode<s> don't yet know the level they're on.

I should point out that implementing cursors could be a little tricky
since multiple views might share the same instance of a single model.
Also, there is a thread-safety issue here.  I can foresee having to
implement mutexes and perhaps something along the lines of a trigger
called #invalidateCursors.  Any thoughts?

>First a minor point: it's conventional for a class to include (on the
>class-side) a #publishedEventsOfInstances.

I'll add my events to the list this evening.  Sorry for breaking your
tool :|

>So I think that you have to trigger #treeChanged: notifications
whenever a >child is moved or replaced (the argument should be the
parent node or nil >for a root item).

I didn't catch this either.  I'll address this issue this evening.

>BTW, I think you may have a bug in ActiveTreeModel>>firstChildOrNil:
where
>it #sends #object to the result of (parentNode firstChildOrNil).  I
think
>that'll break if the parent has no children.  I think there are few
other >places where #object can be sent to nil.

Since we're dealing with objects at the tree level (objects are expected
as arguments, not nodes), I _return_ objects at this level for symmetry.
But I think, in general, I may have other problems with what it is I'm
returning from methods.  I've noticed that the way Smalltalk statements
go together means that the return value takes on more significance, or I
should say a different significance, from what I'm accustomed to in
Eiffel.  I'll explore further what you mean.

>I hope it didn't come across as too negative.

It didin't, but don't mince words: What do you _really_ think?  :-)

Thanks very much for your input.  I will take it to heart and start
revamping.  Ian must be bloody disappointed by now :).  Holistically
speaking, am I on the right track and do you feel that such behavior
will be useful to you?

Cheers,

Eric
post,
> > criticism is welcome.
>
> Thanks for posting this.  I do have a couple of criticisms, so I hope
you
> really meant that ;-)
>
> But first a few observations.
>
> One is that (with one exception) you don't override any of the
existing
> behaviour, nor extend the state of the objects themselves (add
instvars).
> So
> (with that one exception) you could have chosen to package this as
loose
> methods to add to TreeModel and TreeNode.  I'm not saying it /should/
be
> packaged like that, just mentioning that you /could/.  That
possibility
> might
> not have occurred to your Eiffel-trained mind.  The exception is
> ActiveTreeNode>>size -- but I'm not sure what value that is supposed
to
> add; I
> could understand it answering how many children it had
(non-recursive), or
> how
> many nodes it stood for including itself (recursive), but the actual
> implementation seems a little odd for a method called #size.  I would
be
> tempted to rename it to something that doesn't "interfere" with the
> general
> method #size.  In which case all the methods could (only "could",
mind) for
> some
> sort of keyed container (or where an object has a keyed-container-like
> role).
> In this case there isn't a key (compare Sets vs. Dictionaries) so the
name
> I
> would expect to see is something like #replace:with:
>
> Still, I think that as a matter of good naming (as opposed to
idiomatic
> naming), the "Child" part of several of the ActiveTreeModel methods is
> inappropriate -- the object are not children of the tree (any more
than
> the
> elements of an Array are children of the array).  If they are children
at
> all
> then they are children of other objects in the tree (or may be root
> objects --
> and so are not children at all).
>
> A question: the name ActiveTreeModel (and the class comment) suggest
that
> they
> are active in the Eiffel sense.  I'm a bit puzzled by that since I
can't
> see
> anything "active" (in that sense) in this implementation.  Maybe I'm
just
> misunderstanding the meaning you give to the term ?
>
> Anyway, the criticism.  It's about the events you trigger.
>
> First a minor point: it's conventional for a class to include (on the
> class-side) a #publishedEventsOfInstances to say what (public) events
its
> instances trigger.  See for instance TreeModel
> class>publishedEventsOfInstances.  Nothing breaks if you forget to do
> that, but
> it does mean that a useful browsing/documentation option is lost.
(And it
> also
> breaks one of my tools, but I doubt if you care much about that ;-)
>
> The more important point is that ActiveTreeModel breaks the contract
that
> it
> appears to inherit.  It's a subclass of TreeModel and doesn't indicate
> that it
> can't be used as a TreeModel, but in fact will break when used with a
> standard
> TreePresenter and one of the normal tree views.   The class doesn't
> generate
> the necessary update events.  It's OK to change the event you trigger
if
> the
> new class isn't intended to use used in a TreePresenter-based triad
(but I
> don't think that's the case here).  It's also OK to generate new
events
> which
> the existing components don't know about (perhaps you have an extended
> implementation in mind which does know about them).  But it isn't OK,
not
> to
> generate the events which a vanilla tree view expects to see, or it
will
> fail
> to update correctly.  So I think that you have to trigger
#treeChanged:
> notifications whenever a child is moved or replaced (the argument
should
> be the
> parent node or nil for a root item).
>
> As I mentioned before, that will cause the exiting TreeView
implementation
> to
> collapse the changed part of the tree, which may not be what you want
to
> happen, but that's a problem with TreeView and should be fixed there,
not
> by
> breaking the model's contract.  In any case, not all tree view
> implementations
> suffer from that problem.
>
> BTW, I think you may have a bug in ActiveTreeModel>>firstChildOrNil:
where
> it
> #sends #object to the result of (parentNode firstChildOrNil).  I think
> that'll
> break if the parent has no children.  I think there are few other
places
> where
> #object can be sent to nil.
>
> That's It.  I hope it didn't come across as too negative.
>
>     -- chris
>

Eric,

I wouldn't say so myself.  Not unless you are going to foreground the idea that
a tree can be considered to be a mapping from nodes to collections of child
nodes -- in which case I would expect to be able to use #at: or #atChild:, and
probably at least the core part of the protocol(s) understood by keyed
collections (possibly with slightly modified names), such as #do: and
#keysAndValuesDo:, #at:ifAbsent:, #at:ifPresent: etc).

Currently the Tree object uses a map internally, but doesn't appear publicly as
a kind of map -- you can change that if you wish (of course ;-) but I don't
offhand see much benefit in doing so.


> > ...the objects are not children of the tree...
>
> Coming from Eiffel, this is where I'm a little confused by the
> implementation of TreeModel.  Formally, there's only ever _one_ root of
> a tree.  TreeModel automatically sets up an anchorNode, which to me is
> the root.  I'm puzzled by #addRoot:, which to me should be #addToRoot:
> or #addAtRoot, since adding roots would contradict the one-root
> invariant.

It may help to consider that, despite its name, a TreeModel is actually a
Forest -- it has multiple roots.  What may be confusing is that the
/implementation/ (as opposed to the public ADT) is as a single-rooted tree.
That's because it's a handy implementation technique to have a hidden root one
level up from the public roots.  It makes some of the code more
complicated/obscure, but on the whole it makes things simpler.  But, despite
that aspect of the implementation, the ADT is a multiple rooted Forest.


> I should point out that implementing cursors could be a little tricky
> since multiple views might share the same instance of a single model.
> Also, there is a thread-safety issue here.  I can foresee having to
> implement mutexes and perhaps something along the lines of a trigger
> called #invalidateCursors.  Any thoughts?

I may be missing a lot about the Eiffel approach -- I've never used that
language and only read the book once, many years ago -- but I'm not immediately
convinced by the idea of a collection knowing the state of an iteration over
it.  That seems to be confusing two roles, and has (as you note) severe
practical problems.

I would take the approach of the standard Smalltalk collections and have
Internal Iterators (#do: and friends) which hold the necessary state "inside"
the iteration method.  TreeModel already has some iteration methods, but by no
means a complete set -- for instance there's no way to iterate over a subtree.
Optionally, you might also want External Iterators (akin to those in Java);
traditionally External Iterators for Smalltalk are expressed as some sort of
ReadStream (which carries with it a lot of unnecessary baggage unfortunately).

I would solve the problems of concurrent updates (either from within the
iterating Process or from some other Process) by just ignoring it.  In
Smalltalk one is expected to have the sense not to modify a container whilst
iterating it ;-)   And as far as genuine concurrent updates go, I don't think
that containers should be responsible for protecting themselves against it
(mainly because the best they can do is protect their internal state, they
cannot protect the /meaning/ of the data, so the application-level code usually
has to arrange for Mutex protection anyway).


You may find the Object methods #ifNil:, #ifNotNil:, and #ifNil:ifNotNil:
useful for reducing the clutter of nil testing (I don't recall seeing you use
them, so you may not yet have noticed them -- especially as they hadn't been
added to Dolphin when Ted's book came out).  Use like:

    ^ (some expression) ifNotNil: [:it | it sharpness].

or:

    xyz := (some expression) ifNil: [some defaultValue].

Alternatively -- for the case in hand -- you might want to consider using the
Null Object pattern for communication between ActiveTreeModels and
ActiveTreeNodes.  (An instance of ActiveTreeNodes with a nil #object would do
fine I think).

Yet another pattern (one which I rather like), is rather than having a method
which answers a possibly non-existent object, to change the protocol so you
pass the discovered object to a block /if/ it exists (compare
Dictionary>>at:ifPresent:).  E.g.

    aNode withNextDo: [:it | it some action].

That might be over-much bother for this application, but it's a nice pattern to
keep in mind -- it can sometimes clean up client code dramatically.


> > I hope it didn't come across as too negative.
>
> It didin't, but don't mince words: What do you _really_ think?  :-)
> [...] do you feel that such behavior
> will be useful to you?

I'm sure it will be useful.  Whether it will be useful to me personally may be
a different matter -- I already have several custom TreeModel implementations,
so it might not add much to what I've already got.  If I were starting out from
fresh then I would definitely use it.

BTW, comparing your tree with my nearest equivalent (a non-generic TodoList
that could well have inherited from, or been subsumed by, your code had it
existed at the time), I'd suggest adding a few Boolean-valued test methods,
such as #canMoveFirst, #canMoveDown, and so on.  They are handy for simplifying
UI code which must determine whether the corresponding operations should be
enabled.  Just a suggestion...

    -- chris

Chris,

(Because of formatting issues, I've changed the manner in which I quote
from a reply: a single '>' at the beginning and end of the quote).

>
I wouldn't say so myself.  Not unless you are going to foreground the
idea that a tree can be considered to be a mapping from nodes to
collections of child nodes -- in which case I would expect to be able to
use #at: or #atChild:, and probably at least the core part of the
protocol(s) understood by keyed collections (possibly with slightly
modified names), such as #do: and #keysAndValuesDo:, #at:ifAbsent:,
#at:ifPresent: etc).
>

Node-mapping is precisely the behavior I wish to abstract, not
foreground.  I think I'll stick with your original suggestion of
#at:put: for now, and then see how it plays out in a few use cases.  In
searching the framework, #replace:with: seems to have a very different
usage.

>
Currently the Tree object uses a map internally, but doesn't appear
publicly as a kind of map -- you can change that if you wish (of course
;-) but I don't offhand see much benefit in doing so.
>

I don't either.

>
It may help to consider that, despite its name, a TreeModel is actually
a Forest -- it has multiple roots.
>

Yes, the formalities behind the design of the TREE class in Eiffel are
based on FOREST, and the fact that the only object that should ever be
added to a tree is another tree:  A leaf becomes a tree when it takes on
a single child, but since that child must also be a tree, we have two
trees.  Two or more trees form a forest.  So, upon closer inspection, it
turns out that we don't really need to make the distinction.  That's why
in Eiffel you won't a data structure called FOREST.

If I had discovered no notion whatsoever of a tree in the Dolphin
framework, I would have begun with Tree as a subclass of
SequenceableCollection.  Then, I would have created a TreeModel that
wraps Tree.  There would have been no need for TreeNode: Every class in
the framework is already a node :).  The variables <parent>, <item>, and
<children> would reside in Tree, <item> serving as the "node," whatever
it may be.  When I look at a menu, I don't see menu items, only menus,
which are trees.  That some of these trees may be childless (no
sub-menus) is irrelevant really.

I'm digressing a bit.  Sorry.

>
I may be missing a lot about the Eiffel approach...but I'm not
immediately convinced by the idea of a collection knowing the state of
an iteration over it.  That seems to be confusing two roles, and has (as
you note) severe practical problems.
>

I very much like Smalltalk's approach to iteration.  I think this is
where the power of the language shines.  I would agree with you: a
collection should _not_ know about the state of an iteration.  I hope I
haven't conveyed the idea that that's what I'm after :o.  In Eiffel,
CURSOR and ITERATOR are two very different animals, the former
maintaining the state of current position, the latter maintaining the
state of just about anything pertinent to the iteration.  Indeed,
iterators often utilize cursors.

This is what I foresee in the way of cursor for the "active" part of
ActiveTreeModel:

CursorAbstract
        Cursor
                TreeCursor
                        ActiveTreeCursor

and then a <likedCursor> protocol.

As to the states in each, successively:

CursorAbstract: <currentPosition>
Cursor: (no additional states, only concretized behavior)
TreeCursor: <parent>, <firstChild>
ActiveTreeCursor: <level>
<linkedCursor>: <currentPosition>, <siblingBefore>, <siblingAfter>


Eric S. Taylor
ActiveTreeModel>>atChild:put:
> >
> > I missed this one.  Originally I thought the argument of #at:
expected
> > an index, but I can see now in the framework that it is polymorphic
on a
> > number of types of arguments.
> >
> > > In this case there isn't a key (compare Sets vs. Dictionaries) so
the
> > > name I would expect to see is something like #replace:with:...
> >
> > I originally had #replace:with:, but I changed it to #atChild:put:.
But
> > <objectNodeMap> in TreeModel is a PluggableLookupTable, so would
> > #at:put: still be acceptable?
>
> I wouldn't say so myself.  Not unless you are going to foreground the
idea
> that
> a tree can be considered to be a mapping from nodes to collections of
> child
> nodes -- in which case I would expect to be able to use #at: or
#atChild:, of
> > a tree.  TreeModel automatically sets up an anchorNode, which to me
is
> > the root.  I'm puzzled by #addRoot:, which to me should be
#addToRoot:
> > or #addAtRoot, since adding roots would contradict the one-root
> > invariant.
>
> It may help to consider that, despite its name, a TreeModel is
actually a
> Forest -- it has multiple roots.  What may be confusing is that the
> /implementation/ (as opposed to the public ADT) is as a single-rooted
> tree.
> That's because it's a handy implementation technique to have a hidden
root
> one
> level up from the public roots.  It makes some of the code more
> complicated/obscure, but on the whole it makes things simpler.  But,
> despite
> that aspect of the implementation, the ADT is a multiple rooted
Forest.
>
>
> > I should point out that implementing cursors could be a little
tricky
> > since multiple views might share the same instance of a single
model.
> > Also, there is a thread-safety issue here.  I can foresee having to
> > implement mutexes and perhaps something along the lines of a trigger
> > called #invalidateCursors.  Any thoughts?
>
> I may be missing a lot about the Eiffel approach -- I've never used
that
> language and only read the book once, many years ago -- but I'm not
> immediately
> convinced by the idea of a collection knowing the state of an
iteration
> over
> it.  That seems to be confusing two roles, and has (as you note)
severe
> practical problems.
>
> I would take the approach of the standard Smalltalk collections and
have
> Internal Iterators (#do: and friends) which hold the necessary state
> "inside"
> the iteration method.  TreeModel already has some iteration methods,
but
> by no
> means a complete set -- for instance there's no way to iterate over a
> subtree.
> Optionally, you might also want External Iterators (akin to those in
> Java);
> traditionally External Iterators for Smalltalk are expressed as some
sort
> of
> ReadStream (which carries with it a lot of unnecessary baggage
> unfortunately).
>
> I would solve the problems of concurrent updates (either from within
the
> iterating Process or from some other Process) by just ignoring it.  In
> Smalltalk one is expected to have the sense not to modify a container
> whilst
> iterating it ;-)   And as far as genuine concurrent updates go, I
don't
> think
> that containers should be responsible for protecting themselves
against it
> (mainly because the best they can do is protect their internal state,
they
> cannot protect the /meaning/ of the data, so the application-level
code
> usually
> has to arrange for Mutex protection anyway).
>
>
> > > BTW, I think you may have a bug in
ActiveTreeModel>>firstChildOrNil:
> > > where it #sends #object to the result of (parentNode
firstChildOrNil).
> > > I think that'll break if the parent has no children.  I think
there
> are
> > > few
> > other >places where #object can be sent to nil.
> >
> > Since we're dealing with objects at the tree level (objects are
expected
> > as arguments, not nodes), I _return_ objects at this level for
symmetry.
> > But I think, in general, I may have other problems with what it is
I'm
> > returning from methods.  I've noticed that the way Smalltalk
statements
> > go together means that the return value takes on more significance,
or I
> > should say a different significance, from what I'm accustomed to in
> > Eiffel.  I'll explore further what you mean.
>
> You may find the Object methods #ifNil:, #ifNotNil:, and
#ifNil:ifNotNil:
> useful for reducing the clutter of nil testing (I don't recall seeing
you
> use
> them, so you may not yet have noticed them -- especially as they
hadn't using
> the
> Null Object pattern for communication between ActiveTreeModels and
> ActiveTreeNodes.  (An instance of ActiveTreeNodes with a nil #object
would
> do
> fine I think).
>
> Yet another pattern (one which I rather like), is rather than having a
> method
> which answers a possibly non-existent object, to change the protocol
so personally
> may be
> a different matter -- I already have several custom TreeModel
> implementations,
> so it might not add much to what I've already got.  If I were starting
out
> from
> fresh then I would definitely use it.
>
> BTW, comparing your tree with my nearest equivalent (a non-generic
> TodoList
> that could well have inherited from, or been subsumed by, your code
had it
> existed at the time), I'd suggest adding a few Boolean-valued test
> methods,
> such as #canMoveFirst, #canMoveDown, and so on.  They are handy for
> simplifying
> UI code which must determine whether the corresponding operations
should
> be
> enabled.  Just a suggestion...
>
>     -- chris

Chris,

(Because of formatting issues, I've changed the manner in which I quote
from a reply: a single '>' at the beginning and end of the quote).

>
I wouldn't say so myself.  Not unless you are going to foreground the
idea that a tree can be considered to be a mapping from nodes to
collections of child nodes -- in which case I would expect to be able to
use #at: or #atChild:, and probably at least the core part of the
protocol(s) understood by keyed collections (possibly with slightly
modified names), such as #do: and #keysAndValuesDo:, #at:ifAbsent:,
#at:ifPresent: etc).
>

Node-mapping is precisely the behavior I wish to abstract, not
foreground.  I think I'll stick with your original suggestion of
#at:put: for now, and then see how it plays out in a few use cases.  In
searching the framework, #replace:with: seems to have a very different
usage.

>
Currently the Tree object uses a map internally, but doesn't appear
publicly as a kind of map -- you can change that if you wish (of course
;-) but I don't offhand see much benefit in doing so.
>

I don't either.

>
It may help to consider that, despite its name, a TreeModel is actually
a Forest -- it has multiple roots.
>

Yes, the formalities behind the design of the TREE class in Eiffel are
based on FOREST, and the fact that the only object that should ever be
added to a tree is another tree:  A leaf becomes a tree when it takes on
a single child, but since that child must also be a tree, we have two
trees.  Two or more trees form a forest.  So, upon closer inspection, it
turns out that we don't really need to make the distinction.  That's why
in Eiffel you won't a data structure called FOREST.

If I had discovered no notion whatsoever of a tree in the Dolphin
framework, I would have begun with Tree as a subclass of
SequenceableCollection.  Then, I would have created a TreeModel that
wraps Tree.  There would have been no need for TreeNode: Every class in
the framework is already a node :).  The variables <parent>, <item>, and
<children> would reside in Tree, <item> serving as the "node," whatever
it may be.  When I look at a menu, I don't see menu items, only menus,
which are trees.  That some of these trees may be childless (no
sub-menus) is irrelevant really.

I'm digressing a bit.  Sorry.

>
I may be missing a lot about the Eiffel approach...but I'm not
immediately convinced by the idea of a collection knowing the state of
an iteration over it.  That seems to be confusing two roles, and has (as
you note) severe practical problems.
>

I very much like Smalltalk's approach to iteration.  I think this is
where the power of the language shines.  I would agree with you: a
collection should _not_ know about the state of an iteration.  I hope I
haven't conveyed the idea that that's what I'm after :o.  In Eiffel,
CURSOR and ITERATOR are two very different animals, the former
maintaining the state of current position, the latter maintaining the
state of just about anything pertinent to the iteration.  Indeed,
iterators often utilize cursors.

This is what I foresee in the way of cursor for the "active" part of
ActiveTreeModel:


CursorAbstract
        Cursor
                TreeCursor
                        ActiveTreeCursor

and then a <likedCursor> protocol.

As to the states in each, successively:

CursorAbstract: <currentPosition>
Cursor: (no additional states, only concretized behavior)
TreeCursor: <parent>, <firstChild>
ActiveTreeCursor: <level>
<linkedCursor>: <currentPosition>, <siblingBefore>, <siblingAfter>

>
And as far as genuine concurrent updates go, I don't think
that containers should be responsible for protecting themselves against
it...
>

I agree, but I think now we may be mixing metaphors: Tree (ultimately a
type of Container), TreeModel, TreeView, and TreePresenter.  The data
structure Tree should neither trigger events nor respond to any.  The
protection scheme would definitely have to be put into a higher level of
abstraction, closer to the application layer.

>
You may find the Object methods #ifNil:, #ifNotNil:, and
#ifNil:ifNotNil:...et seq.
>

Everything after this sentence is great advice, most instructive.
You've given me much food for thought.

Thanks very much.

Cheers,

Eric
ActiveTreeModel>>atChild:put:
> >
> > I missed this one.  Originally I thought the argument of #at:
> > expected an index, but I can see now in the framework that it is
> > polymorphic on a number of types of arguments.
> >
> > > In this case there isn't a key (compare Sets vs. Dictionaries) so
> > > the name I would expect to see is something like #replace:with:...
> >
> > I originally had #replace:with:, but I changed it to #atChild:put:.

> > of a tree.  TreeModel automatically sets up an anchorNode, which to
> > me is the root.  I'm puzzled by #addRoot:, which to me should be
#addToRoot: single model.
> > Also, there is a thread-safety issue here.  I can foresee having to
> > implement mutexes and perhaps something along the lines of a trigger

> some sort of ReadStream (which carries with it a lot of unnecessary
> baggage unfortunately).
>
> I would solve the problems of concurrent updates (either from within
> the iterating Process or from some other Process) by just ignoring it.

> In Smalltalk one is expected to have the sense not to modify a
> container whilst
> iterating it ;-)   And as far as genuine concurrent updates go, I
don't
> think
> that containers should be responsible for protecting themselves
> against it (mainly because the best they can do is protect their
> internal state, they cannot protect the /meaning/ of the data, so the
> application-level code usually has to arrange for Mutex protection
> anyway).
>
>
> > > BTW, I think you may have a bug in
ActiveTreeModel>>firstChildOrNil:
> > > where it #sends #object to the result of (parentNode
firstChildOrNil).
> > > I think that'll break if the parent has no children.  I think
> > > there
> are
> > > few
> > other >places where #object can be sent to nil.
> >
> > Since we're dealing with objects at the tree level (objects are
> > expected as arguments, not nodes), I _return_ objects at this level
for symmetry.
> > But I think, in general, I may have other problems with what it is
> > I'm returning from methods.  I've noticed that the way Smalltalk
> > statements go together means that the return value takes on more
> > significance, or I should say a different significance, from what
> > I'm accustomed to in Eiffel.  I'll explore further what you mean.
>
> You may find the Object methods #ifNil:, #ifNotNil:, and
#ifNil:ifNotNil:
> with a nil #object would do fine I think).
>
> Yet another pattern (one which I rather like), is rather than having a

Chris,

I apologize if you received a similar post prior to the first one.  I
see now what's going on: I can't save drafts of replies to posts.  When
I hit save, it posts the reply immediately.

The second post completes the response to your response.

Cheers,

Eric

ActiveTreeModel>>atChild:put:
> >
> > I missed this one.  Originally I thought the argument of #at:
expected
> > an index, but I can see now in the framework that it is polymorphic
on a
> > number of types of arguments.
> >
> > > In this case there isn't a key (compare Sets vs. Dictionaries) so
the
> > > name I would expect to see is something like #replace:with:...
> >
> > I originally had #replace:with:, but I changed it to #atChild:put:.
But
> > <objectNodeMap> in TreeModel is a PluggableLookupTable, so would
> > #at:put: still be acceptable?
>
> I wouldn't say so myself.  Not unless you are going to foreground the
idea
> that
> a tree can be considered to be a mapping from nodes to collections of
> child
> nodes -- in which case I would expect to be able to use #at: or
#atChild:, of
> > a tree.  TreeModel automatically sets up an anchorNode, which to me
is
> > the root.  I'm puzzled by #addRoot:, which to me should be
#addToRoot:
> > or #addAtRoot, since adding roots would contradict the one-root
> > invariant.
>
> It may help to consider that, despite its name, a TreeModel is
actually a
> Forest -- it has multiple roots.  What may be confusing is that the
> /implementation/ (as opposed to the public ADT) is as a single-rooted
> tree.
> That's because it's a handy implementation technique to have a hidden
root
> one
> level up from the public roots.  It makes some of the code more
> complicated/obscure, but on the whole it makes things simpler.  But,
> despite
> that aspect of the implementation, the ADT is a multiple rooted
Forest.
>
>
> > I should point out that implementing cursors could be a little
tricky
> > since multiple views might share the same instance of a single
model.
> > Also, there is a thread-safety issue here.  I can foresee having to
> > implement mutexes and perhaps something along the lines of a trigger
> > called #invalidateCursors.  Any thoughts?
>
> I may be missing a lot about the Eiffel approach -- I've never used
that
> language and only read the book once, many years ago -- but I'm not
> immediately
> convinced by the idea of a collection knowing the state of an
iteration
> over
> it.  That seems to be confusing two roles, and has (as you note)
severe
> practical problems.
>
> I would take the approach of the standard Smalltalk collections and
have
> Internal Iterators (#do: and friends) which hold the necessary state
> "inside"
> the iteration method.  TreeModel already has some iteration methods,
but
> by no
> means a complete set -- for instance there's no way to iterate over a
> subtree.
> Optionally, you might also want External Iterators (akin to those in
> Java);
> traditionally External Iterators for Smalltalk are expressed as some
sort
> of
> ReadStream (which carries with it a lot of unnecessary baggage
> unfortunately).
>
> I would solve the problems of concurrent updates (either from within
the
> iterating Process or from some other Process) by just ignoring it.  In
> Smalltalk one is expected to have the sense not to modify a container
> whilst
> iterating it ;-)   And as far as genuine concurrent updates go, I
don't
> think
> that containers should be responsible for protecting themselves
against it
> (mainly because the best they can do is protect their internal state,
they
> cannot protect the /meaning/ of the data, so the application-level
code
> usually
> has to arrange for Mutex protection anyway).
>
>
> > > BTW, I think you may have a bug in
ActiveTreeModel>>firstChildOrNil:
> > > where it #sends #object to the result of (parentNode
firstChildOrNil).
> > > I think that'll break if the parent has no children.  I think
there
> are
> > > few
> > other >places where #object can be sent to nil.
> >
> > Since we're dealing with objects at the tree level (objects are
expected
> > as arguments, not nodes), I _return_ objects at this level for
symmetry.
> > But I think, in general, I may have other problems with what it is
I'm
> > returning from methods.  I've noticed that the way Smalltalk
statements
> > go together means that the return value takes on more significance,
or I
> > should say a different significance, from what I'm accustomed to in
> > Eiffel.  I'll explore further what you mean.
>
> You may find the Object methods #ifNil:, #ifNotNil:, and
#ifNil:ifNotNil:
> useful for reducing the clutter of nil testing (I don't recall seeing
you
> use
> them, so you may not yet have noticed them -- especially as they
hadn't using
> the
> Null Object pattern for communication between ActiveTreeModels and
> ActiveTreeNodes.  (An instance of ActiveTreeNodes with a nil #object
would
> do
> fine I think).
>
> Yet another pattern (one which I rather like), is rather than having a
> method
> which answers a possibly non-existent object, to change the protocol
so personally
> may be
> a different matter -- I already have several custom TreeModel
> implementations,
> so it might not add much to what I've already got.  If I were starting
out
> from
> fresh then I would definitely use it.
>
> BTW, comparing your tree with my nearest equivalent (a non-generic
> TodoList
> that could well have inherited from, or been subsumed by, your code
had it
> existed at the time), I'd suggest adding a few Boolean-valued test
> methods,
> such as #canMoveFirst, #canMoveDown, and so on.  They are handy for
> simplifying
> UI code which must determine whether the corresponding operations
should
> be
> enabled.  Just a suggestion...
>
>     -- chris

Eric,

> Node-mapping is precisely the behavior I wish to abstract, not
> foreground.  I think I'll stick with your original suggestion of
> #at:put: for now, and then see how it plays out in a few use cases.  In
> searching the framework, #replace:with: seems to have a very different
> usage.

It's /entirely/ up to you what you do, of course, but -- for the record -- I
didn't suggest using #at:put:...


> Yes, the formalities behind the design of the TREE class in Eiffel are
> based on FOREST, and the fact that the only object that should ever be
> added to a tree is another tree:

An interesting and reasonable way to design things.  But its very different
from the way that Dolphin TreeModels work -- there a TreeModel isn't the kind
of thing that can be added to another TreeModel (except as an atomic node).

I think to emulate that kind of pattern you would need a new kind of
TreeNode -- something like IndirectionNode perhaps, which would contain a
reference to another TreeModel and "fake up" its own #children by invoking the
foreign TreeModel's #roots.  Actually you'd need a different kind of TreeModel
too -- not inheriting from TreeModel since that "knows" that it knows about all
of its elements.  (There'd be issues with events too, but nothing that can't be
solved with a bit of extra code.)


> If I had discovered no notion whatsoever of a tree in the Dolphin
> framework, I would have begun with Tree as a subclass of
> SequenceableCollection.

Reasonable.  I think that on further investigation you would have found it
better to start by subclassing Collection directly (SequenceableCollection is
about linear collections of objects, and trees are, um, not so linear ;-) but
that general idea would be a good approach.

OTOH, I have tried -- on and off -- to produce a decent Graph (aka "network")
collection class.  So far I have failed.  It's easy enough to create something
that works for a limited subset of potential applications, but as soon as I try
to resolve the problems caused by the wide range of domains that need graphs,
the thing falls apart.  I can create an abstraction which is any of:
    easy to understand and use,
    efficient enough to cover the cases I /know/ I'l need,
    flexible enough to cover the cases I /know/ I'l need,
but I can't get all three :-(

I sort of suspect that the sucess of TreeModel (and its friends) is down to
/not/ attempting to solve this problem in even remotely full generality.


> In Eiffel,
> CURSOR and ITERATOR are two very different animals, the former
> maintaining the state of current position, the latter maintaining the
> state of just about anything pertinent to the iteration.  Indeed,
> iterators often utilize cursors.

I'm afraid I don't understand the distinction you are making there.  I'll just
have to wait and see what the code looks like ;-)

    -- chris

Chris,

>
It's /entirely/ up to you what you do, of course, but -- for the record
-- I didn't suggest using #at:put:...
>

My apologies.  I misunderstood.

>
An interesting and reasonable way to design things.  But its very
different from the way that Dolphin TreeModels work -- there a TreeModel
isn't the kind of thing that can be added to another TreeModel (except
as an atomic node).
>

At the level of Model, I would agree.  And I wouldn't expect TreeModels
to work in this way.  They're serving a higher purpose.

>
I think to emulate that kind of pattern you would need a new kind of
TreeNode -- something like IndirectionNode perhaps, which would contain
a reference to another TreeModel and "fake up" its own #children by
invoking the foreign TreeModel's #roots.  Actually you'd need a
different kind of TreeModel too -- not inheriting from TreeModel since
that "knows" that it knows about all of its elements.  (There'd be
issues with events too, but nothing that can't be solved with a bit of
extra code.)
>

That's the beauty of the recursive definition of a Tree (not a
TreeModel): there is no need to explicitly define a TreeNode.  Further,
a Tree should contain no event-related code.  That would be the
responsibility of TreeModel, TreeView, or TreePresenter.  I would say
that VirtualTreeModel is closer to a fundamental Tree.

>
I think that on further investigation you would have found it better to
start by subclassing Collection directly (SequenceableCollection is
about linear collections of objects, and trees are, um, not so linear
;-) but that general idea would be a good approach.
>

The non-linearity of a Tree is actually a meta-property, occurring only
once we have a Forest.  The list portion of a Tree (in other words, its
list of children) is actually linear.  The data type of that list could
be a LinkedList, OrderedCollection, Array, etc., each variation giving
rise to a whole different set of features serving equally various
purposes.

>
OTOH, I have tried -- on and off -- to produce a decent Graph (aka
"network") collection class.
>

A most ambitious undertaking.  For one of my electives at university I
took a course called Graph Theory.  This was a most challenging course
indeed.  The course started out rather simplisticly, but very quickly
ramped up.  There is a graphs cluster for Eiffel out there under Open
Source.  It took quite some time to develop, and yet it only scratches
the surface.  I wouldn't touch the subject.

>
I'm afraid I don't understand the distinction you are making there
[between CURSOR and ITERATOR].  I'll just have to wait and see what the
code looks like ;-)
>

Yes, yes, the code.  Well, I'm off to that now.  I should close by
saying that you may already be more familiar with the distinction
between CURSOR and ITERATOR than you think.  If you have used, or
interfaced with, a relational database, or worked with SQL, you are
already familiar with CURSOR.  Record pointers in a conventional
database are implemented with this very scheme.  But these record
pointers just sit there until one actually moves them: cursor.next(),
cursor.previous(), cursor.first(), etc.  An ITERATOR, on the other hand,
is programmed with a certain task, or tasks, and a specific rule for
traversal, and then is let loose, so to speak, on the data.  It may
actually use a cursor to advance itself.

Cheers,

Eric
In
> > searching the framework, #replace:with: seems to have a very
different
> > usage.
>
> It's /entirely/ up to you what you do, of course, but -- for the
record --
> I
> didn't suggest using #at:put:...
>
>
> > Yes, the formalities behind the design of the TREE class in Eiffel
are
> > based on FOREST, and the fact that the only object that should ever
be
> > added to a tree is another tree:
>
> An interesting and reasonable way to design things.  But its very
> different
> from the way that Dolphin TreeModels work -- there a TreeModel isn't
the
> kind
> of thing that can be added to another TreeModel (except as an atomic
> node).
>
> I think to emulate that kind of pattern you would need a new kind of
> TreeNode -- something like IndirectionNode perhaps, which would
contain a
> reference to another TreeModel and "fake up" its own #children by
invoking found it
> better to start by subclassing Collection directly
(SequenceableCollection
> is
> about linear collections of objects, and trees are, um, not so linear
;-)
> but
> that general idea would be a good approach.
>
> OTOH, I have tried -- on and off -- to produce a decent Graph (aka
> "network")
> collection class.  So far I have failed.  It's easy enough to create
> something
> that works for a limited subset of potential applications, but as soon
as down
> to
> /not/ attempting to solve this problem in even remotely full
generality.
>
>
> > In Eiffel,
> > CURSOR and ITERATOR are two very different animals, the former
> > maintaining the state of current position, the latter maintaining
the
> > state of just about anything pertinent to the iteration.  Indeed,
> > iterators often utilize cursors.
>
> I'm afraid I don't understand the distinction you are making there.
I'll
> just
> have to wait and see what the code looks like ;-)
>
>     -- chris

Eric,

> I should close by
> saying that you may already be more familiar with the distinction
> between CURSOR and ITERATOR than you think.  [...]

Ah, I see.  A cursor is a place, an iterator moves from place to place.

    -- chris

Chris,

Yes.  Nicely put.

Cheers,

Eric
place.
>
>     -- chris