Class DS_QUICK_SORTER |

    note

>     description:

>         "Indexable data structure sorters using quick 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_QUICK_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.)

    eature -- 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_QUICK_SORTER