; _______________________________________________________________________________________
;|                                                                                       |
;| ..::FreshLib::..  Free, open source. Licensed under "BSD 2-clause" license."          |
;|_______________________________________________________________________________________|
;
;  Description: TGrid object class
;
;  Target OS: Any
;
;  Dependencies:
;  Notes:
;_________________________________________________________________________________________
module "Rectangles library"


; Calculates the bounding rectangle of two source rectangles, pointed by [.src1] and [.src2]
; The result rectangle is placed in RECT structure pointed by [.dest]
;
; All three rectangles may point to the same structures.
;
; Procedure preserves all registers.

proc RectBounding, .dest, .src1, .src2
begin
        pushad


        mov     esi, [.src1]
        mov     edi, [.src2]
        mov     ebx, [.dest]

; min left1, left2

        mov     eax, [esi+RECT.left]
        mov     edx, [edi+RECT.left]

        sub     edx, eax
        sbb     ecx, ecx
        and     ecx, edx
        add     eax, ecx

        mov     [ebx+RECT.left], eax


; min top1, top2

        mov     eax, [esi+RECT.top]
        mov     edx, [edi+RECT.top]

        sub     edx, eax
        sbb     ecx, ecx
        and     ecx, edx
        add     eax, ecx

        mov     [ebx+RECT.top], eax


; max right1, right2

        mov     eax, [esi+RECT.right]
        mov     edx, [edi+RECT.right]

        sub     edx, eax
        sbb     ecx, ecx
        not     ecx
        and     ecx, edx
        add     eax, ecx

        mov     [ebx+RECT.right], eax


; max bottom1, bottom2

        mov     eax, [esi+RECT.bottom]
        mov     edx, [edi+RECT.bottom]

        sub     edx, eax
        sbb     ecx, ecx
        not     ecx
        and     ecx, edx
        add     eax, ecx

        mov     [ebx+RECT.bottom], eax

        popad
        return
endp



; Calculates the intersection of two source rectangles, pointed by [.src1] and [.src2]
; The result rectangle is placed in RECT structure pointed by [.dest]
; All three rectangles may point to the same structures.
;
; Returns CF=0 if rectangles intersect and CF=1 if not.
; If the rectangles does not intersect, the [.dest] rectangle will contain all fields = 0
;
; Procedure preserves all registers.

proc RectIntersect, .dest, .src1, .src2
begin
        pushad

        mov     esi, [.src1]
        mov     edi, [.src2]
        mov     ebx, [.dest]

; max left1, left2
        mov     ecx, [esi+RECT.left]
        mov     eax, [edi+RECT.left]
        cmp     ecx, eax
        cmovl   ecx, eax
        mov     [ebx+RECT.left], ecx

; min right1, right2
        mov     edx, [esi+RECT.right]
        mov     eax, [edi+RECT.right]
        cmp     edx, eax
        cmovg   edx, eax
        mov     [ebx+RECT.right], edx

        cmp     ecx, edx
        jge     .null

; max top1, top2
        mov     ecx, [esi+RECT.top]
        mov     eax, [edi+RECT.top]
        cmp     ecx, eax
        cmovl   ecx, eax
        mov     [ebx+RECT.top], ecx

; min bottom1, bottom2
        mov     edx, [esi+RECT.bottom]
        mov     eax, [edi+RECT.bottom]
        cmp     edx, eax
        cmovg   edx, eax
        mov     [ebx+RECT.bottom], edx

        cmp     ecx, edx
        jge     .null

        clc
        popad
        return

.null:
        xor     eax, eax
        mov     [ebx+RECT.left], eax
        mov     [ebx+RECT.top], eax
        mov     [ebx+RECT.right], eax
        mov     [ebx+RECT.bottom], eax
        stc
        popad
        return
endp




proc RectCopy, .dest, .src
begin
        pushad

        mov     esi, [.src]
        mov     edi, [.dest]

        mov     eax, [esi+RECT.left]
        mov     ecx, [esi+RECT.top]
        mov     edx, [esi+RECT.right]
        mov     ebx, [esi+RECT.bottom]

        mov     [edi+RECT.left], eax
        mov     [edi+RECT.top], ecx
        mov     [edi+RECT.right], edx
        mov     [edi+RECT.bottom], ebx

        popad
        return
