% Section 2.2.3, Topological sorting % Author Andey Dubinchak kachnibud@gmail.com % Thanks to Chan Vinh VONG % Beta-test version % 26.03.2012 % % Each term has the two-octabyte form % % +----+----+----+----+----+----+----+----+ % | COUNT[k] | % +----+----+----+----+----+----+----+----+ % | TOP[k] | % +----+----+----+----+----+----+----+----+ % or % +----+----+----+----+----+----+----+----+ % | SUC | % +----+----+----+----+----+----+----+----+ % | NEXT | % +----+----+----+----+----+----+----+----+ % % Since no deletion from tables is made in the algorithm % (because no storage must be freed for later use), % the operation P <= AVAIL can be done % in an extremely simple way, % as shown in line 99 below; % we need not keep any linked pool of memory, % and we can choose new nodes consecutively. COUNT IS 0 QLINK IS 0 TOP IS 8 SUC IS 0 NEXT IS 8 T IS $0 F IS $1 P IS $2 j IS $3 k IS $4 ZERO IS $5 N IS $6 kx IS $7 nn IS $8 count IS $9 jb IS $10 kb IS $11 jx IS $12 R IS $13 t IS $255 LOC Data_Segment x0 GREG @ X0 IS @ LOC Data_Segment+#B000000 BUFFER (Loaded data) b0 GREG @ B0 IS @ LOC Data_Segment+#B200000 BUFFER (Output data) b20 GREG @ B20 IS @ LOC Data_Segment+#5000000 Storage pool AVAIL GREG @ LOC #100 i_file BYTE "sort.dat",0 o_file BYTE "output.dat",0 i_read OCTA i_file,BinaryRead o_write OCTA o_file,BinaryWrite b_read OCTA B0,400 b_write OCTA B20,400 * inserting Main GETA t,i_read T1: TRAP 0,Fopen,StdIn GETA t,o_write TRAP 0,Fopen,StdOut GETA t,b_read TRAP 0,Fread,StdIn LDOU N,b0 N <- n SET nn,N SET ZERO,0 SET kx,x0 1H STO ZERO,kx,COUNT COUNT[k] <- 0 STO ZERO,kx,TOP TOP[k] <- 0 ADD kx,kx,#10 SUB nn,nn,1 BNN nn,1B LDA jb,b0,8 T2: 2H LDTU j,jb BP j,3F j>0? BZ j,4F JMP 2B 3H ADD kb,jb,4 LDTU k,kb 16ADDU kx,k,x0 LDOU count,kx,COUNT COUNT[k] ADD count,count,1 +1 STOU count,kx,COUNT -> COUNT[k] 16ADDU jx,j,x0 SET P,AVAIL LDA AVAIL,P,#10 AVAIL <- LINK(P). STO k,P,SUC SUC(P) <- k. LDOU T,jx,TOP STOU T,P,NEXT NEXT(P) <- TOP(j) STOU P,jx,TOP TOP(j) <- P ADD jb,jb,8 JMP 2B 4H SET R,0 SET k,N 16ADDU R,R,x0 4H 16ADDU kx,k,x0 LDOU count,kx,COUNT BP count,H41 STO k,R,QLINK QLINK[R] <- k SET R,k 16ADDU R,R,x0 H41 SUB k,k,1 BP k,4B * sorting LDOU F,x0,QLINK F <- QLINK[0] SET nn,0 5H STOU F,b20,nn BZ F,8F ADD nn,nn,#8 SUB N,N,1 N <- N-1 16ADDU F,F,x0 LDOU P,F,TOP P <- TOP(F) BZ P,7F 6H LDO k,P,SUC r4 <- SUC(P) 16ADDU kx,k,x0 LDOU count,kx,COUNT COUNT[r4] SUB count,count,1 -1 STOU count,kx,COUNT ->COUNT[r4] BP count,H61 STO k,R,QLINK SET R,k 16ADDU R,R,x0 H61 LDOU P,P,NEXT P <- NEXT(P) BNZ P,6B 7H LDOU F,F,QLINK JMP 5B 8H GETA t,b_write TRAP 0,Fwrite,StdOut TRAP 0,Halt,0