Elementa v8.0.0
Minimalistic library for any C++ application (C++11 and up)
Loading...
Searching...
No Matches
sparse_graphs.h
Go to the documentation of this file.
1
3#include "elementa/license.inc"
4#include "elementa/checks.inc"
5
6#ifndef ELEMENTA_ADTS_GRAPHS_SPARSEGRAPHS_H
7#define ELEMENTA_ADTS_GRAPHS_SPARSEGRAPHS_H
8
9#include <cstddef>
10#include <iterator>
11#include <type_traits>
12#include <list>
13#include <map>
14#include <string>
15#include "elementa/base/fundamentaltypes.h"
16#include "elementa/base/exceptions.h"
17#include "elementa/patterns/validatable.h"
18#include "elementa/adts/graphs/graphs.h"
19
20#include "elementa/base/debugging.h"
21
22namespace elementa
23{
24
25namespace adts
26{
27
28namespace graphs
29{
30
53/* ***************************************************************************
54
55 Template class: SparseGraph
56
57*******************************************************************************/
58
60
72template <class Vertex, class Edge>
73class SparseGraph: public Graph<Vertex,Edge>
74{
75 public:
76
80 using BaseGraph = Graph<Vertex,Edge>;
81
89 SparseGraph(void):BaseGraph{} {}
90
92 SparseGraph(const SparseGraph & oth):BaseGraph{oth},
93 data_{oth.data_}
94 {}
95
97 SparseGraph & operator=(const SparseGraph & oth)
98 { if (this != &oth) { this->BaseGraph::operator=(oth);
99 data_ = oth.data_; } return(*this); }
100
102 SparseGraph(SparseGraph && oth):BaseGraph{std::move(oth)},
103 data_{std::move(oth.data_)}
104 {}
105
107 SparseGraph & operator=(SparseGraph && oth)
108 { if (this != &oth) { this->BaseGraph::operator=(std::move(oth));
109 data_ = std::move(oth.data_); } return(*this); }
110
112 virtual ~SparseGraph(void) {}
113
114 SparseGraph * clone(void) const
115 { return(new SparseGraph{*this}); }
116
117 SparseGraph * emptyClone(void) const override
118 { return(new SparseGraph); }
119
126 bool empty(void) const
127 { return(data_.empty()); }
128
129 void clear(void)
130 { data_.clear(); }
131
132 size_vertex size_vertices(void) const { return(data_.size_vertices()); }
133
134 size_edge size_edges(void) const { return(data_.size_edges()); }
135
136 typename BaseGraph::viterator origin(
137 const typename BaseGraph::eiterator & it) const
138 { checkEIT(it,ELE_CODE_PLACE);
139 return(vallFromInternal(data_.origin(einternalFromMultit(it)))); }
140
141 typename BaseGraph::viterator destination(
142 const typename BaseGraph::eiterator & it) const
143 { checkEIT(it,ELE_CODE_PLACE);
144 return(vallFromInternal(data_.destination(einternalFromMultit(it))));}
145
152 typename BaseGraph::viterator insert(const Vertex & v)
153 { return(vallFromInternal(data_.insert(v))); }
154
155 typename BaseGraph::eiterator connect(
156 const typename BaseGraph::viterator & itv0,
157 const typename BaseGraph::viterator & itv1,
158 const Edge & e)
159 { checkVIT(itv0,ELE_CODE_PLACE);
160 checkVIT(itv1,ELE_CODE_PLACE);
161 return(eallFromInternal(data_.connect(vinternalFromMultit(itv0),
162 vinternalFromMultit(itv1),e)));}
163
164 void unconnect(const typename BaseGraph::eiterator & ite)
165 { checkEIT(ite,ELE_CODE_PLACE);
166 data_.unconnect(einternalFromMultit(ite)); }
167
168 void unconnect(const typename BaseGraph::VectorOfEIts & sinds)
169 { for (const auto & ite:sinds) unconnect(ite); }
170
171 void erase(const typename BaseGraph::viterator & itv)
172 { checkVIT(itv,ELE_CODE_PLACE);
173 data_.erase(vinternalFromMultit(itv)); }
174
175 void erase(const typename BaseGraph::VectorOfVIts & sinds)
176 { for (const auto & itv:sinds) erase(itv); }
177
180 void splice(BaseGraph & oth,
181 typename BaseGraph::VectorOfVIts * svothinds = nullptr,
182 typename BaseGraph::VectorOfEIts * seothinds = nullptr,
183 typename BaseGraph::VectorOfVIts * svinds = nullptr,
184 typename BaseGraph::VectorOfEIts * seinds = nullptr)
185 { data_.splice(dynamic_cast<SparseGraph &>(oth).data_); }
186
190 private:
191
192
193 // ------ Main data structures
194
195 template <class D>
196 using Cont = std::list<D>; // container for data
197 // must be std::list since list iterators are
198 // never invalidated
199
200 struct VInfo; // forward declaration
201
203 struct EInfo
204 {
205 // Keep a static value with the offset of the "data" field within EInfo.
206 /* Needed since offsetof() cannot be used in structs that are not POD */
207 static size_t & getOffsetOfData(void) noexcept
208 { static size_t ood{0}; return(ood); }
209
210 // Given a pointer to the Edge data, return a pointer to the EInfo
211 static const EInfo * startFromEdge(const Edge * pd)
212 { // getOffsetOfData() necessarily updated since this cannot be called
213 // without creating one EInfo before (see who calls this method)
214 return(reinterpret_cast<const EInfo *>(
215 reinterpret_cast<const char *>(pd) - getOffsetOfData()));
216 }
217
218 using List = Cont<EInfo>; // a list of EInfo
219 using ListOfIts = Cont<typename List::iterator>;//list of List iterators
220
221 Edge data; // user data
222
223 VInfo * org; // pointer to the origin node
224 VInfo * dest; // pointer to the destination node
225 typename ListOfIts::iterator leaving; // iterator on a leaving list
226 typename ListOfIts::iterator entering; // iterator on an entering list
227
228 typename List::iterator myselfit;//myself iterator in main edges storage
229
230 // constructors, just to fill the essential user's data
231
232 EInfo(const Edge & d):data{d}
233 {// the first time a VInfo is constructed, calc. the offset of "data"
234 auto & ood = getOffsetOfData();
235 if (ood == 0) // need to fill it
236 ood = reinterpret_cast<char *>(&data) -
237 reinterpret_cast<char *>(this);
238 }
239
240 EInfo(Edge && d):data{std::move(d)} {}
241 ~EInfo(void) {}
242
243 EInfo(const EInfo & ) = delete;
244 EInfo(EInfo && ) = delete;
245 EInfo & operator=(const EInfo & ) = delete;
246 EInfo & operator=(EInfo && ) = delete;
247
248 };
249
251 struct VInfo
252 {
253 // Keep a static value with the offset of the "data" field within VInfo.
254 /* Needed since offsetof() cannot be used in structs that are not POD */
255 static size_t & getOffsetOfData(void) noexcept
256 { static size_t ood{0}; return(ood); }
257
258 // Given a pointer to the Vertex data, return a pointer to the VInfo
259 static const VInfo * startFromVertex(const Vertex * pd)
260 { // getOffsetOfData() necessarily updated since this cannot be called
261 // without creating one VInfo before (see who calls this method)
262 return(reinterpret_cast<const VInfo *>(
263 reinterpret_cast<const char *>(pd) - getOffsetOfData()));
264 }
265
266 using List = Cont<VInfo>; // a list of VInfo
267 using ListOfIts = Cont<typename List::iterator>;//list of List iterators
268
269 Vertex data; // user data
270
271 typename EInfo::ListOfIts entering; // iterators of entering edges
272 typename EInfo::ListOfIts leaving; // iterators to leaving edges
273
274 typename List::iterator myselfit; // myself it. in main vertices storage
275
276 // constructors, just to fill the essential user's data
277
278 VInfo(const Vertex & d):data{d}
279 {// the first time a VInfo is constructed, calc. the offset of "data"
280 auto & ood = getOffsetOfData();
281 if (ood == 0) // need to fill it
282 ood = reinterpret_cast<char *>(&data) -
283 reinterpret_cast<char *>(this);
284 }
285
286 VInfo(Vertex && d):data{std::move(d)} {}
287 ~VInfo(void) {}
288
289 VInfo(const VInfo & ) = delete;
290 VInfo(VInfo && ) = delete;
291 VInfo & operator=(const VInfo & ) = delete;
292 VInfo & operator=(VInfo && ) = delete;
293
294 };
295
296
297 // ------ Data of the graph (transposition of the Graph<> functionality)
298 // Since these data are internal, not many checks
299 // are done on the methods.
300
301 class Data
302 {
303 public:
304
305 typename VInfo::List vertices_;
306 typename EInfo::List edges_;
307
308 Data(void) {}
309 Data(const Data & oth) { copyFrom(oth); } // O(E+V)
310 Data(Data && oth) { moveFrom(std::move(oth)); }
311 ~Data(void) {}
312 Data & operator=(const Data & oth) // O(E+V)
313 { if (this != &oth) copyFrom(oth); return(*this); }
314 Data & operator=(Data && oth)
315 { if (this != &oth) moveFrom(std::move(oth)); return(*this); }
316
317 // helper functions to manage the data. All O(1) except when noticed.
318
319 bool empty(void) const noexcept
320 { return( (vertices_.empty()) && (edges_.empty()) ); }
321
322 void clear(void)
323 { vertices_.clear(); edges_.clear(); }
324
325 typename VInfo::List::size_type size_vertices(void) const
326 { return(vertices_.size()); }
327
328 typename EInfo::List::size_type size_edges(void) const
329 { return(edges_.size()); }
330
331 typename VInfo::List::iterator origin(
332 const typename EInfo::List::iterator & eit) const
333 { return((*eit).org->myselfit); }
334
335 typename VInfo::List::iterator destination(
336 const typename EInfo::List::iterator & eit) const
337 { return((*eit).dest->myselfit); }
338
339 typename VInfo::List::iterator insert(const Vertex & v)
340 { typename VInfo::List::iterator vit{
341 vertices_.emplace(vertices_.end(),v)};
342 fill(vit); return(vit); }
343
344 typename VInfo::List::iterator insert(Vertex && v)
345 { typename VInfo::List::iterator vit{
346 vertices_.emplace(vertices_.end(),std::move(v))};
347 fill(vit); return(vit); }
348
349 typename EInfo::List::iterator connect(
350 const typename VInfo::List::iterator & itv0,
351 const typename VInfo::List::iterator & itv1,
352 const Edge & e)
353 { typename EInfo::List::iterator eit{
354 edges_.emplace(edges_.end(),e)};
355 fill(eit,itv0,itv1); return(eit); }
356
357 typename EInfo::List::iterator connect(
358 const typename VInfo::List::iterator & itv0,
359 const typename VInfo::List::iterator & itv1,
360 Edge && e)
361 { typename EInfo::List::iterator eit{
362 edges_.emplace(edges_.end(),std::move(e))};
363 fill(eit,itv0,itv1); return(eit); }
364
365 void unconnect(const typename EInfo::List::iterator & ite)
366 {
367 typename VInfo::List::iterator vit0{(*ite).org->myselfit};
368 typename VInfo::List::iterator vit1{(*ite).dest->myselfit};
369 (*vit0).leaving.erase((*ite).leaving);
370 (*vit1).entering.erase((*ite).entering);
371 edges_.erase(ite);
372 }
373
374 void erase(const typename VInfo::List::iterator & itv) // O(deg(ITV))
375 {
376 while (!(*itv).entering.empty())
377 unconnect(*((*itv).entering.begin()));
378 while (!(*itv).leaving.empty())
379 unconnect(*((*itv).leaving.begin()));
380 vertices_.erase(itv);
381 }
382
383 void splice(Data & oth)//doesn't change iterators;clear OTH; O(1)
384 { vertices_.splice(vertices_.end(),std::move(oth.vertices_));
385 edges_.splice(edges_.end(),std::move(oth.edges_)); }
386
387 private:
388
389 void fill(typename VInfo::List::iterator & vit)
390 { (*vit).myselfit = vit; }
391
392 void fill(typename EInfo::List::iterator & eit,
393 const typename VInfo::List::iterator & itv0,
394 const typename VInfo::List::iterator & itv1)
395 {
396 (*eit).myselfit = eit;
397 (*eit).org = &(*itv0);
398 (*eit).dest = &(*itv1);
399 auto itinv0 = (*itv0).leaving.insert((*itv0).leaving.end(),eit);
400 auto itinv1 = (*itv1).entering.insert((*itv1).entering.end(),eit);
401 (*eit).leaving = itinv0;
402 (*eit).entering = itinv1;
403 }
404
405 void moveFrom(Data && oth)
406 {
407 // iterators are not invalidated when moved except when both
408 // containers have incompatible allocators, which is not the case
409 // https://stackoverflow.com/questions/41384793/does-stdmove-invalidate-iterators
410 vertices_ = std::move(oth.vertices_);
411 edges_ = std::move(oth.edges_);
412 }
413
414 void copyFrom(const Data & oth)
415 {
416 clear();
417 std::map<const VInfo *, const VInfo *> vmap;
418 for (const auto & v: oth.vertices_) vmap[&v] = &(*insert(v.data));
419 for (const auto & e: oth.edges_)
420 connect(vmap.at(e.org)->myselfit,
421 vmap.at(e.dest)->myselfit,
422 e.data);
423 }
424
425 };
426
427
428 Data data_;
429
430
431 // ------ Implementations of public iterators
432
434 class VItImpl_All final: public elementa::base::MultItImpl<Vertex>
435 // indirectly derives from Validatable
436 {
437 public:
438
439 VItImpl_All(const typename VInfo::List & vdata,
440 const typename VInfo::List::iterator & vi):
441 vdata_{&vdata},
442 pos_{vi}
443 { elementa::patterns::Validatable::setValid(); }
444
445 VItImpl_All(const VItImpl_All & oth):
446 elementa::patterns::Validatable{oth},
447 elementa::base::MultItImpl<Vertex>{oth}
448 {ELE_CODE_TRACE_OFF;
449 ELE_CODE_TRACE({},"oth.valid: " <<
450 oth.elementa::patterns::Validatable::valid());
451 copyFrom(oth);
452 ELE_CODE_TRACE({},"valid: " <<
453 elementa::patterns::Validatable::valid()); }
454
455 VItImpl_All & operator=(const VItImpl_All &oth)
456 {ELE_CODE_TRACE_OFF;
457 ELE_CODE_TRACE({},"oth.valid: " <<
458 oth.elementa::patterns::Validatable::valid());
459 if (this != &oth)
460 { elementa::patterns::Validatable::operator=(oth);
461 elementa::base::MultItImpl<Vertex>::operator=(oth);
462 copyFrom(oth); }
463 ELE_CODE_TRACE({},"valid: " <<
464 elementa::patterns::Validatable::valid());
465 return(*this); }
466
467 VItImpl_All(VItImpl_All && oth):
468 elementa::patterns::Validatable{std::move(oth)},
469 elementa::base::MultItImpl<Vertex>{std::move(oth)}
470 {ELE_CODE_TRACE_OFF;
471 ELE_CODE_TRACE({},"oth.valid: " <<
472 oth.elementa::patterns::Validatable::valid());
473 copyFrom(oth);
474 ELE_CODE_TRACE({},"valid: " <<
475 elementa::patterns::Validatable::valid()); }
476
477 VItImpl_All & operator=(VItImpl_All && oth)
478 {ELE_CODE_TRACE_OFF;
479 ELE_CODE_TRACE({},"oth.valid: " <<
480 oth.elementa::patterns::Validatable::valid());
481 if (this != &oth)
482 { elementa::patterns::Validatable::operator=(oth);
483 elementa::base::MultItImpl<Vertex>::operator=(oth);
484 copyFrom(oth); }
485 ELE_CODE_TRACE({},"valid: " <<
486 elementa::patterns::Validatable::valid());
487 return(*this); }
488
489 typename BaseGraph::viterator::ImplementationPtr clone(void)const
490 {ELE_CODE_TRACE_OFF;
491 ELE_CODE_TRACE({},"valid: " <<
492 elementa::patterns::Validatable::valid());
493 return(typename BaseGraph::viterator::ImplementationPtr{
494 new VItImpl_All{*this}}); }
495
496 Vertex & operator*(void)
497 { checkDeref(ELE_CODE_PLACE); return((*pos_).data); }
498
499 Vertex * pointedData(void) const
500 { if (pos_ == vdata_->end()) return(nullptr);
501 return(&((*pos_).data)); }
502
503 VItImpl_All & operator++(void)
504 { if (pos_ != vdata_->end()) ++pos_; return(*this); }
505
506 std::string to_string(void) const override
507 { return(std::string{"vit_all(vdata:"} +
508 std::to_string(elementa::base::to_number(vdata_)) +
509 ", &(*pos): " +
510 std::to_string(elementa::base::to_number(&(*pos_)))+ ")");}
511
512 void checkDeref(const std::string & place = "") const
513 { if (pos_ == vdata_->end())
514 throw(elementa::base::invstate{
515 "De-referencing end iterator"}.asEXC(
516 place.empty() ? ELE_CODE_PLACE : place)); }
517
518 private:
519
520 const typename VInfo::List * vdata_; // no ownership
521 typename VInfo::List::iterator pos_;
522
523 void copyFrom(const VItImpl_All & oth)
524 { vdata_ = oth.vdata_; pos_ = oth.pos_; }
525 };
526
527
529 class EItImpl_All final: public elementa::base::MultItImpl<Edge>
530 // indirectly derives from Validatable
531 {
532 public:
533
534 EItImpl_All(const typename EInfo::List & edata,
535 const typename EInfo::List::iterator & ei):
536 edata_{&edata},
537 pos_{ei}
538 { elementa::patterns::Validatable::setValid(); }
539
540 EItImpl_All(const EItImpl_All & oth):
541 elementa::patterns::Validatable{oth},
542 elementa::base::MultItImpl<Edge>{oth}
543 { copyFrom(oth); }
544
545 EItImpl_All & operator=(const EItImpl_All &oth)
546 { if (this != &oth)
547 { elementa::patterns::Validatable::operator=(oth);
548 elementa::base::MultItImpl<Edge>::operator=(oth);
549 copyFrom(oth); } return(*this); }
550
551 EItImpl_All(EItImpl_All && oth):
552 elementa::patterns::Validatable{std::move(oth)},
553 elementa::base::MultItImpl<Edge>{std::move(oth)}
554 { copyFrom(oth); }
555
556 EItImpl_All & operator=(EItImpl_All && oth)
557 { if (this != &oth)
558 { elementa::patterns::Validatable::operator=(oth);
559 elementa::base::MultItImpl<Edge>::operator=(oth);
560 copyFrom(oth); } return(*this); }
561
562 typename BaseGraph::eiterator::ImplementationPtr clone(void)const
563 { return(typename BaseGraph::eiterator::ImplementationPtr{
564 new EItImpl_All{*this}}); }
565
566 Edge & operator*(void)
567 { checkDeref(ELE_CODE_PLACE); return((*pos_).data); }
568
569 Edge * pointedData(void) const
570 { if (pos_ == edata_->end()) return(nullptr);
571 return(&((*pos_).data)); }
572
573 EItImpl_All & operator++(void)
574 { if (pos_ != edata_->end()) ++pos_; return(*this); }
575
576 std::string to_string(void) const override
577 { return(std::string{"eit_all(vdata:"} +
578 std::to_string(elementa::base::to_number(edata_)) +
579 ", &(*pos): " +
580 std::to_string(elementa::base::to_number(&(*pos_)))+ ")");}
581
582 void checkDeref(const std::string & place = "") const
583 { if (pos_ == edata_->end())
584 throw(elementa::base::invstate{
585 "De-referencing end iterator"}.asEXC(
586 place.empty() ? ELE_CODE_PLACE : place)); }
587
588 private:
589
590 const typename EInfo::List * edata_; // no ownership
591 typename EInfo::List::iterator pos_;
592
593 void copyFrom(const EItImpl_All & oth)
594 { edata_ = oth.edata_; pos_ = oth.pos_; }
595 };
596
597
599 class EItImpl_Leaving final: public elementa::base::MultItImpl<Edge>
600 // indirectly derives from Validatable
601 {
602 public:
603
604 EItImpl_Leaving(const typename VInfo::List & vdata,
605 const typename VInfo::List::iterator & vi,
606 bool beginorend = true) // False to create end iterator
607 {
608 if (vi != vdata.end()) // otherwise, invalid iterator
609 {
610 cdata_ = &((*vi).leaving);
611 if (beginorend) pos_ = cdata_->begin();
612 else pos_ = cdata_->end();
613 elementa::patterns::Validatable::setValid();
614 }
615 }
616
617 EItImpl_Leaving(const EItImpl_Leaving & oth):
618 elementa::patterns::Validatable{oth},
619 elementa::base::MultItImpl<Edge>{oth}
620 { copyFrom(oth); }
621
622 EItImpl_Leaving & operator=(const EItImpl_Leaving &oth)
623 { if (this != &oth)
624 { elementa::patterns::Validatable::operator=(oth);
625 elementa::base::MultItImpl<Edge>::operator=(oth);
626 copyFrom(oth); } return(*this); }
627
628 EItImpl_Leaving(EItImpl_Leaving && oth):
629 elementa::patterns::Validatable{std::move(oth)},
630 elementa::base::MultItImpl<Edge>{std::move(oth)}
631 { copyFrom(oth); }
632
633 EItImpl_Leaving & operator=(EItImpl_Leaving && oth)
634 { if (this != &oth)
635 { elementa::patterns::Validatable::operator=(oth);
636 elementa::base::MultItImpl<Edge>::operator=(oth);
637 copyFrom(oth); } return(*this); }
638
639 typename BaseGraph::eiterator::ImplementationPtr clone(void)const
640 { return(typename BaseGraph::eiterator::ImplementationPtr{
641 new EItImpl_Leaving{*this}}); }
642
643 Edge & operator*(void)
644 { checkDeref(ELE_CODE_PLACE); return((*(*pos_)).data); }
645
646 Edge * pointedData(void) const
647 { elementa::patterns::Validatable::checkValid(ELE_CODE_PLACE);
648 if (pos_ == cdata_->end()) return(nullptr);
649 return(&((*(*pos_)).data)); }
650
651 EItImpl_Leaving & operator++(void)
652 { elementa::patterns::Validatable::checkValid(ELE_CODE_PLACE);
653 if (pos_ != cdata_->end()) ++pos_;
654 return(*this); }
655
656 std::string to_string(void) const override
657 { return(std::string{"eit_leaving(cdata:"} +
658 std::to_string(elementa::base::to_number(cdata_)) +
659 ", &(*pos): " +
660 std::to_string(elementa::base::to_number(&(*pos_)))+ ")");}
661
662 void checkDeref(const std::string & place = "") const
663 { elementa::patterns::Validatable::checkValid(
664 (place.empty() ? ELE_CODE_PLACE : place));
665 if (pos_ == cdata_->end())
666 throw(elementa::base::invstate{
667 "De-referencing end iterator"}.asEXC(
668 place.empty() ? ELE_CODE_PLACE : place)); }
669
670 private:
671
672 typename EInfo::ListOfIts * cdata_; // no ownership
673 typename EInfo::ListOfIts::iterator pos_;
674
675 void copyFrom(const EItImpl_Leaving & oth)
676 { cdata_ = oth.cdata_; pos_ = oth.pos_; }
677 };
678
679 // Edge iteration that scans all entering edges of a vertex.
680 class EItImpl_Entering final: public elementa::base::MultItImpl<Edge>
681 // indirectly derives from Validatable
682 {
683 public:
684
685 EItImpl_Entering(const typename VInfo::List & vdata,
686 const typename VInfo::List::iterator & vi,
687 bool beginorend = true) // False to create end iteratr
688 {
689 if (vi != vdata.end()) // otherwise, invalid iterator
690 {
691 cdata_ = &((*vi).entering);
692 if (beginorend) pos_ = cdata_->begin();
693 else pos_ = cdata_->end();
694 elementa::patterns::Validatable::setValid();
695 }
696 }
697
698 EItImpl_Entering(const EItImpl_Entering & oth):
699 elementa::patterns::Validatable{oth},
700 elementa::base::MultItImpl<Edge>{oth}
701 { copyFrom(oth); }
702
703 EItImpl_Entering & operator=(const EItImpl_Entering &oth)
704 { if (this != &oth)
705 { elementa::patterns::Validatable::operator=(oth);
706 elementa::base::MultItImpl<Edge>::operator=(oth);
707 copyFrom(oth); } return(*this); }
708
709 EItImpl_Entering(EItImpl_Entering && oth):
710 elementa::patterns::Validatable{std::move(oth)},
711 elementa::base::MultItImpl<Edge>{std::move(oth)}
712 { copyFrom(oth); }
713
714 EItImpl_Entering & operator=(EItImpl_Entering && oth)
715 { if (this != &oth)
716 { elementa::patterns::Validatable::operator=(oth);
717 elementa::base::MultItImpl<Edge>::operator=(oth);
718 copyFrom(oth); } return(*this); }
719
720 typename BaseGraph::eiterator::ImplementationPtr clone(void)const
721 { return(typename BaseGraph::eiterator::ImplementationPtr{
722 new EItImpl_Entering{*this}}); }
723
724 Edge & operator*(void)
725 { checkDeref(ELE_CODE_PLACE); return((*(*pos_)).data); }
726
727 Edge * pointedData(void) const
728 {
729 elementa::patterns::Validatable::checkValid(ELE_CODE_PLACE);
730 if (pos_ == cdata_->end()) return(nullptr);
731 return(&((*(*pos_)).data));
732 }
733
734 EItImpl_Entering & operator++(void)
735 {
736 elementa::patterns::Validatable::checkValid(ELE_CODE_PLACE);
737 if (pos_ != cdata_->end()) ++pos_;
738 return(*this);
739 }
740
741 std::string to_string(void) const override
742 { return(std::string{"eit_entering(cdata:"} +
743 std::to_string(elementa::base::to_number(cdata_)) +
744 ", &(*pos): " +
745 std::to_string(elementa::base::to_number(&(*pos_)))+ ")");}
746
747 void checkDeref(const std::string & place = "") const
748 {
749 elementa::patterns::Validatable::checkValid(
750 (place.empty() ? ELE_CODE_PLACE : place));
751 if (pos_ == cdata_->end())
752 throw(elementa::base::invstate{
753 "De-referencing end iterator"}.asEXC(
754 place.empty() ? ELE_CODE_PLACE : place));
755 }
756
757 private:
758
759 typename EInfo::ListOfIts * cdata_; // no ownership
760 typename EInfo::ListOfIts::iterator pos_;
761
762 void copyFrom(const EItImpl_Entering & oth)
763 { cdata_ = oth.cdata_; pos_ = oth.pos_; }
764 };
765
766
767 // ------ Checks
768
769 void checkVIT(const typename BaseGraph::viterator & v,
770 const std::string & place = "") const
771 {
772 if ((!v.valid()) || (v.isEnd()))
773 throw(elementa::base::invarg{
774 std::string{(v.valid() ?(v.isEnd() ? "End" : "") :
775 (v.isEnd() ?"Invalid+End" :"Invalid"))} +
776 " vertex iterator"}.asEXC(place.empty() ?
777 ELE_CODE_PLACE : place));
778 }
779
780 void checkEIT(const typename BaseGraph::eiterator & e,
781 const std::string & place = "") const
782 {
783 if ((!e.valid()) || (e.isEnd()))
784 throw(elementa::base::invarg{
785 std::string{(e.valid() ?(e.isEnd() ?"End" : "") :
786 (e.isEnd() ?"Invalid+End" :"Invalid"))} +
787 " edge iterator"}.asEXC(place.empty() ?
788 ELE_CODE_PLACE : place));
789 }
790
791
792 // ------ Transforming public and internal iterators
793
794 typename BaseGraph::viterator vallFromInternal(
795 const typename VInfo::List::iterator & vi) const
796 { return(typename BaseGraph::viterator{
797 typename BaseGraph::viterator::ImplementationPtr{
798 new VItImpl_All{data_.vertices_,vi}}}); }
799
800 typename BaseGraph::eiterator eallFromInternal(
801 const typename EInfo::List::iterator & ei) const
802 { return(typename BaseGraph::eiterator{
803 typename BaseGraph::eiterator::ImplementationPtr{
804 new EItImpl_All{data_.edges_,ei}}}); }
805
806 typename VInfo::List::iterator vinternalFromMultit(
807 const typename BaseGraph::viterator & vit) const
808 { // since VIT exists, at least one VInfo has been created before
809 return(VInfo::startFromVertex(&(*vit))->myselfit); }
810
811 typename EInfo::List::iterator einternalFromMultit(
812 const typename BaseGraph::eiterator & eit) const
813 { // since EIT exists, at least one EInfo has been created before
814 return(EInfo::startFromEdge(&(*eit))->myselfit); }
815
816
817 // ------ Helpers for the public iterators
818
819 typename BaseGraph::viterator vallbegin(void) const
820 { return(vallFromInternal(
821 const_cast<typename VInfo::List &>(data_.vertices_).begin())); }
822
823 typename BaseGraph::viterator vallend(void) const
824 { return(vallFromInternal(
825 const_cast<typename VInfo::List &>(data_.vertices_).end())); }
826
827 typename BaseGraph::eiterator eallbegin(void) const
828 { return(eallFromInternal(
829 const_cast<typename EInfo::List &>(data_.edges_).begin())); }
830
831 typename BaseGraph::eiterator eallend(void) const
832 { return(eallFromInternal(
833 const_cast<typename EInfo::List &>(data_.edges_).end())); }
834
835 typename BaseGraph::eiterator eleavingbegin(
836 const typename BaseGraph::viterator &v) const
837 { checkVIT(v,ELE_CODE_PLACE);
838 return(typename BaseGraph::eiterator{
839 typename BaseGraph::eiterator::ImplementationPtr{
840 new EItImpl_Leaving{data_.vertices_,
841 vinternalFromMultit(v)}}}); }
842
843 typename BaseGraph::eiterator eleavingend(
844 const typename BaseGraph::viterator &v) const
845 { checkVIT(v,ELE_CODE_PLACE);
846 return(typename BaseGraph::eiterator{
847 typename BaseGraph::eiterator::ImplementationPtr{
848 new EItImpl_Leaving{data_.vertices_,
849 vinternalFromMultit(v),false}}}); }
850
851 typename BaseGraph::eiterator eenteringbegin(
852 const typename BaseGraph::viterator &v) const
853 { checkVIT(v,ELE_CODE_PLACE);
854 return(typename BaseGraph::eiterator{
855 typename BaseGraph::eiterator::ImplementationPtr{
856 new EItImpl_Entering{data_.vertices_,
857 vinternalFromMultit(v)}}}); }
858
859 typename BaseGraph::eiterator eenteringend(
860 const typename BaseGraph::viterator &v) const
861 { checkVIT(v,ELE_CODE_PLACE);
862 return(typename BaseGraph::eiterator{
863 typename BaseGraph::eiterator::ImplementationPtr{
864 new EItImpl_Entering{data_.vertices_,
865 vinternalFromMultit(v),false}}}); }
866
867};
868
869
870
873} // end graphs namespace
874
875} // end adts namespace
876
877} // end elementa namespace
878
879
880#endif
881
882
elementa::adts::graphs::Graph::VectorOfEIts
A vector of edge iterators (might be repeated).
Definition: graphs.h:150
elementa::adts::graphs::Graph::VectorOfVIts
A vector of vertex iterators (might be repeated).
Definition: graphs.h:131
ELE_CODE_TRACE_OFF
#define ELE_CODE_TRACE_OFF
Place this inside local scope (e.g., routine) to deactivate traces there.
Definition: debugging.h:283
ELE_CODE_PLACE
#define ELE_CODE_PLACE
Produces a std::string with the place of source where the macro is placed.
Definition: debugging.h:194
elementa::base::invarg
Exception for indicating that some argument of a method/function is invalid.
Definition: exceptions.h:260
elementa::base::invstate
Exception for indicating that some object is in invalid state.
Definition: exceptions.h:230
elementa::base::to_number
LongestUnsigned to_number(const void *p)
Convert a pointer address to a number.
elementa::adts::graphs::Graph::eiterator
elementa::base::MultIterator< Edge > eiterator
Edge iterator. ForwardLegacyIterator.
Definition: graphs.h:121
elementa::adts::graphs::Graph::viterator
elementa::base::MultIterator< Vertex > viterator
Vertex iterator. ForwardLegacyIterator.
Definition: graphs.h:118
elementa::adts::graphs::Graph::operator=
Graph & operator=(const Graph &oth)=default
Copy assignment.
elementa::adts::graphs::Graph
All graph classes derive from this one.
Definition: graphs.h:107
elementa::adts::graphs::size_vertex
size_t size_vertex
For holding numbers of vertices of a graph.
Definition: graphs.h:68
elementa::adts::graphs::size_edge
size_t size_edge
For holding numbers of edges of a graph.
Definition: graphs.h:71
elementa::base::MultItImpl< Vertex >::operator=
MultItImpl & operator=(const MultItImpl &oth)
Copy assignment.
Definition: iterators.h:172
elementa::base::MultItImpl< Vertex >::MultItImpl
MultItImpl(void)
Default constructor: invalid state.
Definition: iterators.h:165
elementa::base::MultItImpl
Base class for implementing diverse iteration behaviors.
Definition: iterators.h:149
elementa::base::MultIterator
A mutable iterator that can have multiple iteration behaviors. Forward case.
Definition: iterators.h:299
elementa::adts::graphs::SparseGraph::size_vertices
size_vertex size_vertices(void) const
Must return the number of vertices.
Definition: sparse_graphs.h:132
elementa::adts::graphs::SparseGraph::operator=
SparseGraph & operator=(const SparseGraph &oth)
Copy assignment.
Definition: sparse_graphs.h:97
elementa::adts::graphs::SparseGraph::SparseGraph
SparseGraph(SparseGraph &&oth)
Move constructor.
Definition: sparse_graphs.h:102
elementa::adts::graphs::SparseGraph::SparseGraph
SparseGraph(void)
Default constructor.
Definition: sparse_graphs.h:89
elementa::adts::graphs::SparseGraph::emptyClone
SparseGraph * emptyClone(void) const override
Derived classes can override this to provide a clone that is "empty".
Definition: sparse_graphs.h:117
elementa::adts::graphs::SparseGraph::splice
void splice(BaseGraph &oth, typename BaseGraph::VectorOfVIts *svothinds=nullptr, typename BaseGraph::VectorOfEIts *seothinds=nullptr, typename BaseGraph::VectorOfVIts *svinds=nullptr, typename BaseGraph::VectorOfEIts *seinds=nullptr)
Definition: sparse_graphs.h:180
elementa::adts::graphs::SparseGraph::size_edges
size_edge size_edges(void) const
Must return the number of edges.
Definition: sparse_graphs.h:134
elementa::adts::graphs::SparseGraph::insert
BaseGraph::viterator insert(const Vertex &v)
Must insert one more vertex in the graph, unconnected to any other.
Definition: sparse_graphs.h:152
elementa::adts::graphs::SparseGraph::SparseGraph
SparseGraph(const SparseGraph &oth)
Copy constructor.
Definition: sparse_graphs.h:92
elementa::adts::graphs::SparseGraph::empty
bool empty(void) const
Must return true if the graph is empty.
Definition: sparse_graphs.h:126
elementa::adts::graphs::SparseGraph::~SparseGraph
virtual ~SparseGraph(void)
Destructor.
Definition: sparse_graphs.h:112
elementa::adts::graphs::SparseGraph::operator=
SparseGraph & operator=(SparseGraph &&oth)
Move assignment.
Definition: sparse_graphs.h:107
elementa::adts::graphs::SparseGraph::clone
SparseGraph * clone(void) const
Derived classes must implement this method varying its return type.
Definition: sparse_graphs.h:114
elementa::adts::graphs::SparseGraph::clear
void clear(void)
Must clear the content of the graph.
Definition: sparse_graphs.h:129
elementa::adts::graphs::SparseGraph
A graph that stores all its info in a sparse manner.
Definition: sparse_graphs.h:74
elementa::patterns::Validatable::operator=
Validatable & operator=(const Validatable &oth)
Derived classes must call this base optor if they have non-default ones.
Definition: validatable.h:135
elementa::patterns::Validatable::valid
bool valid(void) const noexcept
Public method to be used by users of the derived class.
Definition: validatable.h:106
elementa::patterns::Validatable::checkValid
virtual void checkValid(const std::string &place="") const
Call this method if an exception is needed when in invalid state.
Definition: validatable.h:110
elementa::patterns::Validatable::setValid
void setValid(bool defval=true) noexcept
Derived classes can rewrite their own (hiding this, calling this).
Definition: validatable.h:144