View Issue Details

Related ChangesetsJump to NotesJump to History
IDProjectCategoryView StatusDate SubmittedLast Update
0027915Open CASCADEOCCT:Foundation Classespublic2016-09-28 18:322020-04-21 22:28
ReportermsvAssigned Toapn  
PrioritynormalSeverityintegration request 
Status closedResolutionfixed 
Product Version7.0.0 
Target Version7.1.0Fixed in Version7.1.0 
Summary0027915: Foundation Classes - remove the class NCollection_QuickSort
DescriptionThe class NCollection_QuickSort contains old non-optimal algorithm of sorting. The class std::sort makes the job better.

It is suggested to remove NCollection_QuickSort, and replace its usage with std::sort where it is needed. For now, I see the only usage of it in the file BRepExtrema_DistShapeShape.cxx
Steps To ReproduceNot required
TagsNo tags attached.
Test case numberNot needed

Relationships

parent of 0031512 closedbugmaster Open CASCADE Foundation Classes - drop unused class NCollection_Comparator 

Activities

git

2016-09-29 19:08

administrator   ~0058327

Branch CR27915 has been created by ski.

SHA-1: d870d0a07c0b864a64070e5de40f2da46dc16ffc


Detailed log of new commits:

Author: ski
Date: Thu Sep 29 19:08:20 2016 +0300

    0027915: Foundation Classes - remove the class NCollection_QuickSort
    
    Class NCollection_QuickSort was removed.

ski

2016-09-29 19:10

developer   ~0058328

Dear msv,

please review.

msv

2016-09-30 11:57

developer   ~0058331

Please wrap long line 96.

git

2016-09-30 12:06

administrator   ~0058332

Branch CR27915 has been updated forcibly by ski.

SHA-1: 62267893919681755aec8de8d8841591016525b2

ski

2016-09-30 12:07

developer   ~0058333

Done.

kgv

2016-09-30 12:12

developer   ~0058334

Removal of public API should be mentioned in porting notes.

msv

2016-09-30 12:16

developer   ~0058338

Reviewed.

msv

2016-09-30 12:18

developer   ~0058339

Please update porting notes.

git

2016-09-30 12:54

administrator   ~0058342

Branch CR27915 has been updated by ski.

SHA-1: 84180eecec7b73b61c21005d7bfb7b447dcf7e52


Detailed log of new commits:

Author: ski
Date: Thu Sep 29 19:08:20 2016 +0300

    Updated porting notes.

ski

2016-09-30 12:55

developer   ~0058343

Porting notes were updated,

please review.

msv

2016-09-30 14:49

developer   ~0058345

Reviewed.

git

2016-10-03 15:23

administrator   ~0058365

Branch CR27915 has been updated forcibly by mkv.

SHA-1: 47ed13fa8aed429bd633947e31b32d261c691c52

mkv

2016-10-04 16:58

tester   ~0058405

Dear BugMaster,
Branch CR27915 was rebased on current master of occt git-repository.
SHA-1: 47ed13fa8aed429bd633947e31b32d261c691c52

mkv

2016-10-04 16:59

tester   ~0058406

Dear BugMaster,
Branch CR27915 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
SHA-1: 47ed13fa8aed429bd633947e31b32d261c691c52

Number of compiler warnings:

occt component :
Linux: 0 (0 on master)
Windows: 0 (0 on master)
MacOS : 0 (0 on master)

products component :
Linux: 64 (64 on master)
Windows: 0 (0 on master)
MacOS : 1145

Regressions/Differences/Improvements:
http://occt-tests/CR27915-master-OCCT/Debian70-64/bugs/moddata_3/bug24896.html
http://occt-tests/CR27915-master-OCCT/Windows-64-VC10/bugs/moddata_3/bug24896.html
bugs moddata_3 bug24896: FAILED

Testing cases:
Not needed

Testing on Linux:
occt component :
Total MEMORY difference: 90771821 / 90543009 [+0.25%]
Total CPU difference: 19380.519999999833 / 19276.75999999978 [+0.54%]
products component :
Total MEMORY difference: 30032513 / 30036359 [-0.01%]
Total CPU difference: 5178.37999999997 / 5173.459999999983 [+0.10%]

Testing on Windows:
occt component :
Total MEMORY difference: 57228492 / 57236340 [-0.01%]
Total CPU difference: 19240.710937098607 / 18116.099728098634 [+6.21%]
products component :
Total MEMORY difference: 21274098 / 21238613 [+0.17%]
Total CPU difference: 5405.69985169998 / 4976.229098699953 [+8.63%]

There are following differences in images found by testdiff.
http://occt-tests/CR27915-master-OCCT/Debian70-64/diff-Debian70-64.html
http://occt-tests/CR27915-master-OCCT/Windows-64-VC10/diff-Windows-64-VC10-image.html
IMAGE bugs vis bug26056: bug26056.png differs

