# PureBasic Forum

 It is currently Wed May 27, 2020 1:27 am

 All times are UTC + 1 hour

 Page 1 of 3 [ 34 posts ] Go to page 1, 2, 3  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Module with functions for setsPosted: Sat Mar 19, 2011 10:18 pm
 Addict

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
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.77, 2019-10-27
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:
; -- A module with functions for sets
; <https://www.purebasic.fr/english/viewtopic.php?f=12&t=45787>

; Version 1.77, 2019-10-27
; 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 add more fields to the structures for your needs.
; They will just be ignored by the routines of this module.

; ------------------------------------------------------------------------------
; MIT License
;
; Copyright (c) 2011, 2013, 2015, 2017-2019 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

; -- data conversion to set or partition
Declare.i FromString (source\$, *result.Set, caseSensitive.i=#True, sepElm\$=",", brackets\$="{}")
Declare.i FromList (List source\$(), *result.Set, caseSensitive.i=#True)
Declare.i FromArray  (Array source\$(1), *result.Set, caseSensitive.i=#True, start.i=0, last.i=-1)
Declare.i FromArrayI (Array source.i(1), *result.Set, start.i=0, last.i=-1)
Declare.i PartitionFromString (part\$, *p.Partition, caseSensitive.i=#True, sepElm\$=",", sepBlock\$="} {")
Declare.i FromPartition (*p.Partition, *result.Set)

; -- data conversion from set or partition
Declare.i ToList (*a.Set, List result\$(), sortByContent.i=#PB_Sort_Ascending)
Declare.s ToString (*a.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 (*a.Set, file\$, flag.i=0)
Declare.i Load (*a.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 CrossPartition (*a.Partition, *b.Partition, *result.Partition=#Null)

; -- check membership etc.
Declare.i IsSet (source\$, caseSensitive.i=#True, sepElm\$=",", brackets\$="{}")
Declare.i IsElement (*a.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

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 code from my website.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Last edited by Little John on Sun Oct 27, 2019 5:03 am, edited 25 times in total.

Top

 Post subject: Re: Functions for sets (implemented as maps)Posted: Wed Jan 30, 2013 1:30 am
 Addict

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
New version 1.1

Changes
• For compatibility with PB >= 5.10, function Bool() is used where appropriate
(and Macro Bool() was added for PB versions < 5.10)
• In Set_Create_FromString(), the default separator was changed from "|" to ",".
• Set_Intersection()
Set_Union()
Set_Difference()
Set_SymmetricDifference()
now return the size of the resulting set
(makes usage of the functions sometimes more convenient)

New functions
• Set_Create_FromArrayI()
• Set_ToString()
• Set_Similar()

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Functions for sets (implemented as maps)Posted: Wed Jan 30, 2013 4:04 am
 Addict

Joined: Wed Aug 24, 2005 8:39 am
Posts: 2736
Location: Southwest OH - USA
Don't know how I missed this before. Must have been posted when I was wasted (frequently )

Very nice. Many thanks for sharing.

Top

 Post subject: Re: Functions for sets (implemented as maps)Posted: Wed Jan 30, 2013 10:51 am
 Addict

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany

Thanks! You are welcome.

Regards, Little John

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Functions for sets (implemented as maps)Posted: Wed Jan 30, 2013 3:48 pm
 Addict

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
New version 1.11

Fixed
In the function Set_Similar() there was a division by 0, in case two empty sets were compared.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Functions for sets (implemented as maps)Posted: Wed Jan 30, 2013 5:08 pm
 Addict

Joined: Fri Jan 21, 2011 8:25 am
Posts: 1021
Location: 'stralia!
Very useful and straight forward. Thank you.

_________________

Blog: Why Does It Suck? (http://whydoesitsuck.com/)
"You can disagree with me as much as you want, but during this talk, by definition, anybody who disagrees is stupid and ugly."
- Linus Torvalds

Top

 Post subject: Re: Functions for sets (implemented as maps)Posted: Wed Jan 30, 2013 5:53 pm
 Addict

Joined: Sat Dec 31, 2005 5:24 pm
Posts: 2970
Location: Where ya would never look.....
Good job. Thank you very much

_________________
The advantage of a 64 bit operating system over a 32 bit operating system comes down to only being twice the headache.

Top

 Post subject: Re: Functions for sets (implemented as maps)Posted: Thu Jan 31, 2013 6:43 am
 Addict

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
Thank you, guys.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Functions for sets (implemented as maps)Posted: Sat Oct 05, 2013 8:34 am
 Addict

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
New version 1.20

Changes
• The functions are now inside a module (PB 5.20+ required).
=> In your existing code that uses any of these functions, replace Set_xyz() with Set::xyz().

New functions
• New()
• NumberOf_Subsets()
• FirstSubset()
• NextSubset()

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Functions for sets (implemented as maps)Posted: Wed Oct 16, 2013 4:30 pm
 Addict

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
New version 1.21

Changes
• Function Equal() renamed to IsEqual(), so that the name is consistent with IsSubset() etc.
• Some internal cosmetic changes.

New
• The function NumberOf_Subsets() can now take an additional optional parameter:
• NumberOf_Subsets(n) still returns the number of all subsets of a set with n elements.
• NumberOf_Subsets(n, k) returns the number of subsets of a set with n elements, that have exactly k elements.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Module with functions for setsPosted: Wed Oct 16, 2013 7:29 pm
 Addict

Joined: Fri Nov 09, 2012 11:04 pm
Posts: 1758
Location: Uttoxeter, UK
Hi Little John,

Very nice work. Thank you for sharing.

_________________
DE AA EB

Top

 Post subject: Re: Module with functions for setsPosted: Fri Dec 06, 2013 7:13 pm
 Addict

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
Hi davido,
you are welcome!

There is a new version 1.30.

Changes
• Previously, a plain map was used for implementing a set.
Now, the new Structure Set is used. That makes it easier to create arrays of sets, lists of sets etc. For this, also several internal changes were required.
• Removed Macro New()
• Changed function names:
Create_FromString() --> FromString()
Create_FromList() --> FromList()
Create_FromArrayI() --> FromArrayI()
• Function ToString() now has an option for sorting.
• Slightly improved comments
• Slightly improveed demo code

New function
• ToList() converts a set to a linked list of its elements.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Module with functions for setsPosted: Tue Dec 10, 2013 12:36 pm
 Enthusiast

Joined: Tue Jan 25, 2005 7:01 pm
Posts: 460
Location: Canada
Damn, that's quite a useful module, thanks for sharing.

Top

 Post subject: Re: Module with functions for setsPosted: Tue Dec 10, 2013 2:58 pm
 Addict

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3845
Location: Berlin, Germany
Thank you.

The next version will additionally allow to generate all possible partitions of a given set.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Module with functions for setsPosted: Tue Dec 10, 2013 10:03 pm
 Addict

Joined: Fri Nov 09, 2012 11:04 pm
Posts: 1758
Location: Uttoxeter, UK
Version 1.30 is very nice, thank you, for sharing.

Modules have certainly made groups of similar functions so much more pleasant and easier to use than a pbi file of the past!

Looking forward to the next instalment!

_________________
DE AA EB

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 3 [ 34 posts ] Go to page 1, 2, 3  Next

 All times are UTC + 1 hour

#### Who is online

Users browsing this forum: No registered users and 8 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ PureBasic    Coding Questions    Game Programming    3D Programming    Assembly Programming    The PureBasic Editor    The PureBasic Form Designer    General Discussion    Feature Requests and Wishlists    Tricks 'n' Tips Bug Reports    Bugs - Windows    Bugs - Linux    Bugs - Mac OSX    Bugs - IDE    Bugs - Documentation OS Specific    AmigaOS    Linux    Windows    Mac OSX Miscellaneous    Announcement    Off Topic Showcase    Applications - Feedback and Discussion    PureFORM & JaPBe    TailBite

Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye