diff options
author | Damien George <damien.p.george@gmail.com> | 2020-01-13 17:10:41 +1100 |
---|---|---|
committer | Damien George <damien.p.george@gmail.com> | 2020-01-22 17:31:18 +1100 |
commit | fe203bb3e2c98239ece07f340b3e745368636bb8 (patch) | |
tree | 52d1858a4730ffad89491dfbf1118bca3f7a6483 /py/pairheap.c | |
parent | 599371b133ec24c8ccfc3b75dd5a62b94b4b4055 (diff) |
py/pairheap: Add generic implementation of pairing heap data structure.
Diffstat (limited to 'py/pairheap.c')
-rw-r--r-- | py/pairheap.c | 139 |
1 files changed, 139 insertions, 0 deletions
diff --git a/py/pairheap.c b/py/pairheap.c new file mode 100644 index 000000000..caa51bf79 --- /dev/null +++ b/py/pairheap.c @@ -0,0 +1,139 @@ +/* + * This file is part of the MicroPython project, http://micropython.org/ + * + * The MIT License (MIT) + * + * Copyright (c) 2020 Damien P. George + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#include "py/pairheap.h" + +// The mp_pairheap_t.next pointer can take one of the following values: +// - NULL: the node is the top of the heap +// - LSB set: the node is the last of the children and points to its parent node +// - other: the node is a child and not the last child +// The macros below help manage this pointer. +#define NEXT_MAKE_RIGHTMOST_PARENT(parent) ((void*)((uintptr_t)(parent) | 1)) +#define NEXT_IS_RIGHTMOST_PARENT(next) ((uintptr_t)(next) & 1) +#define NEXT_GET_RIGHTMOST_PARENT(next) ((void*)((uintptr_t)(next) & ~1)) + +// O(1), stable +mp_pairheap_t *mp_pairheap_meld(mp_pairheap_lt_t lt, mp_pairheap_t *heap1, mp_pairheap_t *heap2) { + if (heap1 == NULL) { + return heap2; + } + if (heap2 == NULL) { + return heap1; + } + if (lt(heap1, heap2)) { + if (heap1->child == NULL) { + heap1->child = heap2; + } else { + heap1->child_last->next = heap2; + } + heap1->child_last = heap2; + heap2->next = NEXT_MAKE_RIGHTMOST_PARENT(heap1); + return heap1; + } else { + heap1->next = heap2->child; + heap2->child = heap1; + if (heap1->next == NULL) { + heap2->child_last = heap1; + heap1->next = NEXT_MAKE_RIGHTMOST_PARENT(heap2); + } + return heap2; + } +} + +// amortised O(log N), stable +mp_pairheap_t *mp_pairheap_pairing(mp_pairheap_lt_t lt, mp_pairheap_t *child) { + if (child == NULL) { + return NULL; + } + mp_pairheap_t *heap = NULL; + while (!NEXT_IS_RIGHTMOST_PARENT(child)) { + mp_pairheap_t *n1 = child; + child = child->next; + if (!NEXT_IS_RIGHTMOST_PARENT(child)) { + mp_pairheap_t *n2 = child; + child = child->next; + n1 = mp_pairheap_meld(lt, n1, n2); + } + heap = mp_pairheap_meld(lt, heap, n1); + } + heap->next = NULL; + return heap; +} + +// amortised O(log N), stable +mp_pairheap_t *mp_pairheap_delete(mp_pairheap_lt_t lt, mp_pairheap_t *heap, mp_pairheap_t *node) { + // Simple case of the top being the node to delete + if (node == heap) { + return mp_pairheap_pairing(lt, heap->child); + } + + // Case where node is not in the heap + if (node->next == NULL) { + return heap; + } + + // Find parent of node + mp_pairheap_t *parent = node; + while (!NEXT_IS_RIGHTMOST_PARENT(parent->next)) { + parent = parent->next; + } + parent = NEXT_GET_RIGHTMOST_PARENT(parent->next); + + // Replace node with pairing of its children + mp_pairheap_t *next; + if (node == parent->child && node->child == NULL) { + if (NEXT_IS_RIGHTMOST_PARENT(node->next)) { + parent->child = NULL; + } else { + parent->child = node->next; + } + node->next = NULL; + return heap; + } else if (node == parent->child) { + next = node->next; + node->next = NULL; + node = mp_pairheap_pairing(lt, node->child); + parent->child = node; + } else { + mp_pairheap_t *n = parent->child; + while (node != n->next) { + n = n->next; + } + next = node->next; + node->next = NULL; + node = mp_pairheap_pairing(lt, node->child); + if (node == NULL) { + node = n; + } else { + n->next = node; + } + } + node->next = next; + if (NEXT_IS_RIGHTMOST_PARENT(next)) { + parent->child_last = node; + } + return heap; +} |