mkv

2016-10-04 16:59

tester   ~0058407

Dear ski,
Branch CR27915 has been rejected due to:
- regressions/differences/improvements
- differences in images

ski

2016-10-05 13:43

developer   ~0058422

Test case bugs moddata_3 bug24896:

This test case checks intersection between curve and planar face.
There are two solutions:
vertexes (66.6, 11.8556887323157, 0.3) and (66.6, -11.8556887483839, 0.3).
In these points distance between curve and face is equal to 0.
Function BRepExtrema_DistShapeShape founds these two solutions and sorts them by distance (distance is equal to 0 in each solution as i have already said).
In case of std::sort algorithm before last sorting of possible solutions:

0 1 2
0.2999899 1 3
0 1 4

First value in a row is a distance.
Second value is an index of the 1st sub-shape.
Third value is an index of the 2st sub-shape.

After sorting by std::sort we have:

0 1 2
0 1 4
0.2999899 1 3

In case of NCollection_QuickSort algorithm:
Before sorting:
0 1 2
0.2999899 1 3
0 1 4
After sorting:
0 1 4
0 1 2
0.2999899 1 3

So, it seems that solutions are right and just swapped. Test case should be corrected.



Differences in image bugs vis bug26056: bug26056.png
Images are different because of the same reason as above.

In case of std::sort algorithm
Before sorting
49.1999997992 1 1
49.1999997992 1 2
49.1999997992 1 3
49.1999997992 1 4
After soring
49.1999997992 1 1
49.1999997992 1 2
49.1999997992 1 3
49.1999997992 1 4

In case of NCollection_QuickSort algorithm
Before sorting
49.1999997992 1 1
49.1999997992 1 2
49.1999997992 1 3
49.1999997992 1 4
After soring
49.1999997992 1 2
49.1999997992 1 3
49.1999997992 1 4
49.1999997992 1 1

All solutions are right and can be used. Reference image should be updated.

Dear msv,

please comment.

abv

2016-10-05 14:22

manager   ~0058430

Sergey, can you try to use std::stable_sort on these cases? As it seems from your results, std::sort already produces more stable results that NCollection_QuickSort, and thus is better, but stable_sort should give us guarantee of stability in all cases.

msv

2016-10-05 15:09

developer   ~0058432

Sergey, I agree that algorithm DistShapeShape works right. However I have concern about the result image of the test case "bugs vis bug26056". Before the fix, the dimensions were drawn outside of the face and it was clear. Now the dimension lines (light green) overlap with the shapes, and the picture became unclear. Could you go deep in this test case and try to return the picture clear look?

git

2016-10-05 16:16

administrator   ~0058438

Branch CR27915 has been updated forcibly by ski.

SHA-1: 830c185ad9bf75334cfe95c93feba99ada2e7e17

git

2016-10-06 18:08

administrator   ~0058468

Branch CR27915 has been updated by ski.

SHA-1: 0313f9cf162d49ab62a03bf9dd2b153159d39e7b


Detailed log of new commits:

Author: ski
Date: Thu Oct 6 18:08:04 2016 +0300

    Direction of dimension lines was corrected.

ski

2016-10-06 18:44

developer   ~0058470

Test case bugs moddata_3 bug24896:

Without patch (NCollection_QuickSort is used)
Method AIS_LengthDimension::InitEdgeFaceLength computes direction of the edge "anEdge", this direction will be used for direction of the dimension lines.
In case of edge "anEdge" direction is equal to gp_Dir(1,0,0), (First vertex of the edge = (-100, -100, 0), last = (100, -100, 0))
After that InitEdgeFaceLength computes minimum distance between the edge and the face.
In case of NCollection_QuickSort DistShapeShape returns two solutions:
1) (100, -100, 0) Last vertex of the edge "anEdge"
1) (100, -100, 50) Corresponding vertex on the "aFace"
2) (-100, -100, 0) First vertex of the edge "anEdge"
2) (-100, -100, 50) Corresponding vertex on the "aFace"
InitEdgeFaceLength takes the first solution (last vertex of the edge) and builds dimension lines from these vertexes using previusly calculated direction gp_Dir(1,0,0).
After that dimension lines are drawn outside of the face and the edge.

With patch (std::stable_sort is used)
Method AIS_LengthDimension::InitEdgeFaceLength computes direction as it was discribed above.
After that InitEdgeFaceLength computes minimum distance between the edge and the face.
In case of std::stable_sort DistShapeShape returns two solutions:
1) (-100, -100, 0) First vertex of the edge "anEdge"
1) (-100, -100, 50) Corresponding vertex on the "aFace"
2) (100, -100, 0) Last vertex of the edge "anEdge"
2) (100, -100, 50) Corresponding vertex on the "aFace"
InitEdgeFaceLength takes the first one (first vertex of the edge) and builds dimension lines from these vertexes using previusly calculated direction gp_Dir(1,0,0).
After that dimension lines are drawn inside the face and the edge.

