home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / alt / sources / 2601 < prev    next >
Encoding:
Internet Message Format  |  1992-11-21  |  16.3 KB
  1. Path: sparky!uunet!mcsun!sunic!lunic!my!ljp
  2. From: ljp@sm.luth.se (Johan Persson)
  3. Newsgroups: alt.sources
  4. Subject: splaytree-part2/2
  5. Message-ID: <1357@my.sm.luth.se>
  6. Date: 22 Nov 92 13:39:09 GMT
  7. Reply-To: Johan Persson <ljp@my.sm.luth.se>
  8. Organization: University of Lulea, Sweden
  9. Lines: 655
  10.  
  11. Submitted-by: ljp@sm.luth.se
  12. Archive-name: splaytree-part2
  13.  
  14. #!/bin/sh
  15. # This is part 02 of splaytree
  16. if touch 2>&1 | fgrep '[-amc]' > /dev/null
  17.  then TOUCH=touch
  18.  else TOUCH=true
  19. fi
  20. # ============= splay.mod ==============
  21. if test X"$1" != X"-c" -a -f 'splay.mod'; then
  22.     echo "File already exists: skipping 'splay.mod'"
  23. else
  24. echo "x - extracting splay.mod (Text)"
  25. sed 's/^X//' << 'SHAR_EOF' > splay.mod &&
  26. XIMPLEMENTATION MODULE splay;
  27. X(*
  28. X    Title:        Implementation of splay trees
  29. X    Last Edit:    Sun Nov 22 12:57:01 1992
  30. X    Author:        Johan Persson at my9
  31. X
  32. X    SCCS:        @(#)splay.mod       2.1     92/11/22    
  33. X    
  34. X        
  35. X    Description:    This code implements splay tree as described in 
  36. X                    Sleator D. and Tarjan R. "Self adjusting
  37. X            binary trees", JACM Vol 32. No 3, 1985, pp 652-
  38. X            686.
  39. X            
  40. X            The implemenation is based on a top down
  41. X                        splaying heuristics as described in section 4 of 
  42. X            the article.
  43. X
  44. X    Note:        This implementation also supports the operations
  45. X            'getRankElement' which finds the element in the tree
  46. X            with a given rank in O(lgn) time) and 'getRank', 
  47. X            (which returns the rank of a given element)
  48. X            To achive this one must store the weight of a node in
  49. X            each node (i.e the number of descadents). This
  50. X            information must be updated after each operation
  51. X            (insert, delete, find). If this is to costly
  52. X            (it takes O(n)) the source can be modified to remove
  53. X            the call to 'fixRank' in 'insert', 'delete' and
  54. X            'find'
  55. X
  56. X            See 'splay.def' for a complete description
  57. X            of all procedures.
  58. X*)
  59. X
  60. X  IMPORT SYSTEM,Storage,splayItem; 
  61. X   
  62. X  TYPE
  63. X     T = POINTER TO head;
  64. X     Tree = POINTER TO treeNode;
  65. X     treeNode = RECORD
  66. X           l,r:Tree;          (* left and right links *)
  67. X           data:splayItem.T;      (* stored item          *)
  68. X           weight:CARDINAL;
  69. X                         (* number of nodes in the 
  70. X                                subtrees of this node*)
  71. X        END (* record *);
  72. X        
  73. X     cmpFunc = PROCEDURE (splayItem.T, splayItem.T) : CARDINAL;
  74. X    
  75. X     head = RECORD
  76. X            t : Tree;
  77. X          nbr : CARDINAL;   
  78. X        END (* record *);
  79. X        
  80. X
  81. X    PROCEDURE create(VAR tree:T);
  82. X       BEGIN (* create *)
  83. X         Storage.ALLOCATE(tree,SIZE(head));
  84. X     tree^.t := NIL;
  85. X     tree^.nbr := 0;
  86. X       END create;
  87. X
  88. X
  89. X  PROCEDURE destroy(VAR tree:T);
  90. X     PROCEDURE des(t:Tree);
  91. X       BEGIN (* des *)
  92. X     IF t # NIL THEN 
  93. X        des(t^.l);
  94. X        des(t^.r);
  95. X        splayItem.destroy(t^.data);
  96. X        Storage.DEALLOCATE(t,SIZE(treeNode));
  97. X     END (* if *);
  98. X       END des;
  99. X     BEGIN (* destroy *)
  100. X       des(tree^.t); 
  101. X       Storage.DEALLOCATE(tree,SIZE(head));
  102. X       tree := NIL;
  103. X     END destroy;
  104. X  
  105. X   PROCEDURE nbrElem(tree:T): CARDINAL; 
  106. X      BEGIN
  107. X         RETURN tree^.nbr;
  108. X      END nbrElem;
  109. X     
  110. X(* *)
  111. X  PROCEDURE insert(tree:T; item:splayItem.T);
  112. X     VAR n,nn,l,r,node:Tree;
  113. X     BEGIN (* insert *)
  114. X       Storage.ALLOCATE(node,SIZE(treeNode));
  115. X       node^.data := item; 
  116. X       n := tree^.t;
  117. X       tree^.t := node;
  118. X       IF n = NIL THEN
  119. X            node^.l:=NIL; node^.r:=NIL;
  120. X       ELSE 
  121. X            l:=node; r:=node;
  122. X     LOOP 
  123. X       IF splayItem.cmp(item,n^.data) < 0 THEN 
  124. X         nn := n^.l;
  125. X         IF nn=NIL THEN r^.l := n; l^.r := NIL; EXIT;
  126. X         ELSIF splayItem.cmp(item,nn^.data) >= 0 THEN 
  127. X           r^.l := n; r := n; 
  128. X           l^.r := nn; l := nn;
  129. X           n := nn^.r;
  130. X           IF n=NIL THEN r^.l:=NIL; EXIT; END;
  131. X         ELSE (* item < data *)
  132. X           n^.l := nn^.r;
  133. X           r^.l := nn;
  134. X           nn^.r := n;
  135. X           r := nn;
  136. X           n := nn^.l;
  137. X           IF n = NIL THEN l^.r := NIL; EXIT; END;
  138. X         END (* if *);
  139. X       ELSE (* item >= data *)   
  140. X         nn := n^.r;
  141. X         IF nn=NIL THEN l^.r := n; r^.l := NIL; EXIT;
  142. X         ELSIF splayItem.cmp(item,nn^.data) < 0 THEN 
  143. X           l^.r := n; l := n; 
  144. X           r^.l := nn; r:=nn;
  145. X           n := nn^.l;
  146. X           IF n=NIL THEN l^.r:=NIL; EXIT; END;
  147. X         ELSE (* item >= data *)
  148. X           n^.r := nn^.l;
  149. X           l^.r := nn;
  150. X           nn^.l := n;
  151. X           l := nn;
  152. X           n := nn^.r;
  153. X           IF n=NIL THEN r^.l := NIL; EXIT; END;
  154. X         END (* if *)
  155. X       END (* if *);
  156. X     END (* loop *);
  157. X     nn := node^.r;
  158. X     node^.r := node^.l;
  159. X     node^.l := nn;
  160. X       END (* if empty tree*);
  161. X       fixRank(node);
  162. X       INC(tree^.nbr);
  163. X     END insert;
  164. X
  165. X(*   *)
  166. X
  167. X  PROCEDURE delete(tree:T; item:splayItem.T);
  168. X     VAR l,r,nnn,nn,n,pnn:Tree;
  169. X         left,right:treeNode;
  170. X         fFound:BOOLEAN;
  171. X     PROCEDURE replace(VAR p:Tree; n:Tree);
  172. X        VAR r,pr:Tree;
  173. X        BEGIN (* replace *)
  174. X           r:=n^.l;
  175. X       IF r=NIL THEN p:=n^.r;
  176. X       ELSE 
  177. X          IF r^.r=NIL THEN p:=r; p^.r:=n^.r;
  178. X          ELSE 
  179. X             WHILE r^.r#NIL DO pr:=r; r:=r^.r; END;
  180. X             pr^.r:=r^.l;
  181. X             r^.l:=n^.l; r^.r:=n^.r;
  182. X             p:=r;
  183. X          END;
  184. X       END (* if *);
  185. X       splayItem.destroy(n^.data);
  186. X       Storage.DEALLOCATE(n,SIZE(treeNode));
  187. X       DEC(tree^.nbr);
  188. X        END replace;
  189. X     BEGIN (* delete *) 
  190. X        l:=SYSTEM.ADR(left); r:=SYSTEM.ADR(right);
  191. X        n := tree^.t;
  192. X    IF n=NIL THEN RETURN;
  193. X    ELSIF splayItem.cmp(n^.data,item)=0 THEN replace(tree^.t,n);
  194. X    ELSE
  195. X       LOOP
  196. X          IF splayItem.cmp(item,n^.data)<0 THEN
  197. X             nn:=n^.l;
  198. X         IF nn=NIL THEN EXIT;
  199. X         ELSE 
  200. X            IF splayItem.cmp(item,nn^.data)=0 THEN 
  201. X               replace(n^.l,nn);
  202. X               EXIT;  
  203. X            ELSIF splayItem.cmp(item,nn^.data)<0 THEN 
  204. X               nnn:=nn^.l;
  205. X               IF nnn#NIL THEN
  206. X                     IF splayItem.cmp(item,nnn^.data)=0 THEN
  207. X                 replace(nn^.l,nnn);
  208. X                 r^.l:=n; r:=n; n:=nn;
  209. X                 EXIT;
  210. X              ELSE (* case III *) 
  211. X                 n^.l:=nn^.r;
  212. X                 r^.l:=nn; r:=nn; 
  213. X                 nn^.r:=n;
  214. X                 n:=nnn;
  215. X              END (* if *);
  216. X               ELSE (* nnn=NIL *)
  217. X                     r^.l:=n; r:=n; n:=nn;
  218. X              EXIT;
  219. X               END (* if nnn#NIL *);
  220. X            ELSE (* item > n^.data *)
  221. X               nnn:=nn^.r;
  222. X               IF nnn#NIL THEN
  223. X                  IF splayItem.cmp(item,nnn^.data)=0 THEN
  224. X                 replace(nn^.r,nnn);
  225. X                 r^.l:=n; r:=n; n:=nn;
  226. X                 EXIT;
  227. X              ELSE (* case V *)
  228. X                 l^.r:=nn; l:=nn;
  229. X                 r^.l:=n; r:=n;
  230. X                 n:=nnn;
  231. X              END (* if *);
  232. X               ELSE (* nnn=NIL *)
  233. X              r^.l:=n; r:=n; n:=nn;
  234. X              EXIT;
  235. X               END (* if nnn#NIL *);
  236. X            END (* if *);
  237. X         END (* if nn#NIL  *);
  238. X          ELSE (* item>n^.data *)
  239. X               nn:=n^.r;
  240. X         IF nn=NIL THEN EXIT;
  241. X         ELSE 
  242. X            IF splayItem.cmp(item,nn^.data)=0 THEN 
  243. X               replace(n^.r,nn);
  244. X               EXIT;  
  245. X            ELSIF splayItem.cmp(item,nn^.data)>0 THEN 
  246. X               nnn:=nn^.r;
  247. X               IF nnn#NIL THEN
  248. X                     IF splayItem.cmp(item,nnn^.data)=0 THEN
  249. X                 replace(nn^.r,nnn);
  250. X                 l^.r:=n; l:=n; n:=nn;
  251. X                 EXIT;
  252. X              ELSE (* case IV *)
  253. X                 n^.r:=nn^.l;
  254. X                 l^.r:=nn; l:=nn;
  255. X                 nn^.l:=n;
  256. X                 n:=nnn;
  257. X              END (* if *);
  258. X               ELSE (* nnn=NIL *)
  259. X              l^.r:=n; l:=n; n:=nn;
  260. X              EXIT;
  261. X               END (* if nnn#NIL *);
  262. X            ELSE (* item < n^.data *)
  263. X               nnn:=nn^.l;
  264. X               IF nnn#NIL THEN
  265. X                  IF splayItem.cmp(item,nnn^.data)=0 THEN
  266. X                 replace(nn^.l,nnn);
  267. X                 l^.r:=n; l:=n; n:=nn;
  268. X                 EXIT;
  269. X              ELSE (* case VI *)
  270. X                 l^.r:=n; l:=n;
  271. X                 r^.l:=nn; r:=nn;
  272. X                 n:=nnn;
  273. X              END (* if *);
  274. X               ELSE (* nnn=NIL *)
  275. X              l^.r:=n; l:=n; n:=nn;
  276. X              EXIT;
  277. X               END (* if nnn#NIL *);
  278. X            END (* if *);
  279. X         END (* if nn#nil *);
  280. X          END (* if *);
  281. X       END (* loop *);
  282. X       l^.r:=n^.l; r^.l:=n^.r; 
  283. X       n^.l:=left.r; n^.r:=right.l;
  284. X       tree^.t:=n;      
  285. X    END;
  286. X    fixRank(tree^.t);
  287. X     END delete;
  288. X
  289. X
  290. X(*   *)
  291. X  PROCEDURE find(tree:T; item:splayItem.T;VAR found:splayItem.T): BOOLEAN;
  292. X     VAR l,r,nnn,nn,n:Tree;
  293. X         left,right:treeNode;
  294. X         fFound : BOOLEAN;
  295. X     BEGIN (* find *)
  296. X        l:=SYSTEM.ADR(left); r:=SYSTEM.ADR(right);
  297. X    fFound:=FALSE;
  298. X        n := tree^.t;
  299. X    IF n=NIL THEN RETURN FALSE;
  300. X    ELSIF splayItem.cmp(n^.data,item)=0 THEN
  301. X       found:=n^.data; 
  302. X       RETURN TRUE;
  303. X    ELSE
  304. X       LOOP
  305. X          IF splayItem.cmp(item,n^.data)=0 THEN
  306. X             found:=n^.data; fFound:=TRUE;
  307. X         EXIT;
  308. X          ELSIF splayItem.cmp(item,n^.data)<0 THEN
  309. X             nn:=n^.l;
  310. X         IF nn=NIL THEN EXIT;
  311. X         ELSE 
  312. X            IF splayItem.cmp(item,nn^.data)=0 THEN  (* case I   *)
  313. X               r^.l:=n; r:=n; n:=nn;
  314. X               found:=n^.data; fFound:=TRUE;
  315. X               EXIT;  
  316. X            ELSIF splayItem.cmp(item,nn^.data)<0 THEN 
  317. X               nnn:=nn^.l;
  318. X               IF nnn#NIL THEN                  (* case III *)
  319. X              n^.l:=nn^.r;
  320. X              r^.l:=nn; r:=nn; 
  321. X              nn^.r:=n; n:=nnn;
  322. X               ELSE (* nnn=NIL *)
  323. X                     r^.l:=n; r:=n; n:=nn;
  324. X              EXIT;
  325. X               END (* if nnn#NIL *);
  326. X            ELSE (* item > nn^.data *)
  327. X               nnn:=nn^.r;
  328. X               IF nnn#NIL THEN                  (* case V   *)
  329. X              l^.r:=nn; l:=nn;
  330. X              r^.l:=n; r:=n; n:=nnn;
  331. X               ELSE (* nnn=NIL *)
  332. X              r^.l:=n; r:=n; n:=nn;
  333. X              EXIT;
  334. X               END (* if nnn#NIL *);
  335. X            END (* if *);
  336. X         END (* if nn#NIL  *);
  337. X          ELSE (* item>n^.data *)
  338. X               nn:=n^.r;
  339. X         IF nn=NIL THEN EXIT;
  340. X         ELSE 
  341. X            IF splayItem.cmp(item,nn^.data)=0 THEN  (* case II  *)
  342. X               l^.r:=n; l:=n; n:=nn;
  343. X               found:=n^.data; fFound:=TRUE;
  344. X               EXIT;  
  345. X            ELSIF splayItem.cmp(item,nn^.data)>0 THEN 
  346. X               nnn:=nn^.r;
  347. X               IF nnn#NIL THEN                  (* case IV  *)
  348. X              n^.r:=nn^.l;
  349. X              l^.r:=nn; l:=nn;
  350. X              nn^.l:=n; n:=nnn;
  351. X               ELSE (* nnn=NIL *)
  352. X              l^.r:=n; l:=n; n:=nn;
  353. X              EXIT;
  354. X               END (* if nnn#NIL *);
  355. X            ELSE (* item < nn^.data *)
  356. X               nnn:=nn^.l;
  357. X               IF nnn#NIL THEN                  (* case VI  *)
  358. X              l^.r:=n; l:=n;
  359. X              r^.l:=nn; r:=nn; n:=nnn;
  360. X               ELSE (* nnn=NIL *)
  361. X              l^.r:=n; l:=n; n:=nn;
  362. X              EXIT;
  363. X               END (* if nnn#NIL *);
  364. X            END (* if cmp(...) *);
  365. X         END (* if nn=nil *);
  366. X          END (* if cmp(...) *);
  367. X       END (* loop *);
  368. X       r^.l:=n^.r; l^.r:=n^.l; 
  369. X       n^.l:=left.r; n^.r:=right.l; 
  370. X       tree^.t:=n;
  371. X    END;
  372. X    fixRank(tree^.t);
  373. X    RETURN fFound;      
  374. X     END find;
  375. X  
  376. X
  377. X  PROCEDURE getRank(tree:T; item:splayItem.T): CARDINAL;
  378. X     VAR t,p:Tree;rank:CARDINAL;
  379. X     BEGIN (* getRank *)
  380. X       t:=tree^.t;
  381. X       p:=NIL;
  382. X       rank:=1;
  383. X       LOOP 
  384. X         IF t = NIL THEN
  385. X           RETURN 0;
  386. X         ELSE 
  387. X           IF splayItem.cmp(t^.data,item)=0 THEN 
  388. X               IF t^.l # NIL THEN 
  389. X                  RETURN rank+t^.l^.weight;
  390. X               ELSE
  391. X                  RETURN rank;
  392. X               END;
  393. X           ELSIF splayItem.cmp(t^.data,item) > 0  THEN 
  394. X               p:=t;
  395. X               t := t^.l;
  396. X           ELSE
  397. X               IF t^.l#NIL THEN  
  398. X                  rank:=rank+t^.l^.weight+1;
  399. X               ELSE 
  400. X                  INC(rank);
  401. X               END;
  402. X               p:=t;
  403. X               t := t^.r
  404. X           END;
  405. X         END (* if *);
  406. X       END (* loop *);
  407. X     END getRank;
  408. X
  409. X  
  410. X   PROCEDURE getRankElement(tree:T; r:CARDINAL; VAR found:splayItem.T):BOOLEAN;
  411. X      VAR n:Tree;rank,weight:CARDINAL;
  412. X      BEGIN (* getRankElement *)
  413. X         n:=tree^.t;
  414. X     rank:=0;
  415. X     WHILE n#NIL DO
  416. X       IF n^.l#NIL THEN weight:=n^.l^.weight+1;
  417. X       ELSE weight:=1; END; 
  418. X       IF r=rank+weight THEN
  419. X         found:=n^.data;
  420. X         RETURN TRUE;
  421. X       ELSIF r<rank+weight THEN
  422. X         n:=n^.l;
  423. X       ELSE
  424. X         rank:=rank+weight;
  425. X         n:=n^.r; 
  426. X       END (* if *);
  427. X     END;
  428. X     RETURN FALSE;
  429. X      END getRankElement;
  430. X      
  431. X   PROCEDURE fixRank(n:Tree);
  432. X      BEGIN (* fixRank *)
  433. X        IF n#NIL THEN 
  434. X           fixRank(n^.l);
  435. X       fixRank(n^.r);
  436. X       n^.weight:=1;
  437. X       IF n^.l#NIL THEN n^.weight:=n^.weight+n^.l^.weight; END;
  438. X       IF n^.r#NIL THEN n^.weight:=n^.weight+n^.r^.weight; END;
  439. X    END;
  440. X      END fixRank;
  441. X
  442. X  PROCEDURE mapIn(tree:T; f:auxFunc);
  443. X     PROCEDURE mI(t:Tree);
  444. X    BEGIN (* mI *)
  445. X      IF t # NIL THEN mI(t^.l); f(t^.data); mI(t^.r); END;
  446. X    END mI;
  447. X     BEGIN (* mapIn *)
  448. X       mI(tree^.t); 
  449. X     END mapIn;
  450. X
  451. X
  452. X  PROCEDURE mapPre(tree:T; f:auxFunc);
  453. X     PROCEDURE mPr(t:Tree);
  454. X    BEGIN (* mPr *)
  455. X      IF t # NIL THEN f(t^.data); mPr(t^.l); mPr(t^.r); END;
  456. X    END mPr;
  457. X     BEGIN (* mapPre *)
  458. X       mPr(tree^.t); 
  459. X     END mapPre;
  460. X
  461. X
  462. X  PROCEDURE mapPos(tree:T; f:auxFunc);
  463. X     PROCEDURE mPo(t:Tree);
  464. X    BEGIN (* mPo *)
  465. X      IF t # NIL THEN mPo(t^.l); mPo(t^.r); f(t^.data); END;
  466. X    END mPo;
  467. X     BEGIN (* mapPos *)
  468. X       mPo(tree^.t); 
  469. X     END mapPos;
  470. X
  471. XEND splay.
  472. X
  473. SHAR_EOF
  474. $TOUCH -am 1122140092 splay.mod &&
  475. chmod 0444 splay.mod ||
  476. echo "restore of splay.mod failed"
  477. set `wc -c splay.mod`;Wc_c=$1
  478. if test "$Wc_c" != "11524"; then
  479.     echo original size 11524, current size $Wc_c
  480. fi
  481. fi
  482. # ============= splayItem.mod ==============
  483. if test X"$1" != X"-c" -a -f 'splayItem.mod'; then
  484.     echo "File already exists: skipping 'splayItem.mod'"
  485. else
  486. echo "x - extracting splayItem.mod (Text)"
  487. sed 's/^X//' << 'SHAR_EOF' > splayItem.mod &&
  488. X(*
  489. X    Title:        
  490. X    Last Edit:    Sun Nov 22 12:30:53 1992
  491. X    Author:        Johan Persson at my16
  492. X*)
  493. X
  494. XIMPLEMENTATION MODULE splayItem;
  495. X
  496. X  
  497. X  PROCEDURE cmp(a:T; b:T): INTEGER;
  498. X     BEGIN (* cmp *)
  499. X    IF a=b THEN RETURN 0;
  500. X    ELSIF a<b THEN RETURN -1;
  501. X    ELSE RETURN 1;
  502. X    END (* if *);
  503. X     END cmp;
  504. X
  505. X  PROCEDURE destroy(VAR a:T);
  506. X     BEGIN (* destroy *)
  507. X     END destroy;
  508. X     
  509. X  PROCEDURE create(VAR a:T);
  510. X     BEGIN (* create *)
  511. X     END create;
  512. X  
  513. X  
  514. X
  515. XEND splayItem.
  516. SHAR_EOF
  517. $TOUCH -am 1122140092 splayItem.mod &&
  518. chmod 0644 splayItem.mod ||
  519. echo "restore of splayItem.mod failed"
  520. set `wc -c splayItem.mod`;Wc_c=$1
  521. if test "$Wc_c" != "447"; then
  522.     echo original size 447, current size $Wc_c
  523. fi
  524. fi
  525. # ============= splayTest.mod ==============
  526. if test X"$1" != X"-c" -a -f 'splayTest.mod'; then
  527.     echo "File already exists: skipping 'splayTest.mod'"
  528. else
  529. echo "x - extracting splayTest.mod (Text)"
  530. sed 's/^X//' << 'SHAR_EOF' > splayTest.mod &&
  531. XMODULE splayTest; 
  532. X(*
  533. X    Title:        
  534. X    Last Edit:    Sun Nov 22 13:35:40 1992
  535. X    Author:        Johan Persson at my9
  536. X
  537. X    SCCS:        %Z%%M%       %I%     %E%        
  538. X
  539. X*)
  540. X
  541. XIMPORT splay, splayItem, std, string, int, card;
  542. X
  543. X
  544. XVAR t:splay.T;
  545. X    i:splayItem.T;
  546. X    tmp:splayItem.T;
  547. X    
  548. X   
  549. XPROCEDURE printsplayItem(i:splayItem.T);
  550. X   
  551. X   BEGIN (* printsplayItem *)
  552. X     int.write(std.out,i,0);
  553. X     string.writef(std.out,",");   
  554. X   END printsplayItem;
  555. X
  556. X
  557. XPROCEDURE msg(s:ARRAY OF CHAR);
  558. X   BEGIN (* msg *)
  559. X     string.writef(std.out,s);
  560. X   END msg;
  561. X
  562. X
  563. XBEGIN
  564. X
  565. Xmsg("Create the structure ...");
  566. X
  567. Xsplay.create(t);
  568. X
  569. Xmsg("done.\n");
  570. X
  571. Xmsg("Beginning with insertions\n");
  572. X
  573. XFOR i := 0 TO 255 DO
  574. X  splay.insert(t,i);   
  575. XEND (* for *);
  576. X
  577. Xmsg("Done with insertions\n");
  578. X
  579. XIF splay.find(t,13,tmp) THEN
  580. X   msg("found 13 (tmp=");
  581. X   int.write(std.out,tmp,0);
  582. X   msg(") OK.\n");
  583. X   splay.mapPre(t,printsplayItem);
  584. X   msg("\n");
  585. XELSE
  586. X   msg("****** ERROR IN find routine!\n");
  587. XEND (* if *);
  588. X
  589. XIF splay.find(t,18,tmp) THEN
  590. X   msg("found 18 (tmp=");
  591. X   int.write(std.out,tmp,0);
  592. X   msg(") OK.\n");
  593. X   splay.mapPre(t,printsplayItem);
  594. X   msg("\n");
  595. XELSE
  596. X   msg("**** ERROR IN exist routine!\n");
  597. XEND (* if *);
  598. X
  599. XIF splay.find(t,300,tmp) THEN
  600. X   msg("ERROR IN exist routine!  ");
  601. X   msg("found 300 (tmp=");
  602. X   int.write(std.out,tmp,0);
  603. X   msg(")\n");
  604. XELSE
  605. X   msg("Didn't find 300. OK.\n");
  606. X   splay.mapPre(t,printsplayItem);
  607. X   msg("\n");
  608. XEND (* if *);
  609. X
  610. X
  611. Xmsg("Print a sorted version ...\n");
  612. X
  613. Xsplay.mapIn(t,printsplayItem);
  614. X
  615. Xmsg("\n\n Print some rank's\n");
  616. X
  617. XIF splay.getRankElement(t,3,tmp) THEN 
  618. X   msg("3=> "); int.write(std.out,tmp,0); msg("\n");
  619. XELSE 
  620. X   msg("ERROR didn't find rank 3\n\n");
  621. XEND;
  622. X
  623. XIF splay.getRankElement(t,1,tmp) THEN 
  624. X   msg("1=> "); int.write(std.out,tmp,0); msg("\n");
  625. XELSE 
  626. X   msg("ERROR didn't find rank 1\n\n");
  627. XEND;
  628. X
  629. XIF splay.getRankElement(t,6,tmp) THEN 
  630. X   msg("6=> "); int.write(std.out,tmp,0); msg("\n");
  631. XELSE 
  632. X   msg("ERROR didn't find rank 6\n\n");
  633. XEND;
  634. X
  635. XIF splay.getRank(t,255)#256 THEN 
  636. X   msg("**** ERROR IN getRank\n");
  637. XELSE 
  638. X   msg("\n 255 has rank 256\n");
  639. XEND;
  640. X
  641. Xmsg("\n and now we delete som element");
  642. X
  643. Xmsg("\n 6 ..");
  644. X
  645. Xsplay.delete(t,6);
  646. X
  647. Xmsg("\n Print a sorted version ...\n");
  648. X
  649. Xsplay.mapIn(t,printsplayItem);
  650. X
  651. Xmsg("\n");
  652. X
  653. Xsplay.destroy(t);
  654. X
  655. XEND splayTest.
  656. SHAR_EOF
  657. $TOUCH -am 1122140092 splayTest.mod &&
  658. chmod 0644 splayTest.mod ||
  659. echo "restore of splayTest.mod failed"
  660. set `wc -c splayTest.mod`;Wc_c=$1
  661. if test "$Wc_c" != "2242"; then
  662.     echo original size 2242, current size $Wc_c
  663. fi
  664. fi
  665. exit 0
  666.