home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Programming / vahunz / source / ubiqx / ubi_AVLtree.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-04-17  |  5.6 KB  |  304 lines
  1. /*
  2.  * This source file is part of Vahunz,
  3.  * a tool to make source code un-/more legible.
  4.  *
  5.  *--------------------------------------------------------------------------
  6.  *
  7.  * Vahunz and the Ugly library are Copyright (C) 1998 by
  8.  * Thomas Aglassinger <agi@giga.or.at>
  9.  *
  10.  * All rights reserved.
  11.  *
  12.  * Refer to the manual for more information.
  13.  *
  14.  *--------------------------------------------------------------------------
  15.  *
  16.  * Ubiqx library is Copyright (C) 1991-1998 by
  17.  * Christopher R. Hertel <crh@ubiqx.mn.org>
  18.  *
  19.  * Ubiqx library is free software; you can redistribute it and/or
  20.  * modify it under the terms of the GNU Library General Public
  21.  * License as published by the Free Software Foundation; either
  22.  * version 2 of the License, or (at your option) any later version.
  23.  *
  24.  */
  25. #include "ubi_AVLtree.h" 
  26. #include <stdlib.h> 
  27. static char f2A[] = "ubi_AVLtree\n\
  28. \t$Revision: 2.5 $\n\
  29. \t$Date: 1997/12/23 04:00:42 $\n\
  30. \t$Author: crh $\n";
  31. static h1G L1( h1G p )
  32. {
  33. h1G e0Y;
  34. e0Y = p->b9H[i7C];
  35. p->b9H[i7C] = e0Y->b9H[z7V];
  36. e0Y->b9H[z7V] = p;
  37. e0Y->b9H[z6Y] = p->b9H[z6Y];
  38. e0Y->k5O = p->k5O;
  39. if(e0Y->b9H[z6Y])
  40. (e0Y->b9H[z6Y])->b9H[(int)(e0Y->k5O)] = e0Y;
  41. p->b9H[z6Y] = e0Y;
  42. p->k5O = z7V;
  43. if( p->b9H[i7C] )
  44. {
  45. p->b9H[i7C]->b9H[z6Y] = p;
  46. (p->b9H[i7C])->k5O = i7C;
  47. }
  48. p->h4S -= z7O( e0Y->h4S );
  49. (e0Y->h4S)--;
  50. return( e0Y );
  51. } 
  52. static h1G R1( h1G p )
  53. {
  54. h1G e0Y;
  55. e0Y = p->b9H[z7V];
  56. p->b9H[z7V] = e0Y->b9H[i7C];
  57. e0Y->b9H[i7C] = p;
  58. e0Y->b9H[z6Y] = p->b9H[z6Y];
  59. e0Y->k5O = p->k5O;
  60. if(e0Y->b9H[z6Y])
  61. (e0Y->b9H[z6Y])->b9H[(int)(e0Y->k5O)] = e0Y;
  62. p->b9H[z6Y] = e0Y;
  63. p->k5O = i7C;
  64. if(p->b9H[z7V])
  65. {
  66. p->b9H[z7V]->b9H[z6Y] = p;
  67. p->b9H[z7V]->k5O = z7V;
  68. }
  69. p->h4S -= z7O( e0Y->h4S );
  70. (e0Y->h4S)++;
  71. return( e0Y );
  72. } 
  73. static h1G L2( h1G d2J )
  74. {
  75. h1G e0Y, g3Mw;
  76. e0Y = d2J->b9H[i7C];
  77. g3Mw = e0Y->b9H[z7V];
  78. e0Y->b9H[z7V] = g3Mw->b9H[i7C];
  79. g3Mw->b9H[i7C] = e0Y;
  80. d2J->b9H[i7C] = g3Mw->b9H[z7V];
  81. g3Mw->b9H[z7V] = d2J;
  82. g3Mw->b9H[z6Y] = d2J->b9H[z6Y];
  83. g3Mw->k5O = d2J->k5O;
  84. d2J->b9H[z6Y] = g3Mw;
  85. d2J->k5O = z7V;
  86. e0Y->b9H[z6Y] = g3Mw;
  87. e0Y->k5O = i7C;
  88. if( d2J->b9H[i7C] )
  89. {
  90. d2J->b9H[i7C]->b9H[z6Y] = d2J;
  91. d2J->b9H[i7C]->k5O = i7C;
  92. }
  93. if( e0Y->b9H[z7V] )
  94. {
  95. e0Y->b9H[z7V]->b9H[z6Y] = e0Y;
  96. e0Y->b9H[z7V]->k5O = z7V;
  97. }
  98. if(g3Mw->b9H[z6Y])
  99. g3Mw->b9H[z6Y]->b9H[(int)(g3Mw->k5O)] = g3Mw;
  100. switch( g3Mw->h4S )
  101. {
  102. case z7V :
  103. d2J->h4S = t3Db; e0Y->h4S = i7C; break;
  104. case t3Db:
  105. d2J->h4S = t3Db; e0Y->h4S = t3Db; break;
  106. case i7C:
  107. d2J->h4S = z7V; e0Y->h4S = t3Db; break;
  108. }
  109. g3Mw->h4S = t3Db;
  110. return( g3Mw );
  111. } 
  112. static h1G R2( h1G d2J )
  113. {
  114. h1G e0Y, g3Mw;
  115. e0Y = d2J->b9H[z7V];
  116. g3Mw = e0Y->b9H[i7C];
  117. e0Y->b9H[i7C] = g3Mw->b9H[z7V];
  118. g3Mw->b9H[z7V] = e0Y;
  119. d2J->b9H[z7V] = g3Mw->b9H[i7C];
  120. g3Mw->b9H[i7C] = d2J;
  121. g3Mw->b9H[z6Y] = d2J->b9H[z6Y];
  122. g3Mw->k5O = d2J->k5O;
  123. d2J->b9H[z6Y] = g3Mw;
  124. d2J->k5O = i7C;
  125. e0Y->b9H[z6Y] = g3Mw;
  126. e0Y->k5O = z7V;
  127. if( d2J->b9H[z7V] )
  128. {
  129. d2J->b9H[z7V]->b9H[z6Y] = d2J;
  130. d2J->b9H[z7V]->k5O = z7V;
  131. }
  132. if( e0Y->b9H[i7C] )
  133. {
  134. e0Y->b9H[i7C]->b9H[z6Y] = e0Y;
  135. e0Y->b9H[i7C]->k5O = i7C;
  136. }
  137. if(g3Mw->b9H[z6Y])
  138. g3Mw->b9H[z6Y]->b9H[(int)(g3Mw->k5O)] = g3Mw;
  139. switch( g3Mw->h4S )
  140. {
  141. case z7V :
  142. d2J->h4S = i7C; e0Y->h4S = t3Db; break;
  143. case t3Db :
  144. d2J->h4S = t3Db; e0Y->h4S = t3Db; break;
  145. case i7C :
  146. d2J->h4S = t3Db; e0Y->h4S = z7V; break;
  147. }
  148. g3Mw->h4S = t3Db;
  149. return( g3Mw );
  150. } 
  151. static h1G y3Y( h1G p, char o3T )
  152. {
  153. if( p->h4S != o3T )
  154. p->h4S += z7O(o3T);
  155. else
  156. {
  157. char b2P; 
  158. b2P = p->b9H[(int)o3T]->h4S;
  159. if( ( t3Db == b2P ) || ( p->h4S == b2P ) )
  160. p = ( (z7V==o3T) ? R1(p) : L1(p) ); 
  161. else
  162. p = ( (z7V==o3T) ? R2(p) : L2(p) ); 
  163. }
  164. return( p );
  165. } 
  166. static h1G l2B( h1G f1B,
  167. h1G z0G,
  168. char o3T )
  169. {
  170. while( z0G )
  171. {
  172. z0G = y3Y( z0G, o3T );
  173. if( z6Y == z0G->k5O )
  174. return( z0G );
  175. if( t3Db == z0G->h4S )
  176. return( f1B );
  177. o3T = z0G->k5O;
  178. z0G = z0G->b9H[z6Y];
  179. }
  180. return( f1B );
  181. } 
  182. static h1G t4A( h1G f1B,
  183. h1G z0G,
  184. char o3T )
  185. {
  186. while( z0G )
  187. {
  188. z0G = y3Y( z0G, y2Bn(o3T) );
  189. if( z6Y == z0G->k5O )
  190. return( z0G );
  191. if( t3Db != z0G->h4S )
  192. return( f1B );
  193. o3T = z0G->k5O;
  194. z0G = z0G->b9H[z6Y];
  195. }
  196. return( f1B );
  197. } 
  198. static void l9H( h1G *e2L,
  199. h1G k7H,
  200. h1G t2M )
  201. {
  202. register int i;
  203. register int s3U = sizeof( l3Q );
  204. for( i = 0; i < s3U; i++ )
  205. ((unsigned char *)t2M)[i] = ((unsigned char *)k7H)[i];
  206. (*e2L) = t2M;
  207. if(k7H->b9H[z7V ] )
  208. (k7H->b9H[z7V ])->b9H[z6Y] = t2M;
  209. if(k7H->b9H[i7C] )
  210. (k7H->b9H[i7C])->b9H[z6Y] = t2M;
  211. } 
  212. static void q7H( o4R x8O,
  213. h1G v6L,
  214. h1G h3D )
  215. {
  216. h1G *Parent;
  217. l3Q u4M;
  218. h1G v3O = &u4M;
  219. if( v6L->b9H[z6Y] )
  220. Parent = &((v6L->b9H[z6Y])->b9H[(int)(v6L->k5O)]);
  221. else
  222. Parent = (h1G *)&(x8O->k6P);
  223. l9H( Parent, v6L, v3O );
  224. if( h3D->b9H[z6Y] )
  225. Parent = &((h3D->b9H[z6Y])->b9H[(int)(h3D->k5O)]);
  226. else
  227. Parent = (h1G *)&(x8O->k6P);
  228. l9H( Parent, h3D, v6L );
  229. if( v3O->b9H[z6Y] )
  230. Parent = &((v3O->b9H[z6Y])->b9H[(int)(v3O->k5O)]);
  231. else
  232. Parent = (h1G *)&(x8O->k6P);
  233. l9H( Parent, v3O, h3D );
  234. } 
  235. h1G v2G( h1G y2B )
  236. {
  237. (void)u3Ny( (l1Z)y2B );
  238. y2B->h4S = t3Db;
  239. return( y2B );
  240. } 
  241. f6W y6M( o4R x8O,
  242. h1G j4E,
  243. f7P j7S,
  244. h1G *s3L )
  245. {
  246. h1G r9V;
  247. if( !(s3L) ) s3L = &r9V;
  248. if( k2M( x8O,
  249. (l1Z)j4E,
  250. j7S,
  251. (l1Z *)s3L ) )
  252. {
  253. if( (*s3L) )
  254. j4E->h4S = (*s3L)->h4S;
  255. else
  256. {
  257. j4E->h4S = t3Db;
  258. x8O->k6P = (l1Z)l2B( (h1G)x8O->k6P,
  259. j4E->b9H[z6Y],
  260. j4E->k5O );
  261. }
  262. return( s0E );
  263. }
  264. return( b9P ); 
  265. } 
  266. h1G y5R( o4R x8O,
  267. h1G b2L )
  268. {
  269. l1Z p,
  270. *t6Z;
  271. if( (b2L->b9H[z7V]) && (b2L->b9H[i7C]) )
  272. q7H( x8O, b2L, s0K( b2L ) );
  273. if( b2L->b9H[z6Y] )
  274. t6Z = (l1Z *)
  275. &((b2L->b9H[z6Y])->b9H[(int)(b2L->k5O)]);
  276. else
  277. t6Z = &( x8O->k6P );
  278. if( t3Db == b2L->h4S )
  279. (*t6Z) = NULL;
  280. else
  281. {
  282. p = (l1Z)(b2L->b9H[(int)(b2L->h4S)]);
  283. p->b9H[z6Y] = (l1Z)b2L->b9H[z6Y];
  284. p->k5O = b2L->k5O;
  285. (*t6Z) = p;
  286. }
  287. x8O->k6P = (l1Z)t4A( (h1G)x8O->k6P,
  288. b2L->b9H[z6Y],
  289. b2L->k5O );
  290. (x8O->count)--;
  291. return( b2L );
  292. } 
  293. int p8M( int c8H, char *list[] )
  294. {
  295. if( c8H > 0 )
  296. {
  297. list[0] = f2A;
  298. if( c8H > 1 )
  299. return( 1 + x0K( --c8H, &(list[1]) ) );
  300. return( 1 );
  301. }
  302. return( 0 );
  303. } 
  304.