From: Till A. <ti...@ad...> - 2001-12-31 14:11:24
|
Hey folks, I just commited some changes to etox. The obstacle algorithm is now much simpler than the old one and fixes a few corner cases that didnt work properly (obstacles partly off the etox for example). I added comments and rephrased some existing ones. There are still a few things I'd like to simplify/clean up, but I'd like for the maintainers to look at it first, and see if they can live with the changes I made. I tested this with ewl, which seems to be the only thing using etox right now and it didnt break anything there. So Adam, redalb, blader, is that cool with you? If not, feel free to revert. Thanks and a happy new year to all of you, Till -- mailto: ti...@ad... http://www.adam-lilienthal.de/till |
From: Marc C. S. <re...@ds...> - 2001-12-31 15:20:06
|
Hi guys. What kind of trees are you implementing on EWD? If you are implementing trees over dinamic memory (not arrays), you can use an hybrid of AVL and threaded trees (AVL: from G.M.Andel'son-Vel'skii & E.M.Landis, @1962. threaded trees: A.J.Perlis & C.Thomson, @1960, published in Comunications ACM). This kind of hybrid trees solve the next problems: - Insertion, Supression, Search operations in O(log N) cost ever (AVL properities). - Copy of a tree in O(N) cost ever. - Use the tree as an sorted double-linked list recicling the unused pointers of lower nodes: on dinamic memory, more than half part of the struct pointers are unused because this pointers are from terminal nodes (number of terminal nodes in a height balanced tree is N/2). I implemented this structure in C++ succesfully and, if you want, I can help you to do it to E17. That's my especification and assimptotic cost, where: O(1) it's a constant cost (not depends of the number of elements stored in the structure). O(log N) logaritmic cost ('N' is the number of elements in the structure) O(N) linear cost (proportional cost) O(N^2) quadratic cost (exponential) // Default constructor tree::tree(); O(1) // Tipical operations on trees void tree::add(id,elem); O(log N) void tree::del(id); O(log N) bool tree::search(id); O(log N) elem& tree::get(id) // Operations on lists void tree::setOnElem(id); O(log N) void tree::begin(); O(1) void tree::end(); O(1) void tree::next(); O(1) void tree::prev(); O(1) elem& tree::getElem(); O(1) // Struct global operations tree& tree::copy(tree); O(N) tree& tree::=(tree); O(N) int tree::numberOfElems(); O(1) Bye, Ren |
From: Nathan I. <ningerso@d.umn.edu> - 2001-12-31 19:51:10
|
On Mon, 31 Dec 2001, Marc Clausell Samitier wrote: > Hi guys. > > What kind of trees are you implementing on EWD? > > If you are implementing trees over dinamic memory (not arrays), you can use > an hybrid of AVL and threaded trees (AVL: from G.M.Andel'son-Vel'skii & > E.M.Landis, @1962. threaded trees: A.J.Perlis & C.Thomson, @1960, published > in Comunications ACM). We are using an AVL tree implementaion. Although I'm sure it could use some cleanup since, at the time I wrote it, I had no reference to existing AVL tree implementations, and wrote it purely from a description of the AVL ideas. > This kind of hybrid trees solve the next problems: > - Insertion, Supression, Search operations in O(log N) cost ever (AVL > properities). > - Copy of a tree in O(N) cost ever. > - Use the tree as an sorted double-linked list recicling the unused pointers > of lower nodes: on dinamic memory, more than half part of the struct pointers > are unused because this pointers are from terminal nodes (number of terminal > nodes in a height balanced tree is N/2). > > I implemented this structure in C++ succesfully and, if you want, I can help > you to do it to E17. I'm hoping to do some significant changes to ewd and this seems to fit in with what I had in mind. If you would like to help implement it, I would appreciate it as my time is stretched a bit thin at the moment. Feel free to contact me via the list, personal email, or on irc.openprojects.net (nick RbdPngn) if you have questions, concerns, or just want to discuss design issues. Thanks! --------------------------------------------------------------------------- | Nathan Ingersoll | Computer Science/Mathematics | | mailto: ningerso@d.umn.edu | University of Minnesota-Duluth | | http://umn.edu/~ningerso | http://www.d.umn.edu | --------------------------------------------------------------------------- |
From: Marc C. S. <re...@ds...> - 2001-12-31 22:26:21
|
On Mon, 31 Dec 2001, Nathan Ingersoll wrote: > On Mon, 31 Dec 2001, Marc Clausell Samitier wrote: > > > Hi guys. > > > > What kind of trees are you implementing on EWD? > > > > If you are implementing trees over dinamic memory (not arrays), you can use > > an hybrid of AVL and threaded trees (AVL: from G.M.Andel'son-Vel'skii & > > E.M.Landis, @1962. threaded trees: A.J.Perlis & C.Thomson, @1960, published > > in Comunications ACM). > > We are using an AVL tree implementaion. Although I'm sure it could use some > cleanup since, at the time I wrote it, I had no reference to existing AVL > tree implementations, and wrote it purely from a description of the AVL > ideas. Perfect! Adapt your AVL struct to an hybrid threaded AVL is very easy. Just add a boolean variable to each pointer (in the node definition) to determine if a pointer is being reused or have a normal function. Example: struct node { type_info info; (struct node)* leftPointer; (struct node)* rightPointer; char balancingFactor; // PERFECT, RIGHT_BALANCED, LEFT_BALANCED bool isThreadLeftPointer; bool isThreadRightPointer; }; Of course, adapt the "double-linked" operations to the AVL basic structure is not a trivial step, but only must modify (internaly) a recursive AVL insertion function. As soon as possible I will send you the complete operations implemented in C++ and a justification/demostration of the assimptotic cost and right especification (I must translate it, and I need time to do it). > > This kind of hybrid trees solve the next problems: > > - Insertion, Supression, Search operations in O(log N) cost ever (AVL > > properities). > > - Copy of a tree in O(N) cost ever. > > - Use the tree as an sorted double-linked list recicling the unused pointers > > of lower nodes: on dinamic memory, more than half part of the struct pointers > > are unused because this pointers are from terminal nodes (number of terminal > > nodes in a height balanced tree is N/2). > > > > I implemented this structure in C++ succesfully and, if you want, I can help > > you to do it to E17. > I'm hoping to do some significant changes to ewd and this seems to fit in > with what I had in mind. If you would like to help implement it, I would > appreciate it as my time is stretched a bit thin at the moment. Feel free to > contact me via the list, personal email, or on irc.openprojects.net (nick > RbdPngn) if you have questions, concerns, or just want to discuss design > issues. We will be in contact. Thanks! |