summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/source/fonts/malayalam/preproc/avltree.c
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/source/fonts/malayalam/preproc/avltree.c')
-rw-r--r--Master/texmf-dist/source/fonts/malayalam/preproc/avltree.c699
1 files changed, 699 insertions, 0 deletions
diff --git a/Master/texmf-dist/source/fonts/malayalam/preproc/avltree.c b/Master/texmf-dist/source/fonts/malayalam/preproc/avltree.c
new file mode 100644
index 00000000000..909898a01ab
--- /dev/null
+++ b/Master/texmf-dist/source/fonts/malayalam/preproc/avltree.c
@@ -0,0 +1,699 @@
+/*+
+
+TITLE: AVLtree.c general purpose balanced trees.
+
+DESCRIPTION:
+ General purpose binairy-tree functions. This package uses AVL-trees
+ to ensure proper balancing. (The heigth of the tree will never exceed
+ ceil(1.44 * lg(n)), where lg is the logarithm base 2 and n the number
+ of elements.) This package can be used to store any kind of data in a
+ binairy tree. The only thing you have to do is to include AVLtree.h,
+ link AVLtree.lib and call the appropriate functions. You should also
+ provide a function to compare elements, and to free the memory used
+ by elements.
+
+USAGE:
+ To use the AVLtree package, include the file AVLtree.h in your
+ program. A root of a binairy tree can then be declared as follows:
+
+ AVLtree *a_binairy_tree;
+
+ The following operations are defined for Binairy trees:
+
+ -- Insert an element in the tree
+ -- Delete an element in the tree
+ -- Find an element in the tree
+ -- Traverse the tree
+
+ These operations are described below. You should always change the
+ AVLtree structure by these functions. Don't go jamming in its
+ structure yourself: it's delicate.
+
+FUNCTIONS:
+ Inserting an element:
+ Use the function AVLinsert() to insert an element. Its
+ prototype is:
+
+ int AVLinsert(const void *element,
+ AVLtree **root,
+ int (*cmp)(void*, void*));
+
+ element is a pointer to the element you want to insert in the
+ tree. Since it is this pointer that is actually stored in the
+ AVL-tree, you should not touch the space it is pointing at
+ after its insertion in the tree.
+ root is a pointer to a pointer to the root node of the tree.
+ A double reference is needed, since the root can change.
+ cmp() is a user defined function. It should compare two
+ elements and return 0 if the elements are equal, 1 if the first
+ element is 'bigger' than the second, and -1 if the first
+ element is 'smaller' than the second.
+
+ The function will return one of the following codes:
+
+ -- AVL_OK everything is alright.
+ -- AVL_DUP attempt to insert element already present.
+ -- AVL_NO_MEM no memory could be allocated.
+ -- AVL_ERROR called with incorrect parameters.
+
+ Deleting an element:
+ Use the function AVLdelete() to delete an element from the
+ tree. Its prototype is:
+
+ int AVLdelete(const void *element,
+ AVLtree **root,
+ int (*cmp)(void*, void*),
+ void (*del)(void*));
+
+ element is the element to be deleted from the tree.
+ root and cmp() are the same as in AVLinsert(). del() is a user
+ defined function that should free the memory occupied by the
+ element in the tree. It is passed a pointer to the element to
+ be deleted.
+
+ The function will return one of the following codes:
+
+ -- AVL_OK everything is alright.
+ -- AVL_NO_DEL attemp to delete non-existant element.
+ -- AVL_ERROR called with incorrect parameters.
+
+ Finding an element:
+ To find an element, the function AVLfind() should be used. Its
+ prototype is:
+
+ void *AVLfind(const void *element,
+ AVLtree *root,
+ int (*cmp)(void*, void*));
+
+ element is the element to be found, root is a pointer the the
+ root node of the tree. cmp() is the same as in AVLinsert().
+
+ The function will return a pointer to the found element, or
+ NULL if the element could not be found.
+
+ Traversing the tree:
+ The tree can be traversed in three ways:
+
+ -- preorder AVLpreorder()
+ -- inorder AVLinorder()
+ -- postorder AVLpostorder()
+
+ Inorder traversal will yield all elements in their correct
+ order.
+
+ The prototypes are:
+
+ void AVLpreorder(AVLtree *root, void (*func)(void*));
+ void AVLinorder(AVLtree *root,void (*func)(void*));
+ void AVLpostorder(AVLtree *root,void (*func)(void*));
+
+ root is a pointer to the tree to be traversed, and
+ func() is a user defined function that will be called at
+ every node. This could do something with that element, like
+ printing it.
+
+ These functions return nothing.
+
+DOCUMENTATION:
+ Robert L. Kruse, "Data Structures and Program Design" (2nd Ed.)
+ pp. 344-356.
+
+AUTHOR:
+ Jeroen Hellingman, 't Zand 2, 4133TB Vianen, the Netherlands.
+
+COPYRIGHT:
+ Copyright (c) Jeroen Hellingman 1990.
+ License is granted for any non-commercially and non-millitary use
+ of this package, provided that this notice is kept intact. Use of
+ this software in any product that is sold for profit or usage by
+ (semi-)militairy organisations is forbidden. (contact me for
+ commercial usage) Donations are always appreciated (postbank
+ giro 5025409).
+
+CAVEAT:
+ I can take no responseability whatsoever if this software
+ is malfunctioning. If you find any bug in it, please fix it and
+ notice me. If you can't fix it, you can also notice me, I might
+ try to fix it.
+
+HISTORY
+ 18-DEC-1992 last edit
+ 04-NOV-1992 declared static functions static in prototype too.
+ gcc seems to complain about this (JH)
+ 01-DEC-1989 creation (Jeroen Hellingman)
+
+-*/
+
+/* #define TEST */
+
+#include "avltree.h"
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdio.h>
+
+#define TRUE 1
+#define FALSE 0
+
+#define EQUAL 0
+#define LEFT 1
+#define RIGHT 2
+
+/* ANSI C prototypes */
+
+static int insert(const void *element, AVLtree **root,
+ int (*cmp)(void*, void*), int *taller);
+static int delete(const void *element, AVLtree **root,
+ int (*cmp)(void*, void*), void (*del)(void*), int *shorter);
+static void left_balance(AVLtree **root);
+static void right_balance(AVLtree **root);
+static void left_rebalance(AVLtree **root, int *shorter);
+static void right_rebalance(AVLtree **root, int *shorter);
+static void left_rotate(AVLtree **root);
+static void right_rotate(AVLtree **root);
+static void error(int errno);
+
+/* add element to AVL-tree */
+
+int AVLinsert(const void *element,AVLtree **root,int (*cmp)(void*, void*))
+{ int taller = FALSE;
+
+ if(element == NULL) return AVL_ERROR;
+ return insert(element, root, cmp, &taller);
+}
+
+int AVLdelete(const void *element,AVLtree **root,int (*cmp)(void*, void*),
+ void (*del)(void *))
+{ int shorter = FALSE;
+
+ if(element == NULL) return AVL_ERROR;
+ return delete(element, root, cmp, del, &shorter);
+}
+
+static int insert(const void *element, AVLtree **root,
+ int (*cmp)(void*, void*), int *taller)
+{ int result;
+ int tallersubtree = FALSE;
+ AVLtree *subtree; /* needed since you can't do & on a struct member */
+
+ if(*root == NULL) /* then adding is really easy */
+ { *root = (AVLtree *) malloc(sizeof(AVLtree));
+ if(*root == NULL) return AVL_NO_MEM;
+ (*root)->element = element;
+ (*root)->balance = EQUAL;
+ (*root)->left = NULL;
+ (*root)->right = NULL;
+ *taller = TRUE;
+ result = AVL_OK;
+ }
+ else /* recursively insert in appropriate subtree */
+ { int compare = (*cmp)(element,(*root)->element);
+
+ if(compare == 0) return AVL_DUP;
+ else if(compare < 0)
+ { subtree = (*root)->left;
+ result = insert(element,&subtree,cmp,&tallersubtree);
+ (*root)->left = subtree;
+ if(tallersubtree)
+ switch((*root)->balance)
+ { case LEFT: left_balance(root);
+ *taller = FALSE;
+ break;
+ case EQUAL: (*root)->balance = LEFT;
+ *taller = TRUE;
+ break;
+ case RIGHT: (*root)->balance = EQUAL;
+ *taller = FALSE;
+ }
+ else *taller = FALSE;
+ }
+ else
+ { subtree = (*root)->right;
+ result = insert(element,&subtree,cmp,&tallersubtree);
+ (*root)->right = subtree;
+ if(tallersubtree)
+ switch((*root)->balance)
+ { case RIGHT: right_balance(root);
+ *taller = FALSE;
+ break;
+ case EQUAL: (*root)->balance = RIGHT;
+ *taller = TRUE;
+ break;
+ case LEFT: (*root)->balance = EQUAL;
+ *taller = FALSE;
+ }
+ else *taller = FALSE;
+ }
+ }
+ return result;
+} /* end of insert() */
+
+static int delete(const void *element, AVLtree **root,
+ int (*cmp)(void*, void*), void (*del)(void*), int *shorter)
+{ int result;
+ int compare;
+ int shortersubtree = FALSE;
+ AVLtree *subtree;
+
+ if(root == NULL) return AVL_ERROR;
+ if((*root) == NULL) return AVL_NO_DEL;
+ if((*root)->element == NULL) error(6); /* DEBUG */
+ compare = (*cmp)(element,(*root)->element);
+
+ if(compare == 0)
+ {
+ /* check: two children? */
+ if((*root)->left != NULL && (*root)->right != NULL)
+ { AVLtree *pred;
+ void *tmp;
+
+ /* find immediate predecessor */
+ pred = (*root)->left;
+ while(pred->right != NULL) pred = pred->right;
+
+ /* swap element to be deleted with its immediate predecessor */
+ tmp = (*root)->element;
+ (*root)->element = pred->element;
+ pred->element = tmp;
+
+ /* delete predecessor from left subtree */
+ subtree = (*root)->left;
+ result = delete(element,&subtree,cmp,del,&shortersubtree);
+ (*root)->left = subtree;
+
+ /* rebalance tree */
+ if(shortersubtree)
+ switch((*root)->balance)
+ { case RIGHT: right_rebalance(root,shorter);
+ break;
+ case EQUAL: (*root)->balance = RIGHT;
+ *shorter = FALSE;
+ break;
+ case LEFT: (*root)->balance = EQUAL;
+ *shorter = TRUE;
+ }
+
+ }
+ else
+ { /* user must delete his element */
+
+ (*del)((*root)->element);
+ /* delete node */
+ subtree = ((*root)->left == NULL) ? (*root)->right : (*root)->left;
+ free(*root);
+ *root = subtree;
+ *shorter = TRUE;
+ result = AVL_OK;
+ }
+ }
+ else if(compare < 0) /* delete from left subtree */
+ { subtree = (*root)->left;
+ result = delete(element, &subtree, cmp, del, &shortersubtree);
+ (*root)->left = subtree;
+
+ /* rebalance tree */
+ if(shortersubtree)
+ switch((*root)->balance)
+ { case RIGHT: right_rebalance(root,shorter);
+ break;
+ case EQUAL: (*root)->balance = RIGHT;
+ *shorter = FALSE;
+ break;
+ case LEFT: (*root)->balance = EQUAL;
+ *shorter = TRUE;
+ }
+ }
+ else /* delete from right subtree */
+ { subtree = (*root)->right;
+ result = delete(element, &subtree, cmp, del, &shortersubtree);
+ (*root)->right = subtree;
+
+ /* rebalance tree */
+ if(shortersubtree)
+ switch((*root)->balance)
+ { case LEFT: left_rebalance(root,shorter);
+ break;
+ case EQUAL: (*root)->balance = LEFT;
+ *shorter = FALSE;
+ break;
+ case RIGHT: (*root)->balance = EQUAL;
+ *shorter = TRUE;
+ }
+ }
+ return result;
+} /* end of delete() */
+
+static void right_rebalance(AVLtree **root, int *shorter)
+{ AVLtree *rightsub, *leftsubsub;
+
+ if(root == NULL) error(7);
+ if(*root == NULL) error(8);
+ if((*root)->right == NULL) error(9); /* DEBUG */
+
+ rightsub = (*root)->right;
+ switch(rightsub->balance)
+ { case EQUAL: (*root)->balance = RIGHT;
+ rightsub->balance = LEFT;
+ left_rotate(root);
+ *shorter = FALSE;
+ break;
+ case RIGHT: (*root)->balance = EQUAL;
+ rightsub->balance = EQUAL;
+ left_rotate(root);
+ *shorter = TRUE;
+ break;
+ case LEFT: leftsubsub = rightsub->left;
+ switch(leftsubsub->balance)
+ { case EQUAL: (*root)->balance = EQUAL;
+ rightsub->balance = EQUAL;
+ break;
+ case LEFT: (*root)->balance = EQUAL;
+ rightsub->balance = RIGHT;
+ break;
+ case RIGHT: (*root)->balance = LEFT;
+ rightsub->balance = EQUAL;
+ }
+ leftsubsub->balance = EQUAL;
+ right_rotate(&rightsub);
+ (*root)->right = rightsub;
+ left_rotate(root);
+ *shorter = TRUE;
+ }
+} /* end of right_rebalance() */
+
+static void left_rebalance(AVLtree **root, int *shorter)
+{ AVLtree *leftsub, *rightsubsub;
+
+ if(root == NULL) error(10);
+ if(*root == NULL) error(11);
+ if((*root)->left == NULL) error(12); /* DEBUG */
+
+ leftsub = (*root)->left;
+ switch(leftsub->balance)
+ { case EQUAL: (*root)->balance = LEFT;
+ leftsub->balance = RIGHT;
+ right_rotate(root);
+ *shorter = FALSE;
+ break;
+ case LEFT: (*root)->balance = EQUAL;
+ leftsub->balance = EQUAL;
+ right_rotate(root);
+ *shorter = TRUE;
+ break;
+ case RIGHT: rightsubsub = leftsub->right;
+ switch(rightsubsub->balance)
+ { case EQUAL: (*root)->balance = EQUAL;
+ leftsub->balance = EQUAL;
+ break;
+ case RIGHT: (*root)->balance = EQUAL;
+ leftsub->balance = LEFT;
+ break;
+ case LEFT: (*root)->balance = RIGHT;
+ leftsub->balance = EQUAL;
+ }
+ rightsubsub->balance = EQUAL;
+ left_rotate(&leftsub);
+ (*root)->left = leftsub;
+ right_rotate(root);
+ *shorter = TRUE;
+ }
+} /* end of left_rebalance() */
+
+void *AVLfind(const void *element,AVLtree *root,int (*cmp)(void*, void*))
+{ int compare;
+
+ if(root == NULL) return NULL;
+ compare = (*cmp)(element,root->element);
+ if(compare == 0) return root->element;
+ else if(compare < 0)
+ return AVLfind(element,root->left,cmp);
+ else
+ return AVLfind(element,root->right,cmp);
+}
+
+static void left_balance(AVLtree **root)
+{ AVLtree *leftsub, *rightsubsub;
+
+ leftsub = (*root)->left;
+ switch(leftsub->balance)
+ { case LEFT: (*root)->balance = EQUAL;
+ leftsub->balance = EQUAL;
+ right_rotate(root);
+ break;
+ case RIGHT: rightsubsub = leftsub->right;
+ switch(rightsubsub->balance)
+ { case EQUAL: (*root)->balance = EQUAL;
+ leftsub->balance = EQUAL;
+ break;
+ case RIGHT: (*root)->balance = EQUAL;
+ leftsub->balance = LEFT;
+ break;
+ case LEFT: (*root)->balance = RIGHT;
+ leftsub->balance = EQUAL;
+ }
+ rightsubsub->balance = EQUAL;
+ left_rotate(&leftsub);
+ (*root)->left = leftsub;
+ right_rotate(root);
+ }
+} /* end of left_balance() */
+
+static void right_balance(AVLtree **root)
+{ AVLtree *rightsub, *leftsubsub;
+
+ rightsub = (*root)->right;
+ switch(rightsub->balance)
+ { case RIGHT: (*root)->balance = EQUAL;
+ rightsub->balance = EQUAL;
+ left_rotate(root);
+ break;
+ case LEFT: leftsubsub = rightsub->left;
+ switch(leftsubsub->balance)
+ { case EQUAL: (*root)->balance = EQUAL;
+ rightsub->balance = EQUAL;
+ break;
+ case LEFT: (*root)->balance = EQUAL;
+ rightsub->balance = RIGHT;
+ break;
+ case RIGHT: (*root)->balance = LEFT;
+ rightsub->balance = EQUAL;
+ }
+ leftsubsub->balance = EQUAL;
+ right_rotate(&rightsub);
+ (*root)->right = rightsub;
+ left_rotate(root);
+ }
+} /* end of right_balance() */
+
+static void left_rotate(AVLtree **root)
+{
+ if(*root == NULL) error(1);
+ else if((*root)->right == NULL) error(2);
+ else
+ { AVLtree *temp;
+
+ temp = (*root)->right;
+ (*root)->right = temp->left;
+ temp->left = *root;
+ *root = temp;
+ }
+}
+
+static void right_rotate(AVLtree **root)
+{
+ if(*root == NULL) error(3);
+ else if((*root)->left == NULL) error(5);
+ else
+ { AVLtree *temp;
+
+ temp = (*root)->left;
+ (*root)->left = temp->right;
+ temp->right = *root;
+ *root = temp;
+ }
+}
+
+void AVLinorder(AVLtree *root, void (*func)(void*))
+{
+ if(root == NULL) return;
+
+ AVLinorder(root->left, func);
+ (*func)(root->element);
+ AVLinorder(root->right, func);
+}
+
+void AVLpreorder(AVLtree *root, void (*func)(void*))
+{
+ if(root == NULL) return;
+
+ AVLpreorder(root->left, func);
+ AVLpreorder(root->right, func);
+ (*func)(root->element);
+}
+
+void AVLpostorder(AVLtree *root, void (*func)(void*))
+{
+ if(root == NULL) return;
+
+ (*func)(root->element);
+ AVLpostorder(root->left, func);
+ AVLpostorder(root->right, func);
+}
+
+
+static void error(int errno)
+{ fprintf(stderr,"AVLtree package error # %d\n",errno);
+ exit(1);
+}
+
+
+#ifdef TEST
+
+#include <string.h>
+
+#define MAXN 1000
+#define BUFSIZE 512
+
+int fgetline(char *buf, FILE *input);
+int cmp(void*, void*);
+void del(void *p1);
+void show_element(void *element);
+int AVLcheck(AVLtree *root);
+void AVLshowtree(AVLtree *root, void (*func)(void*), int depth);
+
+void AVLshowtree(AVLtree *root, void (*func)(void*), int depth)
+{
+ if(root == NULL) return;
+
+ printf(" [%d](%d) ",root->balance, depth);
+ (*func)(root->element);
+ AVLshowtree(root->left, func, depth+1);
+ AVLshowtree(root->right, func, depth+1);
+}
+
+/* naive compare using strcmp() (ASCII order) */
+
+int cmp(void *p1, void *p2)
+{ return strcmp(p1, p2);
+}
+
+/* routine to delete an element */
+
+void del(void *p1)
+{ free(p1);
+}
+
+/* simple routine to show a node */
+
+void show_element(void *element)
+{ printf("%s\n",element);
+}
+
+void main()
+{ AVLtree *root = NULL;
+ char buf[BUFSIZE];
+ int n = 0, length;
+ char *p;
+
+
+ fprintf(stdout,"testing routine for B-tree package\n");
+ fprintf(stdout,"just read lines from input, put them in the\n");
+ fprintf(stdout,"tree, then traverse the tree in order to\n");
+ fprintf(stdout,"show the lines sorted (stop with '-') \n");
+
+ while(TRUE)
+ { length = fgetline(buf, stdin);
+ if(buf[0] == '-') break;
+ if(length != 0)
+ { if(n == MAXN)
+ { fprintf(stderr, "Too many strings\n");
+ exit(1);
+ }
+ p = malloc(length+1);
+ if(p == NULL)
+ { fprintf(stderr, "Out of memory\n");
+ exit(2);
+ }
+ strcpy(p, buf);
+ if(AVLinsert(p,&root,cmp) != AVL_OK)
+ { fprintf(stderr, "Insertion error\n");
+ }
+ AVLcheck(root);
+ ++n;
+ }
+ if(feof(stdin)) break;
+ }
+
+ /* check tree */
+ AVLcheck(root);
+ /* now try to delete some elements */
+
+ while(TRUE)
+ { length = fgetline(buf, stdin);
+ if(length != 0)
+ { if(n == MAXN)
+ { fprintf(stderr, "Too many strings\n");
+ exit(1);
+ }
+ p = malloc(length+1);
+ if(p == NULL)
+ { fprintf(stderr, "Out of memory\n");
+ exit(2);
+ }
+ strcpy(p, buf);
+ if(AVLdelete(p,&root,cmp,del) != AVL_OK)
+ { fprintf(stderr, "Deletion error\n");
+ }
+ AVLcheck(root);
+ ++n;
+ }
+ if(feof(stdin)) break;
+ }
+
+ AVLshowtree(root,show_element, 1);
+
+ exit(0);
+}
+
+int fgetline(char *buf, FILE *input)
+{ int i = 0, tmp;
+
+ while((tmp = getc(input)) != EOF)
+ { buf[i] = (char)tmp;
+ if(buf[i] == '\n')
+ { buf[i] = '\0';
+ return i;
+ }
+ else
+ { i++;
+ if(i >= BUFSIZE)
+ { fprintf(stderr, "line too long\n");
+ exit(4);
+ }
+ }
+ }
+ buf[i] = '\0';
+ return i;
+}
+
+int AVLcheck(AVLtree *root)
+{ int lh, rh;
+
+ if(root == NULL) return 0;
+
+ lh = AVLcheck(root->left);
+ rh = AVLcheck(root->right);
+
+ if(lh == rh && root->balance != EQUAL)
+ printf("improper balance EQUAL\n");
+ if(lh - rh == 1 && root->balance != LEFT)
+ printf("improper balance LEFT\n");
+ if(lh - rh == -1 && root->balance != RIGHT)
+ printf("improper balance RIGHT\n");
+ if(lh - rh > 1 || lh - rh < -1) printf("Not an AVL-tree\n");
+
+ return (lh < rh ? rh : lh) + 1;
+}
+
+#endif /* TESTing part */
+
+/* end of AVLtree.c */ \ No newline at end of file