To TreeModel or not to TreeModel

Hi all,

I've been working on something for quite sometime now, but still not
quite certain how to go about it.

I'm working on an app for a bookshop. The owner is selling used books,
and since he is a bit of an order freak he has categorized these books
in about 300 hundred different catalogs, most of which are subcatalogs
at varying depth.

So I created a class catalog, which holds a collection of catalogs
(nodes) and a collection of books (leafs).

So far so good.


But it turns out that I want to iterate over the catalog(s) much as I
would like to iterate over a collection.

I've implemented the functionality, with recursive and non-recursive
iteration, but at the end of the day I'm not sure whether to use OA's
TreeModel instead or not.

What would you choose in this scenario?

Günther

Hello Günther,

>To TreeModel or not to TreeModel...

The question of whether to use a tree structure is a fundamental one,
and so one should ask, "To use a tree or not to use a tree?"  Dolphin's
TreeModelAbstract and TreeModel certainly do provide all of the formal
facilities for managing trees (we just came through this ourselves).

>...but at the end of the day I'm not sure whether to use OA's
>TreeModel instead or not.

Yes, most definitely.  The class has all of the _formal_ features of
what we know to be a tree structure, and then other features that make
the class more practical to use in various circumstances.

The example you give certainly qualifies for tree-based implementation.
As for iteration, Dolphin offers the standard preorder and endorder
(a.k.a postorder) iteration schemes.  Have you taken a look at the
#preOrder and #endOrder family of methods in TreeModelAbstract?

Cheers,

Eric

Günther,

> I'm working on an app for a bookshop. The owner is selling used books,
> and since he is a bit of an order freak he has categorized these books
> in about 300 hundred different catalogs, most of which are subcatalogs
> at varying depth.

Just a thought, but is each book in a /single/ category ?  For instance a
French translation of "Through the Looking Glass, and What Alice Found There"
might be categorised under "children's books", "English classics", "French
books", "translations", or any combinations of those (plus others). It would be
difficult to choose which category was most important.  Speaking as an order
freak myself, I would find that very uncomfortable -- and probably, as a
result, end up creating a very deeply nested system of categories.  If I were
allowed to put books in multiple categories (like methods in Dolphin) then I
would be able to use far fewer categories (but probably still rather a lot).

Anyway, the point of that (besides raising an issue that might not yet have
struck you) is that if the books themselves are part of the tree, then there
are two problems adapting that to Dolphin's TreeModels.

If the books can only appear in one category then you have a small problem with
types.  The Dolphin TreeModel stuff is set up on the assumption that all the
objects in the tree conform to the same protocol -- which is unlikely to be the
case for books and book categories.   That's not difficult to get around, but
you do /have/ to get around it, and that might be one reason not to use
TreeModel.

If the books can appear in more than one category, then you have an additional
problem, which is that any given object can only appear once in any given tree
(that's a requirement of both the tree model itself, and of all the extant tree
views).  Again that's not too difficult to get around, but it's something to be
aware of.

All that suggests that it might be easier to have a tree of categories, plus a
separate list of books.  And, much like the way some of the Dolphin tools work,
in the GUI the category tree would be used to /filter/ the list of books which
presented in a separate panel.


> I've implemented the functionality, with recursive and non-recursive
> iteration, but at the end of the day I'm not sure whether to use OA's
> TreeModel instead or not.

No easy answer, I'm afraid.  Just to add another layer of confusion ;-) don't
forget about virtual tree models -- they can be a useful compromise.

FWIW, when I've had this kind of problem I usually create my own structures and
use a VirtualTreeModel, or an ExpandingTreeModel, or (most commonly) a custom
subclass of TreeModel to give it a tree model-ish interface for when I want to
use TreeViews and the like.  That does mean that I miss out on the pre-packaged
implementations of #preOrderDo: and so on, but that doesn't bother me
particularly.

I think what I'm really trying to say here (my mind isn't particularly clear
today, so I'm rambling rather), is that it probably doesn't matter too much
which you decide.  If you start by using a concrete tree model, then you can
always change to a virtual one later if you want.  Likewise if you prefer to
start without an explicit tree model, then it's easy enough to use a virtual
tree model if/when you find you need one after all.   Whichever you choose, you
won't be digging a pit for yourself.

    -- chris

Günther, Chris...

>Just a thought, but is each book in a /single/ category ?

Yes, this would be a pertinent question.  It sounds to me, though, from
your post, that the basis of your categorization is "catalogue," not
various features of the books themselves.

 From a formal perspective, what we call a tree is often also called a
