Actual source code: LabelSifter.hh

  1: #ifndef included_ALE_LabelSifter_hh
  2: #define included_ALE_LabelSifter_hh

  4: #include <iostream>

  6: #ifndef  included_ALE_hh
  7: #include <ALE.hh>
  8: #endif

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

 72:       // reverse_iterator is the reverse of iterator
 73:       class reverse_iterator : public iterator_base {
 74:       public:
 75:         // Standard iterator typedefs
 76:         typedef typename iterator_base::iterator_category  iterator_category;
 77:         typedef typename iterator_base::value_type         value_type;
 78:         typedef typename iterator_base::extractor_type     extractor_type;
 79:         typedef typename iterator_base::difference_type    difference_type;
 80:         typedef typename iterator_base::pointer            pointer;
 81:         typedef typename iterator_base::reference          reference;
 82:         // Underlying iterator type
 83:         typedef typename iterator_base::itor_type          itor_type;
 84:       public:
 85:         reverse_iterator(const itor_type& itor) : iterator_base(itor) {};
 86:         virtual ~reverse_iterator() {};
 87:         //
 88:         virtual reverse_iterator     operator++() {--this->_itor; return *this;};
 89:         virtual reverse_iterator     operator++(int n) {reverse_iterator tmp(this->_itor); --this->_itor; return tmp;};
 90:       };
 91:     }; // class ReversibleIndexSequenceTraits

 93:     //
 94:     // Arrow & ArrowContainer definitions
 95:     //
 96:     template<typename Source_, typename Target_>
 97:     struct  Arrow { //: public ALE::def::Arrow<Source_, Target_, Color_> {
 98:       typedef Arrow   arrow_type;
 99:       typedef Source_ source_type;
100:       typedef Target_ target_type;
101:       source_type source;
102:       target_type target;
103:       Arrow(const source_type& s, const target_type& t) : source(s), target(t) {};
104:       // Flipping
105:       template <typename OtherSource_, typename OtherTarget_>
106:       struct rebind {
107:         typedef Arrow<OtherSource_, OtherTarget_> type;
108:       };
109:       struct flip {
110:         typedef Arrow<target_type, source_type> type;
111:         type arrow(const arrow_type& a) { return type(a.target, a.source);};
112:       };

114:       // Printing
115:       friend std::ostream& operator<<(std::ostream& os, const Arrow& a) {
116:         os << a.source << " ----> " << a.target;
117:         return os;
118:       }

120:       // Arrow modifiers
121:       struct sourceChanger {
122:         sourceChanger(const source_type& newSource) : _newSource(newSource) {};
123:         void operator()(arrow_type& a) {a.source = this->_newSource;}
124:       private:
125:         source_type _newSource;
126:       };

128:       struct targetChanger {
129:         targetChanger(const target_type& newTarget) : _newTarget(newTarget) {};
130:         void operator()(arrow_type& a) { a.target = this->_newTarget;}
131:       private:
132:         const target_type _newTarget;
133:       };
134:     };// struct Arrow
135: 

