note
    description: "Summary description for {DOMINANTS}."
    author: "Christoph Schwizer"
    date: "$Date$"
    revision: "$Revision$"

class
    DOMINANTS

create
    make_with_values

feature {NONE} -- Initialization

cor: ARRAY[COORDINATE]

    make_with_values(n: INTEGER; a: ARRAY[INTEGER])
            -- Initialization for `Current'.
        require
            coordinate_couples: n \\ 2 = 0
        local
            i: INTEGER
            point: COORDINATE
        do
            create cor.make (0, (n / 2).rounded - 1)
            -- write coordinates into array 'cor'
            from i := 0 until i >= n loop
                create point.make_with_value (a[i], a[i + 1])
                cor[(i/2).rounded] := point
                i := i + 2
            end
            -- sort array according to their x-values
io.put_string ("sorting...%N")
            naturalmergesort (cor, 0, cor.count - 1, false)
io.put_string ("sorting done!%N")
        end

feature {APPLICATION}

    print_to_console
        local
            i: INTEGER
        do
            from i := 0 until i >= cor.count loop
                io.put_string ("(")
                io.put_integer (cor[i].return_x)
                io.put_character (',')
                io.put_integer (cor[i].return_y)
                io.put_string (")")
                io.put_character (' ')
                i := i + 1
            end
            io.new_line
        end

    ans: INTEGER
        local
            count, i, j, cur_x, max_x, old_y, max_y: INTEGER
        do
--print_to_console
            max_x := cor[cor.count - 1].return_x
            from i := cor.count - 1 until i < 0 loop

                -- if coordinate is all to the right, it sure is dominant
                if cor[i].return_x = max_x then
                    count := count + 1
--io.put_string ("taking (") io.put_integer (cor[i].return_x) io.put_string (",") io.put_integer (cor[i].return_y) io.put_string (")%N")
                    if cor[i].return_y > max_y then
                        max_y := cor[i].return_y
                    end

                -- elseif it has a bigger global y-maximum, it sure is dominant
                elseif cor[i].return_y >= max_y then
                    count := count + 1
--io.put_string ("taking (") io.put_integer (cor[i].return_x) io.put_string (",") io.put_integer (cor[i].return_y) io.put_string (")%N")
                    if cor[i].return_x /= cur_x then
                        old_y := max_y
                    end
                    max_y := cor[i].return_y

                -- elseif it has the same x-coordinate as the global y-maximum and is bigger than the previous y-maximum, it is dominant too
                elseif cor[i].return_x = cur_x and then cor[i].return_y >= old_y then
                    count := count + 1
--io.put_string ("taking (") io.put_integer (cor[i].return_x) io.put_string (",") io.put_integer (cor[i].return_y) io.put_string (")%N")

                elseif cor[i].return_x /= cur_x then
                    old_y := max_y
                end
                cur_x := cor[i].return_x
                i := i - 1
            end
            result := count
        end


feature {NONE}
sort_y: BOOLEAN

    naturalmergesort (a: ARRAY[COORDINATE]; l, r: INTEGER; sort_using_y: BOOLEAN)
        local
            ll, mm, rr, i, j: INTEGER
        do
            sort_y := sort_using_y
    --------outer cycle-------------------------------------------------------------
            from j := a.count until j <= 1
            loop
                ll := l
                -- reset counter
                j := 0

    ------------inner cycle--------------------------------------------
                -- let 'll' run
                from ll := l    until ll > r
                loop
                    -- let 'mm' run
                    if sort_y then
                        from mm := ll   until (mm >= r or a[mm].return_y > a[mm + 1].return_y)
                        loop
                            mm := mm + 1
                        end
                    else
                        from mm := ll   until (mm >= r or a[mm].return_x > a[mm + 1].return_x)
                        loop
                            mm := mm + 1
                        end
                    end
                    -- 'mm' now points to the last element of the first subsequence

                    -- after 'mm' is found let 'rr' run
                    -- if 'mm' is not the very last element, set 'rr' to the last element of the second subsequence
                    if mm < r then

                        if sort_y then
                            from rr := mm + 1   until (rr >= r or a[rr].return_y > a[rr + 1].return_y)
                            loop
                                rr := rr + 1
                            end
                        else
                            from rr := mm + 1   until (rr >= r or a[rr].return_x > a[rr + 1].return_x)
                            loop
                                rr := rr + 1
                            end
                        end

                        merge (a, ll, mm, rr)

                        -- test output
                        --  io.put_string ("ll = ") io.put_integer (ll)
                        --  io.put_string ("%Narray after merge: ")
                        --  from i := 1
                        --  until i >= a.count
                        --  loop
                        --      io.put_integer (a[i])
                        --      io.put_character (' ')
                        --      i := i + 1
                        --  end
                        --  io.new_line
                        --  io.new_line


                        -- if 'mm' is the very last element, so is 'rr'
                        else rr := mm
                    end

                    ll := rr + 1
                    -- count inner cycle
                    j := j + 1

                    -- test output 'j'
                    -- io.put_string ("j = ")
                    -- io.put_integer (j)
                    -- io.new_line
                end
    ------------inner cycle end-------------------------------


                ll := rr + 1
            end
    --------outer cycle end----------------------------------------------
        end






    merge (arr: ARRAY[COORDINATE]; left, middle, right: INTEGER)
    -- note: input arguments 'left', 'middle' and 'right' are the indices of the array
    -- 'middle' is the last index of the first subsequence

    local
        copy_arr: ARRAY[COORDINATE]
        h, i, j, k: INTEGER
    do
        create copy_arr.make (0, arr.count - 1)
        from i := left; j := middle + 1; k := left
        until (i > middle or j > right)
        loop
            if sort_y then
                if
                    arr[i].return_y <= arr[j].return_y
                then
                    copy_arr[k] := arr[i]
                    i := i + 1
                else
                    copy_arr[k] := arr[j]
                    j := j + 1
                end
            else
                if
                    arr[i].return_x <= arr[j].return_x
                then
                    copy_arr[k] := arr[i]
                    i := i + 1
                else
                    copy_arr[k] := arr[j]
                    j := j + 1
                end
            end
            k := k + 1

        end

        if i > middle
        then -- first subsequence is done
            from h := j until h > right
            loop
                copy_arr[k + h - j] := arr[h]
                h := h + 1
            end
        else -- second subsequence is done
            from h := i until h > middle
            loop
                copy_arr[k + h - i] := arr[h]
                h := h + 1
            end
        end


    -- test: check copy_arr for correctness
--  io.put_string ("copy_arr: %N")
--  from h := 0
--  until h >= copy_arr.count
--  loop io.put_integer (copy_arr[h])
--  io.put_character (' ')
--  h := h + 1
--  end

        -- copy back from 'copy_arr'
        from h := left  until h > right
        loop
            arr[h] := copy_arr[h]
            h := h + 1
        end
    end



end