/
scLazyStreamEx.cc
119 lines (103 loc) · 2.4 KB
/
scLazyStreamEx.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
//A Self Contained example of Lazy Streams Natively in C++
//Based on work by D. Renz and M. Borowczak @ the University of Cincinnati
//http://www2.moreheadstate.edu/files/colleges/science/mcs/mejam/Renz.pdf
#include <iostream>
using namespace std;
class Stream {
public:
int head;
bool isEmpty;
virtual Stream *tail() = 0;
Stream() {isEmpty = false;}
};
class Successor : public Stream{
public:
Successor( int i ){
head = i;
}
Stream *tail(){ return new Successor( head + 1 ); }
};
class Times : public Stream {
Stream *inStream;
int multiplier;
public:
Times( int n, Stream *s ) {
multiplier = n;
inStream = s;
isEmpty = inStream->isEmpty;
if ( !isEmpty ) head = multiplier * inStream->head;
}
Stream *tail() { return new Times( multiplier, inStream->tail() ); }
};
class Merge : public Stream {
Stream *branch1, *branch2;
public:
Merge ( Stream *a, Stream *b ) {
if ( a->isEmpty && b->isEmpty ) {
branch1 = a;
branch2 = b;
isEmpty = true;
} else if ( b->isEmpty ) {
branch1 = a;
branch2 = b;
} else if ( a->isEmpty ) {
branch1 = b;
branch2 = a;
} else if ( a->head < b->head) {
branch1 = a;
branch2 = b;
} else {
branch1 = b;
branch2 = a;
}
head = branch1-> head;
}
Stream *tail() { return new Merge( branch1->tail(), branch2 ); }
};
class List: public Stream {
int *tokens;
int size;
public:
List(int *t, int s ){
tokens = t;
size = s;
if ( size > 0 )
head = tokens[0];
else
isEmpty = true;
}
Stream *tail(){ return new List( &tokens[1],(size - 1) ); }
};
//END LAZY STREAM CLASS DEFINITIONS
//CONSUMER HELPER FUNCTION
//Inputs: STREAM, # of Tokens to Process
void consumer( Stream *s , int toks){
//Hacked for now just so no one complains
if (toks < 0){
toks = 0;
}
for ( int i = 0; ( i < toks && !s->isEmpty ); i++ ){
cout << s->head << endl;
s = s->tail();
}
}
//A 'real' example
//Let's find the first 400 Hamming Numbers {3,5,11}
class Hamming : public Stream {
Stream *p;
public:
Hamming( Stream *givenPrimes ) {
p = givenPrimes;
isEmpty = p->isEmpty;
if(!isEmpty) head = p->head;
}
Stream *tail() {
return new Merge(new Times(p->head, this),new Hamming(p->tail()));
}
};
int main(){
int primes[3]= { 3, 5, 11 };
Stream *h = new Hamming( new List(primes, 3) );
consumer( h, 400 );
return 0;
}