-- This file is free software, which comes along with SmartEiffel. This
-- software is distributed in the hope that it will be useful, but WITHOUT
-- ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
-- FITNESS FOR A PARTICULAR PURPOSE. You can modify it as you want, provided
-- this header is kept unaltered, and a notification of the changes is added.
-- You are allowed to redistribute it and sell it, alone or as a part of
-- another product.
-- Copyright (C) 1994-2002 LORIA - INRIA - U.H.P. Nancy 1 - FRANCE
-- Dominique COLNET and Suzanne COLLIN - SmartEiffel@loria.fr
-- http://SmartEiffel.loria.fr
--
expanded class COLLECTION_SORTER[X -> COMPARABLE]
--
-- Some algorithms to sort any COLLECTION[COMPARABLE].
--
-- Elements are sorted using increasing order: small elements
-- at the begining of the collection, large at the end (decreasing
-- order is implemented by class REVERSE_COLLECTION_SORTER).
--
--
-- How to use this expanded class :
--
-- local
-- sorter: COLLECTION_SORTER[INTEGER]
-- array: ARRAY[INTEGER]
-- do
-- array := <<1,3,2>>
-- sorter.sort(array)
-- check
-- sorter.is_sorted(array)
-- end
-- ...
--
feature
is_sorted(c: COLLECTION[X]): BOOLEAN is
-- Is `c' already sorted ?
-- Uses infix "<=" for comparison.
require
c /= Void
local
i, c_upper: INTEGER
elt1, elt2: X
do
i := c.lower
c_upper := c.upper
Result := True
if c_upper > i then
from
elt1 := c.item(i)
invariant
c.valid_index(i)
until
not Result or else i >= c_upper
loop
i := i + 1
elt2 := c.item(i)
Result := elt1 <= elt2
elt1 := elt2
end
end
ensure
c.is_equal(old c.twin)
end
has(c: COLLECTION[X]; element: X): BOOLEAN is
require
c /= Void
is_sorted(c)
local
idx: INTEGER
do
idx := index_of(c, element)
Result := c.valid_index(idx) and then c.item(idx).is_equal(element)
ensure
Result = c.has(element)
end
index_of(c: COLLECTION[X]; element: X): INTEGER is
require
c /= Void
is_sorted(c)
local
min, max: INTEGER; stop: BOOLEAN
do
if c.is_empty then
Result := c.lower
else
from
min := c.lower
max := c.upper
variant
max - min
until
stop
loop
if min = max then
stop := True
if c.item(min) < element then
Result := min + 1
else
Result := min
end
else
check min < max end
Result := (min + max) // 2
if c.item(Result) < element then
min := Result + 1
else
max := Result
end
end
end
end
ensure
c.has(element) implies c.item(Result).is_equal(element)
end
add(c: COLLECTION[X]; element: X) is
-- Add `element' in collection `c' keeping the sorted property.
require
c /= Void
is_sorted(c)
do
c.add(element, index_of(c, element))
ensure
c.count = old c.count + 1
is_sorted(c)
end
sort(c: COLLECTION[X]) is
-- Sort `c' using the default most efficient sorting algorithm
-- already implemented.
require
c /= Void
do
if not is_sorted(c) then
quick_sort(c)
end
ensure
c.count = old c.count
is_sorted(c)
end
quick_sort(c: COLLECTION[X]) is
-- Sort `c' using the quick sort algorithm.
require
c /= Void
do
quick_sort_region(c,c.lower,c.upper)
ensure
c.count = old c.count
is_sorted(c)
end
von_neuman_sort(c: COLLECTION[X]) is
-- Sort `c' using the Von Neuman algorithm.
-- This algorithm needs to create a second collection.
-- Uses infix "<=" for comparison.
require
c /= Void
local
src, dest, tmp: COLLECTION[X]
nb, count, d_count, c_count, lower, imax: INTEGER
do
c_count := c.count
if c_count > 1 then
lower := c.lower
imax := c.upper + 1
from
count := 1
until
count >= c_count
loop
count := count * 2
nb := nb + 1
end
if nb.odd then
src := c
dest := c.twin
else
dest := c
src := c.twin
end
from
count := 1
variant
c_count * 2 - count
until
count >= c_count
loop
d_count := count * 2
tmp := dest
dest := src
src := tmp
von_neuman_line(src,dest,count,d_count,lower,imax)
count := d_count
end
end
ensure
c.count = old c.count
is_sorted(c)
end
heap_sort(c: COLLECTION[X]) is
-- Sort `c' using the heap sort algorithm.
require
c /= Void
local
i, c_lower, c_upper: INTEGER
do
c_lower := c.lower
c_upper := c.upper
if c_upper > c_lower then
from
-- Build the very first heap first :
from
i := c_lower + c.count // 2 + 1
until
i < c_lower
loop
heap_repair(c,c_lower,i,c_upper)
i := i - 1
end
--
i := c_upper
until
i < c_lower + 1
loop
c.swap(c_lower,i)
heap_repair(c,c_lower,c_lower,i - 1)
i := i - 1
end
end
ensure
c.count = old c.count
is_sorted(c)
end
bubble_sort(c: COLLECTION[X]) is
-- Sort `c' using the bubble sort algorithm.
-- Uses infix "<" for comparison.
require
c /= Void
local
i, imax, imin: INTEGER
modified: BOOLEAN
do
from
imax := c.upper
imin := c.lower
modified := True
until
not modified or else imin >= imax
loop
from
modified := false
i := imax
imin := imin + 1
until
i < imin
loop
if c.item(i) < c.item(i - 1) then
c.swap(i ,i - 1)
modified := True
end
i := i - 1
end
if modified then
from
modified := false
i := imin
imax := imax - 1
until
i > imax
loop
if c.item(i + 1) < c.item(i) then
c.swap(i ,i + 1)
modified := True
end
i := i + 1
end
end
end
ensure
c.count = old c.count
is_sorted(c)
end
feature {NONE}
von_neuman_line(src, dest: COLLECTION[X]; count, d_count, lower, imax: INTEGER) is
require
src /= dest
src.lower = dest.lower
src.upper = dest.upper
count >= 1
d_count = count * 2
lower = src.lower
imax = src.upper + 1
local
sg1: INTEGER
do
from
sg1 := lower
until
sg1 >= imax
loop
von_neuman_inner_sort(src,dest,sg1,count,imax)
sg1 := sg1 + d_count
end
ensure
d_count >= dest.count implies is_sorted(dest)
end
von_neuman_inner_sort(src, dest: COLLECTION[X]; sg1, count, imax: INTEGER) is
require
src.valid_index(sg1)
local
i1, i2, i, i1max, i2max: INTEGER
do
from
i1 := sg1
i2 := sg1 + count
i1max := i2.min(imax)
i2max := (i2 + count).min(imax)
i := i1
until
i1 >= i1max or else i2 >= i2max
loop
if src.item(i1) <= src.item(i2) then
dest.put(src.item(i1),i)
i1 := i1 + 1
else
dest.put(src.item(i2),i)
i2 := i2 + 1
end
i := i + 1
end
if i1 >= i1max then
from until i2 >= i2max
loop
dest.put(src.item(i2),i)
i2 := i2 + 1; i := i + 1
end
else
from until i1 >= i1max
loop
dest.put(src.item(i1),i)
i1 := i1 + 1; i := i + 1
end
end
end
heap_repair(c: COLLECTION[X]; c_lower, first, last: INTEGER) is
-- Repair the heap from the node number `first'
-- It considers that the last item of c is number `last'
-- It supposes that children are heaps.
require
c /= Void
c.lower = c_lower
c_lower <= first
last <= c.upper
local
left_idx, right_idx: INTEGER
do
left_idx := 1 - c_lower + 2 * first
if left_idx <= last then -- not a leaf :
right_idx := 2 - c_lower + 2 * first
if left_idx = last then
if c.item(first) < c.item(left_idx) then
c.swap(first,left_idx)
end
elseif c.item(first) > c.item(left_idx) then
if c.item(first) < c.item(right_idx) then
c.swap(first,right_idx)
heap_repair(c,c_lower,right_idx,last)
end
elseif c.item(left_idx) > c.item(right_idx) then
c.swap(first,left_idx)
heap_repair(c,c_lower,left_idx,last)
else
c.swap(first,right_idx)
heap_repair(c,c_lower,right_idx,last)
end
end
end
quick_sort_region(c: COLLECTION[X]; left, right:INTEGER) is
local
middle: INTEGER; i: INTEGER
do
if left < right then
i := left + (right - left) // 2 + 1
c.swap(left,i)
middle := left
from
i := left +1
until
i > right
loop
if c.item(i) < c.item(left) then
middle := middle + 1
c.swap(middle,i)
end
i := i + 1
end
c.swap(left,middle)
quick_sort_region(c , left , middle - 1)
quick_sort_region(c , middle + 1 , right)
end
end
end -- COLLECTION_SORTER