Actual source code: Sifter.hh

  1: #ifndef included_ALE_Sifter_hh
  2: #define included_ALE_Sifter_hh

  4: /*
  5: #include <boost/multi_index_container.hpp>
  6: #include <boost/multi_index/member.hpp>
  7: #include <boost/multi_index/ordered_index.hpp>
  8: #include <boost/multi_index/composite_key.hpp>
  9: */
 10: #include <iostream>

 12: // ALE extensions

 14: #ifndef  included_ALE_hh
 15: #include <ALE.hh>
 16: #endif


 20: namespace ALE {

 22:   namespace SifterDef {
 23:     // Defines the traits of a sequence representing a subset of a multi_index container Index_.
 24:     // A sequence defines output (input in std terminology) iterators for traversing an Index_ object.
 25:     // Upon dereferencing values are extracted from each result record using a ValueExtractor_ object.
 26:     template <typename Index_, typename ValueExtractor_>
 27:     struct IndexSequenceTraits {
 28:       typedef Index_ index_type;
 29:       class iterator_base {
 30:       public:
 31:         // Standard iterator typedefs
 32:         typedef ValueExtractor_                        extractor_type;
 33:         typedef std::input_iterator_tag                iterator_category;
 34:         typedef typename extractor_type::result_type   value_type;
 35:         typedef int                                    difference_type;
 36:         typedef value_type*                            pointer;
 37:         typedef value_type&                            reference;
 38: 
 39:         // Underlying iterator type
 40:         typedef typename index_type::iterator          itor_type;
 41:       protected:
 42:         // Underlying iterator
 43:         itor_type      _itor;
 44:         // Member extractor
 45:         extractor_type _ex;
 46:       public:
 47:         iterator_base(itor_type itor) {
 48:           this->_itor = itor_type(itor);
 49:         };
 50:         virtual ~iterator_base() {};
 51:         virtual bool              operator==(const iterator_base& iter) const {return this->_itor == iter._itor;};
 52:         virtual bool              operator!=(const iterator_base& iter) const {return this->_itor != iter._itor;};
 53:         // FIX: operator*() should return a const reference, but it won't compile that way, because _ex() returns const value_type
 54:         virtual const value_type  operator*() const {return _ex(*(this->_itor));};
 55:       };// class iterator_base
 56:       class iterator : public iterator_base {
 57:       public:
 58:         // Standard iterator typedefs
 59:         typedef typename iterator_base::iterator_category  iterator_category;
 60:         typedef typename iterator_base::value_type         value_type;
 61:         typedef typename iterator_base::extractor_type     extractor_type;
 62:         typedef typename iterator_base::difference_type    difference_type;
 63:         typedef typename iterator_base::pointer            pointer;
 64:         typedef typename iterator_base::reference          reference;
 65:         // Underlying iterator type
 66:         typedef typename iterator_base::itor_type          itor_type;
 67:       public:
 68:         iterator(const itor_type& itor) : iterator_base(itor) {};
 69:         virtual ~iterator() {};
 70:         //
 71:         virtual iterator   operator++() {++this->_itor; return *this;};
 72:         virtual iterator   operator++(int n) {iterator tmp(this->_itor); ++this->_itor; return tmp;};
 73:       };// class iterator
 74:     }; // struct IndexSequenceTraits
 75: 
 76:     template <typename Index_, typename ValueExtractor_>
 77:     struct ReversibleIndexSequenceTraits {
 78:       typedef IndexSequenceTraits<Index_, ValueExtractor_> base_traits;
 79:       typedef typename base_traits::iterator_base   iterator_base;
 80:       typedef typename base_traits::iterator        iterator;
 81:       typedef typename base_traits::index_type      index_type;

 83:       // reverse_iterator is the reverse of iterator
 84:       class reverse_iterator : public iterator_base {
 85:       public:
 86:         // Standard iterator typedefs
 87:         typedef typename iterator_base::iterator_category  iterator_category;
 88:         typedef typename iterator_base::value_type         value_type;
 89:         typedef typename iterator_base::extractor_type     extractor_type;
 90:         typedef typename iterator_base::difference_type    difference_type;
 91:         typedef typename iterator_base::pointer            pointer;
 92:         typedef typename iterator_base::reference          reference;
 93:         // Underlying iterator type
 94:         typedef typename iterator_base::itor_type          itor_type;
 95:       public:
 96:         reverse_iterator(const itor_type& itor) : iterator_base(itor) {};
 97:         virtual ~reverse_iterator() {};
 98:         //
 99:         virtual reverse_iterator     operator++() {--this->_itor; return *this;};
100:         virtual reverse_iterator     operator++(int n) {reverse_iterator tmp(this->_itor); --this->_itor; return tmp;};
101:       };
102:     }; // class ReversibleIndexSequenceTraits


105:     //
106:     // Rec & RecContainer definitions.
107:     // Rec is intended to denote a graph point record.
108:     //
109:     template <typename Point_>
110:     struct Rec {
111:       typedef Point_ point_type;
112:       template<typename OtherPoint_>
113:       struct rebind {
114:         typedef Rec<OtherPoint_> type;
115:       };
116:       point_type     point;
117:       int            degree;
118:       // Basic interface
119:       Rec() : degree(0){};
120:       Rec(const Rec& r) : point(r.point), degree(r.degree) {}
121:       //Rec(const point_type& p) : point(p), degree(0) {};
122:       Rec(const point_type& p, const int d) : point(p), degree(d) {};
123:       // Printing
124:       friend std::ostream& operator<<(std::ostream& os, const Rec& p) {
125:         os << "<" << p.point << ", "<< p.degree << ">";
126:         return os;
127:       };
128: 
129:       struct degreeAdjuster {
130:         degreeAdjuster(int newDegree) : _newDegree(newDegree) {};
131:         void operator()(Rec& r) { r.degree = this->_newDegree; }
132:       private:
133:         int _newDegree;
134:       };// degreeAdjuster()

136:     };// class Rec

138:     template <typename Point_, typename Rec_>
139:     struct RecContainerTraits {
140:       typedef Rec_ rec_type;
141:       // Index tags
142:       struct pointTag{};
143:       // Rec set definition
144:       typedef ::boost::multi_index::multi_index_container<
145:         rec_type,
146:         ::boost::multi_index::indexed_by<
147:           ::boost::multi_index::ordered_unique<
148:             ::boost::multi_index::tag<pointTag>, BOOST_MULTI_INDEX_MEMBER(rec_type, typename rec_type::point_type, point)
149:           >
150:         >,
151:         ALE_ALLOCATOR<rec_type>
152:       > set_type;
153:       //
154:       // Return types
155:       //

157:      class PointSequence {
158:      public:
159:         typedef IndexSequenceTraits<typename ::boost::multi_index::index<set_type, pointTag>::type,
160:                                     BOOST_MULTI_INDEX_MEMBER(rec_type, typename rec_type::point_type,point)>
161:         traits;
162:       protected:
163:         const typename traits::index_type& _index;
164:       public:
165: 
166:        // Need to extend the inherited iterator to be able to extract the degree
167:        class iterator : public traits::iterator {
168:        public:
169:          iterator(const typename traits::iterator::itor_type& itor) : traits::iterator(itor) {};
170:          virtual const int& degree() const {return this->_itor->degree;};
171:        };
172: 
173:        PointSequence(const PointSequence& seq)            : _index(seq._index) {};
174:        PointSequence(typename traits::index_type& index) : _index(index)     {};
175:        virtual ~PointSequence(){};
176: 
177:        virtual bool empty(){return this->_index.empty();};
178: 
179:        virtual typename traits::index_type::size_type size() {return this->_index.size();};

181:        virtual iterator begin() {
182:          // Retrieve the beginning iterator of the index
183:          return iterator(this->_index.begin());
184:        };
185:        virtual iterator end() {
186:          // Retrieve the ending iterator of the index
187:          // Since the elements in this index are ordered by degree, this amounts to the end() of the index.
188:          return iterator(this->_index.end());
189:        };
190:        virtual bool contains(const typename rec_type::point_type& p) {
191:          // Check whether a given point is in the index
192:          return (this->_index.find(p) != this->_index.end());
193:        }
194:      }; // class PointSequence
195:     };// struct RecContainerTraits


198:     template <typename Point_, typename Rec_>
199:     struct RecContainer {
200:       typedef RecContainerTraits<Point_, Rec_> traits;
201:       typedef typename traits::set_type set_type;
202:       template <typename OtherPoint_, typename OtherRec_>
203:       struct rebind {
204:         typedef RecContainer<OtherPoint_, OtherRec_> type;
205:       };
206:       set_type set;
207:       //
208:       void removePoint(const typename traits::rec_type::point_type& p) {
209:         typename ::boost::multi_index::index<set_type, typename traits::pointTag>::type& index =
210:           ::boost::multi_index::get<typename traits::pointTag>(this->set);
211:         typename ::boost::multi_index::index<set_type, typename traits::pointTag>::type::iterator i = index.find(p);
212:         if (i != index.end()) { // Point exists
213:           index.erase(i);
214:         }
215:       };
216:       //
217:       void adjustDegree(const typename traits::rec_type::point_type& p, int delta) {
218:         typename ::boost::multi_index::index<set_type, typename traits::pointTag>::type& index =
219:           ::boost::multi_index::get<typename traits::pointTag>(this->set);
220:         typename ::boost::multi_index::index<set_type, typename traits::pointTag>::type::iterator i = index.find(p);
221:         if (i == index.end()) { // No such point exists
222:           if(delta < 0) { // Cannot decrease degree of a non-existent point
223:             ostringstream err;
224:             err << "ERROR: adjustDegree: Non-existent point " << p;
225:             std::cout << err << std::endl;
226:             throw(Exception(err.str().c_str()));
227:           }
228:           else { // We CAN INCREASE the degree of a non-existent point: simply insert a new element with degree == delta
229:             std::pair<typename ::boost::multi_index::index<set_type, typename traits::pointTag>::type::iterator, bool> ii;
230:             typename traits::rec_type r(p,delta);
231:             ii = index.insert(r);
232:             if(ii.second == false) {
233:               ostringstream err;
234:               err << "ERROR: adjustDegree: Failed to insert a rec " << r;
235:               std::cout << err << std::endl;
236:               throw(Exception(err.str().c_str()));
237:             }
238:           }
239:         }
240:         else { // Point exists, so we try to modify its degree
241:           // If the adjustment is zero, there is nothing to do, otherwise ...
242:           if(delta != 0) {
243:             int newDegree = i->degree + delta;
244:             if(newDegree < 0) {
245:               ostringstream ss;
246:               ss << "adjustDegree: Adjustment of " << *i << " by " << delta << " would result in negative degree: " << newDegree;
247:               throw Exception(ss.str().c_str());
248:             }
249:             index.modify(i, typename traits::rec_type::degreeAdjuster(newDegree));
250:           }
251:         }
252:       }; // adjustDegree()
253:     }; // struct RecContainer

255:     //
256:     // Arrow & ArrowContainer definitions
257:     //
258:     template<typename Source_, typename Target_, typename Color_>
259:     struct  Arrow { //: public ALE::def::Arrow<Source_, Target_, Color_> {
260:       typedef Arrow   arrow_type;
261:       typedef Source_ source_type;
262:       typedef Target_ target_type;
263:       typedef Color_  color_type;
264:       source_type source;
265:       target_type target;
266:       color_type  color;
267:       Arrow(const source_type& s, const target_type& t, const color_type& c) : source(s), target(t), color(c) {};
268:       // Flipping
269:       template <typename OtherSource_, typename OtherTarget_, typename OtherColor_>
270:       struct rebind {
271:         typedef Arrow<OtherSource_, OtherTarget_, OtherColor_> type;
272:       };
273:       struct flip {
274:         typedef Arrow<target_type, source_type, color_type> type;
275:         type arrow(const arrow_type& a) { return type(a.target, a.source, a.color);};
276:       };

278:       // Printing
279:       friend std::ostream& operator<<(std::ostream& os, const Arrow& a) {
280:         os << a.source << " --(" << a.color << ")--> " << a.target;
281:         return os;
282:       }

284:       // Arrow modifiers
285:       struct sourceChanger {
286:         sourceChanger(const source_type& newSource) : _newSource(newSource) {};
287:         void operator()(arrow_type& a) {a.source = this->_newSource;}
288:       private:
289:         source_type _newSource;
290:       };

292:       struct targetChanger {
293:         targetChanger(const target_type& newTarget) : _newTarget(newTarget) {};
294:         void operator()(arrow_type& a) { a.target = this->_newTarget;}
295:       private:
296:         const target_type _newTarget;
297:       };
298:     };// struct Arrow
299: 

301:     template<typename Source_, typename Target_, typename Color_, typename SupportCompare_>
302:     struct ArrowContainerTraits {
303:     public:
304:       //
305:       // Encapsulated types
306:       //
307:       typedef Arrow<Source_,Target_,Color_>    arrow_type;
308:       typedef typename arrow_type::source_type source_type;
309:       typedef typename arrow_type::target_type target_type;
310:       typedef typename arrow_type::color_type  color_type;
311:       typedef SupportCompare_                  support_compare_type;
312:       // Index tags
313:       struct                                   sourceColorTag{};
314:       struct                                   targetColorTag{};
315:       struct                                   sourceTargetTag{};

317:       // Sequence traits and sequence types
318:       template <typename Index_, typename Key_, typename SubKey_, typename ValueExtractor_>
319:       class ArrowSequence {
320:         // ArrowSequence implements ReversibleIndexSequencTraits with Index_ and ValueExtractor_ types.
321:         // A Key_ object and an optional SubKey_ object are used to extract the index subset.
322:       public:
323:         typedef ReversibleIndexSequenceTraits<Index_, ValueExtractor_>  traits;
324:         //typedef source_type                                             source_type;
325:         //typedef target_type                                             target_type;
326:         //typedef arrow_type                                              arrow_type;
327:         //
328:         typedef Key_                                                    key_type;
329:         typedef SubKey_                                                 subkey_type;
330:       protected:
331:         typename traits::index_type&                                    _index;
332:         key_type                                                  key;
333:         subkey_type                                               subkey;
334:         bool                                                      useSubkey;
335:       public:
336:         // Need to extend the inherited iterators to be able to extract arrow color
337:         class iterator : public traits::iterator {
338:         public:
339:           iterator(const typename traits::iterator::itor_type& itor) : traits::iterator(itor) {};
340:           virtual const source_type& source() const {return this->_itor->source;};
341:           virtual const color_type&  color()  const {return this->_itor->color;};
342:           virtual const target_type& target() const {return this->_itor->target;};
343:           virtual const arrow_type&  arrow()  const {return *(this->_itor);};
344:         };
345:         class reverse_iterator : public traits::reverse_iterator {
346:         public:
347:           reverse_iterator(const typename traits::reverse_iterator::itor_type& itor) : traits::reverse_iterator(itor) {};
348:           virtual const source_type& source() const {return this->_itor->source;};
349:           virtual const color_type&  color()  const {return this->_itor->color;};
350:           virtual const target_type& target() const {return this->_itor->target;};
351:           virtual const arrow_type&  arrow()  const {return *(this->_itor);};
352:         };
353:       public:
354:         //
355:         // Basic ArrowSequence interface
356:         //
357:         ArrowSequence(const ArrowSequence& seq) : _index(seq._index), key(seq.key), subkey(seq.subkey), useSubkey(seq.useSubkey) {};
358:         ArrowSequence(typename traits::index_type& index, const key_type& k) :
359:           _index(index), key(k), subkey(subkey_type()), useSubkey(0) {};
360:         ArrowSequence(typename traits::index_type& index, const key_type& k, const subkey_type& kk) :
361:           _index(index), key(k), subkey(kk), useSubkey(1){};
362:         virtual ~ArrowSequence() {};

364:         void setKey(const key_type& key) {this->key = key;};
365:         void setSubkey(const subkey_type& subkey) {this->subkey = subkey;};
366:         void setUseSubkey(const bool& useSubkey) {this->useSubkey = useSubkey;};
367: 
368:         virtual bool         empty() {return this->_index.empty();};

370:         virtual typename traits::index_type::size_type  size()  {
371:           if (this->useSubkey) {
372:             return this->_index.count(::boost::make_tuple(this->key,this->subkey));
373:           } else {
374:             return this->_index.count(::boost::make_tuple(this->key));
375:           }
376:         };

378:         virtual iterator begin() {
379:           if (this->useSubkey) {
380:             return iterator(this->_index.lower_bound(::boost::make_tuple(this->key,this->subkey)));
381:           } else {
382:             return iterator(this->_index.lower_bound(::boost::make_tuple(this->key)));
383:           }
384:         };
385: 
386:         virtual iterator end() {
387:           if (this->useSubkey) {
388:             return iterator(this->_index.upper_bound(::boost::make_tuple(this->key,this->subkey)));
389:           } else {
390:             return iterator(this->_index.upper_bound(::boost::make_tuple(this->key)));
391:           }
392:         };
393: 
394:         virtual reverse_iterator rbegin() {
395:           if (this->useSubkey) {
396:             return reverse_iterator(--this->_index.upper_bound(::boost::make_tuple(this->key,this->subkey)));
397:           } else {
398:             return reverse_iterator(--this->_index.upper_bound(::boost::make_tuple(this->key)));
399:           }
400:         };
401: 
402:         virtual reverse_iterator rend() {
403:           if (this->useSubkey) {
404:             return reverse_iterator(--this->_index.lower_bound(::boost::make_tuple(this->key,this->subkey)));
405:           } else {
406:             return reverse_iterator(--this->_index.lower_bound(::boost::make_tuple(this->key)));
407:           }
408:         };

410:         template<typename ostream_type>
411:         void view(ostream_type& os, const bool& useColor = false, const char* label = NULL){
412:           if(label != NULL) {
413:             os << "Viewing " << label << " sequence:" << std::endl;
414:           }
415:           os << "[";
416:           for(iterator i = this->begin(); i != this->end(); i++) {
417:             os << " (" << *i;
418:             if(useColor) {
419:               os << "," << i.color();
420:             }
421:             os  << ")";
422:           }
423:           os << " ]" << std::endl;
424:         };
425:       };// class ArrowSequence
426:     };// class ArrowContainerTraits
427: 

429:     // The specialized ArrowContainer types distinguish the cases of unique and multiple colors of arrows on
430:     // for each (source,target) pair (i.e., a single arrow, or multiple arrows between each pair of points).
431:     typedef enum {multiColor, uniColor} ColorMultiplicity;

433:     template<typename Source_, typename Target_, typename Color_, ColorMultiplicity colorMultiplicity, typename SupportCompare_>
434:     struct ArrowContainer {};
435: 
436:     template<typename Source_, typename Target_, typename Color_, typename SupportCompare_>
437:     struct ArrowContainer<Source_, Target_, Color_, multiColor, SupportCompare_> {
438:       // Define container's encapsulated types
439:       typedef ArrowContainerTraits<Source_, Target_, Color_, SupportCompare_>      traits;
440:       // need to def arrow_type locally, since BOOST_MULTI_INDEX_MEMBER barfs when first template parameter starts with 'typename'
441:       typedef typename traits::arrow_type                         arrow_type;
442:       // Container set type
443:       typedef ::boost::multi_index::multi_index_container<
444:         typename traits::arrow_type,
445:         ::boost::multi_index::indexed_by<
446:           ::boost::multi_index::ordered_non_unique<
447:             ::boost::multi_index::tag<typename traits::sourceTargetTag>,
448:             ::boost::multi_index::composite_key<
449:               typename traits::arrow_type,
450:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::source_type, source),
451:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::target_type, target),
452:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::color_type,  color)
453:             >
454:           >,
455:           ::boost::multi_index::ordered_non_unique<
456:             ::boost::multi_index::tag<typename traits::sourceColorTag>,
457:             ::boost::multi_index::composite_key<
458:               typename traits::arrow_type,
459:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::source_type, source),
460:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::color_type,  color),
461:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::target_type, target)
462:             >
463:           >,
464:           ::boost::multi_index::ordered_non_unique<
465:             ::boost::multi_index::tag<typename traits::targetColorTag>,
466:             ::boost::multi_index::composite_key<
467:               typename traits::arrow_type,
468:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::target_type, target),
469:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::color_type,  color),
470:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::source_type, source)
471:             >
472:           >
473:         >,
474:         ALE_ALLOCATOR<typename traits::arrow_type>
475:       > set_type;
476:      // multi-index set of multicolor arrows
477:       set_type set;
478:     }; // class ArrowContainer<multiColor>
479: 
480:     template<typename Source_, typename Target_, typename Color_, typename SupportCompare_>
481:     struct ArrowContainer<Source_, Target_, Color_, uniColor, SupportCompare_> {
482:       // Define container's encapsulated types
483:       typedef ArrowContainerTraits<Source_, Target_, Color_, SupportCompare_> traits;
484:       // need to def arrow_type locally, since BOOST_MULTI_INDEX_MEMBER barfs when first template parameter starts with 'typename'
485:       typedef typename traits::arrow_type                                   arrow_type;

487:       // multi-index set type -- arrow set
488:       typedef ::boost::multi_index::multi_index_container<
489:         typename traits::arrow_type,
490:         ::boost::multi_index::indexed_by<
491:           ::boost::multi_index::ordered_unique<
492:             ::boost::multi_index::tag<typename traits::sourceTargetTag>,
493:             ::boost::multi_index::composite_key<
494:               typename traits::arrow_type,
495:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::source_type, source),
496:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::target_type, target),
497:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::color_type,  color)
498:             >
499:           >,
500:           ::boost::multi_index::ordered_non_unique<
501:             ::boost::multi_index::tag<typename traits::sourceColorTag>,
502:             ::boost::multi_index::composite_key<
503:               typename traits::arrow_type,
504:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::source_type, source),
505:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::color_type,  color),
506:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::target_type, target)
507:             >,
508:             SupportCompare_
509:           >,
510:           ::boost::multi_index::ordered_non_unique<
511:             ::boost::multi_index::tag<typename traits::targetColorTag>,
512:             ::boost::multi_index::composite_key<
513:               typename traits::arrow_type,
514:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::target_type, target),
515:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::color_type,  color),
516:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::source_type, source)
517:             >
518:           >
519:         >,
520:         ALE_ALLOCATOR<typename traits::arrow_type>
521:       > set_type;
522:       // multi-index set of unicolor arrow records
523:       set_type set;
524:     }; // class ArrowContainer<uniColor>
525:   }; // namespace SifterDef