137:     template<typename Source_, typename Target_>
138:     struct ArrowContainerTraits {
139:     public:
140:       //
141:       // Encapsulated types
142:       //
143:       typedef Arrow<Source_,Target_>           arrow_type;
144:       typedef typename arrow_type::source_type source_type;
145:       typedef typename arrow_type::target_type target_type;
146:       // Index tags
147:       struct                                   sourceTargetTag{};
148:       struct                                   targetSourceTag{};

150:       // Sequence traits and sequence types
151:       template <typename Index_, typename Key_, typename SubKey_, typename ValueExtractor_>
152:       class ArrowSequence {
153:         // ArrowSequence implements ReversibleIndexSequencTraits with Index_ and ValueExtractor_ types.
154:         // A Key_ object and an optional SubKey_ object are used to extract the index subset.
155:       public:
156:         typedef ReversibleIndexSequenceTraits<Index_, ValueExtractor_>  traits;
157:         //typedef source_type                                             source_type;
158:         //typedef target_type                                             target_type;
159:         //typedef arrow_type                                              arrow_type;
160:         //
161:         typedef Key_                                                    key_type;
162:         typedef SubKey_                                                 subkey_type;
163:       protected:
164:         typename traits::index_type&                                    _index;
165:         key_type                                                  key;
166:         subkey_type                                               subkey;
167:         bool                                                      useSubkey;
168:       public:
169:         // Need to extend the inherited iterators to be able to extract arrow color
170:         class iterator : public traits::iterator {
171:         public:
172:           iterator(const typename traits::iterator::itor_type& itor) : traits::iterator(itor) {};
173:           virtual const source_type& source() const {return this->_itor->source;};
174:           virtual const target_type& target() const {return this->_itor->target;};
175:           virtual const arrow_type&  arrow()  const {return *(this->_itor);};
176:         };
177:         class reverse_iterator : public traits::reverse_iterator {
178:         public:
179:           reverse_iterator(const typename traits::reverse_iterator::itor_type& itor) : traits::reverse_iterator(itor) {};
180:           virtual const source_type& source() const {return this->_itor->source;};
181:           virtual const target_type& target() const {return this->_itor->target;};
182:           virtual const arrow_type&  arrow()  const {return *(this->_itor);};
183:         };
184:       public:
185:         //
186:         // Basic ArrowSequence interface
187:         //
188:         ArrowSequence(const ArrowSequence& seq) : _index(seq._index), key(seq.key), subkey(seq.subkey), useSubkey(seq.useSubkey) {};
189:         ArrowSequence(typename traits::index_type& index, const key_type& k) :
190:           _index(index), key(k), subkey(subkey_type()), useSubkey(0) {};
191:         ArrowSequence(typename traits::index_type& index, const key_type& k, const subkey_type& kk) :
192:           _index(index), key(k), subkey(kk), useSubkey(1){};
193:         virtual ~ArrowSequence() {};

195:         void setKey(const key_type& key) {this->key = key;};
196:         void setSubkey(const subkey_type& subkey) {this->subkey = subkey;};
197:         void setUseSubkey(const bool& useSubkey) {this->useSubkey = useSubkey;};
198: 
199:         virtual bool         empty() {return this->_index.empty();};

201:         virtual typename traits::index_type::size_type  size()  {
202:           if (this->useSubkey) {
203:             return this->_index.count(::boost::make_tuple(this->key,this->subkey));
204:           } else {
205:             return this->_index.count(::boost::make_tuple(this->key));
206:           }
207:         };

209:         virtual iterator begin() {
210:           if (this->useSubkey) {
211:             return iterator(this->_index.lower_bound(::boost::make_tuple(this->key,this->subkey)));
212:           } else {
213:             return iterator(this->_index.lower_bound(::boost::make_tuple(this->key)));
214:           }
215:         };
216: 
217:         virtual iterator end() {
218:           if (this->useSubkey) {
219:             return iterator(this->_index.upper_bound(::boost::make_tuple(this->key,this->subkey)));
220:           } else {
221:             return iterator(this->_index.upper_bound(::boost::make_tuple(this->key)));
222:           }
223:         };
224: 
225:         virtual reverse_iterator rbegin() {
226:           if (this->useSubkey) {
227:             return reverse_iterator(--this->_index.upper_bound(::boost::make_tuple(this->key,this->subkey)));
228:           } else {
229:             return reverse_iterator(--this->_index.upper_bound(::boost::make_tuple(this->key)));
230:           }
231:         };
232: 
233:         virtual reverse_iterator rend() {
234:           if (this->useSubkey) {
235:             return reverse_iterator(--this->_index.lower_bound(::boost::make_tuple(this->key,this->subkey)));
236:           } else {
237:             return reverse_iterator(--this->_index.lower_bound(::boost::make_tuple(this->key)));
238:           }
239:         };

241:         template<typename ostream_type>
242:         void view(ostream_type& os, const char* label = NULL){
243:           if(label != NULL) {
244:             os << "Viewing " << label << " sequence:" << std::endl;
245:           }
246:           os << "[";
247:           for(iterator i = this->begin(); i != this->end(); i++) {
248:             os << " (" << *i << ")";
249:           }
250:           os << " ]" << std::endl;
251:         };
252:       };// class ArrowSequence
253:     };// class ArrowContainerTraits
254: 

