lab10.asm

; Denys Mosiuk, IO-92
; KPI 2011

assume cs:code, ds:data

.386

dtable struc
    key db  0
    field   db  0
dtable ends

stck segment stack use16
    db  12 dup(?)
stck ends

data segment use16
    var_msg db  "Denys Mosiuk, IO-92, 16", '$'
    nfnd_msg db "Element not found", "$"

    table_space dw  7 dup(?)
    tbl dtable <4,'R'>
        dtable <6,'E'>
        dtable <3,'K'>
        dtable <7,'D'>
        dtable <5,'T'>
        dtable <2,'O'>
        dtable <1,'S'>
    etbl db '$'
    tels equ type dtable
    tbl_size equ (etbl - tbl) / tels
data ends

code segment use16

beg:
    mov ax, data        ; Init data segment
    mov ds, ax

    mov ah, 2           ; === Print variant message
    lea dx, var_msg
    int 21h

                        ; === Shaker's sort
    lea si, tbl
    mov bh, 0
    mov bl, tbl_size+1
    xor dx, dx

l_step:
    xor ch, ch
    mov cl, bl
    sub cl, bh
    sub cl, 1
    cmp cx, 1
    jl l_end

    bt dx, 1
    jnc l_right
    jc l_left

l_right:
    mov dl, 2
l_r_step:
        mov ah, [si].key
        cmp ah, [si+tels].key
        jng l_r_cont
            xchg ah, [si+tels].key
            mov [si].key, ah
            mov ah, [si].field
            xchg ah, [si+tels].field
            mov [si].field, ah
            or dx, 1
l_r_cont:
        add si, tels
    loop l_r_step
    bt dx, 1
    jz l_end

    dec bl
    sub si, tels
    jmp l_step

l_left:
    xor dl, dl
l_l_step:
        mov ah, [si].key
        cmp [si-tels].key, ah
        jng l_l_cont
            xchg ah, [si-tels].key
            mov [si].key, ah
            mov ah, [si].field
            xchg ah, [si-tels].field
            mov [si].field, ah
            or dx, 1
l_l_cont:
        sub si, tels
    loop l_l_step
    bt dx, 1
    jz l_end
    
    inc bh
    add si, tels
    jmp l_step
l_end:

    int 3

    sch_val equ 3           ; === Strait search
    mov cx, tbl_size

    lea si, tbl
sch_loop:
        cmp [si].key, sch_val
        je s_found
        add si, tels 
    loop sch_loop

    mov ah, 2
    lea dx, nfnd_msg
    int 21h
    jmp s_cont

s_found:
    mov ah, [si].field

s_cont:
    int 3

    mov bh, 0               ; === Dihotomy search
    mov bl, tbl_size-1
    mov ch, 2
    mov cl, tels

d_search:
    mov al, bl              ; Count new borders
    sub al, bh
    cbw
    div ch

    add al, ah
    mul cl                  ; Count new element adress
    lea dx, tbl
    add dx, ax
    mov si, dx

    cmp [si].key, sch_val
    je d_found
    jg d_dec
    jl d_inc

d_dec:
    cbw
    div cl
    mov bl, al
    jmp d_search

d_inc:
    mov bh, al
    jmp d_search

d_found:
    mov ah, [si].field

    int 3

    mov ax, 4c00h           ; === Exit to DOS
    int 21h

code ends

end beg