www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Creating a RedBlackTree

reply Bogdan <olar.bogdan.dev gmail.com> writes:
I don't have any experience with using templates. Is it possible 
to create a RB tree containing structs, where the nodes are 
ordered by one struct member?

```
import std.stdio;
import std.container;

enum KeyID: uint
{
	KEY_A,
	KEY_S,
	KEY_D,
	KEY_W
}

struct KeyController
{
	KeyID ID;
	bool isDown;
}


void main()
{
	auto rbt = redBlackTree!KeyController;
}

```

When I run this I get a compile error:
```
Error: template instance 
`std.container.rbtree.RedBlackTree!(KeyController)` does not 
match template declaration RedBlackTree(T, alias less = "a < b", 
bool allowDuplicates = false) if 
(is(typeof(binaryFun!less(T.init, T.init))))
```
May 15 2019
next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Wednesday, 15 May 2019 at 13:08:18 UTC, Bogdan wrote:

 I don't have any experience with using templates. Is it 
 possible to create a RB tree containing structs, where the 
 nodes are ordered by one struct member?

 ```
 import std.stdio;
 import std.container;

 enum KeyID: uint
 {
 	KEY_A,
 	KEY_S,
 	KEY_D,
 	KEY_W
 }

 struct KeyController
 {
 	KeyID ID;
 	bool isDown;
 }


 void main()
 {
 	auto rbt = redBlackTree!KeyController;
 }

 ```

 When I run this I get a compile error:
 ```
 Error: template instance 
 `std.container.rbtree.RedBlackTree!(KeyController)` does not 
 match template declaration RedBlackTree(T, alias less = "a < 
 b", bool allowDuplicates = false) if 
 (is(typeof(binaryFun!less(T.init, T.init))))
 ```


Key controller cannot be compared by less
which is why it fails, give it an opCmp and it'll work.
May 15 2019
parent Bogdan <olar.bogdan.dev gmail.com> writes:
On Wednesday, 15 May 2019 at 13:15:50 UTC, Stefan Koch wrote:

 Key controller cannot be compared by less
 which is why it fails, give it an opCmp and it'll work.


Works fine, thank you! For some reason, I thought that this 
template uses references:
```
enum KeyID: uint
{
	KEY_A,
	KEY_S,
	KEY_D,
	KEY_W
}

struct KeyController
{
	KeyID ID;
	bool isDown;

	int opCmp(ref const KeyController other) const {return this.ID - 
other.ID;}
}

void main()
{
	KeyController[] monitoredKeys = [{KeyID.KEY_A}];

	auto rbt = redBlackTree!KeyController;

	rbt.insert(monitoredKeys);
	writeln(rbt);
	monitoredKeys[0].isDown = true;
	writeln(rbt);
}
```

Output:
```
RedBlackTree([const(KeyController)(KEY_A, false)])
RedBlackTree([const(KeyController)(KEY_A, false)])
```
May 15 2019
prev sibling parent reply drug <drug2004 bk.ru> writes:
On 15.05.2019 16:08, Bogdan wrote:

 I don't have any experience with using templates. Is it possible to 
 create a RB tree containing structs, where the nodes are ordered by one 
 struct member?
 
 ```
 import std.stdio;
 import std.container;
 
 enum KeyID: uint
 {
      KEY_A,
      KEY_S,
      KEY_D,
      KEY_W
 }
 
 struct KeyController
 {
      KeyID ID;
      bool isDown;
 }
 
 
 void main()
 {
      auto rbt = redBlackTree!KeyController;
 }
 
 ```
 
 When I run this I get a compile error:
 ```
 Error: template instance 
 `std.container.rbtree.RedBlackTree!(KeyController)` does not match 
 template declaration RedBlackTree(T, alias less = "a < b", bool 
 allowDuplicates = false) if (is(typeof(binaryFun!less(T.init, T.init))))
 ```
 


You can use predicate for this purpose:
```
auto rbt = redBlackTree!((a, b) => a.ID < b.ID, KeyController);
```

https://run.dlang.io/is/CNRTQf
May 15 2019
parent Bogdan <olar.bogdan.dev gmail.com> writes:
On Wednesday, 15 May 2019 at 13:19:36 UTC, drug wrote:

 You can use predicate for this purpose:
 ```
 auto rbt = redBlackTree!((a, b) => a.ID < b.ID, KeyController);
 ```

 https://run.dlang.io/is/CNRTQf


Even better, thank you!
May 15 2019