endp



proc RectSort, .src
begin
        push    eax ecx esi

        mov     esi, [.src]

        mov     eax, [esi+RECT.left]
        mov     ecx, [esi+RECT.right]
        cmp     ecx, eax
        jge     @f
        mov     [esi+RECT.right], eax
        mov     [esi+RECT.left],ecx
@@:
        mov     eax, [esi+RECT.top]
        mov     ecx, [esi+RECT.bottom]
        cmp     ecx, eax
        jg      @f
        mov     [esi+RECT.top],ecx
        mov     [esi+RECT.bottom], eax
@@:
        pop     esi ecx eax
        return
endp



proc PointInRect, .pRect, .x, .y
begin
        push    eax esi

        mov     esi, [.pRect]
        mov     eax, [.x]

        cmp     eax, [esi+RECT.left]
        jl      .no
        cmp     eax, [esi+RECT.right]
        jge     .no

        mov     eax, [.y]
        cmp     eax, [esi+RECT.top]
        jl      .no
        cmp     eax, [esi+RECT.bottom]
        jge     .no

        stc
        pop     esi eax
        return

.no:
        clc
        pop     esi eax
        return
endp


; converts RECT to TBounds structure.

proc RectToBounds, .ptrBounds, .ptrRect
begin
        pushad

        mov     esi, [.ptrRect]
        mov     edi, [.ptrBounds]

        mov     ebx, [esi+RECT.left]
        mov     edx, [esi+RECT.top]
        mov     eax, [esi+RECT.right]
        mov     ecx, [esi+RECT.bottom]

        sub     eax, ebx
        sub     ecx, edx

        mov     [edi+TBounds.x], ebx
        mov     [edi+TBounds.y], edx
        mov     [edi+TBounds.width], eax
        mov     [edi+TBounds.height], ecx

        popad
        return
endp



;
; Adds new rect to the rectangles list (region).
; Only non intersecting part of the rectangle is added and the resulting
; set of rectangles is always optimal.
;
; As a result some previously added rectangles can be changed or removed.
; The total count of rectangles after this operation can be any.
;
; All rectangles in the array are sorted - i.e. defined by their top/left
; and bottom/right corner, even if [.pRect] contains not sorted rectangle.
;
; Arguments:
;   .pList - pointer to TArray of RECT.
;   .pRect - pointer to RECT to be added to the array.
;
; Returns:
;   edx - pointer to the resulting TArray. Can be the same or reallocated [.pList], depending on the operations.
;

proc RectListAdd, .pList, .pRect
.end   dd ?
.sRect RECT

begin
        pushad

        lea     eax, [.sRect]
        stdcall RectCopy, eax, [.pRect]
        stdcall RectSort, eax

        push    0       ; end of queued commands.

        xor     ecx, ecx                ; from where to start.

.main_loop:
        mov     esi, [.pList]

        mov     edx, [esi+TArray.count]

        shl     ecx, 4
        shl     edx, 4

        lea     edx, [esi+TArray.array+edx]     ; the end of the array.
        lea     esi, [esi+TArray.array+ecx]     ; the start element.

        mov     [.end], edx

.loop:
        cmp     esi, [.end]
        jae     .end_loop


.again:
        mov     eax, [.sRect.right]
        mov     ecx, [.sRect.bottom]

        cmp     eax, [.sRect.left]
        je      .rect_added             ; empty rectangle.
        cmp     ecx, [.sRect.top]
        je      .rect_added             ; empty rectangle.

        dec     eax
        dec     ecx

        stdcall PointToRect, eax, ecx, esi
        lea     ecx, [9*eax]

        stdcall PointToRect, [.sRect.left], [.sRect.top], esi
        add     ecx, eax

        movzx   eax, byte [.cases+ecx]          ; what case for this rectangle?

        test    eax, eax
        jnz     .process_it

        stdcall RectSort, esi
        jmp     .again


.process_it:
        cmp     eax, 1
        je      .rect_added                     ; the rectangle is entirely inside the target rectangle. No need to be added.

        cmp     eax, 2
        je      .try_to_join

        cmp     eax, 6
        jbe     .case_3456

        cmp     eax, 7
        je      .case_7                         ; remove the old rectangle.

        cmp     eax, 11
        jbe     .case_89ab                      ; clip the new rectangle.

        cmp     eax, 15
        jbe     .case_cdef                      ; split the new rectangle on two rectangles.


