Eiffel Media API
Overview Cluster Class Classes Index      Previous Next      Top Features

structure.sort

Class DS_QUICK_SORTER


Direct ancestors

DS_INDEXABLE_SORTER

Creation

Features

Invariants

indexing

description

Indexable data structure sorters using quick sort algorithm

library

Gobo Eiffel Structure Library

copyright

Copyright (c) 2000, Eric Bezault and others

license

Eiffel Forum License v2 (see forum.txt)

date

$Date: 2005/07/13 17:52:52 $

revision

$Revision: 1.17 $

class

DS_QUICK_SORTER [G]

inherit

DS_INDEXABLE_SORTER

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: KL_PART_COMPARATOR [G]

-- Comparison criterion

-- (From DS_INDEXABLE_SORTER)

feature -- Status report

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
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
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
sorted_with_comparator (a_container: DS_INDEXABLE [G]; a_comparator: KL_PART_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
subsorted_with_comparator (a_container: DS_INDEXABLE [G]; a_comparator: KL_PART_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

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)
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)
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)
sort_with_comparator (a_container: DS_INDEXABLE [G]; a_comparator: KL_PART_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)
subsort_with_comparator (a_container: DS_INDEXABLE [G]; a_comparator: KL_PART_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
ensure
subsorted: subsorted_with_comparator (a_container, a_comparator, lower, upper)

invariant

comparator_not_void: comparator /= Void

-- From ANY
reflexive_equality: standard_is_equal (Current)
reflexive_conformance: conforms_to (Current)

end