HPCToolkit
QuickSort.hpp
Go to the documentation of this file.
1 // -*-Mode: C++;-*-
2 
3 // * BeginRiceCopyright *****************************************************
4 //
5 // $HeadURL$
6 // $Id$
7 //
8 // --------------------------------------------------------------------------
9 // Part of HPCToolkit (hpctoolkit.org)
10 //
11 // Information about sources of support for research and development of
12 // HPCToolkit is at 'hpctoolkit.org' and in 'README.Acknowledgments'.
13 // --------------------------------------------------------------------------
14 //
15 // Copyright ((c)) 2002-2019, Rice University
16 // All rights reserved.
17 //
18 // Redistribution and use in source and binary forms, with or without
19 // modification, are permitted provided that the following conditions are
20 // met:
21 //
22 // * Redistributions of source code must retain the above copyright
23 // notice, this list of conditions and the following disclaimer.
24 //
25 // * Redistributions in binary form must reproduce the above copyright
26 // notice, this list of conditions and the following disclaimer in the
27 // documentation and/or other materials provided with the distribution.
28 //
29 // * Neither the name of Rice University (RICE) nor the names of its
30 // contributors may be used to endorse or promote products derived from
31 // this software without specific prior written permission.
32 //
33 // This software is provided by RICE and contributors "as is" and any
34 // express or implied warranties, including, but not limited to, the
35 // implied warranties of merchantability and fitness for a particular
36 // purpose are disclaimed. In no event shall RICE or contributors be
37 // liable for any direct, indirect, incidental, special, exemplary, or
38 // consequential damages (including, but not limited to, procurement of
39 // substitute goods or services; loss of use, data, or profits; or
40 // business interruption) however caused and on any theory of liability,
41 // whether in contract, strict liability, or tort (including negligence
42 // or otherwise) arising in any way out of the use of this software, even
43 // if advised of the possibility of such damage.
44 //
45 // ******************************************************* EndRiceCopyright *
46 
47 /******************************************************************************
48  * File: QuickSort Class *
49  * Author: Christine Patton *
50  * Date: June, 1993 *
51  * *
52  ***************************** QuickSort Public *******************************
53  * *
54  * Constructor: *
55  * Nothing. *
56  * *
57  * Destructor: *
58  * Nothing. *
59  * *
60  * Create: *
61  * This function must be called after creating the object as it allocates *
62  * space for a pointer to an array of void pointers, initializes the number *
63  * of slots in the array, and initializes a pointer to the comparison funct.*
64  * The comparison function should take two arguments and return a positive *
65  * integer if the first argument is greater, a negative one if the second *
66  * argument is greater. *
67  * *
68  * Destroy: *
69  * deallocates the space for the pointers initialized in Create. *
70  * *
71  * Sort: *
72  * recursivley sorts the section of the array from minEntry to maxEntry. *
73  * *
74  **************************** QuickSort Private *******************************
75  * *
76  * Partition: *
77  * returns the rank of element q int the array (all elements less than *
78  * element q are to the left, all elements greater than element q are *
79  * to the right) *
80  * *
81  * Swap: *
82  * pretty much self-explanatory *
83  * *
84  * ArrayPtr: *
85  * pointer to the array that will be sorted *
86  * *
87  * CompareFunc: *
88  * pointer to the comparison function provided by the user *
89  * *
90  * QuickSortCreated: *
91  * set to true in Create (must have value true before Sort, Partition, *
92  * or Swap can be executed) *
93  * *
94  *****************************************************************************/
95 
96 #ifndef QuickSort_h
97 #define QuickSort_h
98 
99 //************************** System Include Files ***************************
100 
101 //*************************** User Include Files ****************************
102 
103 #include <include/uint.h>
104 
105 /************************ QuickSort function prototypes **********************/
106 
107 typedef int (*EntryCompareFunctPtr)(const void*, const void*);
108 
109 /************************** QuickSort class definition ***********************/
110 
111 class QuickSort
112 {
113  public:
114  QuickSort ();
115  virtual ~QuickSort ();
116 
117  void Create (void** UserArrayPtr, const EntryCompareFunctPtr _CompareFunct);
118  void Destroy ();
119 
120  void Sort (const int minEntryIndex, const int maxEntryIndex);
121 
122  private:
123  void** ArrayPtr;
124  EntryCompareFunctPtr CompareFunct;
125 
126  bool QuickSortCreated;
127 
128  void Swap (int a, int b);
129  int Partition (const int min, const int max, const int q);
130 };
131 
132 #endif
EntryCompareFunctPtr
int(* EntryCompareFunctPtr)(const void *, const void *)
Definition: QuickSort.hpp:107
QuickSort::ArrayPtr
void ** ArrayPtr
Definition: QuickSort.hpp:123
QuickSort::Sort
void Sort(const int minEntryIndex, const int maxEntryIndex)
Definition: QuickSort.cpp:133
QuickSort::~QuickSort
virtual ~QuickSort()
Definition: QuickSort.cpp:71
QuickSort::Destroy
void Destroy()
Definition: QuickSort.cpp:86
QuickSort::QuickSortCreated
bool QuickSortCreated
Definition: QuickSort.hpp:126
QuickSort::Partition
int Partition(const int min, const int max, const int q)
Definition: QuickSort.cpp:106
QuickSort::Swap
void Swap(int a, int b)
Definition: QuickSort.cpp:93
QuickSort::CompareFunct
EntryCompareFunctPtr CompareFunct
Definition: QuickSort.hpp:124
QuickSort::Create
void Create(void **UserArrayPtr, const EntryCompareFunctPtr _CompareFunct)
Definition: QuickSort.cpp:76