| 452 | |
| 453 | template <class T> |
| 454 | Reference<PTree<T>> append(const Reference<PTree<T>>& left, const Reference<PTree<T>>& right, Version at) { |
| 455 | if (!left) |
| 456 | return right; |
| 457 | if (!right) |
| 458 | return left; |
| 459 | |
| 460 | Reference<PTree<T>> r = makeReference<PTree<T>>(lastNode(left, at)->data, at); |
| 461 | if (EXPENSIVE_VALIDATION) { |
| 462 | ASSERT(r->data < firstNode(right, at)->data); |
| 463 | } |
| 464 | Reference<PTree<T>> a = left; |
| 465 | remove(a, at, r->data); |
| 466 | |
| 467 | r->pointer[0] = a; |
| 468 | r->pointer[1] = right; |
| 469 | demoteRoot(r, at); |
| 470 | return r; |
| 471 | } |
| 472 | |
| 473 | template <class T, class X> |
| 474 | void split(Reference<PTree<T>> p, const X& x, Reference<PTree<T>>& left, Reference<PTree<T>>& right, Version at) { |