From: Axel S. <A....@ke...> - 2005-11-28 11:27:11
|
Duncan, I'm a bit lost. On Mon, 2005-11-28 at 10:50 +0000, Duncan Coutts wrote: > On Sun, 2005-11-27 at 10:29 +0000, Axel Simon wrote: > > > Maybe we represent a TreeIter as a record of three integers and leave > > the implementation up to the model implementor. As a default for > > trees, I would suggest the following: > > > > We keep an array of entries for all nodes with the same prefix (in the > > TreePath sense). For example, given the tree with the indices: > > 0 > > 0.0 > > 0.1 > > 0.2 > > 0.2.0 > > 0.2.1 > > 0.3 > > 1 > > 1.0 > > 1.1 > > 1.2 > > > > we'd have four arrays: > > prefix = [], elements = [0, 1] > > prefix = [0], elements = [0.0, 0.1, 0.2, 0.3] > > prefix = [0,2], elements = [0.2.0, 0.2.1] > > prefix = [1], element = [1.0, 1.1, 1.2] Ok, let's call this array with the four elements the "prefix array" as you did below. > > Assuming that each row has the same type, we can type-safely create an > > array of arrays that contain these elements. To iterate over these, we > > only need to fields of the TreeIter: One for the outer array number > > (call it y), one for the inner (call it x). > > So this means we need axillary storage proportional to the size of the > tree right? And we have to construct these arrays on demand as we > explore the tree (so as not to force the evaluation of the whole tree > initially). Well, this was meant as an example implementation of a TreeModel. So when I wrote "element = [1.0, 1.1, 1.2]" I actually meant that the "1.0" stands for the data of element 1.0. Afterall, we need to actually store the data somewhere. So what I proposed was not just an indexing scheme but rather a way to implement the data base. If you'd want to implement an on-demand model, then you would have to insert and destroy these arrays on the fly. > > Implementing treeModelIterNext is trivial, since it only needs to > > increment the x field and check if it's still a valid entry. > > Checking if it's a valid entry takes log time doesn't it? Unless instead > of (or perhaps in addition to) the prefix & element arrays containing > indicies they contained the elements themselves. See above. Even if "element" is a plain list, you could store the length of the list separately and then test in O(1) if the next iterator exists. > I think the zipper > works that way, it uses a path of elements rather than a path of > offsets. Which zipper?! > > Implementing treeModelIterChildren and the like requires a search > > through the outer array if the current element has children. But that > > should be quick, > > I was thinking it'd be O(1) since you'd just lookup the y in the array > and then see if it has any children but actually it'd be O(log) because > we represent it by an entry for it's parent and an index below that. The function treeModelIterChildren should give me the following: input output complexity 0.1 0.2 (a) 0.2 0.2.0 (b) 0.2.0 0.2.1 (c) 0.2.1 0.3 (d) 0.3 1 (e) (a) lookup 0.1.0 in hash table, not there, increment last, check if 0.2 is larger than the length of the current array, no, ok (b) lookup 0.2.0 in hash table, found (c) like (a) (d) like (a), but 0.2.2 is out of bounds, lookup 0.3 in hash table, found (e) like (d), but 0.4 not in hash table, lookup 1 in hash table, found In summary, you might need several lookups in a hash table, but it's at most three times (child, sibling, ancestor), unless we can have an incomplete tree (i.e. 0.2 followed by 1.1.1.1, but I don't think that's allowed). > Since each interior node is represented in the array twice, once as a > child and once as a parent. I'm confused here. Each element is represented exactly once in my model. Again, my suggestion is a concrete implementation of a TreeModel which makes do with two integers for indexing. You could do it differently and maybe even have your indexing scheme rather than the two integers. I merely want to point out that you don't think you need such an complex indexing scheme. Maybe you can think of an example implementation with your indexing scheme, so that I can see that it has advantages over this one-array-per-level approach. Axel. |