💾 Archived View for gmi.noulin.net › gitRepositories › wavlTree › file › wavlTree.h.gmi captured on 2023-01-29 at 11:35:59. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
wavlTree.h (2816B)
1 #pragma once
2
3 #include "libsheepyObject.h"
4 #undef put
5
6 /**
7 * WAVL Tree
8 *
9 * The WAVL tree combines elements of AVL & Red-black trees.
10 *
11 * The WAVL tree deletion is described in the 2015 paper "Rank Balanced Trees"
12 * The related RAVL tree is described in the 2016 paper "Deletion Without Rebalancing in Binary Search Trees"
13 * available at:
14 * http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf
15 * http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pdf
16 *
17 *
18 * in this implementation:
19 * - key is int
20 * - value is int
21 *
22 * the code is inspired by:
23 * https://github.com/dmcmanam/bbst-showdown
24 */
25
26 // namespace
27 #ifndef WAVL_NAMESPACE
28 #define WAVL_NAMESPACE wavlTree
29 #endif
30 #define keyt TOKENPASTE(WAVL_NAMESPACE, keyt)
31 #define valuet TOKENPASTE(WAVL_NAMESPACE, valuet)
32 #define nodet TOKENPASTE(WAVL_NAMESPACE, nodet)
33 #define t TOKENPASTE(WAVL_NAMESPACE, t)
34 #define St TOKENPASTE(WAVL_NAMESPACE, St)
35 #define init TOKENPASTE(WAVL_NAMESPACE, init)
36
37 typedef int keyt;
38 typedef int valuet;
39 //typedef char* valuet;
40
41 typedef struct St t;
42
43
44
45 typedef struct nodet nodet;
46 struct nodet {
47 keyt key;
48 valuet value;
49 nodet *left;
50 nodet *right;
51 nodet *parent;
52 int8_t rank;
53 };
54
55 typedef int (*heightFt) (t *tree);
56 typedef valuet (*getFt) (t *tree, keyt k);
57 typedef valuet (*putFt) (t *tree, keyt k, valuet v);
58 typedef valuet (*removeKVFt) (t *tree, keyt k);
59 typedef void (*inOrderTraversalFt)(nodet *X);
60 typedef void (*clearFt) (t *tree);
61 typedef nodet* (*getFirstEntryFt) (t *tree);
62 typedef nodet* (*getLastEntryFt) (t *tree);
63 typedef void (*iterStartFt) (t *tree, nodet *first);
64 typedef bool (*hasNextFt) (t *tree);
65 typedef nodet* (*nextEntryFt) (t *tree);
66 typedef nodet* (*prevEntryFt) (t *tree);
67 typedef bool (*removeCurrentFt) (t *tree);
68
69 struct St {
70 size_t count; // number of entries in the tree
71 size_t modCount; // number of structural modifications to the tree
72 size_t rotations;
73 bool deleteWAVL;
74 nodet *root;
75
76 // private iterator
77 size_t expectedModCount;
78 nodet *next;
79 nodet *lastReturned;
80 // end private iterator
81
82 getFt get;
83 putFt put;
84 heightFt treeHeight;
85 removeKVFt remove;
86 inOrderTraversalFt inOrderTraversal;
87 clearFt clear;
88 getFirstEntryFt getFirstEntry;
89 getLastEntryFt getLastEntry;
90 iterStartFt iterStart;
91 hasNextFt hasNext;
92 nextEntryFt nextEntry;
93 prevEntryFt prevEntry;
94 removeCurrentFt removeCurrent;
95 };
96
97 bool init(t *tree);
98
99 // vim: set expandtab ts=2 sw=2: