| 1 | template <class T> |
| 2 | struct dancing_links { |
| 3 | struct node { |
| 4 | T item; |
| 5 | node *l, *r; |
| 6 | node(const T &_item, node *_l = NULL, node *_r = NULL) |
| 7 | : item(_item), l(_l), r(_r) { |
| 8 | if (l) l->r = this; |
| 9 | if (r) r->l = this; } }; |
| 10 | node *front, *back; |
| 11 | dancing_links() { front = back = NULL; } |
| 12 | node *push_back(const T &item) { |
| 13 | back = new node(item, back, NULL); |
| 14 | if (!front) front = back; |
| 15 | return back; } |
| 16 | node *push_front(const T &item) { |
| 17 | front = new node(item, NULL, front); |
| 18 | if (!back) back = front; |
| 19 | return front; } |
| 20 | void erase(node *n) { |
| 21 | if (!n->l) front = n->r; else n->l->r = n->r; |
| 22 | if (!n->r) back = n->l; else n->r->l = n->l; } |
| 23 | void restore(node *n) { |
| 24 | if (!n->l) front = n; else n->l->r = n; |
| 25 | if (!n->r) back = n; else n->r->l = n; } }; |
| 26 | // vim: cc=60 ts=2 sts=2 sw=2: |
nothing calls this directly
no outgoing calls
no test coverage detected