GRASS GIS 7 Programmer's Manual  7.7.svn(2018)-r73570
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 
37 
38 #ifndef __EMPQ_ADAPTIVE_H
39 #define __EMPQ_ADAPTIVE_H
40 
41 
42 #include "minmaxheap.h"
43 #include "empq.h"
44 #include "empq_impl.h"
45 
46 
47 #define EMPQAD_DEBUG if(G_verbose() > G_verbose_std())
48 
49 
50 enum regim_type {
51  INMEM = 0,
54 };
55 
56 
57 template<class T, class Key>
59 private:
60  //dictates if the structure works in the internal/external memory regim;
61  regim_type regim;
62  MinMaxHeap<T> *im;
63  em_pqueue<T,Key> *em;
64  UnboundedMinMaxHeap<T> *dim; // debug, internal memory pq
65  void initPQ(size_t);
66 public:
67  /* start in INMEM regim by allocating im of size precisely twice the
68  size of the (pqueue within) the em_pqueue; */
71  EMPQueueAdaptive(size_t inMem);
73 
74  void makeExternal();
75  void makeExternalDebug();
76 
77  long maxlen() const; //return the maximum nb of elts that can fit
78  bool is_empty() const; //return true if empty
79  bool is_full() const; //return true if full
80  bool min(T& elt); //return the element with min priority XXX
81  //delete the element with minimum priority in the structure;
82  //return false if pq is empty
83  bool extract_min(T& elt);
84 
85  //extract all elts with min key, add them and return their sum XXX
86  bool extract_all_min(T& elt);
87 
88  /* insert an element; if regim == INMEM, try insert it in im, and if
89  it is full, extract_max pqsize/2 elements of im into a stream,
90  switch to EXTMEM and insert the stream into em; if regim is
91  EXTMEM, insert in em; */
92  bool insert(const T& elt);
93 
94  long size() const; //return the nb of elements in the structure
95 
96  void clear(); /* delete all contents of pq */
97 
98  void verify();
99 };
100 
101 
102 
103 #endif
EMPQueueAdaptive(long N)
Definition: empq_adaptive.h:69
regim_type
Definition: empq_adaptive.h:50
bool extract_min(T &elt)
#define N
Definition: e_intersect.c:923
long maxlen() const
bool is_full() const
bool insert(const T &elt)
bool extract_all_min(T &elt)
bool is_empty() const