256:     // The specialized ArrowContainer types distinguish the cases of unique and multiple colors of arrows on
257:     // for each (source,target) pair (i.e., a single arrow, or multiple arrows between each pair of points).
258:     template<typename Source_, typename Target_, typename Alloc_ = ALE_ALLOCATOR<typename ArrowContainerTraits<Source_, Target_>::arrow_type> >
259:     struct ArrowContainer {
260:       // Define container's encapsulated types
261:       typedef ArrowContainerTraits<Source_, Target_> traits;
262:       // need to def arrow_type locally, since BOOST_MULTI_INDEX_MEMBER barfs when first template parameter starts with 'typename'
263:       typedef typename traits::arrow_type                                   arrow_type;

265:       // multi-index set type -- arrow set
266:       typedef ::boost::multi_index::multi_index_container<
267:         typename traits::arrow_type,
268:         ::boost::multi_index::indexed_by<
269:           ::boost::multi_index::ordered_unique<
270:             ::boost::multi_index::tag<typename traits::sourceTargetTag>,
271:             ::boost::multi_index::composite_key<
272:               typename traits::arrow_type,
273:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::source_type, source),
274:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::target_type, target)
275:             >
276:           >,
277:           ::boost::multi_index::ordered_unique<
278:             ::boost::multi_index::tag<typename traits::targetSourceTag>,
279:             ::boost::multi_index::composite_key<
280:               typename traits::arrow_type,
281:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::target_type, target),
282:               BOOST_MULTI_INDEX_MEMBER(arrow_type, typename traits::source_type, source)
283:             >
284:           >
285:         >,
286:         Alloc_
287:       > set_type;
288:       // multi-index set of arrow records
289:       set_type set;
290:     }; // class ArrowContainer
291:   }; // namespace NewSifterDef

293:   template<typename Source_, typename Target_, typename Alloc_ = ALE_ALLOCATOR<typename NewSifterDef::ArrowContainer<Source_, Target_>::traits::arrow_type> >
294:   class LabelSifter { // class Sifter
295:   public:
296:     typedef struct {
297:       typedef LabelSifter<Source_, Target_, Alloc_> graph_type;
298:       // Encapsulated container types
299:       typedef NewSifterDef::ArrowContainer<Source_, Target_, Alloc_>                 arrow_container_type;
300:       // Types associated with records held in containers
301:       typedef typename arrow_container_type::traits::arrow_type                      arrow_type;
302:       typedef typename arrow_container_type::traits::source_type                     source_type;
303:       typedef typename arrow_container_type::traits::target_type                     target_type;
304:       // Convenient tag names
305:       typedef typename arrow_container_type::traits::sourceTargetTag                 supportInd;
306:       typedef typename arrow_container_type::traits::targetSourceTag                 coneInd;
307:       typedef typename arrow_container_type::traits::sourceTargetTag                 arrowInd;
308:       //
309:       // Return types
310:       //
311:       typedef typename
312:       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, source_type, source)>
313:       arrowSequence;

315:       // FIX: This is a temp fix to include addArrow into the interface; should probably be pushed up to ArrowSequence
316:       struct coneSequence : public arrow_container_type::traits::template ArrowSequence<typename ::boost::multi_index::index<typename arrow_container_type::set_type,coneInd>::type, target_type, source_type, BOOST_MULTI_INDEX_MEMBER(arrow_type, source_type, source)> {
317:       protected:
318:         graph_type& _graph;
319:       public:
320:         typedef typename
321:           arrow_container_type::traits::template ArrowSequence<typename ::boost::multi_index::index<typename arrow_container_type::set_type,coneInd>::type, target_type, source_type, BOOST_MULTI_INDEX_MEMBER(arrow_type, source_type, source)> base_type;
322:         // Encapsulated types
323:         typedef typename base_type::traits traits;
324:         typedef typename base_type::iterator iterator;
325:         typedef typename base_type::reverse_iterator reverse_iterator;
326:         // Basic interface
327:         coneSequence(const coneSequence& seq) : base_type(seq), _graph(seq._graph) {};
328:           coneSequence(graph_type& graph, typename traits::index_type& index, const typename base_type::key_type& k) : base_type(index, k), _graph(graph){};
329:             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) {};
330:               virtual ~coneSequence() {};
331: 
332:         // Extended interface
333:         void addArrow(const arrow_type& a) {
334:           // if(a.target != this->key) {
335:           //               throw ALE::Exception("Arrow target mismatch in a coneSequence");
336:           //             }
337:           this->_graph.addArrow(a);
338:         };
339:         void addArrow(const source_type& s){
340:           this->_graph.addArrow(arrow_type(s,this->key));
341:         };
342: 
343:         virtual bool contains(const source_type& s) {
344:           // Check whether a given point is in the index
345:           typename ::boost::multi_index::index<typename LabelSifter::traits::arrow_container_type::set_type,typename LabelSifter::traits::arrowInd>::type& index = ::boost::multi_index::get<typename LabelSifter::traits::arrowInd>(this->_graph._arrows.set);
346:           return (index.find(::boost::make_tuple(s,this->key)) != index.end());
347:         };
348:       };// struct coneSequence
349: 
350:       // FIX: This is a temp fix to include addArrow into the interface; should probably be pushed up to ArrowSequence
351:       struct supportSequence : public arrow_container_type::traits::template ArrowSequence<typename ::boost::multi_index::index<typename arrow_container_type::set_type,supportInd>::type, source_type, target_type, BOOST_MULTI_INDEX_MEMBER(arrow_type, target_type, target)> {
352:       protected:
353:         graph_type& _graph;
354:       public:
355:         typedef typename
356:           arrow_container_type::traits::template ArrowSequence<typename ::boost::multi_index::index<typename arrow_container_type::set_type,supportInd>::type, source_type, target_type, BOOST_MULTI_INDEX_MEMBER(arrow_type, target_type, target)> base_type;
357:         // Encapsulated types
358:         typedef typename base_type::traits traits;
359:         typedef typename base_type::iterator iterator;
360:         typedef typename base_type::iterator const_iterator;
361:         typedef typename base_type::reverse_iterator reverse_iterator;
362:         // Basic interface
363:         supportSequence(const supportSequence& seq) : base_type(seq), _graph(seq._graph) {};
364:         supportSequence(graph_type& graph, typename traits::index_type& index, const typename base_type::key_type& k) : base_type(index, k), _graph(graph){};
365:         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) {};
366:         virtual ~supportSequence() {};
367: 
368:         // FIX: WARNING: (or a HACK?): we flip the arrow on addition here.
369:         // Fancy interface
370:         void addArrow(const typename arrow_type::flip::type& af) {
371:           this->_graph.addArrow(af.target, af.source);
372:         };
373:         void addArrow(const target_type& t){
374:           this->_graph.addArrow(arrow_type(this->key,t));
375:         };
376:       };// struct supportSequence