; case_gh:  ;Split the new rectangle on two rectangles another way

        sub     eax, 16         ; dest index.

        lea     ecx, [eax+2]    ; src index
        and     ecx, 3

        pushd   [.sRect.bottom] [.sRect.right] [.sRect.top] [.sRect.left]   ; the remaning rectangle.

        mov     edx, [esi+4*ecx]
        mov     [esp+4*eax], edx        ; fix remaining rectangle.

        mov     edx, [esi+4*eax]
        mov     [.sRect + 4*ecx], edx

        lea     eax, [esi-TArray.array]
        sub     eax, [.pList]
        sar     eax, 4
        inc     eax

        push    eax     ; from where to start.
        push    2       ; add rect command.

        jmp     .try_to_join


.case_3456:     ; clip the target rectangle.

        sub     eax, 3  ; offset in target rect.

        mov     edx, [.sRect+4*eax]        ; (X0,Y0,X1,Y1)

        lea     eax, [eax+2]
        and     eax, 3

        mov     [esi+4*eax], edx        ; (A0,B0,A1,B1)

        jmp     .try_to_join


.case_7:        ; the target rectanlge should be removed from the list. The comparison continues with the next rect in the list.

        lea     eax, [esi-TArray.array]
        sub     eax, [.pList]
        sar     eax, 4                          ; sizeof.RECT = 16

        push    eax     ; the index of the rectangle that have to be deleted.
        push    1       ; delete command.
        jmp     .next_rect


.case_89ab:    ; clip the inserted rectangle and continue to the next target rectangle

        sub     eax, 8  ; offset in target rect.

        mov     edx, [esi+4*eax]

        lea     eax, [eax+2]
        and     eax, 3

        mov     [.sRect+4*eax], edx

        jmp     .try_to_join


.case_cdef:     ; split the new rectangle on two rectangles.

        sub     eax, 12         ; src index

        lea     ecx, [eax+2]    ; dest index
        and     ecx, 3

        pushd   [.sRect.bottom] [.sRect.right] [.sRect.top] [.sRect.left]   ; the remaning rectangle.

        mov     edx, [esi+4*eax]
        mov     [esp+4*eax], edx        ; fix remaining first value.
        mov     [.sRect + 4*ecx], edx   ; fix current rectangle

        inc     eax
        and     eax, 3
        lea     ecx, [eax+2]
        and     ecx, 3

        mov     edx, [esi+4*eax]
        mov     [esp+4*ecx], edx        ; fix remaining second value.

        lea     eax, [esi-TArray.array]
        sub     eax, [.pList]
        sar     eax, 4
        inc     eax

        push    eax     ; from where to start.
        push    2       ; add rect command.

        jmp     .next_rect


; try to join the rectangle to the current rectangle

.try_to_join:   ; can be optimized for SIZE!!!

        mov     eax, [.sRect.right]
        mov     ecx, [.sRect.bottom]
        dec     eax
        dec     ecx

        stdcall PointToRect, eax, ecx, esi
        mov     ecx, eax

        stdcall PointToRect, [.sRect.left], [.sRect.top], esi

        cmp     ecx, eax
        jne     .next_rect

        shr     ecx, 1
        jnc     .next_rect     ; only odd numbers can be joined.

        jz      .jcase_0

        dec     ecx

        jz      .jcase_1

        dec     ecx

        jz      .jcase_2

; join case 3

        mov     eax, [.sRect.left]
        mov     ecx, [.sRect.right]
        mov     edx, [.sRect.top]

        cmp     eax, [esi+RECT.left]
        jne     .next_rect

        cmp     ecx, [esi+RECT.right]
        jne     .next_rect

        cmp     edx, [esi+RECT.bottom]
        jne     .next_rect

        push    [esi+RECT.top]
        pop     [.sRect.top]

        jmp     .del_the_current


.jcase_2:
        mov     eax, [.sRect.top]
        mov     ecx, [.sRect.bottom]
        mov     edx, [.sRect.left]

        cmp     eax, [esi+RECT.top]
        jne     .next_rect

        cmp     ecx, [esi+RECT.bottom]
        jne     .next_rect

        cmp     edx, [esi+RECT.right]
        jne     .next_rect

        push    [esi+RECT.left]
        pop     [.sRect.left]

        jmp     .del_the_current


