htbtree.c

elinks下lynx是最重要的二个文本浏览器, 在linux下非常实用, lynx比elinks早的多, 目前好像停止开发, 这是lynx源代码

			    father_of_forefather->right = added_element;
			    father_of_element->left = added_element->right;
			    added_element->right = father_of_element;
			}
			added_element->up = father_of_forefather;
		    }
		    else
		    {
			/*
			**
			**               1                       2
			** When tree   2   3        becomes    4    1
			**            4 5                          5 3
			**
			** 1 is used to show that it is the top of the tree
			*/
			added_element->up = NULL;
			father_of_element->left = added_element->right;
			added_element->right = father_of_element;
		    }
		    father_of_element->up = added_element;
		    if (father_of_element->left != NULL)
			father_of_element->left->up = father_of_element;
		}
		else
		{
		    added_element = father_of_element->right;
		    father_of_element->right_depth = added_element->left_depth;
		    added_element->left_depth = 1 +
			    MAXIMUM(father_of_element->right_depth,
				father_of_element->left_depth);
		    if (father_of_element->up != NULL)
			/* Bug fixed in March 94  -  AS */
		    {
			BOOL first_time;

			father_of_forefather = father_of_element->up;
			forefather_of_element = added_element;
			first_time = YES;
			do
			{
			    if (father_of_forefather->left
				== forefather_of_element->up)
			    {
				depth = father_of_forefather->left_depth;
				if (first_time)
				{
				    father_of_forefather->left_depth = 1
				       + MAXIMUM(forefather_of_element->left_depth,
					       forefather_of_element->right_depth);
				    first_time = NO;
				}
				else
				    father_of_forefather->left_depth = 1
				      + MAXIMUM(forefather_of_element->up->left_depth,
					  forefather_of_element->up->right_depth);
				depth2 = father_of_forefather->left_depth;
			    }
			    else
			    {
				depth = father_of_forefather->right_depth;
				if (first_time)
				{
				    father_of_forefather->right_depth = 1
				       + MAXIMUM(forefather_of_element->left_depth,
					       forefather_of_element->right_depth);
				    first_time = NO;
				}
				else
				    father_of_forefather->right_depth = 1
				      + MAXIMUM(forefather_of_element->up->left_depth,
					   forefather_of_element->up->right_depth);
				depth2 = father_of_forefather->right_depth;
			    }
			    father_of_forefather = father_of_forefather->up;
			    forefather_of_element = forefather_of_element->up;
			} while ((depth != depth2) &&
				 (father_of_forefather != NULL));
			father_of_forefather = father_of_element->up;
			if (father_of_forefather->left == father_of_element)
			{
			    /*
			    **                    3                       3
			    **               4                       6
			    ** When tree   5   6        becomes    4    8
			    **                7 8                 5 7
			    **
			    ** 3 is used to show that it may not be the top of the
			    ** tree.
			    */
			    father_of_forefather->left = added_element;
			    father_of_element->right = added_element->left;
			    added_element->left = father_of_element;
			}
			if (father_of_forefather->right == father_of_element)
			{
			    /*
			    **           3                      3
			    **               4                       6
			    ** When tree   5   6        becomes    4    8
			    **                7 8                 5 7
			    **
			    ** 3 is used to show that it may not be the top of the
			    ** tree
			    */
			    father_of_forefather->right = added_element;
			    father_of_element->right = added_element->left;
			    added_element->left = father_of_element;
			}
			added_element->up = father_of_forefather;
		    }
		    else
		    {
			/*
			**
			**               1                       3
			** When tree   2   3        becomes    1    5
			**                4 5                 2 4
			**
			** 1 is used to show that it is the top of the tree.
			*/
			added_element->up = NULL;
			father_of_element->right = added_element->left;
			added_element->left = father_of_element;
		    }
		    father_of_element->up = added_element;
		    if (father_of_element->right != NULL)
			father_of_element->right->up = father_of_element;
		}
	    }
	}
	while (father_of_element->up != NULL)
	{
	    father_of_element = father_of_element->up;
	}
	tree->top = father_of_element;
    }
}



