Чтобы научить себя С++, я работаю над реализацией красно-черного дерева. Приходящий из Я, Хаскелл, подумал, что было бы интересно узнать, могу ли я использовать свойства красно-черное дерево статически в системе типа С++:
- A node либо красный, либо черный.
- Корень черный [...]
- Все листья (NIL) черные.
- Если a node красный, то оба его дочерних элемента являются черными.
- Каждый путь от данного node к любому из его потомков NIL содержит такое же количество черных узлов. [...]
Я выяснил, как обрабатывать типы для узлов дерева, чтобы удовлетворить ограничениям 1, 3, 4 и 5 с использованием шаблонов:
template <typename Key, typename Value>
class RedBlackTree {
private:
enum class color { Black, Red };
// [1. A node is either red or black]
template <color Color, size_t Height>
struct Node {};
// [3. All leaves are black]
struct Leaf : public Node<color::Black, 0> {};
template <color Left, color Right, size_t ChildHeight>
struct Branch {
public:
template <color ChildColor>
using Child = unique_ptr<Node<ChildColor, ChildHeight>>;
Key key;
Value value;
Child<Left> left;
Child<Right> right;
Branch(Key&& key, Value&& value, Child<Left> left, Child<Right> right) :
key { key }, value { value }, left { left }, right { right } {}
};
// [4. If a node is red, then both its children are black.]
// [5. Every path from a given node to any of its descendant NIL nodes contains
// the same number of black nodes.]
template <size_t Height>
struct RedBranch: public Node<color::Red, Height>
, public Branch<color::Black, color::Black, Height> {
public:
using RedBlackTree::Branch;
};
// [5. Every path from a given node to any of its descendant NIL nodes contains
// the same number of black nodes.]
template <size_t Height, color Left, color Right>
struct BlackBranch: public Node<color::Black, Height>
, public Branch<Left, Right, Height-1> {
public:
using RedBlackTree::Branch;
};
// ...
};
В случае, когда я зашел в тупик, появляется указатель root, который будет сохранен в RedBlackTree
экземпляр типа, удовлетворяющего свойству 2, но по-прежнему полезен.
Я хочу что-то вроде:
template <typename Key, typename Value>
class RedBlackTree {
//...
unique_ptr<Node<color::Black,?>> root = std::make_unique<Leaf>();
//...
}
(заимствовать синтаксис Java), поэтому я могу подстановочные знаки над высотой дерева. Это конечно, не работает.
Я мог бы скомпилировать свой код, если бы сделал
template <typename Key, typename Value, size_t TreeHeight>
class RedBlackTree {
//...
unique_ptr<Node<color::Black,TreeHeight>> root = std::make_unique<Leaf>();
//...
}
Но это не тот тип, который я хочу для дерева - я не хочу, чтобы тип самого дерева
чтобы отразить его высоту, в противном случае тип моего дерева может измениться, когда я вставляю
ключ-значение. Я хочу обновить свой root, чтобы содержать указатель на черный
Node любой высоты.
Вернувшись в haskell-land, я бы решил эту проблему, используя экзистенциальную Количественное:
data Color = Black | Red
data Node (color :: Color) (height :: Nat) key value where
Leaf :: Node 'Black 0 key value
BlackBranch :: Branch left right height key value -> Node 'Black (height+1) key value
RedBranch :: Branch 'Black 'Black height key value -> Node 'Red height key value
data Branch (left :: Color) (right :: Color) (childHeight :: Nat) key value = Branch
{ left :: Node left childHeight key value
, right :: Node right childHeight key value
, key :: key
, value :: value
}
data RedBlackTree key value where
RedBlackTree :: { root :: Node 'Black height key value } -> RedBlackTree key value
Существует ли эквивалентное понятие в С++ 14 (или, может быть, С++ 17), или альтернативный способ, которым я мог бы написать свои определения struct, чтобы дать root полезный и правильный тип?