.jcase_1:
        mov     eax, [.sRect.top]
        mov     ecx, [.sRect.bottom]
        mov     edx, [.sRect.right]

        cmp     eax, [esi+RECT.top]
        jne     .next_rect

        cmp     ecx, [esi+RECT.bottom]
        jne     .next_rect

        cmp     edx, [esi+RECT.left]
        jne     .next_rect

        push    [esi+RECT.right]
        pop     [.sRect.right]

        jmp     .del_the_current


.jcase_0:
        mov     eax, [.sRect.left]
        mov     ecx, [.sRect.right]
        mov     edx, [.sRect.bottom]

        cmp     eax, [esi+RECT.left]
        jne     .next_rect

        cmp     ecx, [esi+RECT.right]
        jne     .next_rect

        cmp     edx, [esi+RECT.top]
        jne     .next_rect

        push    [esi+RECT.bottom]
        pop     [.sRect.bottom]


.del_the_current:
; queue the current rect for deleting.

        lea     eax, [esi-TArray.array]
        sub     eax, [.pList]
        sar     eax, 4                          ; sizeof.RECT = 16

        push    eax     ; the index of the rectangle that have to be deleted.
        push    1       ; delete command.

.next_rect:
        add     esi, sizeof.RECT
        jmp     .loop


.end_loop:

; here add the rectangle

        stdcall AddArrayItems, [.pList], 1
        mov     [.pList], edx

; add the new rectangle to the list.
        pushd   [.sRect.bottom] [.sRect.right] [.sRect.top] [.sRect.left]
        popd    [eax+RECT.left] [eax+RECT.top] [eax+RECT.right] [eax+RECT.bottom]

.rect_added:

        pop     eax     ; pop the command

        test    eax, eax
        jz      .finish_ok

        cmp     eax, 1
        je      .delete_element

        pop     ecx  ; from index?
        popd    [.sRect+RECT.left] [.sRect+RECT.top] [.sRect+RECT.right] [.sRect+RECT.bottom]

        jmp     .main_loop


.delete_element:

        pop     eax     ; the index of the element that have to be removed.
        stdcall DeleteArrayItems, [.pList], eax, 1
        mov     [.pList], edx
        jmp     .rect_added

.finish_ok:
        popad
        mov     edx, [.pList]

;        OutputValue "Rectangles list count:", [edx+TArray.count], 10, -1

        return

.cases db  2,  0, 0,  0,  0, 0, 0, 0, 0
       db  2,  2, 0,  0,  0, 0, 0, 0, 0
       db  2,  2, 2,  0,  0, 0, 0, 0, 0
       db  2,  0, 0,  2,  0, 0, 0, 0, 0
       db 12,  9, 0,  8,  1, 0, 0, 0, 0
       db  6, 13, 2, 16, 10, 2, 0, 0, 0
       db  2,  0, 0,  2,  0, 0, 2, 0, 0
       db  5, 17, 0, 15, 11, 0, 2, 2, 0
       db  7,  3, 2,  4, 14, 2, 2, 2, 2
endp


; Computes where [.pPoint] is located relative to [.pRect]
; and returns one of the following values: (4 is the rectangle itself)
;
;   +---+---+---+
;   | 0 | 1 | 2 |
;   +---+---+---+
;   | 3 | 4 | 5 |
;   +---+---+---+
;   | 6 | 7 | 8 |
;   +---+---+---+


proc PointToRect, .x, .y, .pRect
begin
        pushad

        mov     edi, [.pRect]

        xor     ecx, ecx

        mov     eax, [.x]
        mov     edx, [.y]

        cmp     eax, [edi+RECT.left]
        jl      .x_ok

        inc     ecx

        cmp     eax, [edi+RECT.right]
        jl      .x_ok

        inc     ecx

.x_ok:
        cmp     edx, [edi+RECT.top]
        jl      .y_ok

        add     ecx, 3

        cmp     edx, [edi+RECT.bottom]
        jl      .y_ok

        add     ecx, 3

.y_ok:
        mov     [esp+4*regEAX], ecx
        popad
        return
endp




endmodule
