| 685 | using DLL<C, L>::head; |
| 686 | using Queue<C, L>::tail; |
| 687 | void |
| 688 | sort() |
| 689 | { |
| 690 | if (!head) { |
| 691 | return; |
| 692 | } |
| 693 | bool clean = false; |
| 694 | while (!clean) { |
| 695 | clean = true; |
| 696 | C *v = head; |
| 697 | C *n = this->next(head); |
| 698 | while (n) { |
| 699 | C *f = this->next(n); |
| 700 | if (*n < *v) { |
| 701 | clean = false; |
| 702 | // swap 'em |
| 703 | if (head == v) { |
| 704 | head = n; |
| 705 | } |
| 706 | if (tail == n) { |
| 707 | tail = v; |
| 708 | } |
| 709 | // fix prev (p) |
| 710 | C *p = this->prev(v); |
| 711 | if (p) { |
| 712 | this->next(p) = n; |
| 713 | this->prev(n) = p; |
| 714 | } else { |
| 715 | this->prev(n) = nullptr; |
| 716 | } |
| 717 | // fix follow (f) |
| 718 | if (f) { |
| 719 | this->prev(f) = v; |
| 720 | this->next(v) = f; |
| 721 | } else { |
| 722 | this->next(v) = nullptr; |
| 723 | } |
| 724 | // fix interior |
| 725 | this->prev(v) = n; |
| 726 | this->next(n) = v; |
| 727 | } else { |
| 728 | v = n; |
| 729 | } |
| 730 | n = f; |
| 731 | } |
| 732 | } |
| 733 | } |
| 734 | }; |
| 735 | #define SortableQue(_c, _l) SortableQueue<_c, _c::Link##_##_f> |
| 736 |