So, it is nessecery to reverse the direction of dimension lines in case when first vertex of edge is used.
Changes are located in last commit of branch CR27915.

Dear abv,

please review.

git

2016-10-07 12:16

administrator   ~0058475

Branch CR27915 has been updated forcibly by ski.

SHA-1: 960e1f44f3441108f9b486d14a414f3ec2c52ac2

ski

2016-10-07 13:08

developer   ~0058477

Dear abv,

I have corrected test case bugs moddata_3 bug24896.
Porting notes were modified as it was discussed.
Checking for vertexes was added to have correct direction of dimension lines.

git

2016-10-07 14:38

administrator   ~0058479

Branch CR27915 has been updated by abv.

SHA-1: 9ce1a1503e3f392575d9abf3d5439d971e587bdb


Detailed log of new commits:

Author: abv
Date: Fri Oct 7 14:38:17 2016 +0300

    // minor corrections in AIS

abv

2016-10-07 14:39

manager   ~0058480

Reviewed with some corrections, please test

git

2016-10-07 18:11

administrator   ~0058492

Branch CR27915 has been updated forcibly by mkv.

SHA-1: 45f0ab8fc775e42dcfe586dece5806ff82ebf633

mkv

2016-10-10 19:02

tester   ~0058529

Dear BugMaster,
Branch CR27915 was rebased on current master of occt git-repository.
SHA-1: 45f0ab8fc775e42dcfe586dece5806ff82ebf633

mkv

2016-10-10 19:04

tester   ~0058530

Dear BugMaster,
Branch CR27915 from occt git-repository (and master from products git-repository) was compiled on Linux, MacOS and Windows platforms and tested on Release mode.
SHA-1: 45f0ab8fc775e42dcfe586dece5806ff82ebf633

Number of compiler warnings:

occt component :
Linux: 0 (0 on master)
Windows: 0 (0 on master)
MacOS : 0 (0 on master)

products component :
Linux: 64 (64 on master)
Windows: 0 (0 on master)
MacOS : 1129

Regressions/Differences/Improvements:
No regressions/differences

Testing cases:
Not needed

Testing on Linux:
occt component :
Total MEMORY difference: 90833860 / 91106900 [-0.30%]
Total CPU difference: 19412.109999999855 / 19439.88000000002 [-0.14%]
products component :
Total MEMORY difference: 30039694 / 30012726 [+0.09%]
Total CPU difference: 5240.689999999986 / 5239.289999999958 [+0.03%]

Testing on Windows:
occt component :
Total MEMORY difference: 57231122 / 57241724 [-0.02%]
Total CPU difference: 17941.65940989871 / 18173.586096598698 [-1.28%]
products component :
Total MEMORY difference: 21277667 / 21240754 [+0.17%]
Total CPU difference: 4995.323621099945 / 5008.287304199943 [-0.26%]

There are following differences in images found by testdiff.
http://occt-tests/CR27915-master-OCCT/Debian70-64/diff-Debian70-64.html
http://occt-tests/CR27915-master-OCCT/Windows-64-VC10/diff-Windows-64-VC10-image.html
IMAGE bugs vis bug26056: bug26056.png differs

mkv

2016-10-10 19:05

tester   ~0058531

Dear abv,
Branch CR27915 has been rejected due to:
- differences in images

abv

2016-10-11 08:47

manager   ~0058539

This difference is intentional, please proceed

mkv

2016-10-11 13:12

tester   ~0058569

Dear BugMaster,
Branch CR27915 is TESTED.

git

2016-10-28 21:42

administrator   ~0059461

Branch CR27915 has been deleted by kgv.

SHA-1: 45f0ab8fc775e42dcfe586dece5806ff82ebf633

Related Changesets

occt: master 3c162495

2016-10-13 10:40:12

ski


Committer: apn Details Diff		 0027915: Foundation Classes - remove the class NCollection_QuickSort

Class NCollection_QuickSort was removed.
Direction of dimension lines was corrected.
Updated porting notes.
minor corrections in AIS		 Affected Issues
0027915
mod - dox/dev_guides/upgrade/upgrade.md Diff File
mod - src/AIS/AIS_LengthDimension.cxx Diff File
mod - src/BRepExtrema/BRepExtrema_DistShapeShape.cxx Diff File
mod - src/NCollection/FILES Diff File
rm - src/NCollection/NCollection_QuickSort.hxx Diff File
mod - tests/bugs/moddata_3/bug24896 Diff File
mod - tests/bugs/vis/bug26056 Diff File

Issue History

