Class DS_BUBBLE

Class DS_BUBBLE_SORTER

note

description:

    "Indexable data structure sorters using bubble sort algorithm"

library:    "Gobo Eiffel Structure Library"
author:     "Eric Bezault <ericb@gobosoft.com>"
copyright:  "Copyright (c) 2000-2001, Eric Bezault and others"
license:    "MIT License"

class interface

DS_BUBBLE_SORTER [G -> COMPARABLE]

inherit

DS_INDEXABLE_SORTER [G]
    DS_SORTER [G]

create

make (a_comparator: like comparator)
        -- Create a new sorter.
        -- (From DS_INDEXABLE_SORTER.)
    require
        a_comparator_not_void: a_comparator /= Void
    ensure
        comparator_set: comparator = a_comparator

feature -- Access

comparator: DS_COMPARATOR [G]
        -- Comparison criterion
        -- (From DS_INDEXABLE_SORTER.)

feature -- Status report

sorted (a_container: DS_INDEXABLE [G]): BOOLEAN
        -- Is a_container sorted in increasing order?
        -- (From DS_SORTER.)
    require
        a_container_not_void: a_container /= Void

reverse_sorted (a_container: DS_INDEXABLE [G]): BOOLEAN
        -- Is a_container sorted in decreasing order?
        -- (From DS_SORTER.)
    require
        a_container_not_void: a_container /= Void

sorted_with_comparator (a_container: DS_INDEXABLE [G]; a_comparator: DS_COMPARATOR [G]): BOOLEAN
        -- Is a_container sorted according to
        -- a_comparator's comparison criterion?
        -- (From DS_SORTER.)
    require
        a_container_not_void: a_container /= Void
        a_comparator_not_void: a_comparator /= Void

subsorted (a_container: DS_INDEXABLE [G]; lower, upper: INTEGER): BOOLEAN
        -- Is a_container sorted in increasing order
        -- within bounds lower..upper?
        -- (From DS_INDEXABLE_SORTER.)
    require
        a_container_not_void: a_container /= Void
        valid_lower: 1 <= lower and lower <= a_container.count
        valid_upper: 1 <= upper and upper <= a_container.count
        valid_bounds: lower <= upper

reverse_subsorted (a_container: DS_INDEXABLE [G]; lower, upper: INTEGER): BOOLEAN
        -- Is a_container sorted in decreasing order
        -- within bounds lower..upper?
        -- (From DS_INDEXABLE_SORTER.)
    require
        a_container_not_void: a_container /= Void
        valid_lower: 1 <= lower and lower <= a_container.count
        valid_upper: 1 <= upper and upper <= a_container.count
        valid_bounds: lower <= upper

subsorted_with_comparator (a_container: DS_INDEXABLE [G]; a_comparator: DS_COMPARATOR [G]; lower, upper: INTEGER): BOOLEAN
        -- Is a_container sorted according to a_comparator's
        -- comparison criterion within bounds lower..upper?
        -- (From DS_INDEXABLE_SORTER.)
    require
        a_container_not_void: a_container /= Void
        a_comparator_not_void: a_comparator /= Void
        valid_lower: 1 <= lower and lower <= a_container.count
        valid_upper: 1 <= upper and upper <= a_container.count
        valid_bounds: lower <= upper

feature -- Sort

sort (a_container: DS_INDEXABLE [G])
        -- Sort a_container in increasing order.
        -- (From DS_SORTER.)
    require
        a_container_not_void: a_container /= Void
    ensure
        sorted: sorted (a_container)

reverse_sort (a_container: DS_INDEXABLE [G])
        -- Sort a_container in decreasing order.
        -- (From DS_SORTER.)
    require
        a_container_not_void: a_container /= Void
    ensure
        sorted: reverse_sorted (a_container)

sort_with_comparator (a_container: DS_INDEXABLE [G]; a_comparator: DS_COMPARATOR [G])
        -- Sort a_container according to
        -- a_comparator's comparison criterion?
        -- (From DS_SORTER.)
    require
        a_container_not_void: a_container /= Void
        a_comparator_not_void: a_comparator /= Void
    ensure
        sorted: sorted_with_comparator (a_container, a_comparator)

subsort (a_container: DS_INDEXABLE [G]; lower, upper: INTEGER)
        -- Sort a_container in increasing order
        -- within bounds lower..upper?
        -- (From DS_INDEXABLE_SORTER.)
    require
        a_container_not_void: a_container /= Void
        valid_lower: 1 <= lower and lower <= a_container.count
        valid_upper: 1 <= upper and upper <= a_container.count
        valid_bounds: lower <= upper
    ensure
        subsorted: subsorted (a_container, lower, upper)

reverse_subsort (a_container: DS_INDEXABLE [G]; lower, upper: INTEGER)
        -- Sort a_container in decreasing order
        -- within bounds lower..upper?
        -- (From DS_INDEXABLE_SORTER.)
    require
        a_container_not_void: a_container /= Void
        valid_lower: 1 <= lower and lower <= a_container.count
        valid_upper: 1 <= upper and upper <= a_container.count
        valid_bounds: lower <= upper
    ensure
        subsorted: reverse_subsorted (a_container, lower, upper)

subsort_with_comparator (a_container: DS_INDEXABLE [G]; a_comparator: DS_COMPARATOR [G]; lower, upper: INTEGER)
        -- Sort a_container according to a_comparator's
        -- comparison criterion within bounds lower..upper?
        -- (From DS_INDEXABLE_SORTER.)
    require
        a_container_not_void: a_container /= Void
        a_comparator_not_void: a_comparator /= Void
        valid_lower: 1 <= lower and lower <= a_container.count
        valid_upper: 1 <= upper and upper <= a_container.count
        valid_bounds: lower <= upper
    deferred
    ensure
        subsorted: subsorted_with_comparator (a_container, a_comparator, lower, upper)

invariant

comparator_not_void: comparator /= Void
    -- (From DS_INDEXABLE_SORTER.)

end -- class DS_BUBBLE_SORTER