GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-3f124c5c78
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
84 template <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>();
97  if (deleteInputStream) {
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;
108  MM_manager.print();
109  }
110 
111  // run formation
112  runList = runFormation(instream, cmp);
113  assert(runList);
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);
132  *outstream = new AMI_STREAM<T>(name);
133  delete name; // should be safe, stream makes its own copy
134  }
135  else {
136  /* many runs */
137  *outstream = multiMerge<T, Compare>(runList, cmp);
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;
147  MM_manager.print();
148  }
149 
150  assert(*outstream);
151  assert((*outstream)->stream_len() == instreamLength);
152  return AMI_ERROR_NO_ERROR;
153 }
154 
155 template <class T, class Compare>
156 int isSorted(AMI_STREAM<T> *str, Compare cmp)
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
bool dequeue(T *)
Definition: queue.h:95
unsigned int length() const
Definition: queue.h:60
#define assert(condition)
Definition: lz4.c:393
MM_register MM_manager
Definition: mm.cpp:475
const char * name
Definition: named_colr.c:6