GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
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 
37 #ifndef _AMI_SORT_H
38 #define _AMI_SORT_H
39 
40 #include "ami_sort_impl.h"
41 
42 #define SORT_DEBUG if(0)
43 
44 
45 /* ---------------------------------------------------------------------- */
46 
47 // A version of AMI_sort that takes an input streamof elements of type
48 // T, creates an output stream and and uses the < operator to sort
49 
50 // instream is allocated; *outstream is created
51 // template<class T>
52 // AMI_err
53 // AMI_sort(AMI_STREAM<T> *instream, AMI_STREAM<T> **outstream) {
54 
55 // cout << "Not implemented yet!\n";
56 // exit(1);
57 // return AMI_ERROR_NO_ERROR;
58 // }
59 
60 
61 
62 /* ---------------------------------------------------------------------- */
63 
64 // A version of AMI_sort that takes an input stream of elements of
65 // type T, creates an output stream, and a user-specified comparison
66 // function
67 
68 // instream is allocated; *outstream is created
69 // template<class T>
70 // AMI_err AMI_sort(AMI_STREAM<T> *instream, AMI_STREAM<T> **outstream,
71 // int (*cmp)(const T&, const T&)) {
72 
73 // cout << "Not implemented yet!\n";
74 // exit(1);
75 // return AMI_ERROR_NO_ERROR;
76 // }
77 
78 
79 
80 /* ---------------------------------------------------------------------- */
81 // A version of AMI_sort that takes an input stream of elements of
82 // type T, creates an output stream, and a user-specified comparison
83 // object.
84 
85 //The comparison object "cmp", of (user-defined) class represented by
86 //CMPR, must have a member function called "compare" which is used for
87 //sorting the input stream.
88 
89 
90 
91 
92 // create *outstream
93 template<class T, class Compare>
94 AMI_err
95 AMI_sort(AMI_STREAM<T> *instream, AMI_STREAM<T> **outstream, Compare *cmp,
96  int deleteInputStream = 0)
97 {
98  char* name=NULL;
99  queue<char*>* runList;
100  off_t instreamLength;
101 
102  assert(instream && outstream && cmp);
103  instreamLength = instream->stream_len();
104 
105  if (instreamLength == 0) {
106  *outstream = new AMI_STREAM<T>();
107  if (deleteInputStream) {
108  delete instream;
109  }
110  return AMI_ERROR_NO_ERROR;
111  }
112 
113  SORT_DEBUG {
114  instream->name(&name);
115  cout << "AMI_sort: sorting stream" << name <<", len="
116  << instreamLength << endl;
117  delete name;
118  MM_manager.print();
119  }
120 
121  //run formation
122  runList = runFormation(instream, cmp);
123  assert(runList);
124 
125  if (deleteInputStream) {
126  delete instream;
127  }
128 
129  if(runList->length() == 0) {
130  /* self-check */
131  fprintf(stderr, "ami_sort: Error - no runs created!\n");
132  instream->name(&name);
133  cout << "ami_sort: instream = " << name << endl;
134  exit(1);
135  /* no input... */
136  /* *outstream = new AMI_STREAM<T>(); */
137 
138  } else if(runList->length() == 1) {
139  //if 1 run only
140  runList->dequeue(&name);
141  //printf("SORT: %s\n", name); fflush(stdout);
142  *outstream = new AMI_STREAM<T>(name);
143  delete name; //should be safe, stream makes its own copy
144 
145  } else {
146  /* many runs */
147  *outstream = multiMerge<T,Compare>(runList, cmp);
148  //i thought the templates are not needed in the call, but seems to
149  //help the compiler..laura
150  }
151 
152  assert(runList->length() == 0);
153  delete runList;
154 
155  SORT_DEBUG {
156  cout << "AMI_sort: done" << endl << endl;
157  MM_manager.print();
158  }
159 
160  assert(*outstream);
161  assert((*outstream)->stream_len() == instreamLength);
162  return AMI_ERROR_NO_ERROR;
163 
164 }
165 
166 
167 
168 template<class T, class Compare>
169 int
170 isSorted(AMI_STREAM<T> *str, Compare cmp) {
171  T *prev, *crt;
172  AMI_err ae;
173 
174  assert(str);
175  str->seek(0);
176 
177  if (str->stream_len() <2) return 1;
178 
179  ae = str->read_item(&crt);
180  cout << "reading: " << *crt << endl;
181  prev = new T (*crt);
182  ae = str->read_item(&crt);
183  while (ae == AMI_ERROR_NO_ERROR) {
184  cout << "reading: " << *crt << endl;
185  if (cmp.compare(*prev, *crt) != -1)
186  assert(0);
187  return 0;
188  prev = crt;
189  ae = str->read_item(&crt);
190  }
191  return 1;
192 }
193 
194 
195 #endif // _AMI_SORT_H
AMI_err read_item(T **elt)
Definition: ami_stream.h:543
int isSorted(AMI_STREAM< T > *str, Compare cmp)
Definition: ami_sort.h:170
void print()
Definition: mm.cpp:86
MM_register MM_manager
Definition: mm.cpp:487
#define NULL
Definition: ccmath.h:32
unsigned int length() const
Definition: queue.h:59
AMI_err seek(off_t offset)
Definition: ami_stream.h:460
Definition: queue.h:43
queue< char * > * runFormation(AMI_STREAM< T > *instream, Compare *cmp)
#define assert(condition)
Definition: lz4.c:324
AMI_err name(char **stream_name)
Definition: ami_stream.h:440
#define SORT_DEBUG
Definition: ami_sort.h:42
AMI_err
Definition: ami_stream.h:86
const char * name
Definition: named_colr.c:7
off_t stream_len(void)
Definition: ami_stream.h:388
AMI_err AMI_sort(AMI_STREAM< T > *instream, AMI_STREAM< T > **outstream, Compare *cmp, int deleteInputStream=0)
Definition: ami_sort.h:95
bool dequeue(T *)
Definition: queue.h:94