octave-kai/gnulib-hg: lib/gl_avltree

annotate lib/gl_avltree_oset.c @ 17476:6057744acd2c default tip master

autoupdate

author	Karl Berry <karl@freefriends.org>
date	Fri, 16 Aug 2013 06:32:22 -0700
parents	e542fd46ad6f
children

rev	line source
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	1 /* Ordered set data type implemented by a binary tree.
17249 e542fd46ad6f maint: update all copyright year number ranges Eric Blake <eblake@redhat.com> parents: 16201 diff changeset	2 Copyright (C) 2006-2007, 2009-2013 Free Software Foundation, Inc.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	3 Written by Bruno Haible <bruno@clisp.org>, 2006.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	4
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8436 diff changeset	5 This program is free software: you can redistribute it and/or modify
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	6 it under the terms of the GNU General Public License as published by
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8436 diff changeset	7 the Free Software Foundation; either version 3 of the License, or
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8436 diff changeset	8 (at your option) any later version.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	9
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	10 This program is distributed in the hope that it will be useful,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	11 but WITHOUT ANY WARRANTY; without even the implied warranty of
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	13 GNU General Public License for more details.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	14
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	15 You should have received a copy of the GNU General Public License
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8436 diff changeset	16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	17
7304 1c4ed7637c24 Include <config.h> unconditionally. Bruno Haible <bruno@clisp.org> parents: 6982 diff changeset	18 #include <config.h>
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	19
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	20 /* Specification. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	21 #include "gl_avltree_oset.h"
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	22
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	23 #include <stdlib.h>
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	24
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	25 /* An AVL tree is a binary tree where
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	26 1. The height of each node is calculated as
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	27 heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	28 2. The heights of the subtrees of each node differ by at most 1:
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	29 \| heightof(right) - heightof(left) \| <= 1.
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	30 3. The index of the elements in the node.left subtree are smaller than
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	31 the index of node.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	32 The index of the elements in the node.right subtree are larger than
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	33 the index of node.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	34 */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	35
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	36 /* -------------------------- gl_oset_t Data Type -------------------------- */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	37
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	38 /* Tree node implementation, valid for this file only. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	39 struct gl_oset_node_impl
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	40 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 struct gl_oset_node_impl left; / left branch, or NULL */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	42 struct gl_oset_node_impl right; / right branch, or NULL */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	43 /* Parent pointer, or NULL. The parent pointer is not needed for most
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	44 operations. It is needed so that a gl_oset_node_t can be returned
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 without memory allocation, on which the functions gl_oset_remove_node,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	46 gl_oset_add_before, gl_oset_add_after can be implemented. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	47 struct gl_oset_node_impl *parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	48 int balance; /* heightof(right) - heightof(left),
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	49 always = -1 or 0 or 1 */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 const void *value;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	51 };
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	52 typedef struct gl_oset_node_impl * gl_oset_node_t;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	53
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	54 /* Concrete gl_oset_impl type, valid for this file only. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	55 struct gl_oset_impl
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	56 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	57 struct gl_oset_impl_base base;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	58 struct gl_oset_node_impl root; / root node or NULL */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	59 size_t count; /* number of nodes */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	60 };
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	61
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	62 /* An AVL tree of height h has at least F_(h+2) [Fibonacci number] and at most
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	63 2^h - 1 elements. So, h <= 84 (because a tree of height h >= 85 would have
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	64 at least F_87 elements, and because even on 64-bit machines,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	65 sizeof (gl_oset_node_impl) * F_87 > 2^64
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	66 this would exceed the address space of the machine. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	67 #define MAXHEIGHT 83
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	68
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	69 /* Ensure the tree is balanced, after an insertion or deletion operation.
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	70 The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	71 PARENT = NODE->parent. (NODE can also be NULL. But PARENT is non-NULL.)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	72 Rotation operations are performed starting at PARENT (not NODE itself!). */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	73 static void
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	74 rebalance (gl_oset_t set,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	75 gl_oset_node_t node, int height_diff, gl_oset_node_t parent)
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	76 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	77 for (;;)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	78 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	79 gl_oset_node_t child;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	80 int previous_balance;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	81 int balance_diff;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	82 gl_oset_node_t nodeleft;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	83 gl_oset_node_t noderight;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	84
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	85 child = node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	86 node = parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	87
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	88 previous_balance = node->balance;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	89
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	90 /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	91 branch's height has increased by 1 or the left branch's height has
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	92 decreased by 1, -1 if the right branch's height has decreased by 1 or
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	93 the left branch's height has increased by 1, 0 if no height change. */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	94 if (node->left != NULL \|\| node->right != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	95 balance_diff = (child == node->right ? height_diff : -height_diff);
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	97 /* Special case where above formula doesn't work, because the caller
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	98 didn't tell whether node's left or right branch shrunk from height 1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	99 to NULL. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	100 balance_diff = - previous_balance;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	101
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	102 node->balance += balance_diff;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	103 if (balance_diff == previous_balance)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	104 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	105 /* node->balance is outside the range [-1,1]. Must rotate. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	106 gl_oset_node_t *nodep;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	107
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	108 if (node->parent == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	109 /* node == set->root */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	110 nodep = &set->root;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	111 else if (node->parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	112 nodep = &node->parent->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	113 else if (node->parent->right == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	114 nodep = &node->parent->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	115 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	116 abort ();
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	117
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	118 nodeleft = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	119 noderight = node->right;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	120
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	121 if (balance_diff < 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	122 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	123 /* node->balance = -2. The subtree is heavier on the left side.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	124 Rotate from left to right:
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	125
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	126 *
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	127 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	128 h+2 h
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	129 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	130 gl_oset_node_t nodeleftright = nodeleft->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	131 if (nodeleft->balance <= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	132 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	133 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	134 * h+2\|h+3
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	135 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	136 h+2 h --> / h+1\|h+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	137 / \ \| / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	138 h+1 h\|h+1 h+1 h\|h+1 h
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	139 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	140 node->left = nodeleftright;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	141 nodeleft->right = node;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	142
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	143 nodeleft->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	144 node->parent = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	145 if (nodeleftright != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	146 nodeleftright->parent = node;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	147
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	148 nodeleft->balance += 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	149 node->balance = - nodeleft->balance;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	150
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	151 *nodep = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	152 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	153 ? /* noderight's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	154 h+1 to h. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	155 h+3 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	156 nodeleft->balance - 1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	157 : /* nodeleft's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	158 h+1 to h+2. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	159 h+2 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	160 nodeleft->balance);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	161 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	162 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	163 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	164 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	165 * h+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	166 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	167 h+2 h --> h+1 h+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	168 / \ / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	169 h h+1 h L R h
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	170 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	171 L R
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	172
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	173 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	174 gl_oset_node_t L = nodeleft->right = nodeleftright->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	175 gl_oset_node_t R = node->left = nodeleftright->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	176 nodeleftright->left = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	177 nodeleftright->right = node;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	178
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	179 nodeleftright->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	180 if (L != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	181 L->parent = nodeleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	182 if (R != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	183 R->parent = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	184 nodeleft->parent = nodeleftright;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	185 node->parent = nodeleftright;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	186
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	187 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	188 node->balance = (nodeleftright->balance < 0 ? 1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	189 nodeleftright->balance = 0;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	190
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	191 *nodep = nodeleftright;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	192 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	193 ? /* noderight's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	194 h+1 to h. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	195 h+3 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	196 -1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	197 : /* nodeleft's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	198 h+1 to h+2. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	199 h+2 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	200 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	201 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	202 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	203 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	204 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	205 /* node->balance = 2. The subtree is heavier on the right side.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	206 Rotate from right to left:
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	207
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	208 *
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	209 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	210 h h+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	211 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	212 gl_oset_node_t noderightleft = noderight->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	213 if (noderight->balance >= 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	214 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	215 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	216 * h+2\|h+3
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	217 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	218 h h+2 --> h+1\|h+2 \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	219 / \ / \ \|
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	220 h\|h+1 h+1 h h\|h+1 h+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	221 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	222 node->right = noderightleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	223 noderight->left = node;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	224
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	225 noderight->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	226 node->parent = noderight;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	227 if (noderightleft != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	228 noderightleft->parent = node;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	229
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	230 noderight->balance -= 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	231 node->balance = - noderight->balance;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	232
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	233 *nodep = noderight;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	234 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	235 ? /* nodeleft's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	236 h+1 to h. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	237 h+3 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	238 - noderight->balance - 1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	239 : /* noderight's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	240 h+1 to h+2. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	241 h+2 to h+2\|h+3. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	242 - noderight->balance);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	243 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	244 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	245 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	246 /*
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	247 * h+2
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	248 / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	249 h h+2 --> h+1 h+1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	250 / \ / \ / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	251 h+1 h h L R h
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	252 / \
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	253 L R
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	254
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	255 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	256 gl_oset_node_t L = node->right = noderightleft->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	257 gl_oset_node_t R = noderight->left = noderightleft->right;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	258 noderightleft->left = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	259 noderightleft->right = noderight;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	260
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	261 noderightleft->parent = node->parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	262 if (L != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	263 L->parent = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	264 if (R != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	265 R->parent = noderight;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	266 node->parent = noderightleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	267 noderight->parent = noderightleft;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	268
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	269 node->balance = (noderightleft->balance > 0 ? -1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	270 noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	271 noderightleft->balance = 0;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	272
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	273 *nodep = noderightleft;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	274 height_diff = (height_diff < 0
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	275 ? /* nodeleft's height had been decremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	276 h+1 to h. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	277 h+3 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	278 -1
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	279 : /* noderight's height had been incremented from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	280 h+1 to h+2. The subtree's height changes from
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	281 h+2 to h+2. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	282 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	283 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	284 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	285 node = *nodep;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	286 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	287 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	288 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	289 /* No rotation needed. Only propagation of the height change to the
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	290 next higher level. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	291 if (height_diff < 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	292 height_diff = (previous_balance == 0 ? 0 : -1);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	293 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	294 height_diff = (node->balance == 0 ? 0 : 1);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	295 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	296
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	297 if (height_diff == 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	298 break;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	299
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	300 parent = node->parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	301 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	302 break;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	303 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	304 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	305
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	306 static gl_oset_node_t
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	307 gl_tree_nx_add_first (gl_oset_t set, const void *elt)
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	308 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	309 /* Create new node. */
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	310 gl_oset_node_t new_node =
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	311 (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	312
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	313 if (new_node == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	314 return NULL;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	315
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	316 new_node->left = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	317 new_node->right = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	318 new_node->balance = 0;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	319 new_node->value = elt;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	320
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	321 /* Add it to the tree. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	322 if (set->root == NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	323 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	324 set->root = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	325 new_node->parent = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	326 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	327 else
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	328 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	329 gl_oset_node_t node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	330
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	331 for (node = set->root; node->left != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	332 node = node->left;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	333
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	334 node->left = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	335 new_node->parent = node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	336 node->balance--;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	337
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	338 /* Rebalance. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	339 if (node->right == NULL && node->parent != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	340 rebalance (set, node, 1, node->parent);
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	341 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	342
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	343 set->count++;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	344 return new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	345 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	346
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	347 static gl_oset_node_t
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	348 gl_tree_nx_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	349 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	350 /* Create new node. */
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	351 gl_oset_node_t new_node =
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	352 (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	353 bool height_inc;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	354
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	355 if (new_node == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	356 return NULL;
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	357
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	358 new_node->left = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	359 new_node->right = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	360 new_node->balance = 0;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	361 new_node->value = elt;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	362
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	363 /* Add it to the tree. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	364 if (node->left == NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	365 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	366 node->left = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	367 node->balance--;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	368 height_inc = (node->right == NULL);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	369 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	370 else
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	371 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	372 for (node = node->left; node->right != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	373 node = node->right;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	374 node->right = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	375 node->balance++;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	376 height_inc = (node->left == NULL);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	377 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	378 new_node->parent = node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	379
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	380 /* Rebalance. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	381 if (height_inc && node->parent != NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	382 rebalance (set, node, 1, node->parent);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	383
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	384 set->count++;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	385 return new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	386 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	387
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	388 static gl_oset_node_t
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	389 gl_tree_nx_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	390 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	391 /* Create new node. */
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	392 gl_oset_node_t new_node =
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	393 (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	394 bool height_inc;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	395
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	396 if (new_node == NULL)
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	397 return NULL;
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	398
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	399 new_node->left = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	400 new_node->right = NULL;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	401 new_node->balance = 0;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	402 new_node->value = elt;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	403
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	404 /* Add it to the tree. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	405 if (node->right == NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	406 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	407 node->right = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	408 node->balance++;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	409 height_inc = (node->left == NULL);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	410 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	411 else
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	412 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	413 for (node = node->right; node->left != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	414 node = node->left;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	415 node->left = new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	416 node->balance--;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	417 height_inc = (node->right == NULL);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	418 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	419 new_node->parent = node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	420
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	421 /* Rebalance. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	422 if (height_inc && node->parent != NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	423 rebalance (set, node, 1, node->parent);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	424
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	425 set->count++;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	426 return new_node;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	427 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	428
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	429 static bool
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	430 gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	431 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	432 gl_oset_node_t parent = node->parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	433
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	434 if (node->left == NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	435 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	436 /* Replace node with node->right. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	437 gl_oset_node_t child = node->right;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	438
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	439 if (child != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	440 child->parent = parent;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	441 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	442 set->root = child;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	443 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	444 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	445 if (parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	446 parent->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	447 else /* parent->right == node */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	448 parent->right = child;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	449
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	450 rebalance (set, child, -1, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	451 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	452 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	453 else if (node->right == NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	454 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	455 /* It is not absolutely necessary to treat this case. But the more
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	456 general case below is more complicated, hence slower. */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	457 /* Replace node with node->left. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	458 gl_oset_node_t child = node->left;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	459
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	460 child->parent = parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	461 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	462 set->root = child;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	463 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	464 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	465 if (parent->left == node)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	466 parent->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	467 else /* parent->right == node */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	468 parent->right = child;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	469
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	470 rebalance (set, child, -1, parent);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	471 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	472 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	473 else
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	474 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	475 /* Replace node with the rightmost element of the node->left subtree. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	476 gl_oset_node_t subst;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	477 gl_oset_node_t subst_parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	478 gl_oset_node_t child;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	479
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	480 for (subst = node->left; subst->right != NULL; )
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	481 subst = subst->right;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	482
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	483 subst_parent = subst->parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	484
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	485 child = subst->left;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	486
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	487 /* The case subst_parent == node is special: If we do nothing special,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	488 we get confusion about node->left, subst->left and child->parent.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	489 subst_parent == node
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	490 <==> The 'for' loop above terminated immediately.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	491 <==> subst == subst_parent->left
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	492 [otherwise subst == subst_parent->right]
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	493 In this case, we would need to first set
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	494 child->parent = node; node->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	495 and later - when we copy subst into node's position - again
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	496 child->parent = subst; subst->left = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	497 Altogether a no-op. */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	498 if (subst_parent != node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	499 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	500 if (child != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	501 child->parent = subst_parent;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	502 subst_parent->right = child;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	503 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	504
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	505 /* Copy subst into node's position.
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	506 (This is safer than to copy subst's value into node, keep node in
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	507 place, and free subst.) */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	508 if (subst_parent != node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	509 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	510 subst->left = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	511 subst->left->parent = subst;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	512 }
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	513 subst->right = node->right;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	514 subst->right->parent = subst;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	515 subst->balance = node->balance;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	516 subst->parent = parent;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	517 if (parent == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	518 set->root = subst;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	519 else if (parent->left == node)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	520 parent->left = subst;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	521 else /* parent->right == node */
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	522 parent->right = subst;
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	523
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	524 /* Rebalancing starts at child's parent, that is subst_parent -
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	525 except when subst_parent == node. In this case, we need to use
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	526 its replacement, subst. */
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	527 rebalance (set, child, -1, subst_parent != node ? subst_parent : subst);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	528 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	529
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	530 set->count--;
8436 36bbb949160c Add an element disposal function. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	531 if (set->base.dispose_fn != NULL)
36bbb949160c Add an element disposal function. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	532 set->base.dispose_fn (node->value);
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	533 free (node);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	534 return true;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	535 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	536
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	537 /* Generic binary tree code. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	538 #include "gl_anytree_oset.h"
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	539
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	540 /* For debugging. */
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	541 static unsigned int
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	542 check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	543 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	544 unsigned int left_height =
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	545 (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	546 unsigned int right_height =
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	547 (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	548 int balance = (int)right_height - (int)left_height;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	549
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	550 if (!(node->parent == parent))
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	551 abort ();
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	552 if (!(balance >= -1 && balance <= 1))
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	553 abort ();
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	554 if (!(node->balance == balance))
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	555 abort ();
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	556
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	557 (*counterp)++;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	558
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	559 return 1 + (left_height > right_height ? left_height : right_height);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	560 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	561 void
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	562 gl_avltree_oset_check_invariants (gl_oset_t set)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	563 {
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	564 size_t counter = 0;
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	565 if (set->root != NULL)
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	566 check_invariants (set->root, NULL, &counter);
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	567 if (!(set->count == counter))
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	568 abort ();
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	569 }
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	570
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	571 const struct gl_oset_implementation gl_avltree_oset_implementation =
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	572 {
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	573 gl_tree_nx_create_empty,
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	574 gl_tree_size,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	575 gl_tree_search,
7403 2fbd1f779c5f Add a search_atleast operation. Bruno Haible <bruno@clisp.org> parents: 7304 diff changeset	576 gl_tree_search_atleast,
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	577 gl_tree_nx_add,
6982 d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	578 gl_tree_remove,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	579 gl_tree_oset_free,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	580 gl_tree_iterator,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	581 gl_tree_iterator_next,
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	582 gl_tree_iterator_free
d88d781b8e7b Ordered set data type implemented by a binary tree. Bruno Haible <bruno@clisp.org> parents: diff changeset	583 };

Mercurial > hg > octave-kai > gnulib-hg

annotate lib/gl_avltree_oset.c @ 17476:6057744acd2c default tip master