digitalmars.D.learn - Equivilent of STL Set in D ? ...
- clayasaurus (12/12) Oct 18 2006 Hello, I am converting some C++ code which happens to use STL Set to D.
- Sean Kelly (11/22) Oct 18 2006 No. D's associative array is implemented as a hash table, which is
- clayasaurus (6/29) Oct 18 2006 Alright, since Set is a sorted associative container, I mistakenly
- KlausO (4/9) Oct 19 2006 Nova contains an intrusive red/black tree implementation:
- clayasaurus (3/16) Oct 19 2006 Sounds interesting... I posted some questions on your forum. Thanks.
- Walter Bright (15/25) Oct 20 2006 Looks like you've already done it! It seems a little complex to use,
- KlausO (9/28) Oct 21 2006 That's because it's the intrusive form of a red black tree.
- KlausO (25/30) Oct 22 2006 Ok, I rewrote the intrusive version to a nonintrusive one.
- clayasaurus (12/924) Oct 23 2006 Yes, thank you! I'll give it a try when I get the chance. I really
- KlausO (3/20) Oct 23 2006 Walter suggested it in a previous post. I think he wanted the same
- clayasaurus (2/23) Oct 23 2006 Oh, alright :)
- clayasaurus (7/38) Oct 23 2006 This is a lot better than returning an empty node, though. If you can
- clayasaurus (7/23) Oct 19 2006 Suppose that I don't need sorting, would an associative array work just
- Lutger (5/30) Oct 19 2006 iirc stl's map are sorted too, and also use rb-tree usually as
- Walter Bright (5/8) Oct 20 2006 C++'s balanced binary trees are red-black trees. I had just proposed
- BLS (377/388) Oct 23 2006 http://www.cs.fiu.edu/~weiss/dsj3/code/weiss/nonstandard/RedBlackTree.ja...
- BLS (6/9) Oct 23 2006 Hi algorithm fans, maybe you can help a bit. I own the Algorithms and
- Sean Kelly (12/23) Oct 23 2006 Personally, I like Sedgewick's "Algorithms in C++" series the best. And...
- BLS (21/35) Oct 23 2006 Thanks for your answere Sean,
- Sean Kelly (15/18) Oct 23 2006 I find Sedgewick to be quite readable, but his material is a bit more
- BLS (11/36) Oct 23 2006 Thanks for your inside view.
Hello, I am converting some C++ code which happens to use STL Set to D. I was thinking of ways to implement set in D, but since I never got much into STL set in C++ I want to make sure I am thinking right. 1) Are D's associative arrays equivalent to STL Set? I've read that Set is pretty much just a sorted associative array, can this functionality be achieved in D (using struct as a key type) by overloading opCmp? 2) I suppose I could implement this as a sorted linked list. As far as I can tell set is only being used to hold a collection of elements that are sorted in a certain way. 3) Use DTL's implementation of set. Thanks. ~ Clay
Oct 18 2006
clayasaurus wrote:Hello, I am converting some C++ code which happens to use STL Set to D. I was thinking of ways to implement set in D, but since I never got much into STL set in C++ I want to make sure I am thinking right. 1) Are D's associative arrays equivalent to STL Set? I've read that Set is pretty much just a sorted associative array, can this functionality be achieved in D (using struct as a key type) by overloading opCmp?No. D's associative array is implemented as a hash table, which is unordered by nature. If you require the elements to be sorted you'll either have to use a different container or copy the values to an array and sort the array before doing whatever you want to do with the sorted values. The word count example does this, for example.2) I suppose I could implement this as a sorted linked list. As far as I can tell set is only being used to hold a collection of elements that are sorted in a certain way.The C++ set is implemented as a balanced binary tree, and some sort of binary tree is probably your best bet if you want a sorted container with decent lookup performance.3) Use DTL's implementation of set.Definitely an option. Sean
Oct 18 2006
Sean Kelly wrote:clayasaurus wrote:Alright, since Set is a sorted associative container, I mistakenly thought it had something to do with an associative arrays.Hello, I am converting some C++ code which happens to use STL Set to D. I was thinking of ways to implement set in D, but since I never got much into STL set in C++ I want to make sure I am thinking right. 1) Are D's associative arrays equivalent to STL Set? I've read that Set is pretty much just a sorted associative array, can this functionality be achieved in D (using struct as a key type) by overloading opCmp?No. D's associative array is implemented as a hash table, which is unordered by nature. If you require the elements to be sorted you'll either have to use a different container or copy the values to an array and sort the array before doing whatever you want to do with the sorted values. The word count example does this, for example.Thanks for the info, so all I have to do is create a balanced binary tree with a foreach iterator? :) Seems simple enough. ~ Clay2) I suppose I could implement this as a sorted linked list. As far as I can tell set is only being used to hold a collection of elements that are sorted in a certain way.The C++ set is implemented as a balanced binary tree, and some sort of binary tree is probably your best bet if you want a sorted container with decent lookup performance.
Oct 18 2006
clayasaurus wrote:Thanks for the info, so all I have to do is create a balanced binary tree with a foreach iterator? :) Seems simple enough. ~ ClayNova contains an intrusive red/black tree implementation: http://www.dsource.org/projects/nova/browser/trunk/NOVA/DS/intrusive/redblacktree.d Klaus
Oct 19 2006
clayasaurus <clayasaurus gmail.com> KlausO wrote:clayasaurus wrote:Sounds interesting... I posted some questions on your forum. Thanks. ~ ClayThanks for the info, so all I have to do is create a balanced binary tree with a foreach iterator? :) Seems simple enough. ~ ClayNova contains an intrusive red/black tree implementation: http://www.dsource.org/projects/nova/browser/trunk/NOVA/DS/intr sive/redblacktree.d Klaus
Oct 19 2006
KlausO wrote:clayasaurus wrote:Looks like you've already done it! It seems a little complex to use, however. It shouldn't be necessary to define new classes/structs in order to use it. I should be able to just: import whatever.redblacktree; RedBlackTree(char[], int) foo; // create a red-black tree with key type of char[] and value type of int. ... foo["hello"] = 3; foo["betty"] = 25; bar(foo["hello"]); // bar(3) foo.remove("betty")); ... foreach (v; foo) writefln("value is %s", v);Thanks for the info, so all I have to do is create a balanced binary tree with a foreach iterator? :) Seems simple enough. ~ ClayNova contains an intrusive red/black tree implementation: http://www.dsource.org/projects/nova/browser/trunk/NOVA/DS/intr sive/redblacktree.d
Oct 20 2006
Walter Bright wrote:Looks like you've already done it! It seems a little complex to use, however. It shouldn't be necessary to define new classes/structs in order to use it.That's because it's the intrusive form of a red black tree. Clay had some questions about them I tried to answer: http://www.dsource.org/forums/viewtopic.php?t=1959I should be able to just: import whatever.redblacktree; RedBlackTree(char[], int) foo; // create a red-black tree with key:-) I guess you meant RedBlackTree!(char[], int) foo;type of char[] and value type of int. ... foo["hello"] = 3; foo["betty"] = 25; bar(foo["hello"]); // bar(3) foo.remove("betty")); ... foreach (v; foo) writefln("value is %s", v);Seems to be an interesting task to get used to the new foreach features. I'll give it a try. Klaus
Oct 21 2006
KlausO wrote:Seems to be an interesting task to get used to the new foreach features. I'll give it a try. KlausOk, I rewrote the intrusive version to a nonintrusive one. It has almost the interface you mentioned. Please note: IMHO, there are some points where the template needs some refinement. 1. A third template parameter "bool duplicatesAllowed" should be added and handled in insert/remove via "static if". Then you have multisets at hand ! 2. Sometimes it exposes an interface to the internally used nodes to be able to access the key/value pairs. A special iterator class which could encapsulate the "not found/not inserted" state would be better. 3. The insert via opIndexAssign/find via opIndex is IMHO not optimal because you could not return the "not found/not inserted" state. There are some possibilities to resolve this: a) Throw an exception (IMHO, ugly) b) Return an empty node c) ... any ideas ? Using insert like if (foo.insert("Jill", 13)) looks better to me. Ok, thats it for now. Maybe I find some spare time next week to adress some of the issues. Greets Klaus
Oct 22 2006
KlausO wrote:KlausO wrote:Yes, thank you! I'll give it a try when I get the chance. I really didn't want an intrusive tree. Looks like you have an interesting interface too, although why not have an interface like... RedBlackTree!(int) tree; tree.add(4); tree.add(3); tree.add(7); tree.remove(7); int b = tree.find(7); ? Just wondering how you came up with the interface :) ~ ClaySeems to be an interesting task to get used to the new foreach features. I'll give it a try. KlausOk, I rewrote the intrusive version to a nonintrusive one. It has almost the interface you mentioned. Please note: IMHO, there are some points where the template needs some refinement. 1. A third template parameter "bool duplicatesAllowed" should be added and handled in insert/remove via "static if". Then you have multisets at hand ! 2. Sometimes it exposes an interface to the internally used nodes to be able to access the key/value pairs. A special iterator class which could encapsulate the "not found/not inserted" state would be better. 3. The insert via opIndexAssign/find via opIndex is IMHO not optimal because you could not return the "not found/not inserted" state. There are some possibilities to resolve this: a) Throw an exception (IMHO, ugly) b) Return an empty node c) ... any ideas ? Using insert like if (foo.insert("Jill", 13)) looks better to me. Ok, thats it for now. Maybe I find some spare time next week to adress some of the issues. Greets Klaus ------------------------------------------------------------------------ ////////////////////////////////////////////////////////////////////////// /** Autors: Klaus Oberhofer License: use it for your own purpose *///////////////////////////////////////////////////////////////////////// module redblacktree; enum NodeColor { RedNode = 0, BlackNode = 1 }; ////////////////////////////////////////////////////////////////////////// /** Red/black tree implementation. *///////////////////////////////////////////////////////////////////////// class RedBlackTree(KeyType, ValueType) { public: /// TreeNode type used to form red/black tree static class TreeNode { package: TreeNode left; TreeNode right; NodeColor color; KeyType key; ValueType value; package: this(KeyType key, ValueType value) { this.key = key; this.value = value; left = right = null; color = NodeColor.RedNode; } public: KeyType nkey() { return this.key; } ValueType nvalue() { return this.value; } } private: // The PtrPack struct is used to to save function-calling overhead struct PtrPack { TreeNode t; // The current node TreeNode p; // Parent TreeNode g; // Grandparent TreeNode gg; // Great Grandparent TreeNode s; // Sibling TreeNode rs; // Right children of s TreeNode ls; // Left children of s TreeNode m; // Matching node TreeNode pm; // Parent of matching node }; // the tree root TreeNode root; // Helper functions static TreeNode InsBalance (TreeNode tree, PtrPack pp) { TreeNode cofgg; // New child of great-grandparent int side; side = pp.gg && pp.gg.right is pp.g; if (pp.g.left is pp.p) { if (pp.p.right is pp.t) { // Do double rotate pp.g.left = pp.t.right; pp.t.right = pp.g; pp.p.right = pp.t.left; pp.t.left = pp.p; pp.p = pp.gg; cofgg = pp.t; } else { // Do single rotate right pp.g.left = pp.p.right; pp.p.right = pp.g; cofgg = pp.p; } } else { // pp.g.right is pp.p if (pp.p.left is pp.t) { // Do double rotate pp.g.right = pp.t.left; pp.t.left = pp.g; pp.p.left = pp.t.right; pp.t.right = pp.p; pp.p = pp.gg; cofgg = pp.t; } else { // Do single rotate left pp.g.right = pp.p.left; pp.p.left = pp.g; cofgg = pp.p; } } cofgg.color = NodeColor.BlackNode; pp.g.color = NodeColor.RedNode; if (pp.gg) { if (side) pp.gg.right = cofgg; else pp.gg.left = cofgg; } else tree = cofgg; return tree; } static TreeNode DoReplacement(TreeNode tree, PtrPack pp) { // At this point, pp.m is the node to delete, pp.pm is it's parent, // pp.p is the replacement node, pp.g is it's parent. If pp.m has no // successor, pp.p will = pp.m, and replacement is the non-null // child of pp.m. if (pp.m) { // Matching node was found if (pp.p is pp.m || pp.m.left is null || pp.m.right is null) { // No successor, and/or at least one child null // Get non-null child, if any, else pp.p will be null pp.p = (pp.m.left) ? pp.m.left : pp.m.right; } else { // pp.m has a successor to use as a replacement if (pp.g !is pp.m) { // Successor is not immediate child of pp.m, so detach // from where it is, attach to where pp.m is pp.g.left = pp.p.right; pp.p.right = pp.m.right; } // Finish attaching where pp.m is. pp.p.left = pp.m.left; } // pp.p should have same color as pp.m since it's going where pp.m was if (pp.p) pp.p.color = pp.m.color; } // Fixup pp.pm child link to be pp.p if (pp.m) { if (pp.pm) { if (pp.pm.left is pp.m) pp.pm.left = pp.p; else pp.pm.right = pp.p; } else tree = pp.p; // New root, possibly null } return tree; } static TreeNode DelBalance (TreeNode tree, PtrPack pp) { if ((pp.t is null || pp.t.color == NodeColor.BlackNode) && pp.s !is null && pp.s.color == NodeColor.RedNode) { // Case: pp.t is black, pp.s red. pp.t might be null, // but pp.s and pp.p must not be. // Fix pp.g child to be pp.s. Also pp.s may become pp.p of pp.m if (pp.g) { if (pp.g.left is pp.p) pp.g.left = pp.s; else pp.g.right = pp.s; } else tree = pp.s; if (pp.p is pp.m) pp.pm = pp.s; // Finish rotating if (pp.p.left is pp.t) { // RotateLeft(pp.p); pp.p.right = pp.ls; pp.s.left = pp.p; pp.g = pp.s; pp.s = pp.ls; } else { // RotateRight(pp.p); pp.p.left = pp.rs; pp.s.right = pp.p; pp.g = pp.s; pp.s = pp.rs; } // Fixup children of pp.s if (pp.s) { pp.ls = pp.s.left; pp.rs = pp.s.right; } // Fixup colors pp.p.color = NodeColor.RedNode; pp.g.color = NodeColor.BlackNode; } if (pp.t && pp.t.color == NodeColor.BlackNode && (pp.t.left is null || pp.t.left.color == NodeColor.BlackNode) && (pp.t.right is null || pp.t.right.color == NodeColor.BlackNode)) { // Case: pp.t is a single binary node with two black children. if (pp.s && pp.s.color == NodeColor.BlackNode && (pp.s.left is null || pp.s.left.color == NodeColor.BlackNode) && (pp.s.right is null || pp.s.right.color == NodeColor.BlackNode)) { // Case: pp.t and pp.s are single binary nodes with two black children.. pp.p.color = NodeColor.BlackNode; pp.t.color = NodeColor.RedNode; pp.s.color = NodeColor.RedNode; } else if (pp.ls && pp.ls.color == NodeColor.RedNode) { // Case: Tree is a single binary node with two black children. // pp.s is pair of binary nodes-one red, one black or pp.s is a set // of three binary nodes with a black parent and red child nodes. // pp.ls is red or pp.rs might be red. if (pp.p.left is pp.t) { // Fix colors pp.ls.color = pp.p.color; pp.p.color = NodeColor.BlackNode; pp.t.color = NodeColor.RedNode; // Fix pp.g child to be pp.ls. ALSo pp.ls may become pp.p of pp.m if (pp.g) { if (pp.g.left is pp.p) pp.g.left = pp.ls; else pp.g.right = pp.ls; } else tree = pp.ls; if (pp.p is pp.m) pp.pm = pp.ls; // Finish: DoubleRotateLeft(pp.s, pp.p); pp.p.right = pp.ls.left; pp.ls.left = pp.p; pp.s.left = pp.ls.right; pp.ls.right= pp.s; pp.g = pp.ls; // Do not fix pp.s or pp.ls since they get reassigned // at the top of next loop } else { // Fix colors pp.s.color = pp.p.color; pp.ls.color = NodeColor.BlackNode; pp.p.color = NodeColor.BlackNode; pp.t.color = NodeColor.RedNode; // Fix pp.g child to be pp.s. Also pp.s may become pp.p of pp.m if (pp.g) { if (pp.g.left is pp.p) pp.g.left = pp.s; else pp.g.right = pp.s; } else tree = pp.s; if (pp.p is pp.m) pp.pm = pp.s; // Finish: RotateRight(pp.p); pp.p.left = pp.rs; pp.s.right = pp.p; pp.g = pp.s; // Do not fix pp.s or pp.ls since they get reassigned // at the top of next loop } } else if (pp.rs && pp.rs.color == NodeColor.RedNode) { // Case: pp.t is a single binary node with two black children. // pp.s is a pair of binary nodes-one red, one black. // pp.ls is black, pp.rs is red. if (pp.p.left is pp.t) { // Fix colors pp.rs.color = NodeColor.BlackNode; pp.s.color = pp.p.color; pp.p.color = NodeColor.BlackNode; pp.t.color = NodeColor.RedNode; // Fix pp.g child to be pp.s. Also, pp.s may become pp.p of pp.m if (pp.g) { if (pp.g.left is pp.p) pp.g.left = pp.s; else pp.g.right = pp.s; } else tree = pp.s; if (pp.p is pp.m) pp.pm = pp.s; // Finish: RotateLeft(pp.p); pp.p.right = pp.ls; pp.s.left = pp.p; pp.g = pp.s; // Do not fix pp.s or pp.ls since they get reassigned // at the top of next loop } else { // Fix colors pp.rs.color = pp.p.color; pp.p.color = NodeColor.BlackNode; pp.t.color = NodeColor.RedNode; // Fix pp.g child to become pp.rs. ALSo, pp.rs may become pp.p of pp.m. if (pp.g) { if (pp.g.left is pp.p) pp.g.left = pp.rs; else pp.g.right = pp.rs; } else tree = pp.rs; if (pp.p is pp.m) pp.pm = pp.rs; // Finish: DoubleRotateRight(pp.s, pp.p); pp.p.left = pp.rs.right; pp.rs.right = pp.p; pp.s.right = pp.rs.left; pp.rs.left = pp.s; pp.g = pp.rs; // Do not fix pp.s or pp.ls since they get reassigned // at the top of next loop } } } return tree; } /// returns height of tree at node root int height(TreeNode tree) { int h = 0; if (tree !is null) { int lh = height(tree.left); int rh = height(tree.right); h = ((lh > rh) ? lh : rh) + 1; } return h; } /// returns number of nodes within tree int count (TreeNode tree) { int n = 0; if (tree !is null) { ++n; n += count(tree.left); n += count(tree.right); } return n; } /// get child node with "minimum" value TreeNode getMin(TreeNode tree) { if (tree !is null) { while(tree.right) tree = tree.right; } return tree; } /// get child node with "maximum" value TreeNode getMax (TreeNode tree) { if (tree !is null) { while(tree.left) tree = tree.left; } return tree; } /// insert child node into tree bool insert(TreeNode node) in { assert(node); // add only new nodes assert(node.left is null); assert(node.right is null); } body { bool bInserted = false; PtrPack pp; int side; pp.t = root; pp.p = null; pp.g = null; pp.gg = null; while ((pp.t !is null) && (node.key != pp.t.key)) { // If on a set of three binary nodes with a black // parent node and red child nodes, split it into // two single binary nodes with two black children. if (((pp.t.left !is null) && (pp.t.left.color == NodeColor.RedNode)) && ((pp.t.right !is null) && (pp.t.right.color == NodeColor.RedNode))) { pp.t.color = NodeColor.RedNode; pp.t.left.color = NodeColor.BlackNode; pp.t.right.color = NodeColor.BlackNode; // Check for two reds in a row, and adjust if so if ((pp.p !is null) && (pp.p.color == NodeColor.RedNode)) { root = InsBalance(root, pp); } } pp.gg = pp.g; pp.g = pp.p; pp.p = pp.t; // go to left if node < current node if (node.key < pp.t.key) { pp.t = pp.t.left; side = 0; } else { pp.t = pp.t.right; side = 1; } } // Reached the bottom, with no matching node if (pp.t is null) { bInserted = true; // now insert node // pp.t = node; pp.t.color = NodeColor.RedNode; if (pp.t is null) return 0; // Couldn't add if (pp.p) { if (side) { pp.p.right = pp.t; } else { pp.p.left = pp.t; } } else root = pp.t; // Check for two reds in a row, and adjust if so if (pp.p && pp.p.color == NodeColor.RedNode) { root = InsBalance(root, pp); } } // root always made black root.color = NodeColor.BlackNode; return bInserted; } // traverse tree in ascending order int applyForward(TreeNode tree, int delegate(inout TreeNode) dg) { int result = 0; while(tree) { result = applyForward(tree.left, dg); if (result) return result; result = dg(tree); if (result) return result; tree = tree.right; } return result; } // traverse tree in descending order int applyReverse(TreeNode tree, int delegate(inout TreeNode) dg) { int result = 0; while(tree) { result = applyReverse(tree.right, dg); if (result) return result; result = dg(tree); if (result) return result; tree = tree.left; } return result; } // public interface public: // insert value at position of key bool insert(KeyType key, ValueType value) { // create a new node TreeNode node = new TreeNode(key, value); return insert(node); } // support insertion via operator // e.g. persons["Mary"] = 30; ValueType opIndexAssign(ValueType value, KeyType key) { insert(key, value); return value; } // support find via operator // e.g. int age = persons["Mary"]; ValueType opIndex(KeyType key) { TreeNode node = find(key); return node.value; } /// remove child node which matches key from the tree TreeNode remove(in KeyType compare) { PtrPack pp; if (root is null) return null; pp.t = root; pp.p = null; pp.g = null; pp.m = null; pp.pm = null; while (pp.t) { // Go down the tree one level, searching for node to delete if (pp.t.key == compare) { pp.m = pp.t; // Record matching node pp.pm = pp.p; // And it's parent } // Update ancestor pointers pp.g = pp.p; pp.p = pp.t; if (pp.t.key > compare) { pp.t = pp.p.left; pp.s = pp.p.right; } else { // Walk down even if it matches, to look for successor pp.t = pp.p.right; pp.s = pp.p.left; } if (pp.s) { pp.ls = pp.s.left; pp.rs = pp.s.right; } else { pp.ls = null; pp.rs = null; } root = DelBalance(root, pp); } root = DoReplacement(root, pp); if (root) root.color = NodeColor.BlackNode; // clear connection to tree if (pp.m) { pp.m.left = null; pp.m.right = null; } return pp.m; // TreeNode to delete } /// find child node which matches key TreeNode find(in KeyType compare) { TreeNode t = root; while (t) { if (t.key == compare) break; t = ((t.key > compare) ? t.left : t.right); } return t; } /// find child node which is "above" given key TreeNode findUpper(in KeyType compare) { TreeNode t = root; TreeNode erg = null; while (t) { if (t.key > compare) { // if (t > key) -> remember it // and descend left subtree erg = t; t = t.left; } else { // if (t < key) descend right subtree t = t.right; } } return erg; } /// find child node which is "below" given key TreeNode findLower (in KeyType compare) { TreeNode t = root; TreeNode erg = null; while (t) { if (t.key < compare) { // if (t < key) -> remember it // and descend right subtree erg = t; t = t.right; } else { // if (t >= key) descend left subtree t = t.left; } } return erg; } /// find child node which is above or equal to the given key TreeNode findUpperOrEq (in KeyType compare) { TreeNode t = root; TreeNode erg = null; while (t) { if (t.key < compare) { // if (t < key) descend right subtree t = t.right; } else { // if (t >= key) -> remember it // and descend left subtree erg = t; t = t.left; } } return erg; } /// find child node which is below or equal to the given key TreeNode findLowerOrEq (in KeyType compare) { TreeNode t = root; TreeNode erg = null; while (t) { if (t.key > compare) { // if t > key descend left subtree t = t.left; } else { // if (t <= key) -> remember it // and descend right subtree erg = t; t = t.right; } } return erg; } /// clear tree void clear() { root = null; } /// returns true when tree is empty bool isEmpty() { return (root is null); } /// determine height of tree int height() { return height(root); } /// return number of nodes maintained by tree int count() { return count(root); } /// return node with minimum key TreeNode getMin() { return getMin(root); } /// return node with maximum key TreeNode getMax() { return getMax(root); } int opApply(int delegate(inout TreeNode) dg) { return applyForward(root, dg); } int opApplyReverse(int delegate(inout TreeNode) dg) { return applyReverse(root, dg); } /// debug output; prints tree sideways void PrintSideWays() { _PrintSideWays(root, 0); } void _PrintSideWays (in TreeNode child, in int space) { while(child) { space += 2; _PrintSideWays(child.left, space); for (int idx=0; idx < space; ++idx) printf(" "); printf("%*s\n", child.key); child = child.right; } } } import std.stdio; void main() { RedBlackTree!(char[], int) foo = new RedBlackTree!(char[], int); foo["Sally"]= 11; foo["Joe"] = 12; foo["Jill"] = 13; foo["Mary"] = 14; foo["Jack"] = 15; foo["Carl"] = 16; foo["Nina"] = 17; foo["Tim"] = 18; foo.PrintSideWays(); foreach(v; foo) { writefln(v.key, " ", v.value); } writefln(" "); foreach_reverse(v; foo) { writefln(v.key, " ", v.value); } foo.remove("Mary"); writefln(" "); foreach(v; foo) { writefln(v.key, " ", v.value); } writefln(" "); writefln("Age of Jill: ", foo.find("Jill").value); writefln("Upper(James): ", foo.findUpper("James").key); writefln("Lower(James): ", foo.findLower("James").key); writefln("findUpperOrEq(Nino): ", foo.findUpperOrEq("Nino").key); writefln("findUpperOrEq(Nina): ", foo.findUpperOrEq("Nina").key); writefln("findLowerOrEq(Nino): ", foo.findLowerOrEq("Nino").key); writefln("findLowerOrEq(Nina): ", foo.findLowerOrEq("Nina").key); }
Oct 23 2006
clayasaurus wrote:Yes, thank you! I'll give it a try when I get the chance. I really didn't want an intrusive tree. Looks like you have an interesting interface too, although why not have an interface like... RedBlackTree!(int) tree; tree.add(4); tree.add(3); tree.add(7); tree.remove(7); int b = tree.find(7); ? Just wondering how you came up with the interface :) ~ ClayWalter suggested it in a previous post. I think he wanted the same interface as AAs have.
Oct 23 2006
KlausO wrote:clayasaurus wrote:Oh, alright :)Yes, thank you! I'll give it a try when I get the chance. I really didn't want an intrusive tree. Looks like you have an interesting interface too, although why not have an interface like... RedBlackTree!(int) tree; tree.add(4); tree.add(3); tree.add(7); tree.remove(7); int b = tree.find(7); ? Just wondering how you came up with the interface :) ~ ClayWalter suggested it in a previous post. I think he wanted the same interface as AAs have.
Oct 23 2006
KlausO wrote:KlausO wrote:This is a lot better than returning an empty node, though. If you can tell me why it crashed, then do it :)Seems to be an interesting task to get used to the new foreach features. I'll give it a try. KlausOk, I rewrote the intrusive version to a nonintrusive one. It has almost the interface you mentioned. Please note: IMHO, there are some points where the template needs some refinement. 1. A third template parameter "bool duplicatesAllowed" should be added and handled in insert/remove via "static if". Then you have multisets at hand ! 2. Sometimes it exposes an interface to the internally used nodes to be able to access the key/value pairs. A special iterator class which could encapsulate the "not found/not inserted" state would be better. 3. The insert via opIndexAssign/find via opIndex is IMHO not optimal because you could not return the "not found/not inserted" state. There are some possibilities to resolve this: a) Throw an exception (IMHO, ugly)Using insert like if (foo.insert("Jill", 13)) looks better to me.You could implement both and let the programmer decide. It also might be neat to implement opIn_r, so you can use... if (!("Jill" in tree)) tree.add("Jill");
Oct 23 2006
Sean Kelly wrote:clayasaurus wrote:Suppose that I don't need sorting, would an associative array work just as well? I'm looking at the code again and it isn't very clear that sorting is a requirement, just that I need to have fast insert, lookup (and if not in container, add it), and deletion. Then again, if all that was needed was a hashmap, then I wonder why the author didn't use STL map.Hello, I am converting some C++ code which happens to use STL Set to D. I was thinking of ways to implement set in D, but since I never got much into STL set in C++ I want to make sure I am thinking right. 1) Are D's associative arrays equivalent to STL Set? I've read that Set is pretty much just a sorted associative array, can this functionality be achieved in D (using struct as a key type) by overloading opCmp?No. D's associative array is implemented as a hash table, which is unordered by nature. If you require the elements to be sorted you'll either have to use a different container or copy the values to an array and sort the array before doing whatever you want to do with the sorted values. The word count example does this, for example.
Oct 19 2006
clayasaurus wrote:Sean Kelly wrote:iirc stl's map are sorted too, and also use rb-tree usually as implementation. I think a set in STL is a subset of a map. There is no hashmap in standard (98) C++. So for insert, lookup and deletion a set makes sense in STL.clayasaurus wrote:Suppose that I don't need sorting, would an associative array work just as well? I'm looking at the code again and it isn't very clear that sorting is a requirement, just that I need to have fast insert, lookup (and if not in container, add it), and deletion. Then again, if all that was needed was a hashmap, then I wonder why the author didn't use STL map.Hello, I am converting some C++ code which happens to use STL Set to D. I was thinking of ways to implement set in D, but since I never got much into STL set in C++ I want to make sure I am thinking right. 1) Are D's associative arrays equivalent to STL Set? I've read that Set is pretty much just a sorted associative array, can this functionality be achieved in D (using struct as a key type) by overloading opCmp?No. D's associative array is implemented as a hash table, which is unordered by nature. If you require the elements to be sorted you'll either have to use a different container or copy the values to an array and sort the array before doing whatever you want to do with the sorted values. The word count example does this, for example.
Oct 19 2006
Sean Kelly wrote:The C++ set is implemented as a balanced binary tree, and some sort of binary tree is probably your best bet if you want a sorted container with decent lookup performance.C++'s balanced binary trees are red-black trees. I had just proposed that someone do a red-black tree implementation for D. It's not hard, the algorithms are well known. It just takes a little time to sit down and do it.
Oct 20 2006
Walter Bright schrieb:Sean Kelly wrote:http://www.cs.fiu.edu/~weiss/dsj3/code/weiss/nonstandard/RedBlackTree.java (a generic implementation) My roots are in Modula/Oberon, but if somebody is willing to translate the Java sources into D I am willing to help in translating/implementing the *missing* remove-method (-as good as possible-) , and some helper methods from Modula 3 into D. Björn // *Java basic impl.* public class RedBlackTree<AnyType extends Comparable<? super AnyType>> { /** * Construct the tree. */ public RedBlackTree( ) { nullNode = new RedBlackNode<AnyType>( null ); nullNode.left = nullNode.right = nullNode; header = new RedBlackNode<AnyType>( null ); header.left = header.right = nullNode; } /** * Compare item and t.element, using compareTo, with * caveat that if t is header, then item is always larger. * This routine is called if is possible that t is header. * If it is not possible for t to be header, use compareTo directly. */ private final int compare( AnyType item, RedBlackNode<AnyType> t ) { if( t == header ) return 1; else return item.compareTo( t.element ); } /** * Insert into the tree. * param item the item to insert. * throws DuplicateItemException if item is already present. */ public void insert( AnyType item ) { current = parent = grand = header; nullNode.element = item; while( compare( item, current ) != 0 ) { great = grand; grand = parent; parent = current; current = compare( item, current ) < 0 ? current.left : current.right; // Check if two red children; fix if so if( current.left.color == RED && current.right.color == RED ) handleReorient( item ); } // Insertion fails if already present if( current != nullNode ) throw new DuplicateItemException( item.toString( ) ); current = new RedBlackNode<AnyType>( item, nullNode, nullNode ); // Attach to parent if( compare( item, parent ) < 0 ) parent.left = current; else parent.right = current; handleReorient( item ); } /** * Remove from the tree. * param x the item to remove. * throws UnsupportedOperationException if called. */ public void remove( AnyType x ) { throw new UnsupportedOperationException( ); } /** * Find the smallest item the tree. * return the smallest item or null if empty. */ public AnyType findMin( ) { if( isEmpty( ) ) return null; RedBlackNode<AnyType> itr = header.right; while( itr.left != nullNode ) itr = itr.left; return itr.element; } /** * Find the largest item in the tree. * return the largest item or null if empty. */ public AnyType findMax( ) { if( isEmpty( ) ) return null; RedBlackNode<AnyType> itr = header.right; while( itr.right != nullNode ) itr = itr.right; return itr.element; } /** * Find an item in the tree. * param x the item to search for. * return the matching item or null if not found. */ public AnyType find( AnyType x ) { nullNode.element = x; current = header.right; for( ; ; ) { if( x.compareTo( current.element ) < 0 ) current = current.left; else if( x.compareTo( current.element ) > 0 ) current = current.right; else if( current != nullNode ) return current.element; else return null; } } /** * Make the tree logically empty. */ public void makeEmpty( ) { header.right = nullNode; } /** * Print all items. */ public void printTree( ) { printTree( header.right ); } /** * Internal method to print a subtree in sorted order. * param t the node that roots the tree. */ private void printTree( RedBlackNode<AnyType> t ) { if( t != nullNode ) { printTree( t.left ); System.out.println( t.element ); printTree( t.right ); } } /** * Test if the tree is logically empty. * return true if empty, false otherwise. */ public boolean isEmpty( ) { return header.right == nullNode; } /** * Internal routine that is called during an insertion * if a node has two red children. Performs flip and rotations. * param item the item being inserted. */ private void handleReorient( AnyType item ) { // Do the color flip current.color = RED; current.left.color = BLACK; current.right.color = BLACK; if( parent.color == RED ) // Have to rotate { grand.color = RED; if( ( compare( item, grand ) < 0 ) != ( compare( item, parent ) < 0 ) ) parent = rotate( item, grand ); // Start dbl rotate current = rotate( item, great ); current.color = BLACK; } header.right.color = BLACK; // Make root black } /** * Internal routine that performs a single or double rotation. * Because the result is attached to the parent, there are four cases. * Called by handleReorient. * param item the item in handleReorient. * param parent the parent of the root of the rotated subtree. * return the root of the rotated subtree. */ private RedBlackNode<AnyType> rotate( AnyType item, RedBlackNode<AnyType> parent ) { if( compare( item, parent ) < 0 ) return parent.left = compare( item, parent.left ) < 0 ? rotateWithLeftChild( parent.left ) : // LL rotateWithRightChild( parent.left ) ; // LR else return parent.right = compare( item, parent.right ) < 0 ? rotateWithLeftChild( parent.right ) : // RL rotateWithRightChild( parent.right ); // RR } /** * Rotate binary tree node with left child. */ private static <AnyType> RedBlackNode<AnyType> rotateWithLeftChild( RedBlackNode<AnyType> k2 ) { RedBlackNode<AnyType> k1 = k2.left; k2.left = k1.right; k1.right = k2; return k1; } /** * Rotate binary tree node with right child. */ private static <AnyType> RedBlackNode<AnyType> rotateWithRightChild( RedBlackNode<AnyType> k1 ) { RedBlackNode<AnyType> k2 = k1.right; k1.right = k2.left; k2.left = k1; return k2; } private static class RedBlackNode<AnyType> { // Constructors RedBlackNode( AnyType theElement ) { this( theElement, null, null ); } RedBlackNode( AnyType theElement, RedBlackNode<AnyType> lt, RedBlackNode<AnyType> rt ) { element = theElement; left = lt; right = rt; color = RedBlackTree.BLACK; } AnyType element; // The data in the node RedBlackNode<AnyType> left; // Left child RedBlackNode<AnyType> right; // Right child int color; // Color } private RedBlackNode<AnyType> header; private RedBlackNode<AnyType> nullNode; private static final int BLACK = 1; // BLACK must be 1 private static final int RED = 0; // Used in insert routine and its helpers private RedBlackNode<AnyType> current; private RedBlackNode<AnyType> parent; private RedBlackNode<AnyType> grand; private RedBlackNode<AnyType> great; // Test program public static void main( String [ ] args ) { RedBlackTree<Integer> t = new RedBlackTree<Integer>( ); final int NUMS = 400000; final int GAP = 35461; System.out.println( "Checking... (no more output means success)" ); for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS ) t.insert( i ); if( t.findMin( ) != 1 || t.findMax( ) != NUMS - 1 ) System.out.println( "FindMin or FindMax error!" ); for( int i = 1; i < NUMS; i++ ) if( t.find( i ) != i ) System.out.println( "Find error1!" ); } } // *Modula 3 Remove* PROCEDURE Delete (t: T; k: Key.T; VAR (*OUT*) v: Value.T): BOOLEAN = VAR curr := t.root; rep, repCh: Node; BEGIN (* find the node to delete (if any *) CASE t.keyCompare(k, curr.k) OF | -1 => curr := curr.l | 1 => curr := curr.r | 0 => EXIT END END; IF curr = t.nil THEN RETURN FALSE END; (* locate replacement node and one of its children *) IF curr.l = t.nil OR curr.r = t.nil THEN rep := curr ELSE rep := Successor(t, curr) END; (* splice out "rep" node *) repCh.p := rep.p; IF rep.p = t.nil THEN t.root := repCh ELSE IF rep = rep.p.l THEN repCh.p.l := repCh ELSE repCh.p.r := repCh END END; (* save value of node to be deleted *) v := curr.v; (* copy "rep" fields into "curr" if they are different *) (* rebalance tree if necessary *) IF rep.color = Color.Black THEN DeleteFixup(t, repCh) END; DEC(t.num); RETURN TRUE END Delete; PROCEDURE DeleteFixup (t: T; ch: Node) = VAR p, sib: Node; BEGIN p := ch.p; IF ch = p.l THEN (* "ch" is the left child of "p" *) sib := p.r; IF sib.color = Color.Red THEN (* case 1 *) sib.color := Color.Black; p.color := Color.Red; LeftRotate(t, p, sib); sib := p.r END; IF sib.l.color = Color.Black AND sib.r.color = Color.Black THEN (* case 2 *) sib.color := Color.Red; ch := p ELSE IF sib.r.color = Color.Black THEN (* case 3 *) <* ASSERT sib.l.color = Color.Red *> sib.l.color := Color.Black; sib.color := Color.Red; RightRotate(t, sib, sib.l); sib := p.r END; <* ASSERT sib.r.color = Color.Red *> (* case 4 *) sib.color := p.color; p.color := Color.Black; sib.r.color := Color.Black; LeftRotate(t, p, sib); ch := t.root END ELSE (* "ch" is the right child of "p" *) sib := p.l; IF sib.color = Color.Red THEN (* case 1 *) sib.color := Color.Black; p.color := Color.Red; RightRotate(t, p, sib); sib := p.l END; IF sib.r.color = Color.Black AND sib.l.color = Color.Black THEN (* case 2 *) sib.color := Color.Red; ch := p ELSE IF sib.l.color = Color.Black THEN (* case 3 *) <* ASSERT sib.r.color = Color.Red *> sib.r.color := Color.Black; sib.color := Color.Red; LeftRotate(t, sib, sib.r); sib := p.l END; <* ASSERT sib.l.color = Color.Red *> (* case 4 *) sib.color := p.color; p.color := Color.Black; sib.l.color := Color.Black; RightRotate(t, p, sib); ch := t.root END END END; ch.color := Color.Black END DeleteFixup; Indeed, a wild mixture!!!The C++ set is implemented as a balanced binary tree, and some sort of binary tree is probably your best bet if you want a sorted container with decent lookup performance.C++'s balanced binary trees are red-black trees. I had just proposed that someone do a red-black tree implementation for D. It's not hard, the algorithms are well known. It just takes a little time to sit down and do it.
Oct 23 2006
Walter Bright schrieb:.....that someone do a red-black tree implementation for D. It's not hard, the algorithms are well known. It just takes a little time to sit down and do it.Hi algorithm fans, maybe you can help a bit. I own the Algorithms and Data Structures books from Wirth and Sedgewick. (Both antik/antique ... means Pascal, still true! and of course a little bit outdated) If you have a hint what is worth reading now (except C++ books) Thanks in advance. Björn
Oct 23 2006
BLS wrote:Walter Bright schrieb:Personally, I like Sedgewick's "Algorithms in C++" series the best. And the "Algorithms in Java" versions appear similar, so I think they're probably just as good. I find the writing succinct and clear, and performance is discussed thoroughly and supported by actual test numbers. Also, while I don't like the writing style in M.A. Weiss' first edition "Data Structures and Problem Solving with C++" as much as Sedgewick, it does cover some topics that Sedgewick doesn't. Weiss' more recent edition for Java (and I assume C++), however, is about half as thick and its clarity has suffered from all the editing. But it does still cover the same range of topics, so it may be worth a look. Sean.....that someone do a red-black tree implementation for D. It's not hard, the algorithms are well known. It just takes a little time to sit down and do it.Hi algorithm fans, maybe you can help a bit. I own the Algorithms and Data Structures books from Wirth and Sedgewick. (Both antik/antique ... means Pascal, still true! and of course a little bit outdated) If you have a hint what is worth reading now (except C++ books) Thanks in advance. Björn
Oct 23 2006
Sean Kelly schrieb:Personally, I like Sedgewick's "Algorithms in C++" series the best. And the "Algorithms in Java" versions appear similar, so I think they're probably just as good. I find the writing succinct and clear, and performance is discussed thoroughly and supported by actual test numbers. Also, while I don't like the writing style in M.A. Weiss' first edition "Data Structures and Problem Solving with C++" as much as Sedgewick, it does cover some topics that Sedgewick doesn't. Weiss' more recent edition for Java (and I assume C++), however, is about half as thick and its clarity has suffered from all the editing. But it does still cover the same range of topics, so it may be worth a look. SeanThanks for your answere Sean, Thinking about your answere and the nature of Java (no pointers) I guess that Sedgewick's "Algorithms in Java" could fullfill my needs because I would like to translate a lot of (pseudo) code like this : nodepointer is POINTER to node; node is record begin d is interger; lnode is nodepointer; rnode is nodepointer; data is Anytype; end into D classes. Maybe you know about the meanwhile dead PM3 Modula 3 efforts ... wish we have such a HUGE lib in D. Hope that comparing pointerless Java examples will help to translate Modula sources into D. Ahem... Björn btw :I wonder wether Sedgewick is still using tons of academic terms (means showing how clever he is) or is he meanwhile able to produce some output a human-beeing can read.
Oct 23 2006
BLS wrote:btw :I wonder wether Sedgewick is still using tons of academic terms (means showing how clever he is) or is he meanwhile able to produce some output a human-beeing can read.I find Sedgewick to be quite readable, but his material is a bit more technical than some of the other texts. I personally like this because it makes for good reference material, but if I were teaching the subject I might choose a book that doesn't jump into the middle of things quite so quickly. For comparison, my wife took an algorithm analysis course recently that used Weiss' Java book. She found the descriptions in it confusing, but thought my 1st ed. C++ copy of the same book (same topics but much longer) was excellent. So I'd be inclined to recommend Weiss except his recent editions don't seem as clear as his earlier editions, as a result of some heavy editing to reduce page count. I wish I could suggest others, but aside from Knuth those are the only algorithms books I've actually kept. Sean
Oct 23 2006
Sean Kelly schrieb:BLS wrote:Thanks for your inside view. What I am able to figure out from your message(s) is that reading Sedgewick still requires time and some++ background knowledge,while Weiss (at least in his most recent book) : Algorithm Analyses is somewhat weak, or let's say the didatic part is weak . Regarding Weiss : I hope we are talking about the same book : I mean Data Structures and Problem Solving and *not* Data Structures and Algorithm Analyses. Anyway, your informations are very usefull for me. Thanks a lot! Regards Björnbtw :I wonder wether Sedgewick is still using tons of academic terms (means showing how clever he is) or is he meanwhile able to produce some output a human-beeing can read.I find Sedgewick to be quite readable, but his material is a bit more technical than some of the other texts. I personally like this because it makes for good reference material, but if I were teaching the subject I might choose a book that doesn't jump into the middle of things quite so quickly. For comparison, my wife took an algorithm analysis course recently that used Weiss' Java book. She found the descriptions in it confusing, but thought my 1st ed. C++ copy of the same book (same topics but much longer) was excellent. So I'd be inclined to recommend Weiss except his recent editions don't seem as clear as his earlier editions, as a result of some heavy editing to reduce page count. I wish I could suggest others, but aside from Knuth those are the only algorithms books I've actually kept. Sean
Oct 23 2006