quick sort.a68

# -*- coding: utf-8 -*- #

PR include "types/item.a68" PR;

PROC bigger = (ITEM a, b) BOOL: (
	DATE
		a date = get item date(a),
		b date = get item date(b);

	REF TIME
		a time = get item time(a),
		b time = get item time(b);

	BOOL
		a all day = a time :=: REF TIME(NIL),
		b all day = b time :=: REF TIME(NIL);

		IF a all day THEN TRUE # a #
	ELIF b all day THEN FALSE # b #
	ELSE
		INT
			a hours   := hours   OF a time,
			b hours   := hours   OF b time,
			a minutes := minutes OF a time,
			b minutes := minutes OF b time;

		a hours := (a hours = 0 | 24 | a hours);
		b hours := (b hours = 0 | 24 | b hours);

		IF a hours = b hours THEN
			IF a minutes < b minutes THEN TRUE # a #
			ELSE FALSE # b #
			FI
		ELIF a hours < b hours THEN TRUE # a #
		ELSE FALSE # b #
		FI
	FI
);

PROC swap = (REF [] ITEM arr, INT i, j) VOID: (
	ITEM temp = arr[i];
	arr[i] := arr[j];
	arr[j] := temp
);

PROC partition = (REF [] ITEM arr, INT low, high) INT: (
	ITEM pivot = arr[high];
	INT i := low - 1;

	FOR j FROM low TO high - 1 DO
		IF bigger(arr[j], pivot) THEN
			i +:= 1;
			swap(arr, i, j)
		FI
	OD;

  swap(arr, i + 1, high);
  i + 1
);

PROC quick sort = (REF [] ITEM arr, INT low, high) VOID:
	IF low < high THEN
		INT pi = partition(arr, low, high);

		quick sort(arr, low, pi - 1);
		quick sort(arr, pi + 1, high)
	FI