org 100h

mov si, values
mov [pos_values], si
mov si, keys
mov [pos_keys], si

input:
  mov ah, 01h
  int 21h
  cmp al, byte(32)
  je end_key
  cmp al, byte(13)
  je end_value
  mov [si], al
  inc si
  jmp input

end_key:
  add [count], 1
  mov byte[si], '$'
  add [pos_keys], 64
  mov si, [pos_values]
  jmp input

end_value:
  cmp si, [pos_keys]
  je make_heap
  mov byte[si], '$'
  add [pos_values], 64
  mov si, [pos_keys]
  jmp input

print1:
  mov dl, byte(10)
  mov ah, 02h
  int 21h
print:
  cmp [count], 0
  je exit
  dec [count]
  add [pos_keys], 64
  add [pos_values], 64
  mov si, [pos_keys]
  call print_key
  back1:
  mov dl, ' '
  mov ah, 02h
  int 21h
  mov si, [pos_values]
  jmp print_value

print_key:
  mov dl, [si]
  cmp dl, '$'
  je back1
  mov ah, 02h
  int 21h
  inc si
  jmp print_key

print_value:
  mov dl, [si]
  cmp dl, '$'
  je print1
  mov ah, 02h
  int 21h
  inc si
  jmp print_value

index:
  mov si, keys
  mov [pos_keys], si
  mov si, values
  mov [pos_values], si
  add [pos_keys], -64
  add [pos_values], -64
  jmp print

make_heap:

  mov cx, [count]
  back3:
  mov ax, [count]
  mov [x], ax
  sub [x], cx
  mov ax, [x]
  call put
  loop back3

  jmp sort

exit:
  mov ax, 4c00h
  int 21h
  ret

put:
  mov si, keys
  imul dx, ax, 64
  mov [position], dx

  add si, [position]
  mov di, heap_keys
  add di, [position]
  mov [pos_heap_keys], di
  call copy

  mov si, values
  add si, [position]
  mov di, heap_values
  add di, [position]
  mov [pos_heap_values], di
  call copy

  jmp sift_up
  back4:
  ret


sift_up:
  mov si, heap_keys
  mov dx, [pos_heap_keys]
  cmp si, [pos_heap_keys]
  je back4

  mov di,[pos_heap_keys]
  sub di, si
  shr di, 6
  inc di
  shr di, 1
  shl di, 6
  sub di, 64
  mov bx, di
  add di, si
  mov ax, di

  sub di, si
  mov si, heap_values
  add di, si
  mov bx, di

  mov si, [pos_heap_keys]
  mov di, ax

  push cx
  mov cx, 64
  repe cmpsb
  pop cx

  jg back4
  call swap
  jmp sift_up


swap:
  mov si, ax
  mov di, buffer
  call copy

  mov si, [pos_heap_keys]
  mov di, ax
  call copy

  mov si, buffer
  mov di, [pos_heap_keys]
  call copy

  mov [pos_heap_keys], ax

  mov si, bx
  mov di, buffer
  call copy

  mov si, [pos_heap_values]
  mov di, bx
  call copy

  mov si, buffer
  mov di, [pos_heap_values]
  call copy

  mov [pos_heap_values], bx


  ret

sort:

  mov ax, [count]
  mov cx, [count]
  back5:
  mov [count1], cx
  mov dx, [count1]
  mov ax, [count]
  sub ax, cx
  call pull
  back8:
  loop back5
  jmp back10

pull:
  mov si, heap_keys
  mov di, keys
  imul dx, ax, 64
  mov [position], dx
  add di, [position]
  call copy

  mov si, heap_values
  mov di, values
  add di, [position]
  call copy

  mov di, heap_keys
  mov si, di
  mov bx, [count1]
  imul dx, bx, 64
  sub dx, 64
  mov [position], dx
  add si, [position]
  call copy


  mov di, heap_values
  mov si,di
  add si, [position]
  call copy

  mov si, heap_keys
  mov ax, si
  mov dx, [count1]
  mov bx, si
  sub [count1], 1
  jmp sift_down
  ret


