rtsDTGrid2D_v1.h
17.7 KB
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
#include <vector>
#include <iostream>
using namespace std;
#include "rtsDTGrid1D.h"
#ifndef _RTS_DTGRID2D_H
#define _RTS_DTGRID2D_H
struct IndexPair
{
//int toValue;
int toConn;
int numConn;
};
#include "ColumnUnion.h"
struct Coord2D
{
int x1;
int x2;
};
template<typename T>
class rtsDTGrid2D
{
private:
//main arrays
vector<T> value;
vector<ConnectedComponent> conn;
rtsDTGrid1D<IndexPair> proj1D;
bool randomIndex(rtsDTGrid1D<IndexPair>::iterator &iter1D, int &v_i, int &c_i, int x1, int x2);
//variables to keep track of insertion
int max_coord;
bool grid_insertion_started;
bool column_insertion_started;
public:
rtsDTGrid2D<T>()
{
grid_insertion_started = false;
column_insertion_started = false;
proj1D.background.toConn = -1;
max_coord = 0;
}
bool push(int x1, int x2, T v);
T random(int x1, int x2);
T& back();
T background;
void print();
friend class ColumnUnion;
void dilate(int H);
void insert(rtsDTGrid2D<T> toInsert);
void operator=(T rhs);
void getBounds(int &min_x1, int &min_x2, int &max_x1, int &max_x2);
void dumpValue();
void dumpConn();
//iterator
class iterator;
friend class iterator;
class stencil_iterator;
iterator randomIterator(int x1, int x2);
iterator begin();
iterator before();
iterator end();
iterator after();
};
/**********ITERATOR***********************/
template<typename T>
class rtsDTGrid2D<T>::iterator
{
friend class rtsDTGrid2D;
rtsDTGrid2D<T>* parent;
rtsDTGrid1D<IndexPair>::iterator loc1D;
int iv;
int ic;
int x2;
public:
T Value(){return parent->value[iv];}
int X1(){return loc1D.X1();}
int X2(){return x2;}
iterator(){parent = NULL;}
void SetValue(T value){parent->value[iv] = value;}
void increment()
{
//increment the value
iv++;
//if this exceeds the length of the value array, we are at the end of the grid
if(iv == parent->value.size())
{
(*this) = parent->after();
return;
}
//increment the current coordinate
x2++;
//if we are outside of the current connected component
if(x2 > parent->conn[ic].coordMax)
{
//move to the next connected component
ic++;
//if this is the last connected component in the column
if(ic == loc1D.Value().toConn + loc1D.Value().numConn)
loc1D++;
//if there are no more connected components
if(ic == parent->conn.size())
{
//we're at the end, return end
(*this) = parent->end();
return;
}
x2 = parent->conn[ic].coordMin;
}
}
//boolean operators for comparing iterators
bool operator==(iterator rhs)
{
if(parent == rhs.parent && iv == rhs.iv)
return true;
return false;
}
bool operator!=(iterator rhs){return !((*this) == rhs);}
friend bool operator<(iterator &left, iterator &right)
{
if(left.iv < right.iv)
return true;
return false;
}
friend bool operator<=(iterator &left, iterator &right)
{
if(left.iv <= right.iv)
return true;
return false;
}
void operator++(){increment();}
void increment_until(int p1, int p2)
{
while((*this) != parent->end())
{
if(X1() > p1)
return;
else if(X1() == p1 && X2() >= p2)
return;
increment();
}
}
};
/********STENCIL ITERATOR*****************/
template<typename T>
class rtsDTGrid2D<T>::stencil_iterator : public iterator
{
private:
//list of iterators that make up the template
vector<iterator> iterator_list;
//iterator positions (relative to the position of the stencil iterator)
vector<Coord2D> position_list;
//list containing the values for each position in the stencil
vector<T> value_list;
void refresh_iterators();
void set_values();
void increment_all();
public:
typename rtsDTGrid2D<T>::stencil_iterator operator=(const iterator rhs);
void addPosition(int p1, int p2);
void increment();
void operator++()
{
increment();
}
T getValue(int id){return value_list[id];}
bool exists(int id);
};
template<typename T>
void rtsDTGrid2D<T>::stencil_iterator::increment_all()
{
//run through each iterator and increment to the correct position
int i;
Coord2D dest;
for(i=0; i<iterator_list.size(); i++)
{
//determine the appropriate position for the iterator
dest.x1 = X1() + position_list[i].x1;
dest.x2 = X2() + position_list[i].x2;
//iterate until that position is reached
iterator_list[i].increment_until(dest.x1, dest.x2);
}
set_values();
}
template<typename T>
void rtsDTGrid2D<T>::stencil_iterator::increment()
{
//increment the current position
rtsDTGrid2D<T>::iterator::increment();
increment_all();
}
template<typename T>
void rtsDTGrid2D<T>::stencil_iterator::refresh_iterators()
{
//make sure that the iterator position has been set
if(parent == NULL)
{
cout<<"Iterator location not set."<<endl;
return;
}
//initialize all of the other iterators
int i;
for(i=0; i<iterator_list.size(); i++)
{
//for each iterator, set the iterator to the beginning of the grid
//iterator_list[i] = parent->begin();
iterator_list[i] = parent->randomIterator(X1() + position_list[i].x1,
X2() + position_list[i].x2);
}
//increment_all();
//set the values for all of the iterators
set_values();
}
template<typename T>
void rtsDTGrid2D<T>::stencil_iterator::set_values()
{
int i;
Coord2D dest;
for(i=0; i<iterator_list.size(); i++)
{
//determine the appropriate position for the iterator
dest.x1 = X1() + position_list[i].x1;
dest.x2 = X2() + position_list[i].x2;
//now add the value to the value list
if(iterator_list[i].X1() == dest.x1 && iterator_list[i].X2() == dest.x2)
value_list[i] = iterator_list[i].Value();
else
value_list[i] = parent->background;
}
}
template<typename T>
typename rtsDTGrid2D<T>::stencil_iterator rtsDTGrid2D<T>::stencil_iterator::operator=(const iterator rhs)
{
parent = rhs.parent;
loc1D = rhs.loc1D;
iv = rhs.iv;
ic = rhs.ic;
x2 = rhs.x2;
refresh_iterators();
return (*this);
}
template<typename T>
void rtsDTGrid2D<T>::stencil_iterator::addPosition(int p1, int p2)
{
//add a position to the position list and add a new iterator to the iterator list
Coord2D p;
p.x1 = p1;
p.x2 = p2;
position_list.push_back(p);
rtsDTGrid2D<T>::iterator new_iter;
iterator_list.push_back(new_iter);
T empty;
value_list.push_back(empty);
}
template<typename T>
bool rtsDTGrid2D<T>::stencil_iterator::exists(int id)
{
int i;
Coord2D dest;
//determine the appropriate position for the iterator
dest.x1 = X1() + position_list[id].x1;
dest.x2 = X2() + position_list[id].x2;
//now add the value to the value list
if(iterator_list[id].X1() == dest.x1 && iterator_list[id].X2() == dest.x2)
return true;
else
return false;
}
/**************ITERATOR METHODS IN DT GRID*******************/
template<typename T>
typename rtsDTGrid2D<T>::iterator rtsDTGrid2D<T>::begin()
{
//if the grid is empty, return an iterator to "after"
if(value.size() == 0)
return after();
iterator result;
result.parent = this;
result.ic = 0;
result.iv = 0;
result.x2 = conn[0].coordMin;
result.loc1D = proj1D.begin();
return result;
}
template<typename T>
typename rtsDTGrid2D<T>::iterator rtsDTGrid2D<T>::before()
{
if(value.size() == 0)
return after();
iterator result;
result.parent = this;
result.ic = 0;
result.iv = -1;
//result.x2 = conn[0].coordMin;
result.loc1D = proj1D.before();
return result;
}
template<typename T>
typename rtsDTGrid2D<T>::iterator rtsDTGrid2D<T>::end()
{
//if the grid is empty, return after()
if(value.size() == 0)
return after();
iterator result;
result.parent = this;
result.ic = conn.size() - 1;
result.iv = value.size() - 1;
result.x2 = conn[result.ic].coordMax;
result.loc1D = proj1D.end();
return result;
}
template<typename T>
typename rtsDTGrid2D<T>::iterator rtsDTGrid2D<T>::randomIterator(int x1, int x2)
{
rtsDTGrid2D<T>::iterator result;
result.parent = this;
//perform the random search
int v_i, c_i;
rtsDTGrid1D<IndexPair>::iterator iter1D;
//if the value exists in the grid, create the iterator and return
if(randomIndex(iter1D, v_i, c_i, x1, x2))
{
result.loc1D = iter1D;
result.iv = v_i;
result.ic = c_i;
int offset = v_i - conn[c_i].toValue;
result.x2 = conn[c_i].coordMin + offset;
}
//if the value doesn't exist
else
{
//if the 1D iterator is at the end of the grid, return after()
if(iter1D == proj1D.after())
return after();
//if the value lies before the current column
if(x1 < iter1D.X1() || (x1 == iter1D.X1() && x2 < conn[c_i].coordMin) )
{
result.ic = c_i;
}
//else if the value lies after the current column
else
{
//increment the 1D iterator
iter1D++;
//if this is the last connected component
if(c_i >= conn.size() - 1)
return after();
else
{
c_i++;
result.ic = c_i;
}
}
result.loc1D = iter1D;
result.iv = conn[c_i].toValue;
result.x2 = conn[c_i].coordMin;
}
return result;
}
template<typename T>
typename rtsDTGrid2D<T>::iterator rtsDTGrid2D<T>::after()
{
iterator result;
result.parent = this;
result.ic = conn.size() - 1;
result.iv = value.size();
//result.x2 = conn[result.ic].coordMax;
result.loc1D = proj1D.after();
return result;
}
/**************DT GRID**************************/
template<typename T>
bool rtsDTGrid2D<T>::push(int x1, int x2, T v)
{
//run this code if we have to start a new column in X1. This happens when:
//(a) we have just inserted the first value into the grid
//(b) the value of x1 is greater than the last value of x1
if(grid_insertion_started == false || x1 != proj1D.getMaxX1())
{
//assume that a new column is being created
//create the column in proj1D
IndexPair newPair;
newPair.toConn = conn.size();
//newPair.toValue = value.size();
newPair.numConn = 0;
//if this insertion throws an error, the value was inserted incorrectly
//the error will get thrown by DTGrid1D, so just return
if(!proj1D.push(x1, newPair))
{
cout<<"Out-of-order insertion in D = 2: X1 = "<<x1<<" X2 = "<<x2<<endl;
return false;
}
column_insertion_started = false;
grid_insertion_started = true;
}
//If there is no new column, we still have to check to make sure the value is inserted
//in the correct order in X2:
else
{
if(column_insertion_started && x2 <= max_coord)
{
cout<<"Out-of-order insertion in D = 2: X1 = "<<x1<<" X2 = "<<x2<<endl;
return false;
}
}
//run this code if we have to start a new connected component. This happens when:
//(a) We insert the first value into the column
//(b) There is empty space between the last insertion and this one
if(column_insertion_started == false || x2 > (max_coord + 1))
{
//start a new connected component
ConnectedComponent new_conn;
new_conn.toValue = value.size();
new_conn.coordMin = x2;
new_conn.coordMax = x2;
conn.push_back(new_conn);
//increment the number of connected components for the column in X1
proj1D.back().numConn++;
column_insertion_started = true;
}
//insert the value into the grid:
//(a) Insert the value at the end of the coord array
//(b) Increment the coordMax value of the current connected component
//(c) Change the maximum inserted coordinate to the new value
value.push_back(v);
conn[conn.size() - 1].coordMax = x2;
//change max_coord to the new coordinate
max_coord = x2;
return true;
}
template<typename T>
bool rtsDTGrid2D<T>::randomIndex(rtsDTGrid1D<IndexPair>::iterator &iter1D, int &v_i, int &c_i, int x1, int x2)
{
//search along the first dimension
//get an iterator
iter1D = proj1D.randomIterator(x1);
//if the after() iterator is returned, exit
if(iter1D == proj1D.after())
{
c_i = conn.size();
v_i = value.size();
return false;
}
IndexPair i = iter1D.Value();
//if the 1D column does not exist
if(iter1D.X1() != x1)
{
//get the appropriate values from the 1D iterator
//(which points to the next valid column)
c_i = i.toConn;
v_i = conn[c_i].toValue;
return false;
}
int high, low, mid;
low = i.toConn;
high = i.toConn + i.numConn - 1;
do
{
mid = low + (high - low)/2;
if(x2 > conn[mid].coordMax)
low = mid + 1;
else if(x2 < conn[mid].coordMin)
high = mid - 1;
else break;
}
while(low <= high);
//at this point, mid is either at the appropriate connected component,
//or x2 is not in the grid
if(x2 >= conn[mid].coordMin && x2 <= conn[mid].coordMax)
{
int offset = x2 - conn[mid].coordMin;
c_i = mid;
v_i = conn[mid].toValue + offset;
return true;
}
else
{
c_i = mid;
v_i = conn[c_i].toValue;
return false;
}
}
template<typename T>
T rtsDTGrid2D<T>::random(int x1, int x2)
{
int v_i, c_i;
rtsDTGrid1D<IndexPair>::iterator iter1D;
if(randomIndex(iter1D, v_i, c_i, x1, x2))
return value[v_i];
else
return background;
}
template<typename T>
T& rtsDTGrid2D<T>::back()
{
return value[value.size()-1];
}
template<typename T>
void rtsDTGrid2D<T>::dilate(int H)
{
//if the grid is empty, return unchanged
if(value.size() == 0)
return;
ColumnUnion CUqueue;
CUqueue.ConnectToGrid(&conn);
//dilate the N-1 DT-Grid constituent
rtsDTGrid1D<IndexPair> dilated_proj1D = proj1D;
//an empty pair has a number of connected components equal to zero
//this should not happen in reality and can therefore be used to check for new columns
IndexPair empty_pair;
empty_pair.numConn = 0;
//set the background node to the empty node and dilate the 1D projection
dilated_proj1D.background = empty_pair;
dilated_proj1D.dilate(H);
//create a new DT Grid that will replace this one
rtsDTGrid2D<T> new_grid;
new_grid.proj1D = dilated_proj1D;
new_grid.proj1D.background.toConn = -1;
//create iteratorDilate that iterates along the dilated N-1 grid
rtsDTGrid1D<IndexPair>::stencil_iterator iteratorDilate;
iteratorDilate.addPosition(-H);
iteratorDilate.addPosition(H);
//create an iterator to set the new proj1D values
rtsDTGrid1D<IndexPair>::iterator iteratorNew;
//variables for each iteration
IndexPair new_pair;
vector<ConnectedComponent>::iterator ccIterator;
unsigned int numValues = 0;
for(iteratorNew = new_grid.proj1D.begin(),
iteratorDilate = dilated_proj1D.begin();
iteratorDilate != dilated_proj1D.after();
iteratorNew++,
iteratorDilate++)
{
//cout<<"1D position: "<<iteratorNew.X1()<<endl;
//if a column is entering the stencil
if(iteratorDilate.getValue(1).numConn)
CUqueue.InsertColumn(iteratorDilate.getValue(1));
//compute the union of all columns in the queue
vector<ConnectedComponent> result = CUqueue.ComputeUnion(H);
//compute the new IndexPair representing the column
new_pair.toConn = new_grid.conn.size();
new_pair.numConn = result.size();
//store the index pair
iteratorNew.SetValue(new_pair);
//insert each of the connected components
for(ccIterator = result.begin(); ccIterator!=result.end(); ccIterator++)
{
new_grid.conn.push_back(*ccIterator);
new_grid.conn.back().toValue = numValues;
numValues += (*ccIterator).coordMax - (*ccIterator).coordMin + 1;
}
//if a column is leaving the stencil
if(iteratorDilate.getValue(0).numConn)
CUqueue.RemoveColumn();
}
//allocate space for the new value array
new_grid.value.resize(numValues, background);
//copy the data from this grid into the new grid
new_grid.insert(*this);
//replace this grid with the new grid
conn = new_grid.conn;
value = new_grid.value;
proj1D = new_grid.proj1D;
}
template<typename T>
void rtsDTGrid2D<T>::insert(rtsDTGrid2D<T> toInsert)
{
//create source and destination iterators
rtsDTGrid2D<T>::iterator source = toInsert.begin();
rtsDTGrid2D<T>::iterator dest = begin();
for(source = toInsert.begin(); source != toInsert.after(); source++)
{
//move the destination iterator to the current source position
dest.increment_until(source.X1(), source.X2());
//cout<<"source: "<<source.X1()<<" "<<source.X2()<<": "<<source.Value()<<endl;
//cout<<"dest: "<<dest.X1()<<" "<<dest.X2()<<": "<<dest.Value()<<endl;
//if the position exists in dest
if(dest.X1() == source.X1() && dest.X2() == source.X2())
dest.SetValue(source.Value());
//cout<<"dest: "<<dest.X1()<<" "<<dest.X2()<<": "<<dest.Value()<<endl;
}
}
template<typename T>
void rtsDTGrid2D<T>::getBounds(int &min_x1, int &min_x2, int &max_x1, int &max_x2)
{
//if the grid is empty, return an empty bounding volume
if(value.size() == 0)
{
min_x1 = min_x2 = max_x1 = max_x2 = 0;
return;
}
//get the min and max values for the 1D grid (x1 coordinate)
proj1D.getBounds(min_x1, max_x1);
//initialize the min and max values
min_x2 = conn[0].coordMin;
max_x2 = conn.back().coordMax;
//iterate through all columns finding the smallest and largest coordinate values
rtsDTGrid1D<IndexPair>::iterator i;
IndexPair col;
for(i=proj1D.begin(); i!=proj1D.after(); i++)
{
col = i.Value();
if(conn[col.toConn].coordMin < min_x2)
min_x2 = conn[col.toConn].coordMin;
if(conn[col.toConn + col.numConn - 1].coordMax > max_x2)
max_x2 = conn[col.toConn + col.numConn - 1].coordMax;
}
}
template<typename T>
void rtsDTGrid2D<T>::operator =(T rhs)
{
for(int i=0; i<value.size(); i++)
value[i] = rhs;
}
template<typename T>
void rtsDTGrid2D<T>::dumpValue()
{
for(int i=0; i<value.size(); i++)
cout<<value[i]<<endl;
}
template<typename T>
void rtsDTGrid2D<T>::dumpConn()
{
for(int i=0; i<conn.size(); i++)
cout<<conn[i].toValue<<","<<conn[i].coordMin<<","<<conn[i].coordMax<<endl;
}
#endif