Branch: refs/heads/master
Revision: f4cd299
Author: e-kayrakli
Log Message:
Merge pull request #16124 from Rapiz1/orderedSet
Add module OrderedSet
An orderedSet is a collection of unique ordered elements. Thus it supports more
operations related to the order of elements than a set. e.g. lowerBound
The underlying implementation uses treap which is a randomized binary tree that
supports insertion, deletion, querying in expected O(lgN).
This PR contains
- OrderedSet as a package module
- Treap as a submodule of OrderedSet
- Tests for orderedSet
Related: https://github.com/chapel-lang/chapel/issues/15921
[contributed by @Rapiz1]
[Reviewed by @krishnadey30, @cassella and @e-kayrakli]
Test:
- [x] standard
- [x] gasnet
Modified Files:
A modules/packages/OrderedSet.chpl
A modules/packages/OrderedSet/Treap.chpl
A test/library/packages/OrderedSet/general/COMPOPTS
A test/library/packages/OrderedSet/general/OsetTest.chpl
A test/library/packages/OrderedSet/general/OsetTest.notest
A test/library/packages/OrderedSet/general/add/COMPOPTS
A test/library/packages/OrderedSet/general/add/EXECOPTS
A test/library/packages/OrderedSet/general/add/osetAdd.chpl
A test/library/packages/OrderedSet/general/add/osetAdd.good
A test/library/packages/OrderedSet/general/assign/COMPOPTS
A test/library/packages/OrderedSet/general/assign/osetAssign.chpl
A test/library/packages/OrderedSet/general/assign/osetAssign.good
A test/library/packages/OrderedSet/general/clear/COMPOPTS
A test/library/packages/OrderedSet/general/clear/EXECOPTS
A test/library/packages/OrderedSet/general/clear/osetClear.chpl
A test/library/packages/OrderedSet/general/clear/osetClear.good
A test/library/packages/OrderedSet/general/contains/COMPOPTS
A test/library/packages/OrderedSet/general/contains/osetContains.chpl
A test/library/packages/OrderedSet/general/contains/osetContains.good
A test/library/packages/OrderedSet/general/difference/COMPOPTS
A test/library/packages/OrderedSet/general/difference/osetDifference.chpl
A test/library/packages/OrderedSet/general/difference/osetDifference.good
A test/library/packages/OrderedSet/general/equality/COMPOPTS
A test/library/packages/OrderedSet/general/equality/osetEquality.chpl
A test/library/packages/OrderedSet/general/equality/osetEquality.good
A test/library/packages/OrderedSet/general/init/COMPOPTS
A test/library/packages/OrderedSet/general/init/osetInit.chpl
A test/library/packages/OrderedSet/general/init/osetInit.good
A test/library/packages/OrderedSet/general/initEquals/COMPOPTS
A test/library/packages/OrderedSet/general/initEquals/setInitEquals.chpl
A test/library/packages/OrderedSet/general/initEquals/setInitEquals.good
A test/library/packages/OrderedSet/general/intersection/COMPOPTS
A test/library/packages/OrderedSet/general/intersection/osetIntersection.chpl
A test/library/packages/OrderedSet/general/intersection/osetIntersection.good
A test/library/packages/OrderedSet/general/isDisjoint/COMPOPTS
A test/library/packages/OrderedSet/general/isDisjoint/osetIsDisjoint.chpl
A test/library/packages/OrderedSet/general/isDisjoint/osetIsDisjoint.good
A test/library/packages/OrderedSet/general/isEmpty/COMPOPTS
A test/library/packages/OrderedSet/general/isEmpty/osetIsEmpty.chpl
A test/library/packages/OrderedSet/general/isEmpty/osetIsEmpty.good
A test/library/packages/OrderedSet/general/isIntersecting/COMPOPTS
A test/library/packages/OrderedSet/general/isIntersecting/osetIsIntersecting.chpl
A test/library/packages/OrderedSet/general/isIntersecting/osetIsIntersecting.good
A test/library/packages/OrderedSet/general/kth/COMPOPTS
A test/library/packages/OrderedSet/general/kth/osetKth.chpl
A test/library/packages/OrderedSet/general/kth/osetKth.good
A test/library/packages/OrderedSet/general/lowerBound/osetLowerbound.chpl
A test/library/packages/OrderedSet/general/lowerBound/osetLowerbound.good
A test/library/packages/OrderedSet/general/memleaks/COMPOPTS
A test/library/packages/OrderedSet/general/memleaks/osetCheckMemLeaks.chpl
A test/library/packages/OrderedSet/general/memleaks/osetCheckMemLeaks.execopts
A test/library/packages/OrderedSet/general/memleaks/osetCheckMemLeaks.good
A test/library/packages/OrderedSet/general/neighbours/osetNeighbours.chpl
A test/library/packages/OrderedSet/general/neighbours/osetNeighbours.good
A test/library/packages/OrderedSet/general/properSubset/COMPOPTS
A test/library/packages/OrderedSet/general/properSubset/osetProperSubset.chpl
A test/library/packages/OrderedSet/general/properSubset/osetProperSubset.good
A test/library/packages/OrderedSet/general/properSuperset/COMPOPTS
A test/library/packages/OrderedSet/general/properSuperset/osetProperSuperset.chpl
A test/library/packages/OrderedSet/general/properSuperset/osetProperSuperset.good
A test/library/packages/OrderedSet/general/remove/COMPOPTS
A test/library/packages/OrderedSet/general/remove/osetRemove.chpl
A test/library/packages/OrderedSet/general/remove/osetRemove.good
A test/library/packages/OrderedSet/general/size/COMPOPTS
A test/library/packages/OrderedSet/general/size/osetSize.chpl
A test/library/packages/OrderedSet/general/size/osetSize.good
A test/library/packages/OrderedSet/general/subset/COMPOPTS
A test/library/packages/OrderedSet/general/subset/osetSubset.chpl
A test/library/packages/OrderedSet/general/subset/osetSubset.good
A test/library/packages/OrderedSet/general/superset/COMPOPTS
A test/library/packages/OrderedSet/general/superset/osetSuperset.chpl
A test/library/packages/OrderedSet/general/superset/osetSuperset.good
A test/library/packages/OrderedSet/general/symmetricDifference/COMPOPTS
A test/library/packages/OrderedSet/general/symmetricDifference/osetSymmetricDifference.chpl
A test/library/packages/OrderedSet/general/symmetricDifference/osetSymmetricDifference.good
A test/library/packages/OrderedSet/general/these/COMPOPTS
A test/library/packages/OrderedSet/general/these/osetThese.chpl
A test/library/packages/OrderedSet/general/these/osetThese.good
A test/library/packages/OrderedSet/general/toArray/COMPOPTS
A test/library/packages/OrderedSet/general/toArray/osetToArray.chpl
A test/library/packages/OrderedSet/general/toArray/osetToArray.good
A test/library/packages/OrderedSet/general/types/COMPOPTS
A test/library/packages/OrderedSet/general/types/OsetTypeTest.chpl
A test/library/packages/OrderedSet/general/types/OsetTypeTest.notest
A test/library/packages/OrderedSet/general/types/testBorrowed.chpl
A test/library/packages/OrderedSet/general/types/testBorrowed.good
A test/library/packages/OrderedSet/general/types/testNilableBorrowed.chpl
A test/library/packages/OrderedSet/general/types/testNilableBorrowed.good
A test/library/packages/OrderedSet/general/types/testNilableShared.chpl
A test/library/packages/OrderedSet/general/types/testNilableShared.good
A test/library/packages/OrderedSet/general/types/testNilableTuple.chpl
A test/library/packages/OrderedSet/general/types/testNilableTuple.good
A test/library/packages/OrderedSet/general/types/testNilableUnmanaged.chpl
A test/library/packages/OrderedSet/general/types/testNilableUnmanaged.good
A test/library/packages/OrderedSet/general/types/testRecord.chpl
A test/library/packages/OrderedSet/general/types/testRecord.good
A test/library/packages/OrderedSet/general/types/testShared.chpl
A test/library/packages/OrderedSet/general/types/testShared.good
A test/library/packages/OrderedSet/general/types/testTuple.chpl
A test/library/packages/OrderedSet/general/types/testTuple.good
A test/library/packages/OrderedSet/general/types/testUnmanaged.chpl
A test/library/packages/OrderedSet/general/types/testUnmanaged.good
A test/library/packages/OrderedSet/general/union/COMPOPTS
A test/library/packages/OrderedSet/general/union/osetUnion.chpl
A test/library/packages/OrderedSet/general/union/osetUnion.good
A test/library/packages/OrderedSet/general/upperBound/osetUpperbound.chpl
A test/library/packages/OrderedSet/general/upperBound/osetUpperbound.good
A test/library/packages/OrderedSet/general/writeThis/COMPOPTS
A test/library/packages/OrderedSet/general/writeThis/osetWriteThis.chpl
A test/library/packages/OrderedSet/general/writeThis/osetWriteThis.good
M modules/Makefile
Compare: https://github.com/chapel-lang/chapel/compare/9aacfa02a07d...f4cd299499d2