378:       typedef std::set<source_type, std::less<source_type>, typename Alloc_::template rebind<source_type>::other> coneSet;
379:       typedef ALE::array<source_type> coneArray;
380:       typedef std::set<target_type, std::less<target_type>, typename Alloc_::template rebind<source_type>::other> supportSet;
381:       typedef ALE::array<target_type> supportArray;
382:     } traits;

384:     template <typename OtherSource_, typename OtherTarget_>
385:     struct rebind {
386:       typedef LabelSifter<OtherSource_, OtherTarget_> type;
387:     };

389:     typedef typename traits::source_type     source_type;
390:     typedef typename traits::target_type     target_type;
391:     typedef typename traits::coneSequence    coneSequence;
392:     typedef typename traits::supportSequence supportSequence;
393:     typedef std::set<int>                    capSequence;
394:   public:
395:     // Debug level
396:     int _debug;
397:     //protected:
398:     typename traits::arrow_container_type _arrows;
399:   protected:
400:     MPI_Comm    _comm;
401:     int         _commRank;
402:     int         _commSize;
403:     PetscObject _petscObj;
404:     void __init(MPI_Comm comm) {
405:       static PetscCookie sifterType = -1;
406:       //const char        *id_name = ALE::getClassName<T>();
407:       const char        *id_name = "LabelSifter";
408:       PetscErrorCode     ierr;

410:       if (sifterType < 0) {
411:         PetscCookieRegister(id_name,&sifterType);CHKERROR(ierr, "Error in MPI_Comm_rank");
412:       }
413:       this->_comm = comm;
414:       MPI_Comm_rank(this->_comm, &this->_commRank); CHKERROR(ierr, "Error in MPI_Comm_rank");
415:       MPI_Comm_size(this->_comm, &this->_commSize); CHKERROR(ierr, "Error in MPI_Comm_rank");
416: #ifdef USE_PETSC_OBJ
417:       PetscObjectCreateGeneric(this->_comm, sifterType, id_name, &this->_petscObj);CHKERROR(ierr, "Error in PetscObjectCreate");
418: #endif
419:       //ALE::restoreClassName<T>(id_name);
420:     };
421:     // We store these sequence objects to avoid creating them each query
422:     Obj<typename traits::coneSequence> _coneSeq;
423:     Obj<typename traits::supportSequence> _supportSeq;
424:   public:
425:     //
426:     // Basic interface
427:     //
428:     LabelSifter(MPI_Comm comm = PETSC_COMM_SELF, const int& debug = 0) : _debug(debug), _petscObj(NULL) {
429:       __init(comm);
430:       this->_coneSeq    = new typename traits::coneSequence(*this, ::boost::multi_index::get<typename traits::coneInd>(this->_arrows.set), typename traits::target_type());
431:       this->_supportSeq = new typename traits::supportSequence(*this, ::boost::multi_index::get<typename traits::supportInd>(this->_arrows.set), typename traits::source_type());
432:    }
433:     virtual ~LabelSifter() {
434: #ifdef USE_PETSC_OBJ
435:       if (this->_petscObj) {
437:         PetscObjectDestroy(this->_petscObj); CHKERROR(ierr, "Failed in PetscObjectDestroy");
438:         this->_petscObj = NULL;
439:       }
440: #endif
441:     };
442:     //
443:     // Query methods
444:     //
445:     int         debug()    const {return this->_debug;};
446:     void        setDebug(const int debug) {this->_debug = debug;};
447:     MPI_Comm    comm()     const {return this->_comm;};
448:     int         commSize() const {return this->_commSize;};
449:     int         commRank() const {return this->_commRank;}
450: #ifdef USE_PETSC_OBJ
451:     PetscObject petscObj() const {return this->_petscObj;};
452: #endif

