Menu
▾
▴
gobo-eiffel-develop
|
From: Daniel T. <dan...@gm...> - 2008-04-22 21:35:41
Attachments:
binary_search_tree.tar.gz
|
Hi all I would like to know whether the Gobo community and developers are interested in a binary search tree implementation. Recently I needed it and was not happy with BINARY_SEARCH_TREE from ISE, so I had to build a new one. My implementation inherits from DS_TABLE and DS_BILINEAR. The implementation is NOT finished, I have to revisit every single line of code including the comments. If you are interested I would be happy to get some general feedback, such that I could take it into account when revisiting the code. Test cases are missing so far. Regards Daniel Tuser |
|
From: Colin A. <col...@go...> - 2008-04-23 19:28:24
|
On 22/04/2008, Daniel Tuser <dan...@gm...> wrote: > Hi all > I would like to know whether the Gobo community and developers are > interested in a binary search tree implementation. Recently I needed it and Personally, I've never had the need for one. But I think it would be a useful addition to the structure library. > My implementation inherits from DS_TABLE and DS_BILINEAR. The > implementation is NOT finished, I have to revisit every single line of code > including the comments. If you are interested I would be happy to get some > general feedback, such that I could take it into account when revisiting the > code. Test cases are missing so far. You would also need to write some general documentation in the gobodoc format. I've taken a fairly casual look. Generally it looks good. The one thing that does stand out is that it does not conform to the Gobo styling standards. I'm rather puzzled by this comment: " Direct instances should not be used in practice as the trees may become unbalanced." The class name (DS_BINARY_SEARCH_TREE) does not dictate balanced trees. Nor does there seem to be anything at first glance that requires the tree to be balanced. So perhaps you mean to say that creating direct instances is not advisable. (otherwise you could simply mark the class as deferred). In DS_BINARY_SEARCH_TREE_NODE, the assertion tags on the creation procedures don't read well to me: reuse_if_no_parent: parent = Void reuse_if_no_left_child: left_child = Void reuse_if_no_right_child: right_child = Void I don't understand what is going on here. Make is not used in the class except as a creation procedure, when the assertions are trivially True (nor do it seem to be used in the descendants). Some of the routines are too long to read on the screen. |
|
From: Daniel T. <dan...@gm...> - 2008-04-24 11:51:56
|
Colin Adams wrote: > You would also need to write some general documentation in the gobodoc format. > Ok. > I've taken a fairly casual look. Generally it looks good. > > The one thing that does stand out is that it does not conform to the > Gobo styling standards. > I know that the indexing clause does not conform to the Gobo styling standards so far. And the class name should be in the same line as the class keyword. Those are the two non-conforming things I know. Did you find more? > I'm rather puzzled by this comment: > > " Direct instances should not be used in practice as the trees may > become unbalanced." > > The class name (DS_BINARY_SEARCH_TREE) does not dictate balanced > trees. Nor does there seem to be anything at first glance that > requires the tree to be balanced. > > So perhaps you mean to say that creating direct instances is not > advisable. (otherwise you could simply mark the class as deferred). > You are right. "Not advisable" is much better. > In DS_BINARY_SEARCH_TREE_NODE, the assertion tags on the creation > procedures don't read well to me: > > reuse_if_no_parent: parent = Void > reuse_if_no_left_child: left_child = Void > reuse_if_no_right_child: right_child = Void > > I don't understand what is going on here. Make is not used in the > class except as a creation procedure, when the assertions are > trivially True (nor do it seem to be used in the descendants). > This kind of code is actually the reason why I have to check the whole code again. The design was not detailed when I started, as I just did not know what was needed such that also Red-Black- and AVL-Trees could reuse as much code as possible. So at certain positions it is not yet good enough. > Some of the routines are too long to read on the screen. > I don't like that as well. Those are the algorithms that could also be implemented as recursive features. I will see what I can do to improve that. But I will not make them recursive. A splitting into more features is also not easy as some features would require about 4 or 5 arguments. I was already working on that but stopped because the resulting code was not more readable. It could be done using attributes. But it would take some time. Do you think that has to be changed? Another minor improvement I am going to use is the "Performance: O(...)" comment as it is present in some Gobo classes. Thanks for your comment. |
|
From: Colin A. <col...@go...> - 2008-04-24 12:19:07
|
On 24/04/2008, Daniel Tuser <dan...@gm...> wrote: > > Some of the routines are too long to read on the screen. > > > > > I don't like that as well. Those are the algorithms that could also be > implemented as recursive features. I will see what I can do to improve that. > But I will not make them recursive. > A splitting into more features is also not easy as some features would > require about 4 or 5 arguments. I was already working on that but stopped > because the resulting code was not more readable. It could be done using > attributes. But it would take some time. > Do you think that has to be changed? I would say yes, provided there is no significant performance impact. I don't think passing 5 arguments is a reason not to do it, as the routines receiving 5 arguments are all secret. |
|
From: Colin A. <col...@go...> - 2008-04-24 12:25:09
|
On 24/04/2008, Daniel Tuser <dan...@gm...> wrote: > Colin Adams wrote: > I know that the indexing clause does not conform to the Gobo styling > standards so far. And the class name should be in the same line as the class > keyword. Those are the two non-conforming things I know. Did you find more? There area a load of empty feature clauses and a dummy invariant in at least one class. Then I dislike the absence of a blank line after create and inherit. Also I dislike seeing local variables with names that might class with attributes (and so forcing unnecessary renames in descendants). I personally now write all argument names as a_*, and all local names as either a single chanaracter or l_*. I am converting my existing code on a piecemeal basis. |
|
From: Daniel T. <dan...@gm...> - 2008-04-24 16:50:24
|
Colin Adams wrote: > There area a load of empty feature clauses and a dummy invariant in at > least one > class. > Done. > Then I dislike the absence of a blank line after create and inherit. > Done. > Also I dislike seeing local variables with names that might class with > attributes (and so forcing unnecessary renames in descendants). > I personally now write all argument names as a_*, and all local names > as either a single chanaracter or l_*. I am converting my existing > code on a piecemeal basis. > I like that suggestion and will do it like this. Colin Adams wrote: > On 24/04/2008, Daniel Tuser <dan...@gm...> wrote: > > > >>> Some of the routines are too long to read on the screen. >>> >> I don't like that as well. Those are the algorithms that could also be >> implemented as recursive features. I will see what I can do to improve that. >> But I will not make them recursive. >> A splitting into more features is also not easy as some features would >> require about 4 or 5 arguments. I was already working on that but stopped >> because the resulting code was not more readable. It could be done using >> attributes. But it would take some time. >> Do you think that has to be changed? >> > > I would say yes, provided there is no significant performance impact. > > I don't think passing 5 arguments is a reason not to do it, as the > routines receiving 5 arguments are all secret. > 5 arguments are no reason, I share that point of view. At the end it has to be readable and understandable. I am just not sure if that is achieved by splitting the features. But I will certainly try it. In the Gobo documentation "author" is used in the indexing clause, but most Gobo classes do not have it. So I won't use it. I have several multi-line "description"s in the indexing clause that are enclosed in "[ ]". Should I use % as seen e.g. in DS_SPARSE_TABLE? |
|
From: Eric B. <er...@go...> - 2008-04-24 21:41:30
|
Daniel Tuser wrote: > In the Gobo documentation "author" is used in the indexing clause, but > most Gobo classes do not have it. So I won't use it. No need for "author". > I have several multi-line "description"s in the indexing clause that are > enclosed in "[ ]". Should I use % as seen e.g. in DS_SPARSE_TABLE? You can use "[ ]". -- Eric Bezault mailto:er...@go... http://www.gobosoft.com |
|
From: Colin A. <col...@go...> - 2008-04-26 05:21:16
|
2008/4/24 Daniel Tuser <dan...@gm...>: > I know that the indexing clause does not conform to the Gobo styling > standards so far. And the class name should be in the same line as the class > keyword. Those are the two non-conforming things I know. Did you find more? Also there were several routines without a header comment. |
|
From: Daniel T. <dan...@gm...> - 2008-05-01 08:12:53
Attachments:
binary_search_tree.tar.gz
|
The test cases for binary search trees are now written. The attachment also contains some modifications. I've got a proposals for the class hierarchy of the DS_* classes. I would like to have DS_BILINEAR_TABLE and DS_BILINEAR_SET. And DS_SPARSE_TABLE inherits DS_BILINEAR_TABLE and DS_SPARSE_SET inherits DS_BILINIEAR_SET. In the attachment the binary search tree implementation already uses DS_BILINEAR_TABLE. In my opinion it makes sense to have a common ancestor for hash table and binary search trees that has both the table and cursor features. I am working on a set implementation based on binary search trees. That is why I would like to have DS_BILINEAR_SET as well. I am trying to make it very much like hash table and hash set. The goal is actually to get an abstraction of binary search tree that can be reused for the set implementation. Feedback is still welcome. Colin, are the features still too long? |
|
From: Colin A. <col...@go...> - 2008-05-01 09:08:36
|
On 01/05/2008, Daniel Tuser <dan...@gm...> wrote: > Feedback is still welcome. Colin, are the features still too long? They are fine now. I was a bit surprised to see you have been working on some of these classes for nine years now. Of course they do require some careful thought, but I would think you might be a little quicker than that. :-) (Copyright 2000 - 2008 - change to Copyright 2008, I would think. ) Eric will have to answer your other points. |
|
From: Daniel T. <dan...@gm...> - 2008-05-01 10:41:51
|
Colin Adams wrote: > On 01/05/2008, Daniel Tuser <dan...@gm...> wrote: > > >> Feedback is still welcome. Colin, are the features still too long? >> > > They are fine now. > > I was a bit surprised to see you have been working on some of these > classes for nine years now. Of course they do require some careful > thought, but I would think you might be a little quicker than that. > :-) > > (Copyright 2000 - 2008 - change to Copyright 2008, I would think. ) > > Ok :-) |
|
From: Eric B. <er...@go...> - 2008-05-01 14:07:26
|
Colin Adams wrote: > Eric will have to answer your other points. I'll try to have a look at it today. If I don't have time to do so, then it will have to wait until next Tuesday as I will be away from my computer during the coming days. -- Eric Bezault mailto:er...@go... http://www.gobosoft.com |
|
From: Colin P. A. <co...@co...> - 2008-05-16 17:18:53
|
Daniel, Mark Howard (ECMA committee member and boss of Eric, Franck and myself at AXA Rosenberg) has expressed an interest in Sedgewick's recently introduced left-leaning red-black trees. You might want to add these too (I googled and found quite a few hits, so I think there is sufficient information available). -- Colin Adams Preston Lancashire |
|
From: Daniel T. <dan...@gm...> - 2008-05-18 15:30:47
|
Colin Paul Adams wrote: > Daniel, > > Mark Howard (ECMA committee member and boss of Eric, Franck and myself > at AXA Rosenberg) has expressed an interest in Sedgewick's recently > introduced left-leaning red-black trees. You might want to add these > too (I googled and found quite a few hits, so I think there is > sufficient information available). > Left-leaning red-black trees are very interesting. Now that Sedgewick updated his slides, it should be straight forward to implement at least the extend/put feature, based on the binary search tree classes. But such an implementation has the drawback of using a parent attribute in the tree nodes, whereas that is not required for left-leaning red-black trees. On the other hand I am not sure if there could be a satisfying implementation without a parent attribute in the nodes. I will try to implement them in the next week(s), as soon as I have enough time. It will be interesting to see, if it is as simple as Sedgewick says. I am skeptic that it is faster due to the smaller code size. |
|
From: Daniel T. <dan...@gm...> - 2008-05-27 08:13:26
|
Colin Paul Adams wrote: > Daniel, > > Mark Howard (ECMA committee member and boss of Eric, Franck and myself > at AXA Rosenberg) has expressed an interest in Sedgewick's recently > introduced left-leaning red-black trees. You might want to add these > too (I googled and found quite a few hits, so I think there is > sufficient information available). > Left-leaning red-black trees are now implemented. It was surprising that they are slower than red-black and avl trees. In some random benchmarks avl and red-black trees show nearly the same performance, whereas plain binary search trees are a few percents slower. Left-leaning red-black trees are at least 50% slower than avl and red-black trees. The benchmark tests only put and delete. I have to finish the test cases and check a few classes again. It should be possible to publish the code this week. |
|
From: Daniel T. <dan...@gm...> - 2008-05-30 15:14:44
Attachments:
binary_search_tree.tar.gz
|
My todo list for the binary search trees is now empty. From my point of view it is ready to be released if no one finds weaknesses in the code. The documentation and some examples are missing. There are no xml files for table.html and set.html yet. So I assume that I need to be translated them into xml files first (gobodoc format). Or is there another location where the xml files are? |
|
From: Eric B. <er...@go...> - 2008-05-30 17:11:42
|
Daniel Tuser wrote: > My todo list for the binary search trees is now empty. From my point of > view it is ready to be released if no one finds weaknesses in the code. > The documentation and some examples are missing. > There are no xml files for table.html and set.html yet. So I assume that > I need to be translated them into xml files first (gobodoc format). Or > is there another location where the xml files are? The doc for the structure library was used as a proof of concept for the gobodoc format. The doc was initially written in html, and I wanted to make sure that it was possible to write the doc in gobodoc format and then produce html files that look like the original. That's where the .xml files come from. But the doc for the structure library was never fully translated into the gobodoc format, so I think that the most up-to-date files are the .html files. You should probably use these .html files for the time being. -- Eric Bezault mailto:er...@go... http://www.gobosoft.com |
|
From: Eric B. <er...@go...> - 2008-07-06 17:04:22
|
Daniel Tuser wrote: > My todo list for the binary search trees is now empty. From my point of > view it is ready to be released if no one finds weaknesses in the code. I'm currently looking at integrating your classes into Gobo and I'm wondering whether I can make some modifications first. For example, when I see the name of this class: DS_ABSTRACT_COMMON_RED_BLACK_TREE, I said "Wow!". In Gobo we try to avoid using "ABSTRACT" (all deferred classes are abstract, so it does not give that much information about the class). And "COMMON" does not give that much help either. From what I can see, you have sets and tables implemented with various binary search tree algorithms. In Gobo we already have DS_SPARSE_CONTAINER with the descendants DS_SPARSE_TABLE and DS_SPARSE_SET. I think that's what you tried to do with your "COMMON" classes. So instead of DS_COMMON_BINARY_SEARCH_TREE I suggest DS_BINARY_SEARCH_TREE_CONTAINER, with the indexing clause: "Containers using binary search tree algorithms". Then you have two descendants: the set version DS_BINARY_SEARCH_TREE_SET and the table version DS_BINARY_SEARCH_TREE (for which we don't put the suffix _TABLE because this container is commonly known without it). And use the same naming convention for all binary search tree algorithms. Now, trying to get rid of "ABSTRACT", I wonder why we cannot have DS_LEFT_LEANING_RED_BLACK_TREE that inherits from DS_RED_BLACK_TREE (instead of having this "ABSTRACT" common ancestor). If this is OK, I can do the renaming as well as making sure that the header comments follow the Eiffel style guidelines while integrating the classes in Gobo. -- Eric Bezault mailto:er...@go... http://www.gobosoft.com |
|
From: Eric B. <er...@go...> - 2008-07-18 17:14:23
|
Hi Daniel, Is there a reason why `void_is_valid_key' is False in DS_BINARY_SEARCH_TREE? For example in DS_HASH_TABLE it is possible to have void keys. And the algorithms seem to work with void anyway since `void_is_valid_key' is True in DS_BINARY_SEARCH_TREE_SET. I think that it would make the interface simplier if we could get rid of this feature `void_is_valid_key'. Apart from that, I still need to improve one thing and then it will be ready to be committed in SVN. The problem is with `equality_tester'. This is assumed to be used in many places. Just look at the header comments of `is_subset', `interset', etc. in DS_BINARY_SEARCH_TREE_SET. But in fact it uses KL_COMPARATOR.order_equal. I'm currently trying to use the KL_COMPARATOR as if it was a KL_EQUALITY_TESTER of `equality_tester' (in other words `comparator' and `equality_tester' would be the same object). -- Eric Bezault mailto:er...@go... http://www.gobosoft.com |
|
From: Daniel T. <dan...@gm...> - 2008-07-19 10:13:56
|
Eric Bezault wrote: > Hi Daniel, > > Is there a reason why `void_is_valid_key' is False > in DS_BINARY_SEARCH_TREE? For example in DS_HASH_TABLE > it is possible to have void keys. And the algorithms > seem to work with void anyway since `void_is_valid_key' > is True in DS_BINARY_SEARCH_TREE_SET. I think that it > would make the interface simplier if we could get rid > of this feature `void_is_valid_key'. I will have a closer look at it as I have more time next week. If it works in the void case too, you probably found an artifact I missed. > Apart from that, I still need to improve one thing and > then it will be ready to be committed in SVN. The > problem is with `equality_tester'. This is assumed to > be used in many places. Just look at the header comments > of `is_subset', `interset', etc. in DS_BINARY_SEARCH_TREE_SET. > But in fact it uses KL_COMPARATOR.order_equal. I'm currently > trying to use the KL_COMPARATOR as if it was a > KL_EQUALITY_TESTER of `equality_tester' (in other words > `comparator' and `equality_tester' would be the same > object). When the implementation started, it was actually just one object. I had to split it because some problems with void tests. It made the work easier. I didn't change it because it worked. But it is certainly cleaner, if there is just one such object. |
|
From: Eric B. <er...@go...> - 2008-07-19 16:21:12
|
Daniel Tuser wrote: > Eric Bezault wrote: >> Hi Daniel, >> >> Is there a reason why `void_is_valid_key' is False >> in DS_BINARY_SEARCH_TREE? For example in DS_HASH_TABLE >> it is possible to have void keys. And the algorithms >> seem to work with void anyway since `void_is_valid_key' >> is True in DS_BINARY_SEARCH_TREE_SET. I think that it >> would make the interface simplier if we could get rid >> of this feature `void_is_valid_key'. > I will have a closer look at it as I have more time next week. If it > works in the void case too, you probably found an artifact I missed. I just wrote test cases and it works fine. -- Eric Bezault mailto:er...@go... http://www.gobosoft.com |
|
From: Eric B. <er...@go...> - 2008-07-20 19:47:35
|
Hi Daniel, Your binary search tree classes are now committed to SVN in the SourceForge Gobo project. As agreed, I made some name changes and some header comments and reformatting to better match Gobo's style guildelines. I also removed the unnecessary `void_is_valid_key' and merged `equality_tester' with `comparator'. I probably did some other minor changes, such as making sure that "key" features are not exported in the set classes (set classes don't have the notion of keys in their interface). I didn't review the binary search tree algorithms. But I think that some improvements can be made. For example, would it be possible to redefine `cursor_search_forth' and `cursor_search_back' in DS_BINARY_SEARCH_TREE_SET, to take advantage that the items are sorted, and hence avoid linear traversal? Also, I think that `internal_put' and `internal_put_new' deserve some postconditions that should match those of DS_SET and DS_TABLE so that when they are used to implement the corresponding features in set and table variants the code is correct in terms of DbC. -- Eric Bezault mailto:er...@go... http://www.gobosoft.com |
|
From: Daniel T. <dan...@gm...> - 2008-08-05 22:17:24
|
Hi Eric, I was very busy during the last weeks. As soon as I find some time, I will have a look at the classes once again to make some more improvements, as the one you mentioned. Regards, Daniel Eric Bezault wrote: > Hi Daniel, > > Your binary search tree classes are now committed to SVN in > the SourceForge Gobo project. As agreed, I made some name > changes and some header comments and reformatting to better > match Gobo's style guildelines. I also removed the unnecessary > `void_is_valid_key' and merged `equality_tester' with `comparator'. > I probably did some other minor changes, such as making sure > that "key" features are not exported in the set classes > (set classes don't have the notion of keys in their interface). > > I didn't review the binary search tree algorithms. But I think > that some improvements can be made. For example, would it be > possible to redefine `cursor_search_forth' and `cursor_search_back' > in DS_BINARY_SEARCH_TREE_SET, to take advantage that the items > are sorted, and hence avoid linear traversal? > > Also, I think that `internal_put' and `internal_put_new' deserve > some postconditions that should match those of DS_SET and DS_TABLE > so that when they are used to implement the corresponding features > in set and table variants the code is correct in terms of DbC. > |
|
From: Daniel T. <dan...@gm...> - 2008-05-06 06:44:22
Attachments:
binary_search_tree.tar.gz
|
The two classes DS_BILINEAR_TABLE an DS_BILINEAR_SET are now integrated in the binary search tree implementation. They would be useful in my opinion. For the case that you do not want them, it is not hard to remove them from the implementation. Just to make it clear, the binary search tree implementation is still not finished. There is still at least one bug and I didn't test it extensively. |
|
From: Eric B. <er...@go...> - 2008-05-07 12:11:57
|
Daniel Tuser wrote: > Just to make it clear, the binary search tree implementation is still > not finished. There is still at least one bug and I didn't test it > extensively. In that case, I suggest that I release a new version of Gobo first. Then I will have more time to review your code and see how to best integrate it with the existing classes. -- Eric Bezault mailto:er...@go... http://www.gobosoft.com |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X