gdsl_bstree.c

一个通用的C语言实现的数据结构

    return t;
}

/******************************************************************************/
/* Search functions of binary search trees                                    */
/******************************************************************************/

extern gdsl_element_t
gdsl_bstree_search (const gdsl_bstree_t t, gdsl_compare_func_t f, void* v)
{
    _gdsl_bintree_t n;

    assert (t != NULL);
 
    n = bstree_search (ROOT (t), SENT (t), f ? f : t->comp_f, v);

    return (n == NULL) ? NULL : CONTENT (n);
}

/******************************************************************************/
/* Parse functions of binary search trees                                     */
/******************************************************************************/

extern gdsl_element_t
gdsl_bstree_map_prefix (const gdsl_bstree_t t, gdsl_map_func_t map_f, 
			void* d)
{
    assert (t != NULL);
    assert (map_f != NULL);

    return bstree_prefix_parse (ROOT (t), SENT (t), map_f, d);
}

extern gdsl_element_t
gdsl_bstree_map_infix (const gdsl_bstree_t t, gdsl_map_func_t map_f, void* d)
{
    assert (t != NULL);
    assert (map_f != NULL);

    return bstree_infix_parse (ROOT (t), SENT (t), map_f, d);
}

extern gdsl_element_t
gdsl_bstree_map_postfix (const gdsl_bstree_t t, gdsl_map_func_t map_f, 
			 void* d)
{
    assert (t != NULL);
    assert (map_f != NULL);

    return bstree_postfix_parse (ROOT (t), SENT (t), map_f, d);
}

#if 0
extern gdsl_element_t
gdsl_bstree_level_parse (const gdsl_bstree_t t, gdsl_map_func_t map_f, void* d)
{
    assert (t != NULL);
    assert (map_f != NULL);

    /* !! TO DO... !! */
    return NULL;
}
#endif

/******************************************************************************/
/* Input/output functions of binary search trees                              */
/******************************************************************************/

extern void
gdsl_bstree_write (const gdsl_bstree_t t, gdsl_write_func_t write_f, FILE* file,
		   void* d)
{
    assert (t != NULL);
    assert (write_f != NULL);
    assert (file != NULL);

    bstree_write (ROOT (t), SENT (t), write_f, file, d);
}

extern void
gdsl_bstree_write_xml (const gdsl_bstree_t t, gdsl_write_func_t write_f, 
		       FILE* file, void* d)
{
    assert (t != NULL);
    assert (file != NULL);

    fprintf (file, "<GDSL_BSTREE REF=\"%p\" NAME=\"%s\" CARD=\"%ld\">\n",
	     (void*) t, t->name, t->card);

    bstree_write_xml (ROOT (t), SENT (t), write_f, file, d);

    fprintf (file, "</GDSL_BSTREE>\n");
}

extern void
gdsl_bstree_dump (const gdsl_bstree_t t, gdsl_write_func_t write_f, FILE* file, 
		  void* d)
{
    assert (t != NULL);
    assert (file != NULL);

    fprintf (file, "<GDSL_BSTREE REF=\"%p\" NAME=\"%s\" CARD=\"%ld\">\n",
	     (void*) t, t->name, t->card);
    fprintf (file, "<GDSL_BSTREE_SENT REF=\"%p\" LEFT=\"%p\" RIGHT=\"%p\" PARENT=\"%p\"/>\n", 
	     (void*) SENT (t), (void*) LEFT (SENT (t)), 
	     (void*) RIGHT (SENT (t)), (void*) PARENT (SENT (t)));

    bstree_dump (ROOT (t), SENT (t), write_f, file, d);

    fprintf (file, "</GDSL_BSTREE>\n");
}

/******************************************************************************/
/* Private functions                                                          */
/******************************************************************************/

static gdsl_element_t 
default_alloc (void* e)
{
    return e;
}

static void 
default_free (gdsl_element_t e)
{
    ;
}