454:     // FIX: should probably have cone and const_cone etc, since arrows can be modified through an iterator (modifyColor).
455:     Obj<typename traits::arrowSequence>
456:     arrows(const typename traits::source_type& s, const typename traits::target_type& t) {
457:       return typename traits::arrowSequence(::boost::multi_index::get<typename traits::arrowInd>(this->_arrows.set), s, t);
458:     };
459:     Obj<typename traits::arrowSequence>
460:     arrows(const typename traits::source_type& s) {
461:       return typename traits::arrowSequence(::boost::multi_index::get<typename traits::arrowInd>(this->_arrows.set), s);
462:     };
463: #ifdef SLOW
464:     Obj<typename traits::coneSequence>
465:     cone(const typename traits::target_type& p) {
466:       return typename traits::coneSequence(*this, ::boost::multi_index::get<typename traits::coneInd>(this->_arrows.set), p);
467:     };
468: #else
469:     const Obj<typename traits::coneSequence>&
470:     cone(const typename traits::target_type& p) {
471:       this->_coneSeq->setKey(p);
472:       this->_coneSeq->setUseSubkey(false);
473:       return this->_coneSeq;
474:     };
475: #endif
476:     template<class InputSequence>
477:     Obj<typename traits::coneSet>
478:     cone(const Obj<InputSequence>& points) {
479:       Obj<typename traits::coneSet> cone = typename traits::coneSet();

481:       for(typename InputSequence::iterator p_itor = points->begin(); p_itor != points->end(); ++p_itor) {
482:         const Obj<typename traits::coneSequence>& pCone = this->cone(*p_itor);
483:         cone->insert(pCone->begin(), pCone->end());
484:       }
485:       return cone;
486:     };
487:     template<typename PointCheck>
488:     bool coneContains(const typename traits::target_type& p, const PointCheck& checker) {
489:       typename traits::coneSequence cone(*this, ::boost::multi_index::get<typename traits::coneInd>(this->_arrows.set), p);

491:       for(typename traits::coneSequence::iterator c_iter = cone.begin(); c_iter != cone.end(); ++c_iter) {
492:         if (checker(*c_iter, p)) return true;
493:       }
494:       return false;
495:     };
496:     template<typename PointProcess>
497:     void coneApply(const typename traits::target_type& p, PointProcess& processor) {
498:       typename traits::coneSequence cone(*this, ::boost::multi_index::get<typename traits::coneInd>(this->_arrows.set), p);

500:       for(typename traits::coneSequence::iterator c_iter = cone.begin(); c_iter != cone.end(); ++c_iter) {
501:         processor(*c_iter, p);
502:       }
503:     };
504: #ifdef SLOW
505:     Obj<typename traits::supportSequence>
506:     support(const typename traits::source_type& p) {
507:       return typename traits::supportSequence(*this, ::boost::multi_index::get<typename traits::supportInd>(this->_arrows.set), p);
508:     };
509: #else
510:     const Obj<typename traits::supportSequence>&
511:     support(const typename traits::source_type& p) {
512:       this->_supportSeq->setKey(p);
513:       this->_supportSeq->setUseSubkey(false);
514:       return this->_supportSeq;
515:     };
516: #endif
517:     template<class InputSequence>
518:     Obj<typename traits::supportSet>
519:     support(const Obj<InputSequence>& points){
520:       Obj<typename traits::supportSet> supp = typename traits::supportSet();
521:       for(typename InputSequence::iterator p_itor = points->begin(); p_itor != points->end(); ++p_itor) {
522:         const Obj<typename traits::supportSequence>& pSupport = this->support(*p_itor);
523:         supp->insert(pSupport->begin(), pSupport->end());
524:       }
525:       return supp;
526:     };
527:     template<typename PointCheck>
528:     bool supportContains(const typename traits::source_type& p, const PointCheck& checker) {
529:       typename traits::supportSequence support(*this, ::boost::multi_index::get<typename traits::supportInd>(this->_arrows.set), p);

531:       for(typename traits::supportSequence::iterator s_iter = support.begin(); s_iter != support.end(); ++s_iter) {
532:         if (checker(*s_iter, p)) return true;
533:       }
534:       return false;
535:     };
536:     template<typename PointProcess>
537:     void supportApply(const typename traits::source_type& p, PointProcess& processor) {
538:       typename traits::supportSequence support(*this, ::boost::multi_index::get<typename traits::supportInd>(this->_arrows.set), p);

540:       for(typename traits::supportSequence::iterator s_iter = support.begin(); s_iter != support.end(); ++s_iter) {
541:         processor(*s_iter, p);
542:       }
543:     };

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

