GRASS GIS 8 Programmer's Manual
8.5.0dev(2024)-d6dec75dd4
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
45
enum
regim_type
{
INMEM
= 0,
EXTMEM
,
EXTMEM_DEBUG
};
46
47
template
<
class
T,
class
Key>
48
class
EMPQueueAdaptive
{
49
private
:
50
// dictates if the structure works in the internal/external memory regim;
51
regim_type
regim;
52
MinMaxHeap<T>
*im;
53
em_pqueue<T, Key>
*em;
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; */
60
EMPQueueAdaptive
(
long
N
UNUSED
) :
EMPQueueAdaptive
() {};
61
EMPQueueAdaptive
();
62
EMPQueueAdaptive
(
size_t
inMem);
63
~EMPQueueAdaptive
();
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
Definition:
empq_adaptive.h:48
EMPQueueAdaptive::EMPQueueAdaptive
EMPQueueAdaptive()
Definition:
empq_adaptive_impl.h:78
EMPQueueAdaptive::EMPQueueAdaptive
EMPQueueAdaptive(long N UNUSED)
Definition:
empq_adaptive.h:60
EMPQueueAdaptive::extract_all_min
bool extract_all_min(T &elt)
Definition:
empq_adaptive_impl.h:294
EMPQueueAdaptive::maxlen
long maxlen() const
Definition:
empq_adaptive_impl.h:173
EMPQueueAdaptive::verify
void verify()
Definition:
empq_adaptive_impl.h:278
EMPQueueAdaptive::makeExternal
void makeExternal()
Definition:
empq_adaptive_impl.h:428
EMPQueueAdaptive::clear
void clear()
Definition:
empq_adaptive_impl.h:262
EMPQueueAdaptive::size
long size() const
Definition:
empq_adaptive_impl.h:320
EMPQueueAdaptive::makeExternalDebug
void makeExternalDebug()
Definition:
empq_adaptive_impl.h:400
EMPQueueAdaptive::is_empty
bool is_empty() const
Definition:
empq_adaptive_impl.h:194
EMPQueueAdaptive::extract_min
bool extract_min(T &elt)
Definition:
empq_adaptive_impl.h:343
EMPQueueAdaptive::~EMPQueueAdaptive
~EMPQueueAdaptive()
Definition:
empq_adaptive_impl.h:155
EMPQueueAdaptive::is_full
bool is_full() const
Definition:
empq_adaptive_impl.h:216
EMPQueueAdaptive::min
bool min(T &elt)
Definition:
empq_adaptive_impl.h:225
EMPQueueAdaptive::insert
bool insert(const T &elt)
Definition:
empq_adaptive_impl.h:373
MinMaxHeap
Definition:
minmaxheap.h:781
UnboundedMinMaxHeap
Definition:
minmaxheap.h:823
em_pqueue
Definition:
empq.h:124
N
#define N
Definition:
e_intersect.c:926
empq.h
regim_type
regim_type
Definition:
empq_adaptive.h:45
EXTMEM_DEBUG
@ EXTMEM_DEBUG
Definition:
empq_adaptive.h:45
EXTMEM
@ EXTMEM
Definition:
empq_adaptive.h:45
INMEM
@ INMEM
Definition:
empq_adaptive.h:45
empq_impl.h
UNUSED
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Definition:
gis.h:47
minmaxheap.h
include
grass
iostream
empq_adaptive.h
Generated on Sun Dec 22 2024 07:38:13 for GRASS GIS 8 Programmer's Manual by
1.9.1