static long int 
default_comp (gdsl_element_t e, void* key)
{
    return 0;
}

static void 
bstree_free (_gdsl_bintree_t n, _gdsl_bintree_t sent, gdsl_free_func_t f)
{
    if (n != sent)
	{
	    bstree_free (LEFT (n), sent, f);
	    bstree_free (RIGHT (n), sent, f);
	    f (CONTENT (n));
	    free (n);
	}
}

static ulong
bstree_height (_gdsl_bintree_t n, _gdsl_bintree_t sent)
{
    if (n == sent)
	{
	    return 0UL;
	}

    if (LEFT (n) == sent && RIGHT (n) == sent)
	{
	    return 0UL;
	}

    return (ulong) (1UL + 
		    GDSL_MAX (bstree_height (LEFT (n), sent),
			      bstree_height (RIGHT (n), sent)));
}

static _gdsl_bintree_t
bstree_search (_gdsl_bintree_t root, _gdsl_bintree_t sent, gdsl_compare_func_t f, void* v)
{
    int comp;

    while (root != sent)
	{
	    comp = f (CONTENT (root), v);

	    if (comp == 0)
		{
		    return root;
		}

	    if (comp > 0)
		{
		    root = LEFT (root);
		}
	    else
		{
		    root = RIGHT (root);
		}
	}

    return NULL;
}

static _gdsl_bintree_t
bstree_next (gdsl_bstree_t t, _gdsl_bintree_t n)
{
    n = RIGHT (n);

    while (LEFT (n) != SENT (t))
	{
	    n = LEFT (n);
	}

    return n;
}

static gdsl_element_t
bstree_prefix_parse (_gdsl_bintree_t root, _gdsl_bintree_t sent, 
		     gdsl_map_func_t map_f, void* user_data)
{
    if (root != sent)
	{
	    gdsl_element_t e = CONTENT (root);

	    if (map_f (e, get_location (root, sent), user_data) == GDSL_MAP_STOP) 
		{
		    return e;
		}

	    bstree_prefix_parse (LEFT (root), sent, map_f, user_data);
	    bstree_prefix_parse (RIGHT (root), sent, map_f, user_data); 
	}

    return NULL;
}

static gdsl_element_t
bstree_infix_parse (_gdsl_bintree_t root, _gdsl_bintree_t sent, 
		    gdsl_map_func_t map_f, void* user_data)
{
    if (root != sent)
	{
	    gdsl_element_t e;

	    bstree_infix_parse (LEFT (root), sent, map_f, user_data);

	    e = CONTENT (root);

	    if (map_f (e, get_location (root, sent), user_data) == GDSL_MAP_STOP) 
		{
		    return e;
		}

	    bstree_infix_parse (RIGHT (root), sent, map_f, user_data);
	}

    return NULL;
}

static gdsl_element_t
bstree_postfix_parse (_gdsl_bintree_t root, _gdsl_bintree_t sent, 
		      gdsl_map_func_t map_f, void* user_data)
{
    if (root != sent)
	{
	    gdsl_element_t e;

	    bstree_postfix_parse (LEFT (root), sent, map_f, user_data);
	    bstree_postfix_parse (RIGHT (root), sent, map_f, user_data);

	    e = CONTENT (root);

	    if (map_f (e, get_location (root, sent), user_data) == GDSL_MAP_STOP) 
		{
		    return e;
		}
	}

    return NULL;
}

static void
bstree_write (_gdsl_bintree_t n, _gdsl_bintree_t sent, 
	      gdsl_write_func_t write_f, FILE* file, void* d)
{
    if (n != sent)
	{
	    bstree_write (LEFT (n), sent, write_f, file, d);
	    write_f (CONTENT (n), file, get_location (n, sent), d);
	    bstree_write (RIGHT (n), sent, write_f, file, d);
	}
}