549:       if(label != NULL) {
550:         os << "["<<rank<<"]Viewing LabelSifter '" << label << "':" << std::endl;
551:       }
552:       else {
553:         os << "["<<rank<<"]Viewing a LabelSifter:" << std::endl;
554:       }
555:       os << "'raw' arrow set:" << std::endl;
556:       for(typename traits::arrow_container_type::set_type::iterator ai = _arrows.set.begin(); ai != _arrows.set.end(); ai++) {
557:         os << *ai << std::endl;
558:       }
559:     };
560:     // A parallel viewer
561:     PetscErrorCode view(const char* label = NULL, bool raw = false){
563:       ostringstream txt;
565:       if(this->_debug) {
566:         std::cout << "viewing a LabelSifter, comm = " << this->comm() << ", PETSC_COMM_SELF = " << PETSC_COMM_SELF << ", commRank = " << this->commRank() << std::endl;
567:       }
568:       if(label != NULL) {
569:         PetscPrintf(this->comm(), "viewing LabelSifter: '%s'\n", label);
570:       } else {
571:         PetscPrintf(this->comm(), "viewing a LabelSifter: \n");
572:       }
573:       if(!raw) {
574:         ostringstream txt;
575:         if(this->commRank() == 0) {
576:           txt << "cap --> base:\n";
577:         }
578:         if(_arrows.set.empty()) {
579:           txt << "[" << this->commRank() << "]: empty" << std::endl;
580:         }
581:         for(typename traits::arrow_container_type::set_type::iterator ai = _arrows.set.begin(); ai != _arrows.set.end(); ai++) {
582:           txt << "[" << this->commRank() << "]: " << ai->source << "---->" << ai->target << std::endl;
583:         }
584:         PetscSynchronizedPrintf(this->comm(), txt.str().c_str()); CHKERROR(ierr, "Error in PetscSynchronizedFlush");
585:         PetscSynchronizedFlush(this->comm());  CHKERROR(ierr, "Error in PetscSynchronizedFlush");
586:       }
587:       else { // if(raw)
588:         ostringstream txt;
589:         if(this->commRank() == 0) {
590:           txt << "'raw' arrow set:" << std::endl;
591:         }
592:         for(typename traits::arrow_container_type::set_type::iterator ai = _arrows.set.begin(); ai != _arrows.set.end(); ai++)
593:         {
594:           typename traits::arrow_type arr = *ai;
595:           txt << "[" << this->commRank() << "]: " << arr << std::endl;
596:         }
597:         PetscSynchronizedPrintf(this->comm(), txt.str().c_str()); CHKERROR(ierr, "Error in PetscSynchronizedFlush");
598:         PetscSynchronizedFlush(this->comm());  CHKERROR(ierr, "Error in PetscSynchronizedFlush");
599:       }// if(raw)
600: 
601:       return(0);
602:     };
603:   public:
604:     //
605:     // Lattice queries
606:     //
607:     template<class targetInputSequence>
608:     Obj<typename traits::coneSequence> meet(const Obj<targetInputSequence>& targets);
609:     // unimplemented
610:     template<class sourceInputSequence>
611:     Obj<typename traits::coneSequence> join(const Obj<sourceInputSequence>& sources);
612:   public:
613:     //
614:     // Structural manipulation
615:     //
616:     void clear() {
617:       this->_arrows.set.clear();
618:     };
619:     // This is necessary to work with Completion right now
620:     virtual void addArrow(const typename traits::source_type& p, const typename traits::target_type& q, const int dummy) {
621:       this->addArrow(p, q);
622:     };
623:     virtual void addArrow(const typename traits::source_type& p, const typename traits::target_type& q) {
624:       this->addArrow(typename traits::arrow_type(p, q));
625:       //std::cout << "Added " << arrow_type(p, q);
626:     };
627:     virtual void addArrow(const typename traits::arrow_type& a) {
628:       this->_arrows.set.insert(a);
629:     };
630:     virtual void removeArrow(const typename traits::arrow_type& a) {
631:       // First, produce an arrow sequence for the given source, target combination.
632:       typename traits::arrowSequence::traits::index_type& arrowIndex =
633:         ::boost::multi_index::get<typename traits::arrowInd>(this->_arrows.set);
634:       typename traits::arrowSequence::traits::index_type::iterator i,ii,j;
635:       i = arrowIndex.lower_bound(::boost::make_tuple(a.source,a.target));
636:       ii = arrowIndex.upper_bound(::boost::make_tuple(a.source, a.target));
637:       if (this->_debug) {
638:         std::cout << "removeArrow: attempting to remove arrow:" << a << std::endl;
639:         std::cout << "removeArrow: candidate arrows are:" << std::endl;
640:       }
641:       for(j = i; j != ii; j++) {
642:         if (this->_debug) {
643:           std::cout << " " << *j;
644:         }
645:         // Find the arrow of right color and remove it
646:         if (this->_debug) {
647:           std::cout << std::endl << "removeArrow: found:" << *j << std::endl;
648:         }
649:         arrowIndex.erase(j);
650:         break;
651:       }
652:     };