"hierarchical tree," where hierarchical refers to the specific property
that each node knows of only _one_ predecessor, but perhaps _many_
successors.  The operative word, though, is "knows."  This property
manifests itself in the node with a reference to a single parent and
reference to a list of children.  We can see this in TreeModelAbstract.

As Chris points out, if you have a situation where catalogues and/or
books have associated with them multiple categories, then a hierarchical
tree is no longer the data structure you would need (although I have
peers who might insist that the tree structure still applies, and one
need only duplicate the nodes in each of the various categories to which
they apply).  With a multiple-category scenario, as Chris suggests, what
you have is a typical many-to-many relationship.  Click on a catalogue,
and you might get a list of many books; click on a book, and many
catalogues in the tree might light up.

So, the functionality above might be what drives your design decision:

1) What is the basis of the categorization, the books themselves or the
catalogues?
2) Does a book appear in more than one catalogue?
3) Does each catalogue contain more than one book (I would assume so)?

It might just be that you're looking at a bag-to-bag implementation, not
a tree.  But in a many-to-many relationship, an intermediate "table" has
to map the many parent keys to the many child keys.  Unfortunately, I
don't know what the best practice would be in Smalltalk or, more
specifically, in Dolphin (I'm sure Chris does).  It would take the
following form (note that Parent key and Child key should not be
constrained to uniqueness):

Parent key Child key
========== =========
#cat1 #subcat1
#cat1 #subcat2
#cat2 #subcat1
#cat3 #subcat3
#cat3 #sbucat2
...

Click on #cat1, you get #subcat1 and #subcat2; click on #cat3, you get
#subcat2 and #subcat3, etc.  But then, from the reverse perspective,
click on #subcat2, and you get #cat1 and #cat3.

Since many of the browsers implement this behavior in Dolphin, I'm sure
the framework already provides an easy solution.

Hope this helps.

Cheers,

Eric

books,
> > and since he is a bit of an order freak he has categorized these
books
> > in about 300 hundred different catalogs, most of which are
subcatalogs
> > at varying depth.
>
> Just a thought, but is each book in a /single/ category ?  For
instance a
> French translation of "Through the Looking Glass, and What Alice Found
> There"
> might be categorised under "children's books", "English classics",
"French
> books", "translations", or any combinations of those (plus others). It
> would be
> difficult to choose which category was most important.  Speaking as an
> order
> freak myself, I would find that very uncomfortable -- and probably, as
a
> result, end up creating a very deeply nested system of categories.  If
I
> were
> allowed to put books in multiple categories (like methods in Dolphin)
then problem
> with
> types.  The Dolphin TreeModel stuff is set up on the assumption that
all
> the
> objects in the tree conform to the same protocol -- which is unlikely
to
> be the
> case for books and book categories.   That's not difficult to get
around,
> but
> you do /have/ to get around it, and that might be one reason not to
use
> TreeModel.
>
> If the books can appear in more than one category, then you have an
> additional
> problem, which is that any given object can only appear once in any
given
> tree
> (that's a requirement of both the tree model itself, and of all the
extant
> tree
> views).  Again that's not too difficult to get around, but it's
something
> to be
> aware of.
>
> All that suggests that it might be easier to have a tree of
categories,
> plus a
> separate list of books.  And, much like the way some of the Dolphin
tools
> work,
> in the GUI the category tree would be used to /filter/ the list of
books
> which
> presented in a separate panel.
>
>
> > I've implemented the functionality, with recursive and non-recursive
> > iteration, but at the end of the day I'm not sure whether to use
OA's
> > TreeModel instead or not.
>
> No easy answer, I'm afraid.  Just to add another layer of confusion
;-) pre-
> packaged
> implementations of #preOrderDo: and so on, but that doesn't bother me
> particularly.
>
> I think what I'm really trying to say here (my mind isn't particularly
> clear
> today, so I'm rambling rather), is that it probably doesn't matter too
> much
> which you decide.  If you start by using a concrete tree model, then
you
> can
> always change to a virtual one later if you want.  Likewise if you
prefer
> to
> start without an explicit tree model, then it's easy enough to use a
> virtual
> tree model if/when you find you need one after all.   Whichever you
> choose, you
> won't be digging a pit for yourself.
>
>     -- chris

Chris, Eric ,

thank you all for the replies!

I *used* to do it like this:

        I had a class Catalog with:
        - a name
        - a parent (another catalog or nil)
        - a collection of subcatalogs
        - a collection of books

        I also had a class Book (simplified)
        - with a title
        - an ISBN
        - a price
        - a reference to its catalog

