A virtual currency betting bot for Twitch chat. https://ddark.net/better
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 

314 lines
7.8 KiB

#include <assert.h>
#include "ost.h"
#define depth(n) ((n)? max((n)->depth_left, (n)->depth_right) + 1 : 0)
#define weight(n) ((n)? (n)->weight_left + (n)->weight_right + 1 : 0)
#define max(a,b) (((a) < (b))? (b) : (a))
static ost_node* left_rotate(ost_node* node)
{
ost_node* temp = node->right;
temp->parent = node->parent;
if (temp->parent)
{
if (temp->parent->right == node)
temp->parent->right = temp;
else /*if (temp->parent->left == node)*/
temp->parent->left = temp;
}
node->right = temp->left;
if (node->right) node->right->parent = node;
temp->left = node;
temp->left->parent = temp;
node->weight_right = temp->weight_left;
temp->weight_left += node->weight_left + 1;
node->depth_left = depth(node->left);
node->depth_right = depth(node->right);
temp->depth_left = depth(temp->left);
temp->depth_right = depth(temp->right);
return temp;
}
static ost_node* right_rotate(ost_node* node)
{
ost_node* temp = node->left;
temp->parent = node->parent;
if (temp->parent)
{
if (temp->parent->right == node)
temp->parent->right = temp;
else /*if (temp->parent->left == node)*/
temp->parent->left = temp;
}
node->left = temp->right;
if (node->left) node->left->parent = node;
temp->right = node;
temp->right->parent = temp;
node->weight_left = temp->weight_right;
temp->weight_right += node->weight_right + 1;
node->depth_left = depth(node->left);
node->depth_right = depth(node->right);
temp->depth_left = depth(temp->left);
temp->depth_right = depth(temp->right);
return temp;
}
// Initialize the tree.
void ost_init(ost* tree, int (*comp_fn)(const void*, const void*), void* (*alloc_fn)(size_t), void (*free_fn)(void*))
{
tree->root = NULL;
tree->comp_fn = comp_fn;
tree->alloc_fn = alloc_fn;
tree->free_fn = free_fn;
}
// Removes all nodes from the tree.
void ost_remove_all(ost* tree)
{
if (tree->free_fn && tree->root)
{
ost_node *node = tree->root, *next;
while(node)
{
if (node->left)
{
next = node->left;
node->left = NULL;
}
else if (node->right)
{
next = node->right;
node->right = NULL;
}
else
{
next = node->parent;
tree->free_fn(node);
}
node = next;
}
}
tree->root = NULL;
}
// Insert a new node in the tree. If data is compared to be equal to other nodes already in the tree, the new node is inserted to the right of those nodes, as if it were larger.
ost_node* ost_insert(ost* tree, void* data)
{
ost_node* new_node = tree->alloc_fn(sizeof(ost_node));
new_node->data = data;
new_node->left = new_node->right = new_node->parent = NULL;
new_node->depth_left = new_node->depth_right = 0;
new_node->weight_left = new_node->weight_right = 0;
if (!tree->root)
{
// Tree is empty -- set new node as root
tree->root = new_node;
}
else
{
// Insert the new leaf
ost_node* parent = tree->root;
while (parent)
{
int c = tree->comp_fn(new_node->data, parent->data);
if (c < 0)
{
++parent->weight_left;
if (parent->left == NULL)
{
parent->left = new_node;
new_node->parent = parent;
break;
}
else
{
parent = parent->left;
}
}
else
{
++parent->weight_right;
if (parent->right == NULL)
{
parent->right = new_node;
new_node->parent = parent;
break;
}
else
{
parent = parent->right;
}
}
}
// Rebalance/update ancestors in order
ost_node* node = parent;
while (node)
{
int dl = depth(node->left), dr = depth(node->right);
if (node->depth_left == dl && node->depth_right == dr)
{
// Depth did not change at this level
break;
}
node->depth_left = dl;
node->depth_right = dr;
int diff = node->depth_left - node->depth_right;
if (diff > 1)
{
// Left child is too heavy
if (node->left->depth_left < node->left->depth_right)
node->left = left_rotate(node->left);
node = right_rotate(node);
}
else if (diff < -1)
{
// Right child is too heavy
if (node->right->depth_left > node->right->depth_right)
node->right = right_rotate(node->right);
node = left_rotate(node);
}
if (!node->parent)
tree->root = node;
node = node->parent;
}
}
return new_node;
}
ost_node* ost_find(ost* tree, const void* data)
{
ost_node* node = tree->root;
while (node) {
int c = tree->comp_fn(data, node->data);
if (c == 0)
return node;
else if (c < 0)
node = node->left;
else
node = node->right;
}
return NULL;
}
int ost_count(ost* tree)
{
return weight(tree->root);
}
ost_node* ost_inorder_first(ost* tree)
{
ost_node* node = tree->root;
if (!node) return NULL;
while (node->left)
node = node->left;
return node;
}
ost_node* ost_inorder_last(ost* tree)
{
ost_node* node = tree->root;
if (!node) return NULL;
while (node->right)
node = node->right;
return node;
}
ost_node* ost_inorder_next(ost_node* node)
{
// If there is a right subtree, return the leftmost node in that subtree
if (node->right)
{
node = node->right;
while(node->left)
node = node->left;
return node;
}
// Climb up the tree and find the first link where the parent is to the right of the child. Return that parent.
if (node->parent)
{
while (node->parent && node == node->parent->right)
node = node->parent;
return node->parent;
}
return NULL;
}
ost_node* ost_inorder_prev(ost_node* node)
{
// If there is a left subtree, return the rightmost node in that subtree
if (node->left)
{
node = node->left;
while(node->right)
node = node->right;
return node;
}
// Climb up the tree and find the first link where the parent is to the left of the child. Return that parent.
if (node->parent)
{
while (node->parent && node == node->parent->left)
node = node->parent;
return node->parent;
}
return NULL;
}
ost_node* ost_select(ost* tree, int index)
{
if (!tree->root) return NULL;
ost_node* node = tree->root;
int acc = node->weight_left;
while (1)
{
if (index == acc)
{
return node;
}
else if (index < acc)
{
if (!node->left) break;
node = node->left;
acc -= node->weight_right + 1;
}
else
{
if (!node->right) break;
node = node->right;
acc += node->weight_left + 1;
}
}
return NULL;
}
int ost_index_of(ost_node* node)
{
int acc = node->weight_left;
while (node->parent)
{
if (node == node->parent->right)
acc += weight(node->parent->left) + 1;
node = node->parent;
}
return acc;
}