Lazy hierarchical containers

Vaadin 6 / 7 / 8 Framework Data Binding
1

Hi,


Can a truly lazy, possibly infinitely deep container be implemented cleanly in Vaadin, and if so, how?


Context

I’m looking at how to implement a custom hierarchical container. I want to make a container that lazily builds its children. The item hierarchy can be infinitely deep, so there is no way to enumerate all the items.
If that seems like a far-fetched use-case, take the “variables” view in a debugger (e.g. Eclipse) as an example, where cyclic references also give an infinite tree.
A container that is just very (but not infinitely) deep, and tries to be lazy runs into the same problems.


Details

Some methods in the Container and its sub-interfaces bother me, because they simply cannot be implemented for such a container. It looks to me like they only make sense for a flat container, but Hierarchical extends Container, so there’s no way around them.
To start there’s Container.size() and Container.getItemIds(). It’s not explicit in the api docs, but looking at some of the implementations it looks like this is about all the items in the container, not just the roots.
The only way to implement those is to recursively go into each item, which is not only bad for performance (which, for example for FilesystemContainer, in a big directory structure it definitely is), but in an infinite tree simply impossible.
Strictly speaking, getItemIds()
could
 return an infinite Collection, but I don’t expect code that uses the Collection is going to deal with that properly.

To show the container in a tree, those methods shouldn’t be needed anyways. Letting those methods throw an exception works in my first tests, so they are indeed not called in practice. But it’s not a
right
 solution: there’s no guarantee that nothing is going to call them when combining them with other feature (say, expandItemsRecursively), or in a future version,… They are not optional methods like the ones that throw UnsupportedOperationException.

In fact, if I use such a container in a TreeTable, it already fails because that tries to wrap it in a HierarchicalContainerOrderedWrapper which calls getItemIds(). I can try to work around that by implementing Ordered myself, but then I’m just stuck with even more methods that are impossible to implement, such as lastItemId() and prevItemId(): both may require to go infinitely deep again.

Do I misunderstand something, or is it impossible to have infinite, or even just truly lazy hierarchical containers cleanly?

Thanks.

2

I’m not exactly sure what you are looking for, but it’s possible to create and remove tree items dynamically as the user expands or collapses a tree item, and in that way have infinitely large trees.

For example, combine:

[list]

[]

Node Expand Events
 with
[]

Node Collapse Events

[/list]The demo actually combines the two so you can open and close the tree infinitely.

3

The container interfaces do have quite a few methods that are not relevant in all cases - another common case is read-only containers that do have to implement many “empty” methods. We do want to improve the situation, but as some changes may break existing APIs, they will have to wait for the next major version. Other, non-breaking changes might come sooner.

The Tree component, I believe, does not need the “problematic” methods you mentioned, but a Table does - e.g. meaningful scroll bars for an infinitely sized container would pose problems. The TreeTable add-on is technically a Table with the hierarchy shown in the first column, so the underlying code does call some container methods the Tree component does not use.

The methods mentioned by Marko might also work in that case, although I don’t really know the internals of TreeTable. You can either remove and add the extra items of act as if they were filtered out - the two approaches are essentially the same. Only the visible items should be considered by (most of) the public methods of Container/Ordered/Indexed such as size() and lastItemId().

If you want to use your container in a Table (including a TreeTable), you should also implement Indexed, not only Ordered - otherwise, performance will suffer significantly.

As a related note, the current version of the ComboBox component also needs these getItemIds(), so it is not as lazy as it should be - there is a ticket to address this.

4

(Typed this answer yesterday before Henri’s answer, but the forum was down so posting it now as is)

I’m new to Vaadin, so maybe this comes from looking at the design
differently. I’m trying to apply a similar (MV(C/P)-like) approach as
I’ve seen in other UI toolkits.
To me, the container is the representation of (or the way for the
component to access) the data; so it’s the model. Changing the content
of the model because in the UI a different part of it is visible feels
wrong because:

  • The data behind doesn’t change when a user expands a node, so the
    container shouldn’t change (or send out events that claim it changed).
  • Multiple views should be able to use the same Container as
    dataSource without interfering with each other. I didn’t try it, but
    with the approach from that sample, if you have two trees, closing a
    node in one tree that’s also open in another one would make it
    suddenly disappear.
  • The classes providing the model should be separated from the view.
    The model shouldn’t be listening to the view (to the expand events),
    and the view shouldn’t be the one to fill the model (with already
    existing data).
  • Such things are not needed for flat containers either. For example
    you don’t add and remove items to a container because the view is
    scrolling.

