12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * ctrees.h 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * Author: mozman 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * Copyright (c) 2010-2013 by Manfred Moitzi 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * License: MIT-License 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) */ 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef __CTREES_H 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define __CTREES_H 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <Python.h> 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)typedef struct tree_node node_t; 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)struct tree_node { 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) node_t *link[2]; 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PyObject *key; 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PyObject *value; 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int xdata; 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)typedef node_t* nodeptr; 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* common binary tree functions */ 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void ct_delete_tree(node_t *root); 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)int ct_compare(PyObject *key1, PyObject *key2); 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)PyObject *ct_get_item(node_t *root, PyObject *key); 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)node_t *ct_find_node(node_t *root, PyObject *key); 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)node_t *ct_succ_node(node_t *root, PyObject *key); 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)node_t *ct_prev_node(node_t *root, PyObject *key); 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)node_t *ct_max_node(node_t *root); 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)node_t *ct_min_node(node_t *root); 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)node_t *ct_floor_node(node_t *root, PyObject *key); 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)node_t *ct_ceiling_node(node_t *root, PyObject *key); 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)int ct_index_of(node_t *root, PyObject *key); 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)node_t *ct_node_at(node_t *root, int index); 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* unbalanced binary tree */ 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)int ct_bintree_insert(node_t **root, PyObject *key, PyObject *value); 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)int ct_bintree_remove(node_t **root, PyObject *key); 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* avl-tree functions */ 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)int avl_insert(node_t **root, PyObject *key, PyObject *value); 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)int avl_remove(node_t **root, PyObject *key); 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* rb-tree functions */ 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)int rb_insert(node_t **root, PyObject *key, PyObject *value); 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)int rb_remove(node_t **root, PyObject *key); 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif 52