PUBLIC HTBTElement * HTBTree_next ARGS2(
			       HTBTree*,       tree,
			       HTBTElement*,   ele)
    /**************************************************************************
    ** this function returns a pointer to the leftmost element if ele is NULL,
    ** and to the next object to the right otherwise.
    ** If no elements left, returns a pointer to NULL.
    */
{
    HTBTElement * father_of_element;
    HTBTElement * father_of_forefather;

    if (ele == NULL)
    {
	father_of_element = tree->top;
	if (father_of_element != NULL)
	    while (father_of_element->left != NULL)
		father_of_element = father_of_element->left;
    }
    else
    {
	father_of_element = ele;
	if (father_of_element->right != NULL)
	{
	    father_of_element = father_of_element->right;
	    while (father_of_element->left != NULL)
		father_of_element = father_of_element->left;
	}
	else
	{
	    father_of_forefather = father_of_element->up;
		while (father_of_forefather &&
		       (father_of_forefather->right == father_of_element))
		{
		    father_of_element = father_of_forefather;
		    father_of_forefather = father_of_element->up;
		}
	    father_of_element = father_of_forefather;
	}
    }
#ifdef BTREE_TRACE
    /* The option -DBTREE_TRACE will give much more information
    ** about the way the process is running, for debugging matters
    */
    if (father_of_element != NULL)
    {
	printf("\nObject = %s\t",(char *)father_of_element->object);
	if (father_of_element->up != NULL)
	    printf("Objet du pere = %s\n",
		   (char *)father_of_element->up->object);
	else printf("Pas de Pere\n");
	if (father_of_element->left != NULL)
	    printf("Objet du fils gauche = %s\t",
		   (char *)father_of_element->left->object);
	else printf("Pas de fils gauche\t");
	if (father_of_element->right != NULL)
	    printf("Objet du fils droit = %s\n",
		   (char *)father_of_element->right->object);
	else printf("Pas de fils droit\n");
	printf("Profondeur gauche = %d\t",father_of_element->left_depth);
	printf("Profondeur droite = %d\n",father_of_element->right_depth);
	printf("      **************\n");
    }
#endif
    return father_of_element;
}