654:     void addCone(const typename traits::source_type& source, const typename traits::target_type& target){
655:       this->addArrow(source, target);
656:     };
657:     template<class sourceInputSequence>
658:     void
659:     addCone(const Obj<sourceInputSequence>& sources, const typename traits::target_type& target){
660:       if (this->_debug > 1) {std::cout << "Adding a cone " << std::endl;}
661:       for(typename sourceInputSequence::iterator iter = sources->begin(); iter != sources->end(); ++iter) {
662:         if (this->_debug > 1) {std::cout << "Adding arrow from " << *iter << " to " << target << std::endl;}
663:         this->addArrow(*iter, target);
664:       }
665:     };
666:     void clearCone(const typename traits::target_type& t) {
667:       // Use the cone sequence types to clear the cone
668:       typename traits::coneSequence::traits::index_type& coneIndex =
669:         ::boost::multi_index::get<typename traits::coneInd>(this->_arrows.set);
670:       typename traits::coneSequence::traits::index_type::iterator i, ii, j;
671:       if (this->_debug > 20) {
672:         std::cout << "clearCone: removing cone over " << t;
673:         std::cout << std::endl;
674:         const Obj<typename traits::coneSequence>& cone = this->cone(t);
675:         std::cout << "[";
676:         for(typename traits::coneSequence::iterator ci = cone->begin(); ci != cone->end(); ci++) {
677:           std::cout << "  " << ci.arrow();
678:         }
679:         std::cout << "]" << std::endl;
680:       }
681:       i = coneIndex.lower_bound(::boost::make_tuple(t));
682:       ii = coneIndex.upper_bound(::boost::make_tuple(t));
683:       coneIndex.erase(i,ii);
684:     };// clearCone()