sift_down:
  mov [min], bx
  mov si, bx

  mov di, heap_keys
  mov [t], di
  mov di, bx
  sub di, [t]
  add di, 64
  shr di, 6
  shl di, 1
  push di
  mov ax, [count1]
  cmp di, [count1]
  jg back8
  jmp compare_to_left
  back6:
  pop di
  inc di
  mov ax, [count1]
  cmp di, [count1]
  jg back7
  jmp compare_to_right
  back7:

  cmp [min], bx
  je back8

  mov ax, [min]
  mov [t], ax
  mov [pos_heap_keys], bx
  mov ax, [min]

  mov si, heap_keys
  sub bx, si
  mov [pos_heap_values], bx
  mov si, heap_values
  add [pos_heap_values], si

  mov si, heap_keys
  sub [min], si
  mov bx, [min]
  mov si, heap_values
  add bx, si

  call swap
  mov bx, [t]

  jmp sift_down



copy:
  push cx
  mov cx, 64
  rep movsb
  pop cx
  ret


compare_to_left:
  mov si, heap_keys
  shl di, 6
  sub di, 64
  add di, si
  mov [t], di
  mov si, [min]
  push cx
  mov cx, 64
  repe cmpsb
  pop cx
  js back6
  mov ax, [t]
  mov [min], ax
  jmp back6

compare_to_right:
  mov si, heap_keys
  shl di, 6
  sub di, 64
  add di, si
  mov [t], di
  mov si, [min]
  push cx
  mov cx, 64
  repe cmpsb
  pop cx
  js back7
  mov ax, [t]
  mov [min], ax
  jmp back7

back10:
  mov si, buffer
  jmp seek

seek:

  mov ah, 01h
  int 21h
  cmp al, byte(13)
  je end_word
  mov [si], al
  inc si
  jmp seek


end_word:
  mov di, buffer
  cmp si, di
  je exit
  mov byte[si], '$'
  jmp bin_search

bin_search:
  mov si, keys
  mov [left], si
  imul dx, [count], 64
  add si, dx
  mov [right], si
  mov si, keys
  sub [right], si
  sub [left], si
  add [left], 64
  add [right], 64
  shr [left], 6
  shr [right], 6
  mov ax, [left]
  back11:
  inc ax
  mov bx, [right]
  cmp ax, [right]
  js back12


  dec ax
  mov si, values
  dec ax
  shl ax, 6
  add si, ax
  jmp print_answer

back12:
  mov bx, [left]
  add bx, [right]
  shr bx, 1
  mov dx, bx
  dec bx
  shl bx, 6
  mov si, keys
  add si, bx
  mov di, buffer
  mov [c], si
  mov bx, [si]
  mov dx, [di]
  push cx
  mov cx, 64
  repe cmpsb
  pop cx
  jg back13

  mov si, keys
  sub [c], si
  add [c], 64
  shr [c], 6

  mov bx, [c]
  mov [left], bx
  mov ax, [left]
  jmp back11


back13:
  mov si, keys
  sub [c], si
  add [c], 64
  shr [c], 6
  mov bx, [c]
  mov [right], bx
  mov ax, [left]
  jmp back11

print_answer:
  mov dl, [si]
  cmp dl, '$'
  je back14
  mov ah, 02h
  int 21h
  inc si
  jmp print_answer

back14:
  mov dl, byte(10)
  mov ah, 02h
  int 21h
  jmp back10

position dw ?
x dw ?
pos_bufer dw 0
count dw 0
count1 dw 0
c dw ?
right dw ?
left dw ?
min dw ?
pos_heap_keys dw ?
pos_heap_values dw ?
pos_keys dw ?
t dw ?
pos_values dw ?
keys: rb 1024
values: rb 1024
heap_keys: db 1024 dup(0)
heap_values: rb 1024
buffer: rb 64