Note that my container is not a copy of the data that has to be filled
before it can be used (like HierarchicalContainer) but an adapter to
access existing data (like FilesystemContainer, and the SQL and JPA
ones). I’m not saying it’s a bad sample, it just really doesn’t fit
with how I’d want to cleanly design a bigger application.

And I don’t think I’m on a wrong track here with my design, because it
seems the containers in Vaadin itself struggle with the same problem.
For example take a look at the implementation of FilesystemContainer’s
size() and rootItemIds(). To me that looks like methods the
FilesystemContainer doesn’t really “want” to implement, but has to
because it’s in the interface. Create a new FilesystemContainer(new
File(“/”)), use it in a tree, and it works because you’re
lucky

and those methods aren’t called. Use it in a treetable and it starts
recursively scanning the whole hard drive even if it just needs to
show the root.

I’m looking for a way to avoid those problems that doesn’t involve
just hoping nobody calls those methods (or being forced to write
containers as copies of data instead of interfaces to it).

5

I agree that it would be nicer if those weren’t there. But they aren’t such a big problem at all, because they’re clearly marked as optional methods. They’re expected to throw UnsupportedOperationExceptions. The java Collections framework does exactly the same. Methods where are not marked as optional, but
appear to be optional in certain situations
 are the problematic ones.

Btw, the Joda-time API is a good example for how to separate read from write-interfaces, with having “Readable*” interfaces, extended by writable ones. I suspect that could even (at least partly) be introduced without breaking backwards compatibility; adding a super-interface without adding methods is compatible. Just automatically wrap them in wrappers that throw UnsupportedOperationExceptions in cases where something that only reads is still expecting the full interface.

But in my opinion, the TreeTable shouldn’t call those methods. If it needs them it’s because of some implementation detail, not because of what it tries to accomplish. As long as nodes are not all expanded, the view isn’t infinite, so there should be no problem with scrollbars.

But the container doesn’t (or shouldn’t) know which ones are visible (see my previous comment).

I’m considering writing some base hierarchical containers (and maybe publishing them as addon) that allow you to implement one with a “cleaner” interface, but I’m not sure yet what the best way to do that is. I might take an approach similar to the samples (pointed out by Marko), having a Container that’s tied to the view and keeps a local copy of the part of the model that is visible (and sends events when the user is navigating), and delegates to a Container-alike-interface that is separate (and only sends events if the model really changed).

6

Marko,

I am also new to vaadin, but am looking at the millercolumns add-on, which leverages the hierarchical containers.

so, I’d like to use the miller columns add-on, as I like the way it gives a nice visual representation of the way the various pieces of data are related.

however, I’m very concerned about the amount of data that this would have to keep in memory on the server.


here is the bottom line:

I would much rather have scaling issues to do with the number of active users rather than the number of rows that a database contains.


here is some more detail:

if I go down this route, and the miller column contents per location in the hierarchy is actually based on the contents of a database table that could have many thousands of rows, would I have to pre-load all of those rows because the item in the hierarchy needed to be able to be represented? (keep in mind that the miller columns add-on presents a scrollable region within which to view / select the next item in the hierarchy from which to drill into the next layer down - do all of the actual rows have to be kept in memory? - I don’t believe they should have to be).

If the answer is ‘yes’, then there is a performance issue due to memory use.

I have played around with the lazy container add-on, and like the way that it essentially has a ‘window’ into the actual available data (somewhat like the table visually has) by way of judicious use of limit and ofset options on the sql queries - so, it only holds onto a minimal subset of the data that’s actually available. this is much more scaleable and supportable.

so the question is: can the hierarchical container be fed by a lazy/windowing container allowing me to use miller columns that retrieve/hold the bare minimum of data while giving the user the visual experience I’d like (ie: miller columns)?