/usr/lib/grass70/include/grass/iostream/ami_sort.h is in grass-dev 7.0.3-1build1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 | /****************************************************************************
*
* MODULE: iostream
*
* COPYRIGHT (C) 2007 Laura Toma
*
*
* Iostream is a library that implements streams, external memory
* sorting on streams, and an external memory priority queue on
* streams. These are the fundamental components used in external
* memory algorithms.
* Credits: The library was developed by Laura Toma. The kernel of
* class STREAM is based on the similar class existent in the GPL TPIE
* project developed at Duke University. The sorting and priority
* queue have been developed by Laura Toma based on communications
* with Rajiv Wickremesinghe. The library was developed as part of
* porting Terraflow to GRASS in 2001. PEARL upgrades in 2003 by
* Rajiv Wickremesinghe as part of the Terracost project.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program 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. See the GNU
* General Public License for more details.
* **************************************************************************/
#ifndef _AMI_SORT_H
#define _AMI_SORT_H
#include "ami_sort_impl.h"
#define SORT_DEBUG if(0)
/* ---------------------------------------------------------------------- */
// A version of AMI_sort that takes an input streamof elements of type
// T, creates an output stream and and uses the < operator to sort
// instream is allocated; *outstream is created
// template<class T>
// AMI_err
// AMI_sort(AMI_STREAM<T> *instream, AMI_STREAM<T> **outstream) {
// cout << "Not implemented yet!\n";
// exit(1);
// return AMI_ERROR_NO_ERROR;
// }
/* ---------------------------------------------------------------------- */
// A version of AMI_sort that takes an input stream of elements of
// type T, creates an output stream, and a user-specified comparison
// function
// instream is allocated; *outstream is created
// template<class T>
// AMI_err AMI_sort(AMI_STREAM<T> *instream, AMI_STREAM<T> **outstream,
// int (*cmp)(const T&, const T&)) {
// cout << "Not implemented yet!\n";
// exit(1);
// return AMI_ERROR_NO_ERROR;
// }
/* ---------------------------------------------------------------------- */
// A version of AMI_sort that takes an input stream of elements of
// type T, creates an output stream, and a user-specified comparison
// object.
//The comparison object "cmp", of (user-defined) class represented by
//CMPR, must have a member function called "compare" which is used for
//sorting the input stream.
// create *outstream
template<class T, class Compare>
AMI_err
AMI_sort(AMI_STREAM<T> *instream, AMI_STREAM<T> **outstream, Compare *cmp,
int deleteInputStream = 0)
{
char* name=NULL;
queue<char*>* runList;
off_t instreamLength;
assert(instream && outstream && cmp);
instreamLength = instream->stream_len();
if (instreamLength == 0) {
*outstream = new AMI_STREAM<T>();
if (deleteInputStream) {
delete instream;
}
return AMI_ERROR_NO_ERROR;
}
SORT_DEBUG {
instream->name(&name);
cout << "AMI_sort: sorting stream" << name <<", len="
<< instreamLength << endl;
delete name;
MM_manager.print();
}
//run formation
runList = runFormation(instream, cmp);
assert(runList);
if (deleteInputStream) {
delete instream;
}
if(runList->length() == 0) {
/* self-check */
fprintf(stderr, "ami_sort: Error - no runs created!\n");
instream->name(&name);
cout << "ami_sort: instream = " << name << endl;
exit(1);
/* no input... */
/* *outstream = new AMI_STREAM<T>(); */
} else if(runList->length() == 1) {
//if 1 run only
runList->dequeue(&name);
//printf("SORT: %s\n", name); fflush(stdout);
*outstream = new AMI_STREAM<T>(name);
delete name; //should be safe, stream makes its own copy
} else {
/* many runs */
*outstream = multiMerge<T,Compare>(runList, cmp);
//i thought the templates are not needed in the call, but seems to
//help the compiler..laura
}
assert(runList->length() == 0);
delete runList;
SORT_DEBUG {
cout << "AMI_sort: done" << endl << endl;
MM_manager.print();
}
assert(*outstream);
assert((*outstream)->stream_len() == instreamLength);
return AMI_ERROR_NO_ERROR;
}
template<class T, class Compare>
int
isSorted(AMI_STREAM<T> *str, Compare cmp) {
T *prev, *crt;
AMI_err ae;
assert(str);
str->seek(0);
if (str->stream_len() <2) return 1;
ae = str->read_item(&crt);
cout << "reading: " << *crt << endl;
prev = new T (*crt);
ae = str->read_item(&crt);
while (ae == AMI_ERROR_NO_ERROR) {
cout << "reading: " << *crt << endl;
if (cmp.compare(*prev, *crt) != -1)
assert(0);
return 0;
prev = crt;
ae = str->read_item(&crt);
}
return 1;
}
#endif // _AMI_SORT_H
|