0024473: TKMath, BVH - introduce template-based package for Bounding volume hierarchy...
[occt.git] / src / BVH / BVH_Sorter.lxx
1 // Created on: 2014-01-10
2 // Created by: Denis BOGOLEPOV
3 // Copyright (c) 2013 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
7 // This library is free software; you can redistribute it and / or modify it
8 // under the terms of the GNU Lesser General Public version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 // =======================================================================
17 // function : Perform
18 // purpose  :
19 // =======================================================================
20 template<class T, int N>
21 void BVH_Sorter<T, N>::Perform (BVH_Set<T, N>*         theSet,
22                                 const Standard_Integer theAxis)
23 {
24   Perform (theSet, theAxis, 0, theSet->Size() - 1);
25 }
26
27 // =======================================================================
28 // function : Perform
29 // purpose  :
30 // =======================================================================
31 template<class T, int N>
32 void BVH_Sorter<T, N>::Perform (BVH_Set<T, N>*         theSet,
33                                 const Standard_Integer theAxis,
34                                 const Standard_Integer theBegElement,
35                                 const Standard_Integer theEndElement)
36 {
37   Standard_Integer aLft = theBegElement;
38   Standard_Integer aRgh = theEndElement;
39
40   T aPivot = theSet->Center ((aRgh + aLft) / 2, theAxis);
41
42   while (aLft < aRgh)
43   {
44     while (theSet->Center (aLft, theAxis) < aPivot && aLft < theEndElement)
45     {
46       ++aLft;
47     }
48
49     while (theSet->Center (aRgh, theAxis) > aPivot && aRgh > theBegElement)
50     {
51       --aRgh;
52     }
53
54     if (aLft <= aRgh)
55     {
56       if (aLft != aRgh)
57       {
58         theSet->Swap (aLft, aRgh);
59       }
60
61       ++aLft;
62       --aRgh;
63     }
64   }
65
66   if (aRgh > theBegElement)
67   {
68     Perform (theSet, theAxis, theBegElement, aRgh);
69   }
70
71   if (aLft < theEndElement)
72   {
73     Perform (theSet, theAxis, aLft, theEndElement);
74   }
75 }