391 lines
14 KiB
COBOL
391 lines
14 KiB
COBOL
IDENTIFICATION DIVISION.
|
|
PROGRAM-ID. KD-TREE-TEST.
|
|
DATA DIVISION.
|
|
WORKING-STORAGE SECTION.
|
|
01 KD-TREE-STATE.
|
|
05 NUM-DIMENSIONS PIC 9(4) COMP.
|
|
05 TOTAL-NODES PIC 9(6) COMP.
|
|
05 TREE-ROOT PIC 9(6) COMP.
|
|
05 BEST-NODE PIC 9(6) COMP.
|
|
05 BEST-DISTANCE COMP-2.
|
|
05 VISITED-COUNT PIC 9(6) COMP.
|
|
05 MAX-NODES PIC 9(6) COMP VALUE 1005.
|
|
|
|
01 KD-NODES-DATA.
|
|
05 NODES OCCURS 1005 TIMES.
|
|
10 COORDS COMP-2 OCCURS 3 TIMES.
|
|
10 LEFT-CHILD PIC 9(6) COMP.
|
|
10 RIGHT-CHILD PIC 9(6) COMP.
|
|
|
|
01 KD-PTRS-DATA.
|
|
05 PTRS OCCURS 1005 TIMES.
|
|
10 NODE-PTR PIC 9(6) COMP.
|
|
|
|
01 TARGET-NODE-DATA.
|
|
05 TARGET-COORDS COMP-2 OCCURS 3 TIMES.
|
|
|
|
01 I PIC 9(6) COMP.
|
|
01 BEGIN-IDX PIC 9(6) COMP.
|
|
01 END-IDX PIC 9(6) COMP.
|
|
01 DIM-IDX PIC 9(4) COMP.
|
|
|
|
01 DISP-COORD-1 PIC -Z9.9(6).
|
|
01 DISP-COORD-2 PIC -Z9.9(6).
|
|
01 DISP-COORD-3 PIC -Z9.9(6).
|
|
01 TMP-DIST COMP-2.
|
|
01 DISP-DIST PIC -Z9.9(6).
|
|
01 DISP-VISITED PIC Z(5)9.
|
|
|
|
01 L-POINTS PIC 9(6) COMP.
|
|
01 SEED PIC 9(9) COMP.
|
|
01 DUMMY-FLOAT COMP-2.
|
|
|
|
PROCEDURE DIVISION.
|
|
MAIN-PROCEDURE.
|
|
MOVE FUNCTION CURRENT-DATE(11:6) TO SEED
|
|
COMPUTE DUMMY-FLOAT = FUNCTION RANDOM(SEED)
|
|
|
|
PERFORM TEST-WIKIPEDIA
|
|
DISPLAY " "
|
|
MOVE 100 TO L-POINTS
|
|
PERFORM TEST-RANDOM
|
|
DISPLAY " "
|
|
MOVE 1000 TO L-POINTS
|
|
PERFORM TEST-RANDOM
|
|
|
|
STOP RUN.
|
|
|
|
TEST-WIKIPEDIA.
|
|
INITIALIZE KD-NODES-DATA
|
|
MOVE 2 TO NUM-DIMENSIONS
|
|
MOVE 6 TO TOTAL-NODES
|
|
|
|
MOVE 0 TO TREE-ROOT
|
|
MOVE 0 TO BEST-NODE
|
|
MOVE 0 TO VISITED-COUNT
|
|
|
|
MOVE 2 TO COORDS(1, 1) MOVE 3 TO COORDS(1, 2)
|
|
MOVE 5 TO COORDS(2, 1) MOVE 4 TO COORDS(2, 2)
|
|
MOVE 9 TO COORDS(3, 1) MOVE 6 TO COORDS(3, 2)
|
|
MOVE 4 TO COORDS(4, 1) MOVE 7 TO COORDS(4, 2)
|
|
MOVE 8 TO COORDS(5, 1) MOVE 1 TO COORDS(5, 2)
|
|
MOVE 7 TO COORDS(6, 1) MOVE 2 TO COORDS(6, 2)
|
|
|
|
PERFORM VARYING I FROM 1 BY 1 UNTIL I > 6
|
|
MOVE I TO NODE-PTR OF PTRS(I)
|
|
END-PERFORM
|
|
|
|
MOVE 1 TO BEGIN-IDX
|
|
MOVE 7 TO END-IDX
|
|
MOVE 1 TO DIM-IDX
|
|
CALL "MAKE-TREE" USING KD-TREE-STATE KD-NODES-DATA KD-PTRS-DATA
|
|
BEGIN-IDX END-IDX DIM-IDX TREE-ROOT
|
|
|
|
MOVE 9 TO TARGET-COORDS(1)
|
|
MOVE 2 TO TARGET-COORDS(2)
|
|
MOVE 0 TO TARGET-COORDS(3)
|
|
|
|
MOVE 1 TO DIM-IDX
|
|
CALL "FIND-NEAREST" USING KD-TREE-STATE KD-NODES-DATA TARGET-NODE-DATA
|
|
TREE-ROOT DIM-IDX
|
|
|
|
*> DISPLAY "Tree dump:"
|
|
*> PERFORM VARYING I FROM 1 BY 1 UNTIL I > 6
|
|
*> DISPLAY "Node " I ": (" FUNCTION TRIM(COORDS(I, 1)) ", " FUNCTION TRIM(COORDS(I, 2)) ") "
|
|
*> "L=" LEFT-CHILD(I) " R=" RIGHT-CHILD(I)
|
|
*> END-PERFORM
|
|
|
|
DISPLAY "Wikipedia example data:"
|
|
COMPUTE TMP-DIST = FUNCTION SQRT(BEST-DISTANCE)
|
|
MOVE COORDS(BEST-NODE, 1) TO DISP-COORD-1
|
|
MOVE COORDS(BEST-NODE, 2) TO DISP-COORD-2
|
|
DISPLAY "nearest point: (" FUNCTION TRIM(DISP-COORD-1) ", "
|
|
FUNCTION TRIM(DISP-COORD-2) ")"
|
|
MOVE TMP-DIST TO DISP-DIST
|
|
DISPLAY "distance: " FUNCTION TRIM(DISP-DIST)
|
|
MOVE VISITED-COUNT TO DISP-VISITED
|
|
DISPLAY "nodes visited: " FUNCTION TRIM(DISP-VISITED).
|
|
|
|
TEST-RANDOM.
|
|
INITIALIZE KD-NODES-DATA
|
|
MOVE 3 TO NUM-DIMENSIONS
|
|
MOVE L-POINTS TO TOTAL-NODES
|
|
|
|
MOVE 0 TO TREE-ROOT
|
|
MOVE 0 TO BEST-NODE
|
|
MOVE 0 TO VISITED-COUNT
|
|
|
|
PERFORM VARYING I FROM 1 BY 1 UNTIL I > L-POINTS
|
|
COMPUTE COORDS(I, 1) = FUNCTION RANDOM
|
|
COMPUTE COORDS(I, 2) = FUNCTION RANDOM
|
|
COMPUTE COORDS(I, 3) = FUNCTION RANDOM
|
|
MOVE I TO NODE-PTR OF PTRS(I)
|
|
END-PERFORM
|
|
|
|
MOVE 1 TO BEGIN-IDX
|
|
COMPUTE END-IDX = L-POINTS + 1
|
|
MOVE 1 TO DIM-IDX
|
|
CALL "MAKE-TREE" USING KD-TREE-STATE KD-NODES-DATA KD-PTRS-DATA
|
|
BEGIN-IDX END-IDX DIM-IDX TREE-ROOT
|
|
|
|
COMPUTE TARGET-COORDS(1) = FUNCTION RANDOM
|
|
COMPUTE TARGET-COORDS(2) = FUNCTION RANDOM
|
|
COMPUTE TARGET-COORDS(3) = FUNCTION RANDOM
|
|
|
|
MOVE 1 TO DIM-IDX
|
|
CALL "FIND-NEAREST" USING KD-TREE-STATE KD-NODES-DATA TARGET-NODE-DATA
|
|
TREE-ROOT DIM-IDX
|
|
|
|
DISPLAY "Random data (" L-POINTS " points):"
|
|
MOVE TARGET-COORDS(1) TO DISP-COORD-1
|
|
MOVE TARGET-COORDS(2) TO DISP-COORD-2
|
|
MOVE TARGET-COORDS(3) TO DISP-COORD-3
|
|
DISPLAY "target: (" FUNCTION TRIM(DISP-COORD-1) ", "
|
|
FUNCTION TRIM(DISP-COORD-2) ", "
|
|
FUNCTION TRIM(DISP-COORD-3) ")"
|
|
|
|
COMPUTE TMP-DIST = FUNCTION SQRT(BEST-DISTANCE)
|
|
MOVE COORDS(BEST-NODE, 1) TO DISP-COORD-1
|
|
MOVE COORDS(BEST-NODE, 2) TO DISP-COORD-2
|
|
MOVE COORDS(BEST-NODE, 3) TO DISP-COORD-3
|
|
DISPLAY "nearest point: (" FUNCTION TRIM(DISP-COORD-1) ", "
|
|
FUNCTION TRIM(DISP-COORD-2) ", "
|
|
FUNCTION TRIM(DISP-COORD-3) ")"
|
|
MOVE TMP-DIST TO DISP-DIST
|
|
DISPLAY "distance: " FUNCTION TRIM(DISP-DIST)
|
|
MOVE VISITED-COUNT TO DISP-VISITED
|
|
DISPLAY "nodes visited: " FUNCTION TRIM(DISP-VISITED).
|
|
|
|
END PROGRAM KD-TREE-TEST.
|
|
|
|
IDENTIFICATION DIVISION.
|
|
PROGRAM-ID. MAKE-TREE IS RECURSIVE.
|
|
DATA DIVISION.
|
|
LOCAL-STORAGE SECTION.
|
|
01 QS-RIGHT PIC 9(6) COMP.
|
|
01 N-IDX PIC 9(6) COMP.
|
|
01 NEXT-DIM PIC 9(4) COMP.
|
|
01 N-PLUS-1 PIC 9(6) COMP.
|
|
|
|
LINKAGE SECTION.
|
|
01 KD-TREE-STATE.
|
|
05 NUM-DIMENSIONS PIC 9(4) COMP.
|
|
05 TOTAL-NODES PIC 9(6) COMP.
|
|
05 TREE-ROOT PIC 9(6) COMP.
|
|
05 BEST-NODE PIC 9(6) COMP.
|
|
05 BEST-DISTANCE COMP-2.
|
|
05 VISITED-COUNT PIC 9(6) COMP.
|
|
05 MAX-NODES PIC 9(6) COMP.
|
|
|
|
01 KD-NODES-DATA.
|
|
05 NODES OCCURS 1005 TIMES.
|
|
10 COORDS COMP-2 OCCURS 3 TIMES.
|
|
10 LEFT-CHILD PIC 9(6) COMP.
|
|
10 RIGHT-CHILD PIC 9(6) COMP.
|
|
|
|
01 KD-PTRS-DATA.
|
|
05 PTRS OCCURS 1005 TIMES.
|
|
10 NODE-PTR PIC 9(6) COMP.
|
|
|
|
01 BEGIN-IDX PIC 9(6) COMP.
|
|
01 END-IDX PIC 9(6) COMP.
|
|
01 DIM-IDX PIC 9(4) COMP.
|
|
01 RET-NODE PIC 9(6) COMP.
|
|
|
|
PROCEDURE DIVISION USING KD-TREE-STATE KD-NODES-DATA KD-PTRS-DATA
|
|
BEGIN-IDX END-IDX DIM-IDX RET-NODE.
|
|
IF END-IDX <= BEGIN-IDX
|
|
MOVE 0 TO RET-NODE
|
|
GOBACK
|
|
END-IF
|
|
|
|
COMPUTE N-IDX = BEGIN-IDX + (END-IDX - BEGIN-IDX) / 2
|
|
COMPUTE QS-RIGHT = END-IDX - 1
|
|
|
|
CALL "QUICK-SELECT" USING KD-TREE-STATE KD-NODES-DATA KD-PTRS-DATA
|
|
BEGIN-IDX QS-RIGHT N-IDX DIM-IDX RET-NODE
|
|
|
|
COMPUTE NEXT-DIM = FUNCTION MOD(DIM-IDX, NUM-DIMENSIONS) + 1
|
|
|
|
CALL "MAKE-TREE" USING KD-TREE-STATE KD-NODES-DATA KD-PTRS-DATA
|
|
BEGIN-IDX N-IDX NEXT-DIM LEFT-CHILD(RET-NODE)
|
|
|
|
COMPUTE N-PLUS-1 = N-IDX + 1
|
|
CALL "MAKE-TREE" USING KD-TREE-STATE KD-NODES-DATA KD-PTRS-DATA
|
|
N-PLUS-1 END-IDX NEXT-DIM RIGHT-CHILD(RET-NODE)
|
|
|
|
GOBACK.
|
|
END PROGRAM MAKE-TREE.
|
|
|
|
IDENTIFICATION DIVISION.
|
|
PROGRAM-ID. QUICK-SELECT.
|
|
DATA DIVISION.
|
|
WORKING-STORAGE SECTION.
|
|
01 RANGE-SIZE PIC 9(6) COMP.
|
|
01 PIVOT PIC 9(6) COMP.
|
|
01 PIVOT-VAL PIC 9(6) COMP.
|
|
01 TEMP PIC 9(6) COMP.
|
|
01 STORE-IDX PIC 9(6) COMP.
|
|
01 I PIC 9(6) COMP.
|
|
01 I-VAL PIC 9(6) COMP.
|
|
01 RET-PIVOT PIC 9(6) COMP.
|
|
|
|
LINKAGE SECTION.
|
|
01 KD-TREE-STATE.
|
|
05 NUM-DIMENSIONS PIC 9(4) COMP.
|
|
05 TOTAL-NODES PIC 9(6) COMP.
|
|
05 TREE-ROOT PIC 9(6) COMP.
|
|
05 BEST-NODE PIC 9(6) COMP.
|
|
05 BEST-DISTANCE COMP-2.
|
|
05 VISITED-COUNT PIC 9(6) COMP.
|
|
05 MAX-NODES PIC 9(6) COMP.
|
|
|
|
01 KD-NODES-DATA.
|
|
05 NODES OCCURS 1005 TIMES.
|
|
10 COORDS COMP-2 OCCURS 3 TIMES.
|
|
10 LEFT-CHILD PIC 9(6) COMP.
|
|
10 RIGHT-CHILD PIC 9(6) COMP.
|
|
|
|
01 KD-PTRS-DATA.
|
|
05 PTRS OCCURS 1005 TIMES.
|
|
10 NODE-PTR PIC 9(6) COMP.
|
|
|
|
01 L-LEFT PIC 9(6) COMP.
|
|
01 L-RIGHT PIC 9(6) COMP.
|
|
01 L-N PIC 9(6) COMP.
|
|
01 L-DIM PIC 9(4) COMP.
|
|
01 L-RET PIC 9(6) COMP.
|
|
|
|
PROCEDURE DIVISION USING KD-TREE-STATE KD-NODES-DATA KD-PTRS-DATA
|
|
L-LEFT L-RIGHT L-N L-DIM L-RET.
|
|
MAIN-LOOP.
|
|
PERFORM UNTIL 1 = 0
|
|
IF L-LEFT = L-RIGHT
|
|
MOVE NODE-PTR OF PTRS(L-LEFT) TO L-RET
|
|
GOBACK
|
|
END-IF
|
|
|
|
COMPUTE RANGE-SIZE = L-RIGHT - L-LEFT + 1
|
|
COMPUTE PIVOT = L-LEFT + FUNCTION INTEGER(RANGE-SIZE * FUNCTION RANDOM)
|
|
IF PIVOT > L-RIGHT
|
|
MOVE L-RIGHT TO PIVOT
|
|
END-IF
|
|
|
|
MOVE NODE-PTR OF PTRS(PIVOT) TO PIVOT-VAL
|
|
MOVE NODE-PTR OF PTRS(L-RIGHT) TO TEMP
|
|
MOVE PIVOT-VAL TO NODE-PTR OF PTRS(L-RIGHT)
|
|
MOVE TEMP TO NODE-PTR OF PTRS(PIVOT)
|
|
MOVE L-LEFT TO STORE-IDX
|
|
|
|
PERFORM VARYING I FROM L-LEFT BY 1 UNTIL I >= L-RIGHT
|
|
MOVE NODE-PTR OF PTRS(I) TO I-VAL
|
|
IF COORDS(I-VAL, L-DIM) < COORDS(PIVOT-VAL, L-DIM)
|
|
MOVE NODE-PTR OF PTRS(STORE-IDX) TO TEMP
|
|
MOVE I-VAL TO NODE-PTR OF PTRS(STORE-IDX)
|
|
MOVE TEMP TO NODE-PTR OF PTRS(I)
|
|
ADD 1 TO STORE-IDX
|
|
END-IF
|
|
END-PERFORM
|
|
|
|
MOVE NODE-PTR OF PTRS(STORE-IDX) TO TEMP
|
|
MOVE NODE-PTR OF PTRS(L-RIGHT) TO NODE-PTR OF PTRS(STORE-IDX)
|
|
MOVE TEMP TO NODE-PTR OF PTRS(L-RIGHT)
|
|
MOVE STORE-IDX TO RET-PIVOT
|
|
|
|
IF L-N = RET-PIVOT
|
|
MOVE NODE-PTR OF PTRS(L-N) TO L-RET
|
|
GOBACK
|
|
ELSE
|
|
IF L-N < RET-PIVOT
|
|
COMPUTE L-RIGHT = RET-PIVOT - 1
|
|
ELSE
|
|
COMPUTE L-LEFT = RET-PIVOT + 1
|
|
END-IF
|
|
END-IF
|
|
END-PERFORM.
|
|
END PROGRAM QUICK-SELECT.
|
|
|
|
IDENTIFICATION DIVISION.
|
|
PROGRAM-ID. FIND-NEAREST IS RECURSIVE.
|
|
DATA DIVISION.
|
|
LOCAL-STORAGE SECTION.
|
|
01 I PIC 9(4) COMP.
|
|
01 DIFF COMP-2.
|
|
01 DIST-SQ COMP-2.
|
|
01 DX COMP-2.
|
|
01 DX-SQ COMP-2.
|
|
01 NEXT-DIM PIC 9(4) COMP.
|
|
01 FIRST-CHILD PIC 9(6) COMP.
|
|
01 SECOND-CHILD PIC 9(6) COMP.
|
|
|
|
LINKAGE SECTION.
|
|
01 KD-TREE-STATE.
|
|
05 NUM-DIMENSIONS PIC 9(4) COMP.
|
|
05 TOTAL-NODES PIC 9(6) COMP.
|
|
05 TREE-ROOT PIC 9(6) COMP.
|
|
05 BEST-NODE PIC 9(6) COMP.
|
|
05 BEST-DISTANCE COMP-2.
|
|
05 VISITED-COUNT PIC 9(6) COMP.
|
|
05 MAX-NODES PIC 9(6) COMP.
|
|
|
|
01 KD-NODES-DATA.
|
|
05 NODES OCCURS 1005 TIMES.
|
|
10 COORDS COMP-2 OCCURS 3 TIMES.
|
|
10 LEFT-CHILD PIC 9(6) COMP.
|
|
10 RIGHT-CHILD PIC 9(6) COMP.
|
|
|
|
01 TARGET-NODE-DATA.
|
|
05 TARGET-COORDS COMP-2 OCCURS 3 TIMES.
|
|
|
|
01 L-CURR PIC 9(6) COMP.
|
|
01 L-DIM PIC 9(4) COMP.
|
|
|
|
PROCEDURE DIVISION USING KD-TREE-STATE KD-NODES-DATA TARGET-NODE-DATA
|
|
L-CURR L-DIM.
|
|
IF L-CURR = 0
|
|
GOBACK
|
|
END-IF
|
|
|
|
ADD 1 TO VISITED-COUNT
|
|
|
|
COMPUTE DIST-SQ = 0
|
|
PERFORM VARYING I FROM 1 BY 1 UNTIL I > NUM-DIMENSIONS
|
|
COMPUTE DIFF = TARGET-COORDS(I) - COORDS(L-CURR, I)
|
|
COMPUTE DIST-SQ = DIST-SQ + DIFF * DIFF
|
|
END-PERFORM
|
|
|
|
IF BEST-NODE = 0 OR DIST-SQ < BEST-DISTANCE
|
|
MOVE DIST-SQ TO BEST-DISTANCE
|
|
MOVE L-CURR TO BEST-NODE
|
|
END-IF
|
|
|
|
IF BEST-DISTANCE = 0
|
|
GOBACK
|
|
END-IF
|
|
|
|
COMPUTE DX = COORDS(L-CURR, L-DIM) - TARGET-COORDS(L-DIM)
|
|
|
|
COMPUTE NEXT-DIM = L-DIM + 1
|
|
IF NEXT-DIM > NUM-DIMENSIONS
|
|
MOVE 1 TO NEXT-DIM
|
|
END-IF
|
|
|
|
IF DX > 0
|
|
MOVE LEFT-CHILD(L-CURR) TO FIRST-CHILD
|
|
MOVE RIGHT-CHILD(L-CURR) TO SECOND-CHILD
|
|
ELSE
|
|
MOVE RIGHT-CHILD(L-CURR) TO FIRST-CHILD
|
|
MOVE LEFT-CHILD(L-CURR) TO SECOND-CHILD
|
|
END-IF
|
|
|
|
CALL "FIND-NEAREST" USING KD-TREE-STATE KD-NODES-DATA TARGET-NODE-DATA
|
|
FIRST-CHILD NEXT-DIM
|
|
|
|
COMPUTE DX-SQ = DX * DX
|
|
IF DX-SQ < BEST-DISTANCE
|
|
CALL "FIND-NEAREST" USING KD-TREE-STATE KD-NODES-DATA TARGET-NODE-DATA
|
|
SECOND-CHILD NEXT-DIM
|
|
END-IF
|
|
|
|
GOBACK.
|
|
END PROGRAM FIND-NEAREST.
|