static void
bstree_write_xml (_gdsl_bintree_t n, _gdsl_bintree_t sent, 
		  gdsl_write_func_t write_f, FILE* file, void* d)
{
    if (n != sent)
	{
	    bstree_write_xml (LEFT (n), sent, write_f, file, d);

	    if (LEFT (n) == sent && RIGHT (n) == sent)
		{
		    fprintf (file, "<GDSL_BSTREE_LEAF REF=\"%p\"", (void*) n);
		}
	    else
		{
		    fprintf (file, "<GDSL_BSTREE_NODE REF=\"%p\"", (void*) n);
		}

	    if (LEFT (n) != sent || RIGHT (n) != sent)
		{
		    if (LEFT (n) != sent)
			{
			    fprintf (file, " LEFT=\"%p\"", (void*) LEFT (n));
			}
		    else
			{
			    fprintf (file, " LEFT=\"\"");
			}
	  
		    if (RIGHT (n) != sent)
			{
			    fprintf (file, " RIGHT=\"%p\"", (void*) RIGHT (n));
			}
		    else
			{
			    fprintf (file, " RIGHT=\"\"");
			}
		}

	    if (PARENT (n) != sent)
		{
		    fprintf (file, " PARENT=\"%p\">", (void*) PARENT (n));
		}
	    else
		{
		    fprintf (file, " PARENT=\"\">");
		}

	    if (write_f != NULL)
		{
		    write_f (CONTENT (n), file, get_location (n, sent), d);
		}

	    if (LEFT (n) == sent && RIGHT (n) == sent)
		{
		    fprintf (file, "</GDSL_BSTREE_LEAF>\n");
		}
	    else
		{
		    fprintf (file, "</GDSL_BSTREE_NODE>\n");
		}

	    bstree_write_xml (RIGHT (n), sent, write_f, file, d);
	}
}

static void
bstree_dump (_gdsl_bintree_t n, _gdsl_bintree_t sent, 
	     gdsl_write_func_t write_f, FILE* file, void* d)
{
    if (n != sent)
	{
	    bstree_dump (LEFT (n), sent, write_f, file, d);

	    if (LEFT (n) == sent && RIGHT (n) == sent)
		{
		    fprintf (file, "<GDSL_BSTREE_LEAF REF=\"%p\"", (void*) n);
		}
	    else
		{
		    fprintf (file, "<GDSL_BSTREE_NODE REF=\"%p\"", (void*) n);
		}

	    if (CONTENT (n) != NULL)
		{
		    fprintf (file, " CONTENT=\"%p\"", (void*) CONTENT (n));
		}
	    else
		{
		    fprintf (file, " CONTENT=\"\"");
		}

	    fprintf (file, " LEFT=\"%p\" RIGHT=\"%p\"", (void*) LEFT (n), (void*) RIGHT (n));

	    if (PARENT (n) != NULL)
		{
		    fprintf (file, " PARENT=\"%p\">", (void*) PARENT (n));
		}
	    else
		{
		    fprintf (file, " PARENT=\"\">");
		}

	    if (write_f != NULL)
		{
		    write_f (CONTENT (n), file, get_location (n, sent), d);
		}

	    if (LEFT (n) == sent && RIGHT (n) == sent)
		{
		    fprintf (file, "</GDSL_BSTREE_LEAF>\n");
		}
	    else
		{
		    fprintf (file, "</GDSL_BSTREE_NODE>\n");
		}

	    bstree_dump (RIGHT (n), sent, write_f, file, d);
	}
}

static gdsl_location_t
get_location (_gdsl_bintree_t n, _gdsl_bintree_t s)
{
    gdsl_location_t location = GDSL_LOCATION_UNDEF;

    if (PARENT (n) == s)
	{
	    location |= GDSL_LOCATION_ROOT;
	}

    if (LEFT (n) == s && RIGHT (n) == s)
	{
	    location |= GDSL_LOCATION_LEAF;
	}

    return location;
}


/** EMACS **
 * Local variables:
 * mode: c
 * c-basic-offset: 4
 * End:
 */