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