0031035: Coding - uninitialized class fields reported by Visual Studio Code Analysis
[occt.git] / src / MAT / MAT_Graph.cxx
1 // Created on: 1993-05-06
2 // Created by: Yves FRICAUD
3 // Copyright (c) 1993-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17
18 #include <MAT_Arc.hxx>
19 #include <MAT_BasicElt.hxx>
20 #include <MAT_Bisector.hxx>
21 #include <MAT_DataMapIteratorOfDataMapOfIntegerBasicElt.hxx>
22 #include <MAT_DataMapOfIntegerArc.hxx>
23 #include <MAT_DataMapOfIntegerBasicElt.hxx>
24 #include <MAT_Edge.hxx>
25 #include <MAT_Graph.hxx>
26 #include <MAT_ListOfBisector.hxx>
27 #include <MAT_Node.hxx>
28 #include <MAT_SequenceOfArc.hxx>
29 #include <MAT_Zone.hxx>
30 #include <Precision.hxx>
31 #include <Standard_Type.hxx>
32
33 IMPLEMENT_STANDARD_RTTIEXT(MAT_Graph,Standard_Transient)
34
35 //------------------
36 // functions static.
37 //-------------------
38   static Handle(MAT_Arc) MakeArc(const Handle(MAT_Bisector)&     aBisector,
39                                  MAT_DataMapOfIntegerBasicElt&   TheBasicElts,
40                                  MAT_DataMapOfIntegerArc&        TheArcs,
41                                  Standard_Integer&               IndTabArcs);
42
43 // =====================================================================
44 // Constructeur vide.
45 // =====================================================================
46 MAT_Graph::MAT_Graph()
47 : numberOfArcs(0),
48   numberOfNodes(0),
49   numberOfBasicElts(0),
50   numberOfInfiniteNodes(0)
51 {
52 }
53
54 // =====================================================================
55 // function : Perform
56 // purpose  : Creation du graphe contenant le resultat.
57 // =====================================================================
58 void MAT_Graph::Perform(const Standard_Boolean             SemiInfinite,
59                         const Handle(MAT_ListOfBisector)&  TheRoots,
60                         const Standard_Integer             NbBasicElts,
61                         const Standard_Integer             NbArcs)
62 {
63   Standard_Integer        NbRoots;
64   Handle(MAT_Arc)         FirstArc;
65   Handle(MAT_Arc)         CurrentArc;
66   Handle(MAT_Node)        Extremite;
67   Standard_Integer        IndTabArcs = 1;
68   Standard_Integer        IndTabNodes;
69   Standard_Integer        i;
70   Standard_Real           DistExt;
71   Standard_Integer        IndExt;
72   Handle(MAT_Arc)         PreviousArc = CurrentArc;
73
74   //------------------------
75   // Construction du graphe.
76   //------------------------
77
78   if (SemiInfinite) {
79     NbRoots               = TheRoots->Number();
80     numberOfInfiniteNodes = NbRoots;
81   }
82   else {
83     NbRoots               = 1;
84     numberOfInfiniteNodes = 0;
85   } 
86
87   numberOfArcs         = NbArcs;
88   numberOfBasicElts    = NbBasicElts;
89   numberOfNodes        = NbRoots + NbArcs;
90   IndTabNodes          = numberOfNodes;
91
92   //---------------------------
93   //... Creation des BasicElts.
94   //---------------------------
95   for (i = 1; i <= NbBasicElts; i++) {
96     theBasicElts.Bind(i,new MAT_BasicElt(i));
97     theBasicElts(i)->SetGeomIndex(i);
98   }
99
100   //--------------------------------------------------------------------
101   // ... Creation des ARCS et des NODES.
102   //     Construction des arbres d arcs a partir des <Bisector> racines.
103   //--------------------------------------------------------------------
104
105   if (SemiInfinite) {
106
107     // Plusieurs points d entree a l infini.
108     //--------------------------------------
109     TheRoots->First();
110
111     while (TheRoots->More()) {
112       CurrentArc = MakeArc(TheRoots->Current(),
113                            theBasicElts,
114                            theArcs,
115                            IndTabArcs);
116       Extremite = new MAT_Node (0,CurrentArc,Precision::Infinite());
117       Extremite ->SetIndex     (IndTabNodes);
118       CurrentArc->SetSecondNode(Extremite);
119       theNodes.Bind(IndTabNodes,Extremite);
120       TheRoots->Next();     
121       IndTabNodes--;
122     }
123   }
124   else {
125     // -----------------------------------------------
126     // Un seul point d entree .
127     // Creation d un premier ARC et du NODE racine.
128     // -----------------------------------------------
129     NbRoots = 1;
130     TheRoots->First();
131     CurrentArc = MakeArc(TheRoots->Current(),
132                          theBasicElts,
133                          theArcs,
134                          IndTabArcs);
135     DistExt   = TheRoots->Current()->FirstEdge()->Distance();
136     IndExt    = TheRoots->Current()->EndPoint();
137
138     Extremite = new MAT_Node(IndExt,CurrentArc,DistExt);
139     Extremite ->SetIndex     (IndTabNodes);
140     CurrentArc->SetSecondNode(Extremite);
141     theNodes.Bind(IndTabNodes,Extremite);
142     IndTabNodes--;
143     
144     // -----------------------------------------------------------
145     // ...Creation des ARCs issues de la racine.
146     //    Codage des voisinages sur ces arcs et mise a jour de la
147     //    sequence des arcs issue du Node racine.
148     // -----------------------------------------------------------
149     FirstArc     = CurrentArc;
150     PreviousArc  = FirstArc;
151     TheRoots->Next();
152
153     while (TheRoots->More()) {
154       CurrentArc = MakeArc(TheRoots->Current(),
155                            theBasicElts,
156                            theArcs,
157                            IndTabArcs);
158       CurrentArc ->SetSecondNode(Extremite);
159       CurrentArc ->SetNeighbour (MAT_Left,Extremite ,PreviousArc);
160       PreviousArc->SetNeighbour (MAT_Right,Extremite,CurrentArc);
161
162       PreviousArc = CurrentArc;
163       TheRoots->Next();
164     }
165     FirstArc  ->SetNeighbour (MAT_Left ,Extremite,CurrentArc);
166     CurrentArc->SetNeighbour (MAT_Right,Extremite,FirstArc);
167   }
168
169   // ----------------------------------------------------
170   // Les sequence des Arcs des Nodes racines sont a jour.
171   // Mise a jour des sequences des autres Nodes.
172   // ----------------------------------------------------
173   UpDateNodes(IndTabNodes);
174 }
175
176 //=============================================================================
177 //function : Arc
178 //Purpose  :
179 //=============================================================================
180 Handle(MAT_Arc)  MAT_Graph::Arc(const Standard_Integer Index) const
181 {
182   return theArcs(Index);
183 }
184
185 //=============================================================================
186 //function : BasicElt
187 //Purpose  :
188 //=============================================================================
189 Handle(MAT_BasicElt)  MAT_Graph::BasicElt(const Standard_Integer Index) const
190 {
191   return theBasicElts(Index);
192 }
193
194 //=============================================================================
195 //function : Node
196 //Purpose  :
197 //=============================================================================
198 Handle(MAT_Node)  MAT_Graph::Node(const Standard_Integer Index) const
199 {
200   return theNodes(Index);
201 }
202
203 //=============================================================================
204 //function : NumberOfArcs
205 //Purpose  :
206 //=============================================================================
207 Standard_Integer  MAT_Graph::NumberOfArcs() const
208 {
209   return numberOfArcs;
210 }
211
212 //=============================================================================
213 //function : NumberOfNodes
214 //Purpose  :
215 //=============================================================================
216 Standard_Integer  MAT_Graph::NumberOfNodes() const
217 {
218   return numberOfNodes;
219 }
220
221 //=============================================================================
222 //function : NumberOfInfiniteNodes
223 //Purpose  :
224 //=============================================================================
225 Standard_Integer  MAT_Graph::NumberOfInfiniteNodes() const
226 {
227   return numberOfInfiniteNodes;
228 }
229
230 //=============================================================================
231 //function : NumberOfBasicElts
232 //Purpose  :
233 //=============================================================================
234 Standard_Integer  MAT_Graph::NumberOfBasicElts() const
235 {
236   return numberOfBasicElts;
237 }
238
239 //=============================================================================
240 //function : FusionOfBasicElts 
241 //Purpose  :
242 //=============================================================================
243 void MAT_Graph::FusionOfBasicElts(const Standard_Integer  IndexElt1, 
244                                   const Standard_Integer  IndexElt2,
245                                         Standard_Boolean& MergeArc1,
246                                         Standard_Integer& IGeomArc1,
247                                         Standard_Integer& IGeomArc2,
248                                         Standard_Boolean& MergeArc2,
249                                         Standard_Integer& IGeomArc3,
250                                         Standard_Integer& IGeomArc4)
251 {
252   Handle(MAT_BasicElt) Elt1 = theBasicElts(IndexElt1);
253   Handle(MAT_BasicElt) Elt2 = theBasicElts(IndexElt2);
254   
255   if (Elt1 == Elt2) return;
256
257   Standard_Integer i;
258   Handle(MAT_Zone) Zone2   = new MAT_Zone(Elt2);
259
260   //--------------------------------------------------------------------
261   // Les arcs de la zone de Elt2 ne separent plus Elt2 et qq chose mais
262   // Elt1 et qq chose.
263   //--------------------------------------------------------------------
264   for (i = 1; i <= Zone2->NumberOfArcs(); i++) {
265      if (Zone2->ArcOnFrontier(i)->FirstElement() == Elt2) {
266        theArcs(Zone2->ArcOnFrontier(i)->Index())->SetFirstElement(Elt1);
267      }
268      else {
269        theArcs(Zone2->ArcOnFrontier(i)->Index())->SetSecondElement(Elt1);
270      }
271    }
272
273   //-------------------------------------------------------------------
274   // le EndArc de Elt1 et le StartArc de Elt2 peuvent separes les memes
275   // elements de base => Fusion des deux arcs et mise a jour des noeuds.
276   //-------------------------------------------------------------------
277   Handle(MAT_Arc) EA1 = Elt1->EndArc();
278   Handle(MAT_Arc) SA2 = Elt2->StartArc();
279
280   Handle(MAT_BasicElt) E1 = EA1->FirstElement();
281   Handle(MAT_BasicElt) E2 = EA1->SecondElement();
282   Handle(MAT_BasicElt) E3 = SA2->FirstElement();
283   Handle(MAT_BasicElt) E4 = SA2->SecondElement();
284   MergeArc1 = Standard_False;
285
286   if ( (E1 == E3 || E1 == E4) && (E2 == E3 || E2 == E4)) {
287     FusionOfArcs(theArcs(EA1->Index()),theArcs(SA2->Index()));
288     MergeArc1 = Standard_True;
289     IGeomArc1 = EA1->GeomIndex();
290     IGeomArc2 = SA2->GeomIndex();
291   }
292   
293   //-------------------------------------------------
294   // La fin de Elt1 devient la fin de Elt2.
295   //-------------------------------------------------
296   Elt1->SetEndArc(Elt2->EndArc());
297
298   //-------------------------------------------------------------------
299   // le EndArc de Elt1 et le StartArc de Elt1 peuvent separer les memes
300   // elements de base.
301   // si les noeuds des arcs ne sont pas sur le contour 
302   //    => fusion des arcs.(contour ferme compose d un seul BasicElt)
303   // sinon rien            (contour ferme compose de deux BasicElts)
304   //-------------------------------------------------------------------
305   Handle(MAT_Arc) SA1 = Elt1->StartArc();
306   EA1 = Elt1->EndArc();
307
308   if ( EA1 != SA1 ) {
309     E1 = EA1->FirstElement ();
310     E2 = EA1->SecondElement();
311     E3 = SA1->FirstElement ();
312     E4 = SA1->SecondElement();
313
314     Standard_Boolean OnFig = (EA1->FirstNode() ->OnBasicElt() ||
315                               EA1->SecondNode()->OnBasicElt() ||
316                               SA1->FirstNode() ->OnBasicElt() ||
317                               SA1->SecondNode()->OnBasicElt() );
318
319     MergeArc2 = Standard_False;
320
321     if ((E1 == E3 || E1 == E4) && (E2 == E3 || E2 == E4) && !OnFig) {
322       FusionOfArcs(theArcs(EA1->Index()),theArcs(SA1->Index()));
323       MergeArc2 = Standard_True;
324       IGeomArc3 = EA1->GeomIndex();
325       IGeomArc4 = SA1->GeomIndex();
326     }
327   }
328   
329   //----------------------------------------------------
330   // un element de base a ete elimine.
331   //----------------------------------------------------
332   theBasicElts.UnBind(Elt2->Index());
333   numberOfBasicElts--;
334 }
335
336 //=============================================================================
337 // function : FusionOfArcs
338 // purpose  : Fusion de deux arcs separant les memes elements.
339 //            l <Arc1> ira du Second noeud de <Arc2> au second Noeud de <Arc1>.
340 //=============================================================================
341 void MAT_Graph::FusionOfArcs(const Handle(MAT_Arc)& Arc1, 
342                              const Handle(MAT_Arc)& Arc2)
343 {
344
345   Handle(MAT_Node) OldNode1 = Arc1->FirstNode();
346   Handle(MAT_Node) OldNode2 = Arc2->FirstNode();
347
348   Arc1->SetFirstNode(Arc2->SecondNode());
349   
350   //--------------------------------------------------------------------
351   // Mise a jour des voisinages autour du nouveau premier noeud de Arc1.
352   //--------------------------------------------------------------------
353   if (!Arc2->SecondNode()->Infinite()) {
354     Handle(MAT_Arc) LNeighbour = Arc2->Neighbour(Arc2->SecondNode(),MAT_Left);
355     Handle(MAT_Arc) RNeighbour = Arc2->Neighbour(Arc2->SecondNode(),MAT_Right);
356   
357     Arc1->SetFirstArc(MAT_Left,LNeighbour);
358     Arc1->SetFirstArc(MAT_Right,RNeighbour);
359     theArcs(LNeighbour->Index())->SetNeighbour(MAT_Right,
360                                                Arc2->SecondNode(),
361                                                Arc1);
362     theArcs(RNeighbour->Index())->SetNeighbour(MAT_Left,
363                                                Arc2->SecondNode(),
364                                                Arc1);
365   }
366   else {
367     Handle(MAT_Arc) EmptyArc;
368     Arc1->SetFirstArc(MAT_Left ,EmptyArc);
369     Arc1->SetFirstArc(MAT_Right,EmptyArc);
370   }
371
372   //-------------------------------------------------------------------
373   // Mise a jour du premier noeud Arc1.
374   //-----------------------------------------------------------------
375   Arc1->FirstNode()->SetLinkedArc(Arc1);
376
377   //------------------------------------
378   // Elimination de Arc2 et des OldNode 
379   //------------------------------------
380   if (theNodes.IsBound(OldNode1->Index())) {
381     theNodes.UnBind(OldNode1->Index());
382     numberOfNodes--;
383   }
384   if (theNodes.IsBound(OldNode2->Index())) {
385     theNodes.UnBind(OldNode2->Index());
386     numberOfNodes--;
387   }
388
389   // Note: the Arc2 is actually a reference to a handle contained in theArcs map;
390   // it is necessary to create copy of that handle and use only it to access
391   // that object, since the handle contained in the map is destroyed by UnBind()
392   Handle(MAT_Arc) anArc2 = Arc2;
393   theArcs .UnBind(Arc2->Index());
394   numberOfArcs--;
395   
396   for (Standard_Integer i = 1; i <= 2; i++){
397     Handle(MAT_BasicElt) BE;
398     if (i == 1)
399       BE  = theBasicElts(anArc2->FirstElement ()->Index());
400     else
401       BE  = theBasicElts(anArc2->SecondElement ()->Index());
402
403     if (BE->StartArc()  == anArc2) { BE->SetStartArc(Arc1);}
404     if (BE->EndArc  ()  == anArc2) { BE->SetEndArc  (Arc1);}
405   }
406 }
407
408 //=============================================================================
409 // function : CompactArcs
410 // purpose  : Decalage des Arcs pour boucher les trous.
411 //=============================================================================
412 void MAT_Graph::CompactArcs() 
413 {
414   Standard_Integer IFind      = 0;  
415   Standard_Integer i          = 1;
416   Standard_Boolean YaDecalage = Standard_False;
417
418   while (IFind < numberOfArcs) {
419     if (!theArcs.IsBound(i)) {
420       YaDecalage = Standard_True;
421     }
422     else {
423       IFind++;
424       if (YaDecalage) {
425         theArcs(i)->SetIndex(IFind);
426         theArcs.Bind(IFind,theArcs(i));
427         theArcs.UnBind(i);
428       }
429     }
430     i++;
431   }
432 }
433
434 //=============================================================================
435 // function : CompactNodes
436 // purpose  : Decalage des Nodes pour boucher les trous.
437 //=============================================================================
438 void MAT_Graph::CompactNodes() 
439 {
440   Standard_Integer IFind      = 0;  
441   Standard_Integer i          = 1;
442   Standard_Boolean YaDecalage = Standard_False;
443
444   while (IFind < numberOfNodes) {
445     if (!theNodes.IsBound(i)) {
446       YaDecalage = Standard_True;
447     }
448     else {
449       IFind++;
450       if (YaDecalage) {
451         theNodes(i)->SetIndex(IFind);
452         theNodes.Bind(IFind,theNodes(i));
453         theNodes.UnBind(i);
454       }
455     }
456     i++;
457   }
458 }
459
460 //=============================================================================
461 // function : ChangeBasicElts
462 // purpose  : 
463 //=============================================================================
464 void MAT_Graph::ChangeBasicElts(const MAT_DataMapOfIntegerBasicElt& NewMap) 
465 {
466   theBasicElts = NewMap;   
467   MAT_DataMapIteratorOfDataMapOfIntegerBasicElt Ite;
468   for (Ite.Initialize(theBasicElts); Ite.More(); Ite.Next()) {
469     Ite.Value()->SetIndex(Ite.Key());
470   }
471 }
472
473 //=============================================================================
474 //function : ChangeBasicElt
475 //Purpose  :
476 //=============================================================================
477 Handle(MAT_BasicElt)  MAT_Graph::ChangeBasicElt(const Standard_Integer Index) 
478 {
479   return theBasicElts(Index);
480 }
481
482 //=============================================================================
483 // function : UpDateNodes
484 // purpose  : Mise a jour des sequence d'ARC de chaque FirstNode de chaque arc.
485 //            et stockage de chaque noeud dans la table des noeuds.
486 //            Les noeuds racines sont traites dans PERFORM.
487 //=============================================================================
488 void MAT_Graph::UpDateNodes (Standard_Integer&  IndTabNodes)
489 {  
490   Standard_Integer    i;
491   Handle(MAT_Node)    Bout;
492   Handle(MAT_Arc)     CurrentArc;
493   
494   for (i = 1; i <= numberOfArcs; i++) {
495     Bout = theArcs(i)->FirstNode();
496     theNodes.Bind(IndTabNodes,Bout);
497     Bout->SetIndex(IndTabNodes);
498     IndTabNodes--;
499     Bout->SetLinkedArc(theArcs(i));
500   }
501 }
502
503
504 //=============================================================================
505 // function : MakeArc
506 // purpose  : Creation des <ARCS> en parcourant l'arbre issue de <aBisector>.
507 //=============================================================================
508 static Handle(MAT_Arc) MakeArc(const Handle(MAT_Bisector)&     aBisector,
509                                MAT_DataMapOfIntegerBasicElt&   TheBasicElts,
510                                MAT_DataMapOfIntegerArc&        TheArcs,
511                                Standard_Integer&               IndTabArcs)
512 {
513   Handle(MAT_Arc)              CurrentArc;
514   Handle(MAT_Arc)              PrevArc;
515   Handle(MAT_Arc)              NextArc;
516   Handle(MAT_Node)             Extremite;
517   Handle(MAT_ListOfBisector)   BisectorList;
518   Standard_Real                DistExt;
519   
520 #ifdef OCCT_DEBUG_Graph
521   std::cout<<"Construction Arc : Index"<<aBisector->IndexNumber()<<std::endl;
522   std::cout<<"Construction Arc : Bisector"<<aBisector->BisectorNumber()<<std::endl;
523 #endif
524   
525   CurrentArc = new MAT_Arc(IndTabArcs,
526                            aBisector->BisectorNumber(),
527                            TheBasicElts(aBisector->FirstEdge()->EdgeNumber()),
528                            TheBasicElts(aBisector->SecondEdge()->EdgeNumber())
529                            );
530   DistExt   = aBisector->DistIssuePoint();
531   if (DistExt == Precision::Infinite()) {
532     DistExt = 1.0;
533 #ifdef OCCT_DEBUG_Graph
534     std::cout<<"PB:RECUPERATION DISTANCE SUR ISSUEPOINT."<<std::endl;
535 #endif
536   }
537   
538   Extremite = new MAT_Node(aBisector->IssuePoint(),CurrentArc,DistExt);
539
540   CurrentArc->SetFirstNode(Extremite);
541   BisectorList = aBisector->List();
542   BisectorList->First();
543
544   if (!BisectorList->More()) {
545     // -------------------
546     // Arc sur le contour.
547     // -------------------
548     TheBasicElts(aBisector->SecondEdge()->EdgeNumber())
549       ->SetStartArc(CurrentArc);
550     TheBasicElts(aBisector->FirstEdge()->EdgeNumber())
551       ->SetEndArc(CurrentArc);
552   }
553   else {
554     PrevArc = CurrentArc;
555       
556     while (BisectorList->More()) {
557       NextArc = MakeArc(BisectorList->Current(),
558                         TheBasicElts,
559                         TheArcs,
560                         IndTabArcs);
561       NextArc->SetSecondNode(Extremite);
562       NextArc->SetNeighbour (MAT_Left ,Extremite,PrevArc);
563       PrevArc->SetNeighbour (MAT_Right,Extremite,NextArc);
564       PrevArc  = NextArc;
565       BisectorList->Next();
566     }
567     CurrentArc->SetNeighbour(MAT_Left ,Extremite,NextArc);
568     NextArc   ->SetNeighbour(MAT_Right,Extremite,CurrentArc);
569   }
570   
571 #ifdef OCCT_DEBUG_Graph
572   std::cout<<"IndTabArcs = "<<IndTabArcs<<std::endl;
573   std::cout<<"ArcIndex   = "<<CurrentArc->ArcIndex()<<std::endl;
574 #endif  
575   CurrentArc->SetIndex(IndTabArcs);
576   TheArcs.Bind(IndTabArcs,CurrentArc);
577   IndTabArcs          = IndTabArcs + 1;
578
579   return CurrentArc;
580 }
581
582
583
584
585