Date Modified Username Field Change
2016-09-28 18:32 msv New Issue
2016-09-28 18:32 msv Assigned To => abv
2016-09-28 18:35 abv Assigned To abv => ski
2016-09-28 18:35 abv Status new => assigned
2016-09-29 12:32 kgv Severity tweak => integration request
2016-09-29 12:32 kgv Summary Remove the class NCollection_QuickSort => Foundation Classes - remove the class NCollection_QuickSort
2016-09-29 19:08 git Note Added: 0058327
2016-09-29 19:10 ski Note Added: 0058328
2016-09-29 19:10 ski Assigned To ski => msv
2016-09-29 19:10 ski Status assigned => resolved
2016-09-29 19:10 ski Steps to Reproduce Updated
2016-09-30 11:57 msv Note Added: 0058331
2016-09-30 11:57 msv Assigned To msv => ski
2016-09-30 11:57 msv Status resolved => assigned
2016-09-30 12:06 git Note Added: 0058332
2016-09-30 12:07 ski Note Added: 0058333
2016-09-30 12:07 ski Assigned To ski => msv
2016-09-30 12:07 ski Status assigned => resolved
2016-09-30 12:12 kgv Note Added: 0058334
2016-09-30 12:16 msv Note Added: 0058338
2016-09-30 12:16 msv Assigned To msv => bugmaster
2016-09-30 12:16 msv Status resolved => reviewed
2016-09-30 12:18 msv Note Added: 0058339
2016-09-30 12:18 msv Assigned To bugmaster => ski
2016-09-30 12:18 msv Status reviewed => assigned
2016-09-30 12:54 git Note Added: 0058342
2016-09-30 12:55 ski Note Added: 0058343
2016-09-30 12:55 ski Assigned To ski => msv
2016-09-30 12:55 ski Status assigned => resolved
2016-09-30 14:49 msv Note Added: 0058345
2016-09-30 14:49 msv Assigned To msv => bugmaster
2016-09-30 14:49 msv Status resolved => reviewed
2016-10-03 12:35 mkv Assigned To bugmaster => mkv
2016-10-03 15:23 git Note Added: 0058365
2016-10-04 16:58 mkv Note Added: 0058405
2016-10-04 16:59 mkv Note Added: 0058406
2016-10-04 16:59 mkv Note Added: 0058407
2016-10-04 16:59 mkv Assigned To mkv => ski
2016-10-04 16:59 mkv Status reviewed => assigned
2016-10-04 17:00 mkv Test case number => Not needed
2016-10-05 13:43 ski Note Added: 0058422
2016-10-05 13:43 ski Assigned To ski => msv
2016-10-05 13:43 ski Status assigned => feedback
2016-10-05 14:22 abv Note Added: 0058430
2016-10-05 15:09 msv Note Added: 0058432
2016-10-05 15:09 msv Assigned To msv => ski
2016-10-05 15:09 msv Status feedback => assigned
2016-10-05 16:16 git Note Added: 0058438
2016-10-06 18:08 git Note Added: 0058468
2016-10-06 18:44 ski Note Added: 0058470
2016-10-06 18:44 ski Assigned To ski => abv
2016-10-06 18:44 ski Status assigned => resolved
2016-10-07 12:16 git Note Added: 0058475
2016-10-07 13:08 ski Note Added: 0058477
2016-10-07 14:38 git Note Added: 0058479
2016-10-07 14:39 abv Note Added: 0058480
2016-10-07 14:39 abv Assigned To abv => bugmaster
2016-10-07 14:39 abv Status resolved => reviewed
2016-10-07 16:00 mkv Assigned To bugmaster => mkv
2016-10-07 18:11 git Note Added: 0058492
2016-10-10 19:02 mkv Note Added: 0058529
2016-10-10 19:04 mkv Note Added: 0058530
2016-10-10 19:05 mkv Note Added: 0058531
2016-10-10 19:05 mkv Assigned To mkv => abv
2016-10-10 19:05 mkv Status reviewed => feedback
2016-10-11 08:46 abv Assigned To abv => mkv
2016-10-11 08:47 abv Note Added: 0058539
2016-10-11 13:12 mkv Note Added: 0058569
2016-10-11 13:12 mkv Assigned To mkv => bugmaster
2016-10-11 13:12 mkv Status feedback => tested
2016-10-20 15:13 apn Changeset attached => occt master 3c162495
2016-10-20 15:13 apn Assigned To bugmaster => apn
2016-10-20 15:13 apn Status tested => verified
2016-10-20 15:13 apn Resolution open => fixed
2016-10-28 21:42 git Note Added: 0059461
2016-12-09 16:30 aiv Status verified => closed
2016-12-09 16:38 aiv Fixed in Version => 7.1.0
2020-04-21 22:28 kgv Relationship added parent of 0031512