#ifdef TEST
main ()
    /******************************************************
    ** This is just a test to show how to handle HTBTree.c
    */
{
    HTBTree * tree;
    HTBTElement * next_element;

    tree = HTBTree_new((HTComparer)strcasecomp);
    HTBTree_add(tree,"hypertext");
    HTBTree_add(tree,"Addressing");
    HTBTree_add(tree,"X11");
    HTBTree_add(tree,"Tools");
    HTBTree_add(tree,"Proposal.wn");
    HTBTree_add(tree,"Protocols");
    HTBTree_add(tree,"NeXT");
    HTBTree_add(tree,"Daemon");
    HTBTree_add(tree,"Test");
    HTBTree_add(tree,"Administration");
    HTBTree_add(tree,"LineMode");
    HTBTree_add(tree,"DesignIssues");
    HTBTree_add(tree,"MarkUp");
    HTBTree_add(tree,"Macintosh");
    HTBTree_add(tree,"Proposal.rtf.wn");
    HTBTree_add(tree,"FIND");
    HTBTree_add(tree,"Paper");
    HTBTree_add(tree,"Tcl");
    HTBTree_add(tree,"Talks");
    HTBTree_add(tree,"Architecture");
    HTBTree_add(tree,"VMSHelp");
    HTBTree_add(tree,"Provider");
    HTBTree_add(tree,"Archive");
    HTBTree_add(tree,"SLAC");
    HTBTree_add(tree,"Project");
    HTBTree_add(tree,"News");
    HTBTree_add(tree,"Viola");
    HTBTree_add(tree,"Users");
    HTBTree_add(tree,"FAQ");
    HTBTree_add(tree,"WorkingNotes");
    HTBTree_add(tree,"Windows");
    HTBTree_add(tree,"FineWWW");
    HTBTree_add(tree,"Frame");
    HTBTree_add(tree,"XMosaic");
    HTBTree_add(tree,"People");
    HTBTree_add(tree,"All");
    HTBTree_add(tree,"Curses");
    HTBTree_add(tree,"Erwise");
    HTBTree_add(tree,"Carl");
    HTBTree_add(tree,"MidasWWW");
    HTBTree_add(tree,"XPM");
    HTBTree_add(tree,"MailRobot");
    HTBTree_add(tree,"Illustrations");
    HTBTree_add(tree,"VMClient");
    HTBTree_add(tree,"XPA");
    HTBTree_add(tree,"Clients.html");
    HTBTree_add(tree,"Library");
    HTBTree_add(tree,"CERNLIB_Distribution");
    HTBTree_add(tree,"libHTML");
    HTBTree_add(tree,"WindowsPC");
    HTBTree_add(tree,"tkWWW");
    HTBTree_add(tree,"tk2.3");
    HTBTree_add(tree,"CVS-RCS");
    HTBTree_add(tree,"DecnetSockets");
    HTBTree_add(tree,"SGMLStream");
    HTBTree_add(tree,"NextStep");
    HTBTree_add(tree,"CVSRepository_old");
    HTBTree_add(tree,"ArthurSecret");
    HTBTree_add(tree,"CVSROOT");
    HTBTree_add(tree,"HytelnetGate");
    HTBTree_add(tree,"cern.www.new.src");
    HTBTree_add(tree,"Conditions");
    HTBTree_add(tree,"HTMLGate");
    HTBTree_add(tree,"Makefile");
    HTBTree_add(tree,"Newsgroups.html");
    HTBTree_add(tree,"People.html");
    HTBTree_add(tree,"Bugs.html");
    HTBTree_add(tree,"Summary.html");
    HTBTree_add(tree,"zDesignIssues.wn");
    HTBTree_add(tree,"HT.draw");
    HTBTree_add(tree,"HTandCERN.wn");
    HTBTree_add(tree,"Ideas.wn");
    HTBTree_add(tree,"MarkUp.wn");
    HTBTree_add(tree,"Proposal.html");
    HTBTree_add(tree,"SearchPanel.draw");
    HTBTree_add(tree,"Comments.wn");
    HTBTree_add(tree,"Xanadu.html");
    HTBTree_add(tree,"Storinglinks.html");
    HTBTree_add(tree,"TheW3Book.html");
    HTBTree_add(tree,"Talk_Feb-91.html");
    HTBTree_add(tree,"JFosterEntry.txt");
    HTBTree_add(tree,"Summary.txt");
    HTBTree_add(tree,"Bibliography.html");
    HTBTree_add(tree,"HTandCern.txt");
    HTBTree_add(tree,"Talk.draw");
    HTBTree_add(tree,"zDesignNotes.html");
    HTBTree_add(tree,"Link.html");
    HTBTree_add(tree,"Status.html");
    HTBTree_add(tree,"http.txt");
    HTBTree_add(tree,"People.html~");
    HTBTree_add(tree,"TAGS");
    HTBTree_add(tree,"summary.txt");
    HTBTree_add(tree,"Technical.html");
    HTBTree_add(tree,"Terms.html");
    HTBTree_add(tree,"JANETAccess.html");
    HTBTree_add(tree,"People.txt");
    HTBTree_add(tree,"README.txt");
    HTBTree_add(tree,"CodingStandards.html");
    HTBTree_add(tree,"Copyright.txt");
    HTBTree_add(tree,"Status_old.html");
    HTBTree_add(tree,"patches~");
    HTBTree_add(tree,"RelatedProducts.html");
    HTBTree_add(tree,"Implementation");
    HTBTree_add(tree,"History.html");
    HTBTree_add(tree,"Makefile.bak");
    HTBTree_add(tree,"Makefile.old");
    HTBTree_add(tree,"Policy.html");
    HTBTree_add(tree,"WhatIs.html");
    HTBTree_add(tree,"TheProject.html");
    HTBTree_add(tree,"Notation.html");
    HTBTree_add(tree,"Helping.html");
    HTBTree_add(tree,"Cyber-WWW.sit.Hqx");
    HTBTree_add(tree,"Glossary.html");
    HTBTree_add(tree,"maketags.html");
    HTBTree_add(tree,"IntroCS.html");
    HTBTree_add(tree,"Contrib");
    HTBTree_add(tree,"Help.html");
    HTBTree_add(tree,"CodeManagExec");
    HTBTree_add(tree,"HT-0.1draz");
    HTBTree_add(tree,"Cello");
    HTBTree_add(tree,"TOPUB");
    HTBTree_add(tree,"BUILD");
    HTBTree_add(tree,"BUILDALL");
    HTBTree_add(tree,"Lynx");
    HTBTree_add(tree,"ArthurLibrary");
    HTBTree_add(tree,"RashtyClient");
    HTBTree_add(tree,"#History.html#");
    HTBTree_add(tree,"PerlServers");
    HTBTree_add(tree,"modules");
    HTBTree_add(tree,"NCSA_httpd");
    HTBTree_add(tree,"MAIL2HTML");
    HTBTree_add(tree,"core");
    HTBTree_add(tree,"EmacsWWW");
#ifdef BTREE_TRACE
    printf("\nTreeTopObject=%s\n\n",tree->top->object);
#endif
    next_element = HTBTree_next(tree,NULL);
    while (next_element != NULL)
    {
#ifndef BTREE_TRACE
	printf("The next element is %s\n",next_element->object);
#endif
	next_element = HTBTree_next(tree,next_element);
    }
    HTBTree_free(tree);
}


#endif