pintos-os.org Git - pspp/blob - src/ui/gui/pspp-rb-tree.h

   1  /* PSPPIRE - a graphical user interface for PSPP.
   2     Copyright (C) 2011 Free Software Foundation, Inc.
   3
   4     This program is free software: you can redistribute it and/or modify
   5     it under the terms of the GNU General Public License as published by
   6     the Free Software Foundation, either version 3 of the License, or
   7     (at your option) any later version.
   8
   9     This program is distributed in the hope that it will be useful,
  10     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12     GNU General Public License for more details.
  13
  14     You should have received a copy of the GNU General Public License
  15     along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 /* gtkrbtree.h
  18  * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
  19  *
  20  * This library is free software; you can redistribute it and/or
  21  * modify it under the terms of the GNU Library General Public
  22  * License as published by the Free Software Foundation; either
  23  * version 2 of the License, or (at your option) any later version.
  24  *
  25  * This library is distributed in the hope that it will be useful,
  26  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  28  * Library General Public License for more details.
  29  *
  30  * You should have received a copy of the GNU Library General Public
  31  * License along with this library; if not, write to the
  32  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  33  * Boston, MA 02111-1307, USA.
  34  */
  35
  36 /* A Red-Black Tree implementation used specifically by PsppSheetView.
  37  */
  38 #ifndef __PSPP_RBTREE_H__
  39 #define __PSPP_RBTREE_H__
  40
  41 #include <glib.h>
  42
  43
  44 G_BEGIN_DECLS
  45
  46
  47 typedef enum
  48 {
  49   PSPP_RBNODE_BLACK = 1 << 0,
  50   PSPP_RBNODE_RED = 1 << 1,
  51   PSPP_RBNODE_IS_PARENT = 1 << 2,
  52   PSPP_RBNODE_IS_SELECTED = 1 << 3,
  53   PSPP_RBNODE_IS_PRELIT = 1 << 4,
  54   PSPP_RBNODE_IS_SEMI_COLLAPSED = 1 << 5,
  55   PSPP_RBNODE_IS_SEMI_EXPANDED = 1 << 6,
  56   PSPP_RBNODE_INVALID = 1 << 7,
  57   PSPP_RBNODE_COLUMN_INVALID = 1 << 8,
  58   PSPP_RBNODE_DESCENDANTS_INVALID = 1 << 9,
  59   PSPP_RBNODE_NON_COLORS = PSPP_RBNODE_IS_PARENT |
  60                           PSPP_RBNODE_IS_SELECTED |
  61                           PSPP_RBNODE_IS_PRELIT |
  62                           PSPP_RBNODE_IS_SEMI_COLLAPSED |
  63                           PSPP_RBNODE_IS_SEMI_EXPANDED |
  64                           PSPP_RBNODE_INVALID |
  65                           PSPP_RBNODE_COLUMN_INVALID |
  66                           PSPP_RBNODE_DESCENDANTS_INVALID
  67 } GtkRBNodeColor;
  68
  69 typedef struct _GtkRBTree GtkRBTree;
  70 typedef struct _GtkRBNode GtkRBNode;
  71 typedef struct _GtkRBTreeView GtkRBTreeView;
  72
  73 typedef void (*GtkRBTreeTraverseFunc) (GtkRBTree  *tree,
  74                                        GtkRBNode  *node,
  75                                        gpointer  data);
  76
  77 struct _GtkRBTree
  78 {
  79   GtkRBNode *root;
  80   GtkRBNode *nil;
  81   GtkRBTree *parent_tree;
  82   GtkRBNode *parent_node;
  83 };
  84
  85 struct _GtkRBNode
  86 {
  87   guint flags : 14;
  88
  89   /* We keep track of whether the aggregate count of children plus 1
  90    * for the node itself comes to an even number.  The parity flag is
  91    * the total count of children mod 2, where the total count of
  92    * children gets computed in the same way that the total offset gets
  93    * computed. i.e. not the same as the "count" field below which
  94    * doesn't include children. We could replace parity with a
  95    * full-size int field here, and then take % 2 to get the parity flag,
  96    * but that would use extra memory.
  97    */
  98
  99   guint parity : 1;
 100
 101   GtkRBNode *left;
 102   GtkRBNode *right;
 103   GtkRBNode *parent;
 104
 105   /* count is the number of nodes beneath us, plus 1 for ourselves.
 106    * i.e. node->left->count + node->right->count + 1
 107    */
 108   gint count;
 109
 110   /* this is the total of sizes of
 111    * node->left, node->right, our own height, and the height
 112    * of all trees in ->children, iff children exists because
 113    * the thing is expanded.
 114    */
 115   gint offset;
 116
 117   /* Child trees */
 118   GtkRBTree *children;
 119 };
 120
 121
 122 #define PSPP_RBNODE_GET_COLOR(node)             (node?(((node->flags&PSPP_RBNODE_RED)==PSPP_RBNODE_RED)?PSPP_RBNODE_RED:PSPP_RBNODE_BLACK):PSPP_RBNODE_BLACK)
 123 #define PSPP_RBNODE_SET_COLOR(node,color)       if((node->flags&color)!=color)node->flags=node->flags^(PSPP_RBNODE_RED|PSPP_RBNODE_BLACK)
 124 #define PSPP_RBNODE_GET_HEIGHT(node)            (node->offset-(node->left->offset+node->right->offset+(node->children?node->children->root->offset:0)))
 125 #define PSPP_RBNODE_SET_FLAG(node, flag)        G_STMT_START{ (node->flags|=flag); }G_STMT_END
 126 #define PSPP_RBNODE_UNSET_FLAG(node, flag)      G_STMT_START{ (node->flags&=~(flag)); }G_STMT_END
 127 #define PSPP_RBNODE_FLAG_SET(node, flag)        (node?(((node->flags&flag)==flag)?TRUE:FALSE):FALSE)
 128
 129
 130 GtkRBTree *_pspp_rbtree_new              (void);
 131 void       _pspp_rbtree_free             (GtkRBTree              *tree);
 132 void       _pspp_rbtree_remove           (GtkRBTree              *tree);
 133 void       _pspp_rbtree_destroy          (GtkRBTree              *tree);
 134 GtkRBNode *_pspp_rbtree_insert_before    (GtkRBTree              *tree,
 135                                          GtkRBNode              *node,
 136                                          gint                    height,
 137                                          gboolean                valid);
 138 GtkRBNode *_pspp_rbtree_insert_after     (GtkRBTree              *tree,
 139                                          GtkRBNode              *node,
 140                                          gint                    height,
 141                                          gboolean                valid);
 142 void       _pspp_rbtree_remove_node      (GtkRBTree              *tree,
 143                                          GtkRBNode              *node);
 144 void       _pspp_rbtree_reorder          (GtkRBTree              *tree,
 145                                          gint                   *new_order,
 146                                          gint                    length);
 147 GtkRBNode *_pspp_rbtree_find_count       (GtkRBTree              *tree,
 148                                          gint                    count);
 149 void       _pspp_rbtree_node_set_height  (GtkRBTree              *tree,
 150                                          GtkRBNode              *node,
 151                                          gint                    height);
 152 void       _pspp_rbtree_node_mark_invalid(GtkRBTree              *tree,
 153                                          GtkRBNode              *node);
 154 void       _pspp_rbtree_node_mark_valid  (GtkRBTree              *tree,
 155                                          GtkRBNode              *node);
 156 void       _pspp_rbtree_column_invalid   (GtkRBTree              *tree);
 157 void       _pspp_rbtree_mark_invalid     (GtkRBTree              *tree);
 158 void       _pspp_rbtree_set_fixed_height (GtkRBTree              *tree,
 159                                          gint                    height,
 160                                          gboolean                mark_valid);
 161 gint       _pspp_rbtree_node_find_offset (GtkRBTree              *tree,
 162                                          GtkRBNode              *node);
 163 gint       _pspp_rbtree_node_find_parity (GtkRBTree              *tree,
 164                                          GtkRBNode              *node);
 165 gint       _pspp_rbtree_find_offset      (GtkRBTree              *tree,
 166                                          gint                    offset,
 167                                          GtkRBTree             **new_tree,
 168                                          GtkRBNode             **new_node);
 169 void       _pspp_rbtree_traverse         (GtkRBTree              *tree,
 170                                          GtkRBNode              *node,
 171                                          GTraverseType           order,
 172                                          GtkRBTreeTraverseFunc   func,
 173                                          gpointer                data);
 174 GtkRBNode *_pspp_rbtree_next             (GtkRBTree              *tree,
 175                                          GtkRBNode              *node);
 176 GtkRBNode *_pspp_rbtree_prev             (GtkRBTree              *tree,
 177                                          GtkRBNode              *node);
 178 void       _pspp_rbtree_next_full        (GtkRBTree              *tree,
 179                                          GtkRBNode              *node,
 180                                          GtkRBTree             **new_tree,
 181                                          GtkRBNode             **new_node);
 182 void       _pspp_rbtree_prev_full        (GtkRBTree              *tree,
 183                                          GtkRBNode              *node,
 184                                          GtkRBTree             **new_tree,
 185                                          GtkRBNode             **new_node);
 186
 187 gint       _pspp_rbtree_get_depth        (GtkRBTree              *tree);
 188
 189 /* This func checks the integrity of the tree */
 190 #ifdef G_ENABLE_DEBUG
 191 void       _pspp_rbtree_test             (const gchar            *where,
 192                                          GtkRBTree              *tree);
 193 void       _pspp_rbtree_debug_spew       (GtkRBTree              *tree);
 194 #endif
 195
 196
 197 G_END_DECLS
 198
 199
 200 #endif /* __PSPP_RBTREE_H__ */