← Back to branch summary

~ubuntu-branches/ubuntu/wily/gargoyle-free/wily-proposed

« back to all changes in this revision

Viewing changes to tads/tads3/vmsort.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Sylvain Beucler
  • Date: 2009-09-11 20:09:43 UTC
  • Revision ID: james.westby@ubuntu.com-20090911200943-idgzoyupq6650zpn
Tags: upstream-2009-08-25
Import upstream version 2009-08-25

Show diffs side-by-side

added added

removed removed

Lines of Context:
tads/tads3/vmsort.cpp
 
1
#ifdef RCSID
 
2
static char RCSid[] =
 
3
"$Header$";
 
4
#endif
 
5
 
 
6
/* 
 
7
 *   Copyright (c) 2000, 2002 Michael J. Roberts.  All Rights Reserved.
 
8
 *   
 
9
 *   Please see the accompanying license file, LICENSE.TXT, for information
 
10
 *   on using and copying this software.  
 
11
 */
 
12
/*
 
13
Name
 
14
  vmsort.cpp - T3 VM quicksort implementation
 
15
Function
 
16
  Implements quicksort.  We use our own implementation rather than the
 
17
  standard C library's qsort() routine for two reasons.  First, we might
 
18
  want to throw an exception out of the comparison routine, and it is
 
19
  not clear that it is safe to longjmp() past qsort() on every type of
 
20
  machine and every C run-time implementation.  Second, the standard C
 
21
  library's qsort() routine doesn't provide any means to pass a context
 
22
  to the comparison callback, and further insists that the data to be
 
23
  sorted be arranged as an array; we provide a higher-level abstraction
 
24
  for the comparison callback.
 
25
Notes
 
26
  
 
27
Modified
 
28
  05/14/00 MJRoberts  - Creation
 
29
*/
 
30
 
 
31
#include <stdlib.h>
 
32
#include "t3std.h"
 
33
#include "vmglob.h"
 
34
#include "vmsort.h"
 
35
 
 
36
 
 
37
/* ------------------------------------------------------------------------ */
 
38
/*
 
39
 *   perform a quicksort
 
40
 */
 
41
void CVmQSortData::sort(VMG_ size_t l, size_t r)
 
42
{
 
43
    /* proceed if we have a non-empty range */
 
44
    if (r > l)
 
45
    {
 
46
        size_t i, j;
 
47
        size_t v_idx = r;
 
48
 
 
49
        /* start at the ends of the range */
 
50
        i = l - 1;
 
51
        j = r;
 
52
 
 
53
        /* partition the range */
 
54
        do
 
55
        {
 
56
            /* find the leftmost element >= the right element */
 
57
            do
 
58
            {
 
59
                ++i;
 
60
            } while (i != r && compare(vmg_ i, v_idx) < 0);
 
61
 
 
62
            /* find the rightmost element <= the right element */
 
63
            do
 
64
            {
 
65
                --j;
 
66
            } while (j != l && compare(vmg_ j, v_idx) > 0);
 
67
 
 
68
            /* exchange elements i and j */
 
69
            exchange(vmg_ i, j);
 
70
 
 
71
            /* if we moved the 'v' element, follow that in the index */
 
72
            if (v_idx == i)
 
73
                v_idx = j;
 
74
            else if (v_idx == j)
 
75
                v_idx = i;
 
76
 
 
77
        } while (j > i);
 
78
 
 
79
        /* undo the last exchange */
 
80
        exchange(vmg_ i, j);
 
81
 
 
82
        /* exchange the right value into the pivot point */
 
83
        exchange(vmg_ i, r);
 
84
 
 
85
        /* recursively sort the subranges */
 
86
        if (i > l)
 
87
            sort(vmg_ l, i - 1);
 
88
        if (i < r)
 
89
            sort(vmg_ i + 1, r);
 
90
    }
 
91
}
 
92