686:     void clearSupport(const typename traits::source_type& s) {
687:       // Use the cone sequence types to clear the cone
688:       typename
689:         traits::supportSequence::traits::index_type& suppIndex = ::boost::multi_index::get<typename traits::supportInd>(this->_arrows.set);
690:       typename traits::supportSequence::traits::index_type::iterator i, ii, j;
691:       i = suppIndex.lower_bound(::boost::make_tuple(s));
692:       ii = suppIndex.upper_bound(::boost::make_tuple(s));
693:       suppIndex.erase(i,ii);
694:     };
695:     void setCone(const typename traits::source_type& source, const typename traits::target_type& target){
696:       this->clearCone(target); this->addCone(source, target);
697:     };
698:     template<class sourceInputSequence>
699:     void setCone(const Obj<sourceInputSequence>& sources, const typename traits::target_type& target) {
700:       this->clearCone(target); this->addCone(sources, target);
701:     };
702:     template<class targetInputSequence>
703:     void addSupport(const typename traits::source_type& source, const Obj<targetInputSequence >& targets) {
704:       if (this->_debug > 1) {std::cout << "Adding a support " << std::endl;}
705:       for(typename targetInputSequence::iterator iter = targets->begin(); iter != targets->end(); ++iter) {
706:         if (this->_debug > 1) {std::cout << "Adding arrow from " << source << " to " << *iter << std::endl;}
707:         this->addArrow(source, *iter);
708:       }
709:     };
710:     template<typename Sifter_, typename AnotherSifter_>
711:     void add(const Obj<Sifter_>& cbg, const Obj<AnotherSifter_>& baseRestriction = NULL) {
712:       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);
713:       bool baseRestrict = !baseRestriction.isNull();
714: 
715:       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) {
716:         if (baseRestrict) {
717:           if (!baseRestriction->getSupportSize(a_iter->target) && !baseRestriction->getConeSize(a_iter->target)) continue;
718:         }
719:         this->addArrow(*a_iter);
720:       }
721:     };
722:     template<typename Sifter_, typename AnotherSifter_, typename Renumbering_>
723:     void add(const Obj<Sifter_>& cbg, const Obj<AnotherSifter_>& baseRestriction, Renumbering_& renumbering) {
724:       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);

726:       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) {
727:         if (renumbering.find(a_iter->target) == renumbering.end()) continue;
728:         target_type target = renumbering[a_iter->target];

730:         if (!baseRestriction->getSupportSize(target) && !baseRestriction->getConeSize(target)) continue;
731:         this->addArrow(a_iter->source, target);
732:       }
733:     };
734:     int getCapSize() const {
735:       std::set<source_type> cap;
736:       for(typename traits::arrow_container_type::set_type::iterator a_iter = _arrows.set.begin(); a_iter != _arrows.set.end(); ++a_iter) {
737:         cap.insert(a_iter->source);
738:       }
739:       return cap.size();
740:     };
741:     capSequence cap() const {
742:       std::set<source_type> cap;
743:       for(typename traits::arrow_container_type::set_type::iterator a_iter = _arrows.set.begin(); a_iter != _arrows.set.end(); ++a_iter) {
744:         cap.insert(a_iter->source);
745:       }
746:       return cap;
747:     };
748:     int getBaseSize() const {
749:       std::set<target_type> base;
750:       for(typename traits::arrow_container_type::set_type::iterator a_iter = _arrows.set.begin(); a_iter != _arrows.set.end(); ++a_iter) {
751:         base.insert(a_iter->target);
752:       }
753:       return base.size();
754:     };
755:   public: // Compatibility with fixed storage variants
756:     typedef Interval<target_type> chart_type;
757:     chart_type& getChart() {static chart_type chart(0, 0); return chart;};
758:     template<typename chart_type>
759:     void setChart(const chart_type& chart) {};
760:     void setConeSize(target_type p, int s) {};
761:     void setSupportSize(source_type p, int s) {};
762:     void allocate() {};
763:     void recalculateLabel() {};
764:   }; // class LabelSifter
765: } // namespace ALE

767: #endif // ifdef included_ALE_LabelSifter_hh