Module with functions for sets
Posted: Sat Mar 19, 2011 10:18 pm
Hi all,
a set is a basic datatype. It is defined as a collection with no duplicate elements, in which order has no significance.
Since the same is true for map keys, I have implemented sets using PureBasic's maps.
For detailed information about the functions, see comments in the code.
Current version: 1.81, 2021-03-28
Purebasic 5.20 LTS or newer required because the code is inside of a module.
Cross-platform, x86 and x64, Unicode compliant.
MIT License.
Since the code now has more than 60 000 characters, it can't be posted here completely anymore.
You can download the ZIP archive with the complete module code and some demo code from my website.
a set is a basic datatype. It is defined as a collection with no duplicate elements, in which order has no significance.
Since the same is true for map keys, I have implemented sets using PureBasic's maps.
For detailed information about the functions, see comments in the code.
Current version: 1.81, 2021-03-28
Purebasic 5.20 LTS or newer required because the code is inside of a module.
Cross-platform, x86 and x64, Unicode compliant.
MIT License.
Code: Select all
; -- A module with functions for sets
; <https://www.purebasic.fr/english/viewtopic.php?f=12&t=45787>
; Version 1.81, 2021-03-28
; Purebasic 5.20 LTS or newer is required because of the module.
; Cross-platform, x86 and x64, Unicode compliant.
; The sets are implemented using PureBasic's maps. Like a map, a set is a
; collection with no duplicate elements, in which order has no significance
; (see e.g. <https://en.wikipedia.org/wiki/Set_(mathematics)>).
; The elements of the sets are strings, represented by the *keys* of the
; maps. The values of the map elements are ignored.
; A partition of a set 's' is a collection of non-empty disjoint subsets
; of 's' (blocks) whose union is 's'
; (see e.g. <https://en.wikipedia.org/wiki/Partition_of_a_set>).
; The data types used here are the structures 'Set' and 'Partition'.
; You can use the fields 'Label$' and 'Value' in both structures for your
; own purposes. Depending on your program, 'Value' could mean e.g. cost
; or weight or could be an ordinal number used for sorting the sets or
; partitions.
; If you want, you can Extend the structures according to your needs
; (see "set_demo_coalitions.pb"). The additional fields will be ignored
; by the routines of this module.
; ------------------------------------------------------------------------------
; MIT License
;
; Copyright (c) 2011, 2013, 2015, 2017-2019, 2021 Jürgen Lüthje <http://luethje.eu/>
; Copyright (c) 2015 for assembler code in procedure _Choose() Wilbert
;
; Permission is hereby granted, free of charge, to any person obtaining a copy
; of this software and associated documentation files (the "Software"), to deal
; in the Software without restriction, including without limitation the rights
; to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
; copies of the Software, and to permit persons to whom the Software is
; furnished to do so, subject to the following conditions:
;
; The above copyright notice and this permission notice shall be included in all
; copies or substantial portions of the Software.
;
; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
; IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
; FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
; AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
; LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
; OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
; SOFTWARE.
; ------------------------------------------------------------------------------
DeclareModule Set
EnableExplicit
Structure Set
Map Element.i() ; * read only *
NumElements.i ; * read only *
Label$
Value.i
EndStructure
Structure Partition
List Block.Set() ; * read only *
NumBlocks.i ; * read only *
Label$
Value.i
EndStructure
#DontSort = -1
; for procedure NumberOf_PartitionsT()
#All = 1
#SameSize = 2
Macro Size (_set_)
; return the number of elements in _set_
MapSize(_set_\Element())
EndMacro
Macro Clear (_set_)
ClearMap(_set_\Element())
_set_\NumElements = 0
_set_\Label$ = ""
_set_\Value = 0
EndMacro
Macro Copy (_source_, _dest_)
; copy set _source_ to _dest_
CopyStructure(_source_, _dest_, Set::Set)
EndMacro
Macro AddElement (_set_, _x_, _caseSensitive_=#True)
; add element _x_ to _set_, if it is not there already
If _caseSensitive_ = #True
AddMapElement(_set_\Element(), _x_)
Else
AddMapElement(_set_\Element(), LCase(_x_))
EndIf
_set_\NumElements = Set::Size(_set_)
EndMacro
Macro RemoveElement (_set_, _x_, _caseSensitive_=#True)
; remove element _x_ from _set_, if it is there
; (If _x_ is not in _set_, no error will be raised.)
If _caseSensitive_ = #True
DeleteMapElement(_set_\Element(), _x_)
Else
DeleteMapElement(_set_\Element(), LCase(_x_))
EndIf
_set_\NumElements = Set::Size(_set_)
EndMacro
Macro PartitionSize (_p_)
; return the number of blocks in _p_
ListSize(_p_\Block())
EndMacro
Macro ClearPartition (_p_)
ClearList(_p_\Block())
_p_\NumBlocks = 0
_p_\Label$ = ""
_p_\Value = 0
EndMacro
; -- creating sets and partitions
Declare.i Create (*s.Set, lo.i, hi.i, stepp.i=1)
Declare.i FromString (*s.Set, source$, caseSensitive.i=#True, sepElm$=",", brackets$="{}")
Declare.i FromList (*s.Set, List source$(), caseSensitive.i=#True)
Declare.i FromArray (*s.Set, Array source$(1), caseSensitive.i=#True, start.i=0, last.i=-1)
Declare.i FromArrayI (*s.Set, Array source.i(1), start.i=0, last.i=-1)
Declare.i PartitionFromString (*p.Partition, part$, caseSensitive.i=#True, sepElm$=",", sepBlock$="} {")
Declare.i FromPartition (*s.Set, *p.Partition)
; -- data conversion from sets and partitions
Declare.i ToList (*s.Set, List result$(), sortByContent.i=#PB_Sort_Ascending)
Declare.s ToString (*s.Set, sortByContent.i=#PB_Sort_Ascending, sepElm$=",", brackets$="{}")
Declare.i PartitionToList (*p.Partition, List result$(), sortByContent.i=#PB_Sort_Ascending, sortBlocksBySize.i=#PB_Sort_Descending, sepElm$=",")
Declare.s PartitionToString (*p.Partition, sortByContent.i=#PB_Sort_Ascending, sortBlocksBySize.i=#PB_Sort_Descending, sepElm$=",", sepBlock$="} {")
; -- save / load
Declare.i Save (*s.Set, file$, flag.i=0)
Declare.i Load (*s.Set, file$)
; -- basic operations
Declare.i Union (*a.Set, *b.Set, *result.Set=#Null)
Declare.i Intersection (*a.Set, *b.Set, *result.Set=#Null)
Declare.i Difference (*a.Set, *b.Set, *result.Set=#Null)
Declare.i SymmetricDifference (*a.Set, *b.Set, *result.Set=#Null)
Declare.i Product (*a.Set, *b.Set, *result.Set, brackets.i=#True)
Declare.i CrossPartition (*a.Partition, *b.Partition, *result.Partition=#Null)
; -- check membership etc.
Declare.i IsSet (source$, caseSensitive.i=#True, sepElm$=",", brackets$="{}")
Declare.i IsElement (*s.Set, x$, caseSensitive.i=#True)
Declare.i IsSubset (*super.Set, *sub.Set)
Declare.i IsProperSubset (*super.Set, *sub.Set)
Declare.i IsEqual (*a.Set, *b.Set)
Declare.i IsDisjoint (*a.Set, *b.Set)
Declare.d Similar (*a.Set, *b.Set)
Declare.i CheckPartition (*p.Partition, *s.Set=#Null)
Declare.i IsEqualPartition (*a.Partition, *b.Partition, ordered.i=#False)
; -- calculate basic numbers
Declare.q NumberOf_Subsets (n.l)
Declare.q NumberOf_SubsetsK (n.l, k.l)
Declare.q NumberOf_Partitions (n.l, ordered.i=#False)
Declare.q NumberOf_PartitionsK (n.l, k.l, ordered.i=#False)
Declare.q NumberOf_PartitionsT (type$, ordered.i=#False)
; -- generate subsets of a given set
Declare.i FirstSubset (*s.Set, *sub.Set)
Declare.i NextSubset (*s.Set, *sub.Set)
Declare.i FirstSubsetK (*s.Set, *sub.Set, k.l)
Declare.i NextSubsetK (*s.Set, *sub.Set)
; -- generate unordered partitions of a given set
Declare.i FirstPartition (*s.Set, *p.Partition)
Declare.i NextPartition (*s.Set, *p.Partition)
Declare.i FirstPartitionK (*s.Set, *p.Partition, k.l)
Declare.i NextPartitionK (*s.Set, *p.Partition)
Declare.i FirstPartitionT (*s.Set, *p.Partition, type$)
Declare.i NextPartitionT (*s.Set, *p.Partition)
EndDeclareModule
You can download the ZIP archive with the complete module code and some demo code from my website.