GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-6c790bf5c0
empq_adaptive.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 __EMPQ_ADAPTIVE_H
37 #define __EMPQ_ADAPTIVE_H
38 
39 #include "minmaxheap.h"
40 #include "empq.h"
41 #include "empq_impl.h"
42 
43 #define EMPQAD_DEBUG if (G_verbose() > G_verbose_std())
44 
46 
47 template <class T, class Key>
49 private:
50  // dictates if the structure works in the internal/external memory regim;
51  regim_type regim;
52  MinMaxHeap<T> *im;
54  UnboundedMinMaxHeap<T> *dim; // debug, internal memory pq
55  void initPQ(size_t);
56 
57 public:
58  /* start in INMEM regim by allocating im of size precisely twice the
59  size of the (pqueue within) the em_pqueue; */
62  EMPQueueAdaptive(size_t inMem);
64 
65  void makeExternal();
66  void makeExternalDebug();
67 
68  long maxlen() const; // return the maximum nb of elts that can fit
69  bool is_empty() const; // return true if empty
70  bool is_full() const; // return true if full
71  bool min(T &elt); // return the element with min priority XXX
72  // delete the element with minimum priority in the structure;
73  // return false if pq is empty
74  bool extract_min(T &elt);
75 
76  // extract all elts with min key, add them and return their sum XXX
77  bool extract_all_min(T &elt);
78 
79  /* insert an element; if regim == INMEM, try insert it in im, and if
80  it is full, extract_max pqsize/2 elements of im into a stream,
81  switch to EXTMEM and insert the stream into em; if regim is
82  EXTMEM, insert in em; */
83  bool insert(const T &elt);
84 
85  long size() const; // return the nb of elements in the structure
86 
87  void clear(); /* delete all contents of pq */
88 
89  void verify();
90 };
91 
92 #endif
EMPQueueAdaptive(long N UNUSED)
Definition: empq_adaptive.h:60
bool extract_all_min(T &elt)
bool extract_min(T &elt)
bool insert(const T &elt)
#define N
Definition: e_intersect.c:926
regim_type
Definition: empq_adaptive.h:45
@ EXTMEM_DEBUG
Definition: empq_adaptive.h:45
@ EXTMEM
Definition: empq_adaptive.h:45
@ INMEM
Definition: empq_adaptive.h:45
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Definition: gis.h:47