527:   //
528:   // ASifter (short for Abstract Sifter, structurally a bipartite graph with colored arrows) implements a sequential interface
529:   // similar to that of Sieve, except the source and target points may have different types and iterated operations (e.g., nCone,
530:   // closure) are not available.
531:   //
532: template<typename Source_, typename Target_, typename Color_, SifterDef::ColorMultiplicity colorMultiplicity, typename SupportCompare_ = ::boost::multi_index::composite_key_compare<std::less<Source_>, std::less<Color_>, std::less<Target_> >, typename SourceCtnr_ = SifterDef::RecContainer<Source_, SifterDef::Rec<Source_> >, typename TargetCtnr_ = SifterDef::RecContainer<Target_, SifterDef::Rec<Target_> > >
533:   class ASifter { // class ASifter
534:   public:
535:     typedef struct {
536:       typedef ASifter<Source_, Target_, Color_, colorMultiplicity, SupportCompare_, SourceCtnr_, TargetCtnr_> graph_type;
537:       // Encapsulated container types
538:       typedef SifterDef::ArrowContainer<Source_, Target_, Color_, colorMultiplicity, SupportCompare_> arrow_container_type;
539:       typedef SourceCtnr_                                                            cap_container_type;
540:       typedef TargetCtnr_                                                            base_container_type;
541:       // Types associated with records held in containers
542:       typedef typename arrow_container_type::traits::arrow_type                      arrow_type;
543:       typedef typename arrow_container_type::traits::source_type                     source_type;
544:       typedef typename cap_container_type::traits::rec_type                          sourceRec_type;
545:       typedef typename arrow_container_type::traits::target_type                     target_type;
546:       typedef typename base_container_type::traits::rec_type                         targetRec_type;
547:       typedef typename arrow_container_type::traits::color_type                      color_type;
548:       typedef typename arrow_container_type::traits::support_compare_type            support_compare_type;
549:       // Convenient tag names
550:       typedef typename arrow_container_type::traits::sourceColorTag                  supportInd;
551:       typedef typename arrow_container_type::traits::targetColorTag                  coneInd;
552:       typedef typename arrow_container_type::traits::sourceTargetTag                 arrowInd;
553:       typedef typename base_container_type::traits::pointTag                         baseInd;
554:       typedef typename cap_container_type::traits::pointTag                          capInd;
555:       //
556:       // Return types
557:       //
558:       typedef typename
559:       arrow_container_type::traits::template ArrowSequence<typename ::boost::multi_index::index<typename arrow_container_type::set_type,arrowInd>::type, source_type, target_type, BOOST_MULTI_INDEX_MEMBER(arrow_type, color_type, color)>
560:       arrowSequence;

562:       // FIX: This is a temp fix to include addArrow into the interface; should probably be pushed up to ArrowSequence
563:       struct coneSequence : public arrow_container_type::traits::template ArrowSequence<typename ::boost::multi_index::index<typename arrow_container_type::set_type,coneInd>::type, target_type, color_type, BOOST_MULTI_INDEX_MEMBER(arrow_type, source_type, source)> {
564:       protected:
565:         graph_type& _graph;
566:       public:
567:         typedef typename
568:           arrow_container_type::traits::template ArrowSequence<typename ::boost::multi_index::index<typename arrow_container_type::set_type,coneInd>::type, target_type, color_type, BOOST_MULTI_INDEX_MEMBER(arrow_type, source_type, source)> base_type;
569:         // Encapsulated types
570:         typedef typename base_type::traits traits;
571:         typedef typename base_type::iterator iterator;
572:         typedef typename base_type::reverse_iterator reverse_iterator;
573:         // Basic interface
574:         coneSequence(const coneSequence& seq) : base_type(seq), _graph(seq._graph) {};
575:           coneSequence(graph_type& graph, typename traits::index_type& index, const typename base_type::key_type& k) : base_type(index, k), _graph(graph){};
576:             coneSequence(graph_type& graph, typename traits::index_type& index, const typename base_type::key_type& k, const typename base_type::subkey_type& kk) : base_type(index, k, kk), _graph(graph) {};
577:               virtual ~coneSequence() {};
578: 
579:         // Extended interface
580:         void addArrow(const arrow_type& a) {
581:           // if(a.target != this->key) {
582:           //               throw ALE::Exception("Arrow target mismatch in a coneSequence");
583:           //             }
584:           this->_graph.addArrow(a);
585:         };
586:         void addArrow(const source_type& s, const color_type& c){
587:           this->_graph.addArrow(arrow_type(s,this->key,c));
588:         };
589: 
590:         virtual bool contains(const source_type& s) {
591:           // Check whether a given point is in the index
592:           typename ::boost::multi_index::index<typename ASifter::traits::arrow_container_type::set_type,typename ASifter::traits::arrowInd>::type& index = ::boost::multi_index::get<typename ASifter::traits::arrowInd>(this->_graph._arrows.set);
593:           return (index.find(::boost::make_tuple(s,this->key)) != index.end());
594:         };
595:       };// struct coneSequence
596: 
597:       // FIX: This is a temp fix to include addArrow into the interface; should probably be pushed up to ArrowSequence
598:       struct supportSequence : public arrow_container_type::traits::template ArrowSequence<typename ::boost::multi_index::index<typename arrow_container_type::set_type,supportInd>::type, source_type, color_type, BOOST_MULTI_INDEX_MEMBER(arrow_type, target_type, target)> {
599:       protected:
600:         graph_type& _graph;
601:       public:
602:         typedef typename
603:           arrow_container_type::traits::template ArrowSequence<typename ::boost::multi_index::index<typename arrow_container_type::set_type,supportInd>::type, source_type, color_type, BOOST_MULTI_INDEX_MEMBER(arrow_type, target_type, target)> base_type;
604:         // Encapsulated types
605:         typedef typename base_type::traits traits;
606:         typedef typename base_type::iterator iterator;
607:         typedef typename base_type::reverse_iterator reverse_iterator;
608:         // Basic interface
609:         supportSequence(const supportSequence& seq) : base_type(seq), _graph(seq._graph) {};
610:         supportSequence(graph_type& graph, typename traits::index_type& index, const typename base_type::key_type& k) : base_type(index, k), _graph(graph){};
611:         supportSequence(graph_type& graph, typename traits::index_type& index, const typename base_type::key_type& k, const typename base_type::subkey_type& kk) : base_type(index, k, kk), _graph(graph) {};
612:         virtual ~supportSequence() {};
613: 
614:         // FIX: WARNING: (or a HACK?): we flip the arrow on addition here.
615:         // Fancy interface
616:         void addArrow(const typename arrow_type::flip::type& af) {
617:           this->_graph.addArrow(af.target, af.source, af.color);
618:         };
619:         void addArrow(const target_type& t, const color_type& c){
620:           this->_graph.addArrow(arrow_type(this->key,t,c));
621:         };
622:       };// struct supportSequence

624: 
625:       typedef typename base_container_type::traits::PointSequence baseSequence;
626:       typedef typename cap_container_type::traits::PointSequence  capSequence;
627:       typedef std::set<source_type>   coneSet;
628:       typedef ALE::array<source_type> coneArray;
629:       typedef std::set<target_type>   supportSet;
630:       typedef ALE::array<target_type> supportArray;
631:     } traits;

633:     template <typename OtherSource_, typename OtherTarget_, typename OtherColor_, SifterDef::ColorMultiplicity otherColorMultiplicity,
634:               typename OtherSupportCompare_  = ::boost::multi_index::composite_key_compare<std::less<OtherSource_>, std::less<OtherColor_>, std::less<OtherTarget_> >,
635:               typename OtherSourceCtnr_ = SifterDef::RecContainer<OtherSource_, SifterDef::Rec<OtherSource_> >,
636:               typename OtherTargetCtnr_ = SifterDef::RecContainer<OtherTarget_, SifterDef::Rec<OtherTarget_> > >
637:     struct rebind {
638:       typedef ASifter<OtherSource_, OtherTarget_, OtherColor_, otherColorMultiplicity, OtherSupportCompare_, OtherSourceCtnr_, OtherTargetCtnr_> type;
639:     };

641:   public:
642:     // Debug level
643:     int _debug;
644:     //protected:
645:     typename traits::arrow_container_type _arrows;
646:     typename traits::base_container_type  _base;
647:     typename traits::cap_container_type   _cap;
648:   protected:
649:     MPI_Comm    _comm;
650:     int         _commRank;
651:     int         _commSize;
652:     PetscObject _petscObj;
653:     void __init(MPI_Comm comm) {
654:       static PetscCookie sifterType = -1;
655:       //const char        *id_name = ALE::getClassName<T>();
656:       const char        *id_name = "Sifter";
657:       PetscErrorCode     ierr;

659:       if (sifterType < 0) {
660:         PetscLogClassRegister(&sifterType, id_name);CHKERROR(ierr, "Error in MPI_Comm_rank");
661:       }
662:       this->_comm = comm;
663:       MPI_Comm_rank(this->_comm, &this->_commRank); CHKERROR(ierr, "Error in MPI_Comm_rank");
664:       MPI_Comm_size(this->_comm, &this->_commSize); CHKERROR(ierr, "Error in MPI_Comm_rank");
665:       PetscObjectCreateGeneric(this->_comm, sifterType, id_name, &this->_petscObj);CHKERROR(ierr, "Error in PetscObjectCreate");
666:       //ALE::restoreClassName<T>(id_name);
667:     };
668:     // We store these sequence objects to avoid creating them each query
669:     Obj<typename traits::coneSequence> _coneSeq;
670:     Obj<typename traits::supportSequence> _supportSeq;
671:   public:
672:     //
673:     // Basic interface
674:     //
675:     ASifter(MPI_Comm comm = PETSC_COMM_SELF, const int& debug = 0) : _debug(debug), _petscObj(NULL) {
676:       __init(comm);
677:       this->_coneSeq    = new typename traits::coneSequence(*this, ::boost::multi_index::get<typename traits::coneInd>(this->_arrows.set), typename traits::target_type());
678:       this->_supportSeq = new typename traits::supportSequence(*this, ::boost::multi_index::get<typename traits::supportInd>(this->_arrows.set), typename traits::source_type());
679:    }
680:     virtual ~ASifter() {
681:       if (this->_petscObj) {
683:         PetscObjectDestroy(this->_petscObj); CHKERROR(ierr, "Failed in PetscObjectDestroy");
684:         this->_petscObj = NULL;
685:       }
686:     };
687:     //
688:     // Query methods
689:     //
690:     int         debug()    const {return this->_debug;};
691:     void        setDebug(const int debug) {this->_debug = debug;};
692:     MPI_Comm    comm()     const {return this->_comm;};
693:     int         commSize() const {return this->_commSize;};
694:     int         commRank() const {return this->_commRank;}
695:     PetscObject petscObj() const {return this->_petscObj;};

697:     // FIX: need const_cap, const_base returning const capSequence etc, but those need to have const_iterators, const_begin etc.
698:     Obj<typename traits::capSequence> cap() {
699:       return typename traits::capSequence(::boost::multi_index::get<typename traits::capInd>(this->_cap.set));
700:     };
701:     Obj<typename traits::baseSequence> base() {
702:       return typename traits::baseSequence(::boost::multi_index::get<typename traits::baseInd>(this->_base.set));
703:     };
704:     bool capContains(const typename traits::source_type& p) {
705:       typename traits::capSequence cap(::boost::multi_index::get<typename traits::capInd>(this->_cap.set));

707:       //for(typename traits::capSequence::iterator c_iter = cap.begin(); c_iter != cap.end(); ++c_iter) {
708:       //}
709:       return cap.contains(p);
710:     };
711:     bool baseContains(const typename traits::target_type& p) {
712:       typename traits::baseSequence base(::boost::multi_index::get<typename traits::baseInd>(this->_base.set));

714:       //for(typename traits::capSequence::iterator c_iter = cap.begin(); c_iter != cap.end(); ++c_iter) {
715:       //}
716:       return base.contains(p);
717:     };
718:     // FIX: should probably have cone and const_cone etc, since arrows can be modified through an iterator (modifyColor).
719:     Obj<typename traits::arrowSequence>
720:     arrows(const typename traits::source_type& s, const typename traits::target_type& t) {
721:       return typename traits::arrowSequence(::boost::multi_index::get<typename traits::arrowInd>(this->_arrows.set), s, t);
722:     };
723:     Obj<typename traits::arrowSequence>
724:     arrows(const typename traits::source_type& s) {
725:       return typename traits::arrowSequence(::boost::multi_index::get<typename traits::arrowInd>(this->_arrows.set), s);
726:     };
727: #ifdef SLOW
728:     Obj<typename traits::coneSequence>
729:     cone(const typename traits::target_type& p) {
730:       return typename traits::coneSequence(*this, ::boost::multi_index::get<typename traits::coneInd>(this->_arrows.set), p);
731:     };
732: #else
733:     const Obj<typename traits::coneSequence>&
734:     cone(const typename traits::target_type& p) {
735:       this->_coneSeq->setKey(p);
736:       this->_coneSeq->setUseSubkey(false);
737:       return this->_coneSeq;
738:     };
739: #endif
740:     template<class InputSequence>
741:     Obj<typename traits::coneSet>
742:     cone(const Obj<InputSequence>& points) {
743:       return this->cone(points, typename traits::color_type(), false);
744:     };
745: #ifdef SLOW
746:     Obj<typename traits::coneSequence>
747:     cone(const typename traits::target_type& p, const typename traits::color_type& color) {
748:       return typename traits::coneSequence(*this, ::boost::multi_index::get<typename traits::coneInd>(this->_arrows.set), p, color);
749:     };
750: #else
751:     const Obj<typename traits::coneSequence>&
752:     cone(const typename traits::target_type& p, const typename traits::color_type& color) {
753:       this->_coneSeq->setKey(p);
754:       this->_coneSeq->setSubkey(color);
755:       this->_coneSeq->setUseSubkey(true);
756:       return this->_coneSeq;
757:     };
758: #endif
759:     template<class InputSequence>
760:     Obj<typename traits::coneSet>
761:     cone(const Obj<InputSequence>& points, const typename traits::color_type& color, bool useColor = true) {
762:       Obj<typename traits::coneSet> cone = typename traits::coneSet();
763:       for(typename InputSequence::iterator p_itor = points->begin(); p_itor != points->end(); ++p_itor) {
764:         Obj<typename traits::coneSequence> pCone;
765:         if (useColor) {
766:           pCone = this->cone(*p_itor, color);
767:         } else {
768:           pCone = this->cone(*p_itor);
769:         }
770:         cone->insert(pCone->begin(), pCone->end());
771:       }
772:       return cone;
773:     };
774:     template<typename PointCheck>
775:     bool coneContains(const typename traits::target_type& p, const PointCheck& checker) {
776:       typename traits::coneSequence cone(*this, ::boost::multi_index::get<typename traits::coneInd>(this->_arrows.set), p);

778:       for(typename traits::coneSequence::iterator c_iter = cone.begin(); c_iter != cone.end(); ++c_iter) {
779:         if (checker(*c_iter, p)) return true;
780:       }
781:       return false;
782:     };
783:     template<typename PointProcess>
784:     void coneApply(const typename traits::target_type& p, PointProcess& processor) {
785:       typename traits::coneSequence cone(*this, ::boost::multi_index::get<typename traits::coneInd>(this->_arrows.set), p);

787:       for(typename traits::coneSequence::iterator c_iter = cone.begin(); c_iter != cone.end(); ++c_iter) {
788:         processor(*c_iter, p);
789:       }
790:     };
791: #ifdef SLOW
792:     Obj<typename traits::supportSequence>
793:     support(const typename traits::source_type& p) {
794:       return typename traits::supportSequence(*this, ::boost::multi_index::get<typename traits::supportInd>(this->_arrows.set), p);
795:     };
796: #else
797:     const Obj<typename traits::supportSequence>&
798:     support(const typename traits::source_type& p) {
799:       this->_supportSeq->setKey(p);
800:       this->_supportSeq->setUseSubkey(false);
801:       return this->_supportSeq;
802:     };
803: #endif
804: #ifdef SLOW
805:     Obj<typename traits::supportSequence>
806:     support(const typename traits::source_type& p, const typename traits::color_type& color) {
807:       return typename traits::supportSequence(*this, ::boost::multi_index::get<typename traits::supportInd>(this->_arrows.set), p, color);
808:     };
809: #else
810:     const Obj<typename traits::supportSequence>&
811:     support(const typename traits::source_type& p, const typename traits::color_type& color) {
812:       this->_supportSeq->setKey(p);
813:       this->_supportSeq->setSubkey(color);
814:       this->_supportSeq->setUseSubkey(true);
815:       return this->_supportSeq;
816:     };
817: #endif
818:     template<class InputSequence>
819:     Obj<typename traits::supportSet>
820:     support(const Obj<InputSequence>& sources) {
821:       return this->support(sources, typename traits::color_type(), false);
822:     };
823:     template<class InputSequence>
824:     Obj<typename traits::supportSet>
825:     support(const Obj<InputSequence>& points, const typename traits::color_type& color, bool useColor = true){
826:       Obj<typename traits::supportSet> supp = typename traits::supportSet();
827:       for(typename InputSequence::iterator p_itor = points->begin(); p_itor != points->end(); ++p_itor) {
828:         Obj<typename traits::supportSequence> pSupport;
829:         if (useColor) {
830:           pSupport = this->support(*p_itor, color);
831:         } else {
832:           pSupport = this->support(*p_itor);
833:         }
834:         supp->insert(pSupport->begin(), pSupport->end());
835:       }
836:       return supp;
837:     };
838:     template<typename PointCheck>
839:     bool supportContains(const typename traits::source_type& p, const PointCheck& checker) {
840:       typename traits::supportSequence support(*this, ::boost::multi_index::get<typename traits::supportInd>(this->_arrows.set), p);

842:       for(typename traits::supportSequence::iterator s_iter = support.begin(); s_iter != support.end(); ++s_iter) {
843:         if (checker(*s_iter, p)) return true;
844:       }
845:       return false;
846:     };
847:     template<typename PointProcess>
848:     void supportApply(const typename traits::source_type& p, PointProcess& processor) {
849:       typename traits::supportSequence support(*this, ::boost::multi_index::get<typename traits::supportInd>(this->_arrows.set), p);

851:       for(typename traits::supportSequence::iterator s_iter = support.begin(); s_iter != support.end(); ++s_iter) {
852:         processor(*s_iter, p);
853:       }
854:     };

856:     template<typename ostream_type>
857:     void view(ostream_type& os, const char* label = NULL, bool rawData = false){
858:       int rank = this->commRank();

860:       if(label != NULL) {
861:         os << "["<<rank<<"]Viewing Sifter '" << label << "':" << std::endl;
862:       }
863:       else {
864:         os << "["<<rank<<"]Viewing a Sifter:" << std::endl;
865:       }
866:       if(!rawData) {
867:         os << "cap --> base:" << std::endl;
868:         Obj<typename traits::capSequence> cap = this->cap();
869:         for(typename traits::capSequence::iterator capi = cap->begin(); capi != cap->end(); capi++) {
870:           const Obj<typename traits::supportSequence>& supp = this->support(*capi);

872:           for(typename traits::supportSequence::iterator suppi = supp->begin(); suppi != supp->end(); suppi++) {
873:             os << *capi << "--(" << suppi.color() << ")-->" << *suppi << std::endl;
874:           }
875:         }
876:         os << "base <-- cap:" << std::endl;
877:         Obj<typename traits::baseSequence> base = this->base();
878:         for(typename traits::baseSequence::iterator basei = base->begin(); basei != base->end(); basei++) {
879:           const Obj<typename traits::coneSequence>& cone = this->cone(*basei);

881:           for(typename traits::coneSequence::iterator conei = cone->begin(); conei != cone->end(); conei++) {
882:             os << *basei <<  "<--(" << conei.color() << ")--" << *conei << std::endl;
883:           }
884:         }
885:         os << "cap --> outdegrees:" << std::endl;
886:         for(typename traits::capSequence::iterator capi = cap->begin(); capi != cap->end(); capi++) {
887:           os << *capi <<  "-->" << capi.degree() << std::endl;
888:         }
889:         os << "base <-- indegrees:" << std::endl;
890:         for(typename traits::baseSequence::iterator basei = base->begin(); basei != base->end(); basei++) {
891:           os << *basei <<  "<--" << basei.degree() << std::endl;
892:         }
893:       }
894:       else {
895:         os << "'raw' arrow set:" << std::endl;
896:         for(typename traits::arrow_container_type::set_type::iterator ai = _arrows.set.begin(); ai != _arrows.set.end(); ai++)
897:         {
898:           typename traits::arrow_type arr = *ai;
899:           os << arr << std::endl;
900:         }
901:         os << "'raw' base set:" << std::endl;
902:         for(typename traits::base_container_type::set_type::iterator bi = _base.set.begin(); bi != _base.set.end(); bi++)
903:         {
904:           typename traits::base_container_type::traits::rec_type bp = *bi;
905:           os << bp << std::endl;
906:         }
907:         os << "'raw' cap set:" << std::endl;
908:         for(typename traits::cap_container_type::set_type::iterator ci = _cap.set.begin(); ci != _cap.set.end(); ci++)
909:         {
910:           typename traits::cap_container_type::traits::rec_type cp = *ci;
911:           os << cp << std::endl;
912:         }
913:       }
914:     };
915:     // A parallel viewer
916:     PetscErrorCode view(const char* label = NULL, bool raw = false){
918:       ostringstream txt;
920:       if(this->_debug) {
921:         std::cout << "viewing a Sifter, comm = " << this->comm() << ", PETSC_COMM_SELF = " << PETSC_COMM_SELF << ", commRank = " << this->commRank() << std::endl;
922:       }
923:       if(label != NULL) {
924:         PetscPrintf(this->comm(), "viewing Sifter: '%s'\n", label);
925:       } else {
926:         PetscPrintf(this->comm(), "viewing a Sifter: \n");
927:       }
928:       if(!raw) {
929:         ostringstream txt;
930:         if(this->commRank() == 0) {
931:           txt << "cap --> base:\n";
932:         }
933:         typename traits::capSequence cap   = this->cap();
934:         typename traits::baseSequence base = this->base();
935:         if(cap.empty()) {
936:           txt << "[" << this->commRank() << "]: empty" << std::endl;
937:         }
938:         for(typename traits::capSequence::iterator capi = cap.begin(); capi != cap.end(); capi++) {
939:           const Obj<typename traits::supportSequence>& supp = this->support(*capi);
940:           for(typename traits::supportSequence::iterator suppi = supp->begin(); suppi != supp->end(); suppi++) {
941:             txt << "[" << this->commRank() << "]: " << *capi << "--(" << suppi.color() << ")-->" << *suppi << std::endl;
942:           }
943:         }
944:         //
945:         PetscSynchronizedPrintf(this->comm(), txt.str().c_str()); CHKERROR(ierr, "Error in PetscSynchronizedFlush");
946:         PetscSynchronizedFlush(this->comm());  CHKERROR(ierr, "Error in PetscSynchronizedFlush");
947:         //
948:         ostringstream txt1;
949:         if(this->commRank() == 0) {
950:           //txt1 << "cap <point,degree>:\n";
951:           txt1 << "cap:\n";
952:         }
953:         txt1 << "[" << this->commRank() << "]:  [";
954:         for(typename traits::capSequence::iterator capi = cap.begin(); capi != cap.end(); capi++) {
955:           //txt1 << " <" << *capi << "," << capi.degree() << ">";
956:           txt1 << "  " << *capi;
957:         }
958:         txt1 << " ]" << std::endl;
959:         //
960:         PetscSynchronizedPrintf(this->comm(), txt1.str().c_str()); CHKERROR(ierr, "Error in PetscSynchronizedFlush");
961:         PetscSynchronizedFlush(this->comm());  CHKERROR(ierr, "Error in PetscSynchronizedFlush");
962:         //
963:         ostringstream txt2;
964:         if(this->commRank() == 0) {
965:           //txt2 << "base <point,degree>:\n";
966:           txt2 << "base:\n";
967:         }
968:         txt2 << "[" << this->commRank() << "]:  [";
969:         for(typename traits::baseSequence::iterator basei = base.begin(); basei != base.end(); basei++) {
970:           txt2 << "  " << *basei;
971:           //txt2 << " <" << *basei << "," << basei.degree() << ">";
972:         }
973:         txt2 << " ]" << std::endl;
974:         //
975:         PetscSynchronizedPrintf(this->comm(), txt2.str().c_str()); CHKERROR(ierr, "Error in PetscSynchronizedFlush");
976:         PetscSynchronizedFlush(this->comm());  CHKERROR(ierr, "Error in PetscSynchronizedFlush");
977:       }
978:       else { // if(raw)
979:         ostringstream txt;
980:         if(this->commRank() == 0) {
981:           txt << "'raw' arrow set:" << std::endl;
982:         }
983:         for(typename traits::arrow_container_type::set_type::iterator ai = _arrows.set.begin(); ai != _arrows.set.end(); ai++)
984:         {
985:           typename traits::arrow_type arr = *ai;
986:           txt << "[" << this->commRank() << "]: " << arr << std::endl;
987:         }
988:         PetscSynchronizedPrintf(this->comm(), txt.str().c_str()); CHKERROR(ierr, "Error in PetscSynchronizedFlush");
989:         PetscSynchronizedFlush(this->comm());  CHKERROR(ierr, "Error in PetscSynchronizedFlush");
990:         //
991:         ostringstream txt1;
992:         if(this->commRank() == 0) {
993:           txt1 << "'raw' base set:" << std::endl;
994:         }
995:         for(typename traits::base_container_type::set_type::iterator bi = _base.set.begin(); bi != _base.set.end(); bi++)
996:         {
997:           typename traits::base_container_type::traits::rec_type bp = *bi;
998:           txt1 << "[" << this->commRank() << "]: " << bp << std::endl;
999:         }
1000:         PetscSynchronizedPrintf(this->comm(), txt1.str().c_str()); CHKERROR(ierr, "Error in PetscSynchronizedFlush");
1001:         PetscSynchronizedFlush(this->comm());  CHKERROR(ierr, "Error in PetscSynchronizedFlush");
1002:         //
1003:         ostringstream txt2;
1004:         if(this->commRank() == 0) {
1005:           txt2 << "'raw' cap set:" << std::endl;
1006:         }
1007:         for(typename traits::cap_container_type::set_type::iterator ci = _cap.set.begin(); ci != _cap.set.end(); ci++)
1008:         {
1009:           typename traits::cap_container_type::traits::rec_type cp = *ci;
1010:           txt2 << "[" << this->commRank() << "]: " << cp << std::endl;
1011:         }
1012:         PetscSynchronizedPrintf(this->comm(), txt2.str().c_str()); CHKERROR(ierr, "Error in PetscSynchronizedFlush");
1013:         PetscSynchronizedFlush(this->comm());  CHKERROR(ierr, "Error in PetscSynchronizedFlush");
1014:       }// if(raw)
1015: 
1016:       return(0);
1017:     };
1018:   public:
1019:     //
1020:     // Lattice queries
1021:     //
1022:     template<class targetInputSequence>
1023:     Obj<typename traits::coneSequence> meet(const Obj<targetInputSequence>& targets);
1024:     // unimplemented
1025:     template<class targetInputSequence>
1026:     Obj<typename traits::coneSequence> meet(const Obj<targetInputSequence>& targets, const typename traits::color_type& color);
1027:     // unimplemented
1028:     template<class sourceInputSequence>
1029:     Obj<typename traits::coneSequence> join(const Obj<sourceInputSequence>& sources);
1030:     // unimplemented
1031:     template<class sourceInputSequence>
1032:     Obj<typename traits::coneSequence> join(const Obj<sourceInputSequence>& sources, const typename traits::color_type& color);
1033:   public:
1034:     //
1035:     // Structural manipulation
1036:     //
1037:     void clear() {
1038:       this->_arrows.set.clear(); this->_base.set.clear(); this->_cap.set.clear();
1039:     };
1040:     void addBasePoint(const typename traits::target_type t) {
1041:       /* // Increase degree by 0, which won't affect an existing point and will insert a new point, if necessery
1042:          this->_base.adjustDegree(t,0); */
1043:       this->_base.set.insert(typename traits::targetRec_type(t,0));
1044:     };
1045:     void addBasePoint(const typename traits::targetRec_type b) {
1046:       this->_base.set.insert(b);
1047:     };
1048:     void removeBasePoint(const typename traits::target_type t) {
1049:       if (this->_debug) {std::cout << " Removing " << t << " from the base" << std::endl;}
1050:       // Clear the cone and remove the point from _base
1051:       this->clearCone(t);
1052:       this->_base.removePoint(t);
1053:     };
1054:     void addCapPoint(const typename traits::source_type s) {
1055:       /* // Increase degree by 0, which won't affect an existing point and will insert a new point, if necessery
1056:          this->_cap.adjustDegree(s,0); */
1057:       this->_cap.set.insert(typename traits::sourceRec_type(s,0));
1058:     };
1059:     void addCapPoint(const typename traits::sourceRec_type c) {
1060:       this->_cap.set.insert(c);
1061:     };
1062:     void removeCapPoint(const typename traits::source_type s) {
1063:       if (this->_debug) {std::cout << " Removing " << s << " from the cap" << std::endl;}
1064:       // Clear the support and remove the point from _cap
1065:       this->clearSupport(s);
1066:       this->_cap.removePoint(s);
1067:     };
1068:     virtual void addArrow(const typename traits::source_type& p, const typename traits::target_type& q) {
1069:       this->addArrow(p, q, typename traits::color_type());
1070:     };
1071:     virtual void addArrow(const typename traits::source_type& p, const typename traits::target_type& q, const typename traits::color_type& color) {
1072:       this->addArrow(typename traits::arrow_type(p, q, color));
1073:       //std::cout << "Added " << arrow_type(p, q, color);
1074:     };
1075:     virtual bool checkArrow(const typename traits::arrow_type& a) {
1076:       if (this->_cap.set.find(a.source) == this->_cap.set.end()) return false;
1077:       if (this->_base.set.find(a.target) == this->_base.set.end()) return false;
1078:       return true;
1079:     };
1080:     virtual void addArrow(const typename traits::arrow_type& a, bool restrict = false) {
1081:       if (restrict && !this->checkArrow(a)) return;
1082:       this->_arrows.set.insert(a);
1083:       this->addBasePoint(a.target);
1084:       this->addCapPoint(a.source);
1085:     };
1086:     virtual void removeArrow(const typename traits::arrow_type& a) {
1087:       // First, produce an arrow sequence for the given source, target combination.
1088:       typename traits::arrowSequence::traits::index_type& arrowIndex =
1089:         ::boost::multi_index::get<typename traits::arrowInd>(this->_arrows.set);
1090:       typename traits::arrowSequence::traits::index_type::iterator i,ii,j;
1091:       i = arrowIndex.lower_bound(::boost::make_tuple(a.source,a.target));
1092:       ii = arrowIndex.upper_bound(::boost::make_tuple(a.source, a.target));
1093:       if (this->_debug) {
1094:         std::cout << "removeArrow: attempting to remove arrow:" << a << std::endl;
1095:         std::cout << "removeArrow: candidate arrows are:" << std::endl;
1096:       }
1097:       for(j = i; j != ii; j++) {
1098:         if (this->_debug) {
1099:           std::cout << " " << *j;
1100:         }
1101:         // Find the arrow of right color and remove it
1102:         if(j->color == a.color) {
1103:           if (this->_debug) {
1104:             std::cout << std::endl << "removeArrow: found:" << *j << std::endl;
1105:           }
1106:           /* this->_base.adjustDegree(a.target, -1); this->_cap.adjustDegree(a.source,-1); */
1107:           arrowIndex.erase(j);
1108:           break;
1109:         }
1110:       }
1111:     };

1113:     void addCone(const typename traits::source_type& source, const typename traits::target_type& target){
1114:       this->addArrow(source, target);
1115:     };
1116:     template<class sourceInputSequence>
1117:     void addCone(const Obj<sourceInputSequence>& sources, const typename traits::target_type& target) {
1118:       this->addCone(sources, target, typename traits::color_type());
1119:     };
1120:     void addCone(const typename traits::source_type& source, const typename traits::target_type& target, const typename traits::color_type& color) {
1121:       this->addArrow(source, target, color);
1122:     };
1123:     template<class sourceInputSequence>
1124:     void
1125:     addCone(const Obj<sourceInputSequence>& sources, const typename traits::target_type& target, const typename traits::color_type& color){
1126:       if (this->_debug > 1) {std::cout << "Adding a cone " << std::endl;}
1127:       for(typename sourceInputSequence::iterator iter = sources->begin(); iter != sources->end(); ++iter) {
1128:         if (this->_debug > 1) {std::cout << "Adding arrow from " << *iter << " to " << target << "(" << color << ")" << std::endl;}
1129:         this->addArrow(*iter, target, color);
1130:       }
1131:     };
1132:     void clearCone(const typename traits::target_type& t) {
1133:       clearCone(t, typename traits::color_type(), false);
1134:     };

1136:     void clearCone(const typename traits::target_type& t, const typename traits::color_type&  color, bool useColor = true) {
1137:       // Use the cone sequence types to clear the cone
1138:       typename traits::coneSequence::traits::index_type& coneIndex =
1139:         ::boost::multi_index::get<typename traits::coneInd>(this->_arrows.set);
1140:       typename traits::coneSequence::traits::index_type::iterator i, ii, j;
1141:       if (this->_debug > 20) {
1142:         std::cout << "clearCone: removing cone over " << t;
1143:         if(useColor) {
1144:           std::cout << " with color" << color << std::endl;
1145:           const Obj<typename traits::coneSequence>& cone = this->cone(t,color);
1146:           std::cout << "[";
1147:           for(typename traits::coneSequence::iterator ci = cone->begin(); ci != cone->end(); ci++) {
1148:             std::cout << "  " << ci.arrow();
1149:           }
1150:           std::cout << "]" << std::endl;
1151:         }
1152:         else {
1153:           std::cout << std::endl;
1154:           const Obj<typename traits::coneSequence>& cone = this->cone(t);
1155:           std::cout << "[";
1156:           for(typename traits::coneSequence::iterator ci = cone->begin(); ci != cone->end(); ci++) {
1157:             std::cout << "  " << ci.arrow();
1158:           }
1159:           std::cout << "]" << std::endl;
1160:         }
1161:       }
1162:       if (useColor) {
1163:         i = coneIndex.lower_bound(::boost::make_tuple(t,color));
1164:         ii = coneIndex.upper_bound(::boost::make_tuple(t,color));
1165:       } else {
1166:         i = coneIndex.lower_bound(::boost::make_tuple(t));
1167:         ii = coneIndex.upper_bound(::boost::make_tuple(t));
1168:       }
1169:       for(j = i; j != ii; j++){
1170:         // Adjust the degrees before removing the arrow; use a different iterator, since we'll need i,ii to do the arrow erasing.
1171:         if (this->_debug) {
1172:           std::cout << "clearCone: adjusting degrees for endpoints of arrow: " << *j << std::endl;
1173:         }
1174:         /* this->_cap.adjustDegree(j->source, -1);
1175:            this->_base.adjustDegree(j->target, -1); */
1176:       }
1177:       coneIndex.erase(i,ii);
1178:     };// clearCone()

1180:     template<class InputSequence>
1181:     void
1182:     restrictBase(const Obj<InputSequence>& points) {
1183:       typename traits::baseSequence base = this->base();
1184:       typename std::set<typename traits::target_type> remove;
1185: 
1186:       for(typename traits::baseSequence::iterator bi = base.begin(); bi != base.end(); bi++) {
1187:         // Check whether *bi is in points, if it is NOT, remove it
1188:         //           if (!points->contains(*bi)) {
1189:         if (points->find(*bi) == points->end()) {
1190:           //             this->removeBasePoint(*bi);
1191:           remove.insert(*bi);
1192:         }
1193:       }
1194:       //FIX
1195:       for(typename std::set<typename traits::target_type>::iterator r_iter = remove.begin(); r_iter != remove.end(); ++r_iter) {
1196:         this->removeBasePoint(*r_iter);
1197:       }
1198:     };

1200:     template<class InputSequence>
1201:     void
1202:     excludeBase(const Obj<InputSequence>& points) {
1203:       for(typename InputSequence::iterator pi = points->begin(); pi != points->end(); pi++) {
1204:         this->removeBasePoint(*pi);
1205:       }
1206:     };

1208:     template<class InputSequence>
1209:     void
1210:     restrictCap(const Obj<InputSequence>& points) {
1211:       typename traits::capSequence cap = this->cap();
1212:       for(typename traits::capSequence::iterator ci = cap.begin(); ci != cap.end(); ci++) {
1213:         // Check whether *ci is in points, if it is NOT, remove it
1214:         if(points->find(*ci) == points->end()) {
1215:           this->removeCapPoint(*ci);
1216:         }
1217:       }
1218:     };

1220:     template<class InputSequence>
1221:     void
1222:     excludeCap(const Obj<InputSequence>& points) {
1223:       for(typename InputSequence::iterator pi = points->begin(); pi != points->end(); pi++) {
1224:         this->removeCapPoint(*pi);
1225:       }
1226:     };

1228:     void clearSupport(const typename traits::source_type& s) {
1229:       clearSupport(s, typename traits::color_type(), false);
1230:     };
1231:     void clearSupport(const typename traits::source_type& s, const typename traits::color_type&  color, bool useColor = true) {
1232:       // Use the cone sequence types to clear the cone
1233:       typename
1234:         traits::supportSequence::traits::index_type& suppIndex = ::boost::multi_index::get<typename traits::supportInd>(this->_arrows.set);
1235:       typename traits::supportSequence::traits::index_type::iterator i, ii, j;
1236:       if (useColor) {
1237:         i = suppIndex.lower_bound(::boost::make_tuple(s,color));
1238:         ii = suppIndex.upper_bound(::boost::make_tuple(s,color));
1239:       } else {
1240:         i = suppIndex.lower_bound(::boost::make_tuple(s));
1241:         ii = suppIndex.upper_bound(::boost::make_tuple(s));
1242:       }
1243:       for(j = i; j != ii; j++){
1244:         // Adjust the degrees before removing the arrow
1245:         /* this->_cap.adjustDegree(j->source, -1);
1246:            this->_base.adjustDegree(j->target, -1); */
1247:       }
1248:       suppIndex.erase(i,ii);
1249:     };
1250:     void setCone(const typename traits::source_type& source, const typename traits::target_type& target){
1251:       this->clearCone(target, typename traits::color_type(), false); this->addCone(source, target);
1252:     };
1253:     template<class sourceInputSequence>
1254:     void setCone(const Obj<sourceInputSequence>& sources, const typename traits::target_type& target) {
1255:       this->clearCone(target, typename traits::color_type(), false); this->addCone(sources, target, typename traits::color_type());
1256:     };
1257:     void setCone(const typename traits::source_type& source, const typename traits::target_type& target, const typename traits::color_type& color) {
1258:       this->clearCone(target, color, true); this->addCone(source, target, color);
1259:     };
1260:     template<class sourceInputSequence>
1261:     void setCone(const Obj<sourceInputSequence>& sources, const typename traits::target_type& target, const typename traits::color_type& color){
1262:       this->clearCone(target, color, true); this->addCone(sources, target, color);
1263:     };
1264:     template<class targetInputSequence>
1265:     void addSupport(const typename traits::source_type& source, const Obj<targetInputSequence >& targets);
1266:     // Unimplemented
1267:     template<class targetInputSequence>
1268:     void addSupport(const typename traits::source_type& source, const Obj<targetInputSequence>& targets, const typename traits::color_type& color);
1269:     template<typename Sifter_>
1270:     void add(const Obj<Sifter_>& cbg, bool restrict = false) {
1271:       typename ::boost::multi_index::index<typename Sifter_::traits::arrow_container_type::set_type, typename Sifter_::traits::arrowInd>::type& aInd = ::boost::multi_index::get<typename Sifter_::traits::arrowInd>(cbg->_arrows.set);
1272: 
1273:       for(typename ::boost::multi_index::index<typename Sifter_::traits::arrow_container_type::set_type, typename Sifter_::traits::arrowInd>::type::iterator a_iter = aInd.begin(); a_iter != aInd.end(); ++a_iter) {
1274:         this->addArrow(*a_iter, restrict);
1275:       }
1276:       if (!restrict) {
1277:         typename ::boost::multi_index::index<typename Sifter_::traits::base_container_type::set_type, typename Sifter_::traits::baseInd>::type& bInd = ::boost::multi_index::get<typename Sifter_::traits::baseInd>(this->_base.set);
1278: 
1279:         for(typename ::boost::multi_index::index<typename Sifter_::traits::base_container_type::set_type, typename Sifter_::traits::baseInd>::type::iterator b_iter = bInd.begin(); b_iter != bInd.end(); ++b_iter) {
1280:           this->addBasePoint(*b_iter);
1281:         }
1282:         typename ::boost::multi_index::index<typename Sifter_::traits::cap_container_type::set_type, typename Sifter_::traits::capInd>::type& cInd = ::boost::multi_index::get<typename Sifter_::traits::capInd>(this->_cap.set);
1283: 
1284:         for(typename ::boost::multi_index::index<typename Sifter_::traits::cap_container_type::set_type, typename Sifter_::traits::capInd>::type::iterator c_iter = cInd.begin(); c_iter != cInd.end(); ++c_iter) {
1285:           this->addCapPoint(*c_iter);
1286:         }
1287:       }
1288:     };
1289:   }; // class ASifter

