copying 2.5 over to trunk
[blender-staging.git] / source / blender / blenlib / BLI_dlrbTree.h
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
21  * All rights reserved.
22  *
23  * Contributor(s): Joshua Leung (original author)
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 #ifndef BLI_DLRB_TREE_H
29 #define BLI_DLRB_TREE_H
30
31 /* Double-Linked Red-Black Tree Implementation:
32  * 
33  * This is simply a Red-Black Tree implementation whose nodes can later
34  * be arranged + retrieved as elements in a Double-Linked list (i.e. ListBase).
35  * The Red-Black Tree implementation is based on the methods defined by Wikipedia.
36  */
37
38 /* ********************************************** */
39 /* Data Types and Type Defines  */
40
41 /* Base Structs --------------------------------- */
42
43 /* Basic Layout for a Node */
44 typedef struct DLRBT_Node {
45         /* ListBase capabilities */
46         struct DLRBT_Node *next, *prev;         
47         
48         /* Tree Associativity settings */
49         struct DLRBT_Node *left, *right;
50         struct DLRBT_Node *parent;
51         
52         char tree_col;
53         /* ... for nice alignment, next item should usually be a char too... */
54 } DLRBT_Node;
55
56 /* Red/Black defines for tree_col */
57 enum eDLRBT_Colors {
58         DLRBT_BLACK= 0,
59         DLRBT_RED,
60 };
61
62 /* -------- */
63
64 /* The Tree Data */
65 typedef struct DLRBT_Tree {
66         /* ListBase capabilities */
67         void *first, *last;                     /* these should be based on DLRBT_Node-s */
68
69         /* Root Node */
70         void *root;                                     /* this should be based on DLRBT_Node-s */
71 } DLRBT_Tree;
72
73 /* ********************************************** */
74 /* Public API */
75
76 /* Create a new tree, and initialise as necessary */
77 DLRBT_Tree *BLI_dlrbTree_new(void);
78
79 /* Initialises some given trees */
80 void BLI_dlrbTree_init(DLRBT_Tree *tree);
81
82 /* Free some tree */
83 void BLI_dlrbTree_free(DLRBT_Tree *tree);
84
85 /* Make sure the tree's Double-Linked list representation is valid */
86 void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree);
87
88
89
90 /* Balance the tree after the given element has been added to it 
91  * (using custom code, in the Binary Tree way).
92  */
93 void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node);
94
95 /* Remove the given element from the tree and balance again */
96 // FIXME: this is not implemented yet... 
97 void BLI_dlrbTree_remove(DLRBT_Tree *tree, DLRBT_Node *node);
98
99 /* ********************************************** */
100
101 #endif // BLI_DLRB_TREE_H