whenever I would ask a catalog to add a book to its collection of books
the catalog would also call Book>>catalog to set itself as the new
catalog of this book.

The book would then send Catalog>>removeBook: to its old catalog.

This way I would ensure that any one book exists only in one catalog at
a time. (Which is also what the customer wants).

I would have similar behaviour in

        Catalog>>addCatalog: aCatalog
        catalogs add: aCatalog
        aCatalog parent: self

and so on.

My application would also hold on to the root catalog.

But in a way, this tree is also a collection, there are things that I
want to do like >>detect: >>do: >>inject: for instance, in order to get
the sum of the prices of the books or what not.

The tree model makes a distinction between TreeModel (being the
collection of sort) and TreeNode, being an *element* in the collection.

Chris I know I can pretty much go either way, I'm just not sure yet.

There seem to be points in favor of TreeModel/TreeNode

        -iteration over the nodes
        -observer pattern on the tree structure
       
There seem to be points in using Catalog with 2 collection one for Book
and one for Catalog

        -I can clearly identify only the catalog being the node in the tree and
have separate calls for the books.
        - also iteration

But there's a drawback, for instance the Book needs to know about its
catalog, something that (according to some other attendees of the
monthly Smalltalk User group meeting in Frankfurt today) should not be
(I tend to agree here).
I need the book to know about its catalog so far in order to move one
book from one catalog to the other, i.e. so that it can send its old
catalog *remove me*.

They suggested a Librarian Object instead which would move a book from
one catalog to the other.

So there are quite some issues here and I haven't figured out yet

I have also written my answers between the questions

Eric Taylor schrieb:
> Günther, Chris...
>
>> Just a thought, but is each book in a /single/ category ?
>

Yes, a book can only be in one category at a time.


> Yes, this would be a pertinent question.  It sounds to me, though, from
> your post, that the basis of your categorization is "catalogue," not
> various features of the books themselves.
>

I'm not sure what you mean here

In my understanding that would no longer be a tree, but a graph

With a multiple-category scenario, as Chris suggests, what
> you have is a typical many-to-many relationship.  Click on a catalogue,
> and you might get a list of many books; click on a book, and many
> catalogues in the tree might light up.
>
> So, the functionality above might be what drives your design decision:
>
> 1) What is the basis of the categorization, the books themselves or the
> catalogues?

I can't answer that because I don't understand the question :)

> 2) Does a book appear in more than one catalogue?

No

> 3) Does each catalogue contain more than one book (I would assume so)?

Oh yes indeed
>
> It might just be that you're looking at a bag-to-bag implementation, not
> a tree.  But in a many-to-many relationship, an intermediate "table" has
> to map the many parent keys to the many child keys.  Unfortunately, I
> don't know what the best practice would be in Smalltalk or, more
> specifically, in Dolphin (I'm sure Chris does).  It would take the
> following form (note that Parent key and Child key should not be
> constrained to uniqueness):
>

Now "bag-to-bag implementation" I don't think applies here, but the idea
is also interesting.

That's also interesting, I must just say I have not observed that yet.

I think I need to look at this first in isolation

I.e. the catalogs are definitely a tree so the TreeModel/TreeNode could
apply to the catalogs.

But the books are things in their own right, from a books point of view
it is not relevant in which catalog it is in nor what that catalogs
position in the tree is.

So maybe I should use some other mechanism, a Librarian class maybe, for
the book catalog association.?



Günther

Günther,

> My application would also hold on to the root catalog.
>
> But in a way, this tree is also a collection, there are things that I
> want to do like >>detect: >>do: >>inject: for instance, in order to get
> the sum of the prices of the books or what not.

But if the tree holds both books and catalogs, you'll end up including the
price of the catalogs in the total.  You can hack around that (e.g. by making
catalogs have #price zero), but it might be awkward.  To me it seems better to
have special methods (not generic) like, say, catalog>>booksDo: and
catalog>>allBooksDo: (one recurses into sub-catalogs, the other doesn't), and
on top of those you can build methods like Catalog>>totalPrice,
Catalog>>booksWithISBN: and so on.

So, if you /do/ use a TreeModel (or a derivation) to hold your catalogs, then
the generic Collections-style methods would only iterate over the catalogs
themselves, not over the books they contain.

BTW, notice that TreeModel only has methods for iterating over the /whole/
collection, not for iterating over the collection below some specific branch.
I don't know if you need that functionality, but if you do then
TreeModel/TreeNode don't provide it for you.

    -- chris