1291:   // A UniSifter aka Sifter
1292:   template <typename Source_, typename Target_, typename Color_,
1293:             typename SupportCompare_ = ::boost::multi_index::composite_key_compare<std::less<Source_>, std::less<Color_>, std::less<Target_> >,
1294:             typename SourceCtnr_ = SifterDef:: RecContainer<Source_, SifterDef::Rec<Source_> >, typename TargetCtnr_= SifterDef::RecContainer<Target_, SifterDef::Rec<Target_> > >
1295:   class Sifter : public ASifter<Source_, Target_, Color_, SifterDef::uniColor, SupportCompare_, SourceCtnr_, TargetCtnr_> {
1296:   public:
1297:       typedef typename ASifter<Source_, Target_, Color_, SifterDef::uniColor, SupportCompare_, SourceCtnr_, TargetCtnr_>::traits       traits;
1298:     template <typename OtherSource_, typename OtherTarget_, typename OtherColor_,
1299:               typename OtherSupportCompare_  = ::boost::multi_index::composite_key_compare<std::less<OtherSource_>, std::less<OtherColor_>, std::less<OtherTarget_> >,
1300:               typename OtherSourceCtnr_ = SifterDef::RecContainer<OtherSource_, SifterDef::Rec<OtherSource_> >,
1301:               typename OtherTargetCtnr_ = SifterDef::RecContainer<OtherTarget_, SifterDef::Rec<OtherTarget_> >      >
1302:     struct rebind {
1303:       typedef Sifter<OtherSource_, OtherTarget_, OtherColor_, OtherSupportCompare_, OtherSourceCtnr_, OtherTargetCtnr_> type;
1304:     };
1305:     // Re-export some typedefs expected by CoSifter
1306:     typedef typename traits::arrow_type                                             Arrow_;
1307:     typedef typename traits::coneSequence                                           coneSequence;
1308:     typedef typename traits::supportSequence                                        supportSequence;
1309:     typedef typename traits::baseSequence                                           baseSequence;
1310:     typedef typename traits::capSequence                                            capSequence;
1311:     // Basic interface
1312:     Sifter(MPI_Comm comm = PETSC_COMM_SELF, const int& debug = 0) :
1313:       ASifter<Source_, Target_, Color_, SifterDef::uniColor, SupportCompare_, SourceCtnr_, TargetCtnr_>(comm, debug) {};

1315:     const typename traits::color_type&
1316:     getColor(const typename traits::source_type& s, const typename traits::target_type& t, bool fail = true) {
1317:       typedef typename ::boost::multi_index::index<typename traits::arrow_container_type::set_type,typename traits::arrowInd>::type index_type;

1319:       const index_type& _index = ::boost::multi_index::get<typename traits::arrowInd>(this->_arrows.set);
1320: #if 0
1321:       ::boost::tuple<typename traits::source_type, typename traits::target_type> key = ::boost::make_tuple(s, t);
1322:       typename index_type::iterator begin = _index.lower_bound(key);
1323:       if(begin != _index.upper_bound(key)) {
1324:         return begin->color;
1325:       }
1326: #else
1327:       const typename index_type::iterator begin = _index.find(::boost::make_tuple(s, t));
1328:       if (begin != _index.end()) {
1329:         return begin->color;
1330:       }
1331: #endif
1332: //       typename traits::arrowSequence arr(::boost::multi_index::get<typename traits::arrowInd>(this->_arrows.set), s, t);
1333: //       if(arr.begin() != arr.end()) {
1334: //         return arr.begin().color();
1335: //       }
1336:       if (fail) {
1337:         ostringstream o;
1338:         o << "Arrow " << s << " --> " << t << " not present";
1339:         throw ALE::Exception(o.str().c_str());
1340:       } else {
1341:         static typename traits::color_type c;
1342:         return c;
1343:       }
1344:     };

1346:     template<typename ColorChanger>
1347:     void modifyColor(const typename traits::source_type& s, const typename traits::target_type& t, const ColorChanger& changeColor) {
1348:       typename ::boost::multi_index::index<typename traits::arrow_container_type::set_type, typename traits::arrowInd>::type& index =
1349:         ::boost::multi_index::get<typename traits::arrowInd>(this->_arrows.set);
1350:       typename ::boost::multi_index::index<typename traits::arrow_container_type::set_type, typename traits::arrowInd>::type::iterator i =
1351:         index.find(::boost::make_tuple(s,t));
1352:       if (i != index.end()) {
1353:         index.modify(i, changeColor);
1354:       } else {
1355:         typename traits::arrow_type a(s, t, typename traits::color_type());
1356:         changeColor(a);
1357:         this->addArrow(a);
1358:       }
1359:     };

1361:     struct ColorSetter {
1362:       ColorSetter(const typename traits::color_type& color) : _color(color) {};
1363:       void operator()(typename traits::arrow_type& p) const {
1364:         p.color = _color;
1365:       }
1366:     private:
1367:       const typename traits::color_type& _color;
1368:     };

1370:     void setColor(const typename traits::source_type& s, const typename traits::target_type& t, const typename traits::color_type& color) {
1371:       ColorSetter colorSetter(color);
1372:       typename ::boost::multi_index::index<typename traits::arrow_container_type::set_type, typename traits::arrowInd>::type& index =
1373:         ::boost::multi_index::get<typename traits::arrowInd>(this->_arrows.set);
1374:       typename ::boost::multi_index::index<typename traits::arrow_container_type::set_type, typename traits::arrowInd>::type::iterator i =
1375:         index.find(::boost::make_tuple(s,t));
1376:       if (i != index.end()) {
1377:         index.modify(i, colorSetter);
1378:       } else {
1379:         typename traits::arrow_type a(s, t, color);
1380:         this->addArrow(a);
1381:       }
1382:     };
1383:   };// class Sifter

1385: } // namespace ALE

1387: #endif