1############################################################################# 2## 3## This file is part of GAP, a system for computational discrete algebra. 4## This file's authors include Martin Schönert. 5## 6## Copyright of GAP belongs to its developers, whose names are too numerous 7## to list here. Please refer to the COPYRIGHT file for details. 8## 9## SPDX-License-Identifier: GPL-2.0-or-later 10## 11## This file contains some functions for proper sets. 12## 13## <#GAPDoc Label="[1]{set}"> 14## The following functions, if not explicitly stated differently, 15## take two arguments, <A>set</A> and <A>obj</A>, 16## where <A>set</A> must be a proper set, 17## otherwise an error is signalled; 18## If the second argument <A>obj</A> is a list that is not a proper set 19## then <Ref Oper="Set"/> is silently applied to it first. 20## <#/GAPDoc> 21## 22 23 24############################################################################# 25## 26#F SSortedListList( <list> ) . . . . . . . . . . . . . . . . . set of <list> 27## 28## <ManSection> 29## <Func Name="SSortedListList" Arg='list'/> 30## 31## <Description> 32## <Ref Func="SSortedListList"/> returns a mutable, strictly sorted list 33## containing the same elements as the <E>internally represented</E> list 34## <A>list</A> (which may have holes). 35## <Ref Func="SSortedListList"/> makes a shallow copy, sorts it, 36## and removes duplicates. 37## <Ref Func="SSortedListList"/> is an internal function. 38## </Description> 39## </ManSection> 40## 41DeclareSynonym( "SSortedListList", LIST_SORTED_LIST ); 42 43 44############################################################################# 45## 46#O IsEqualSet( <list1>, <list2> ) . . . . check if lists are equal as sets 47## 48## <#GAPDoc Label="IsEqualSet"> 49## <ManSection> 50## <Oper Name="IsEqualSet" Arg='list1, list2'/> 51## 52## <Description> 53## <Index Subkey="for set equality">test</Index> 54## tests whether <A>list1</A> and <A>list2</A> are equal 55## <E>when viewed as sets</E>, that is if every element of <A>list1</A> is 56## an element of <A>list2</A> and vice versa. 57## Either argument of <Ref Oper="IsEqualSet"/> may also be a list that is 58## not a proper set, in which case <Ref Oper="Set"/> is applied to it first. 59## <P/> 60## If both lists are proper sets then they are of course equal if and only 61## if they are also equal as lists. 62## Thus <C>IsEqualSet( <A>list1</A>, <A>list2</A> )</C> is equivalent to 63## <C>Set( <A>list1</A> ) = Set( <A>list2</A> )</C> 64## (see <Ref Oper="Set"/>), but the former is more efficient. 65## <P/> 66## <Example><![CDATA[ 67## gap> IsEqualSet( [2,3,5,7,11], [11,7,5,3,2] ); 68## true 69## gap> IsEqualSet( [2,3,5,7,11], [2,3,5,7,11,13] ); 70## false 71## ]]></Example> 72## </Description> 73## </ManSection> 74## <#/GAPDoc> 75## 76DeclareOperation( "IsEqualSet", [ IsList, IsList ] ); 77 78 79############################################################################# 80## 81#O IsSubsetSet( <list1>, <list2> ) . check if <list2> is a subset of <list1> 82## 83## <#GAPDoc Label="IsSubsetSet"> 84## <ManSection> 85## <Oper Name="IsSubsetSet" Arg='list1, list2'/> 86## 87## <Description> 88## tests whether every element of <A>list2</A> is contained in <A>list1</A>. 89## Either argument of <Ref Oper="IsSubsetSet"/> may also be a list 90## that is not a proper set, 91## in which case <Ref Oper="Set"/> is applied to it first. 92## </Description> 93## </ManSection> 94## <#/GAPDoc> 95## 96DeclareOperation( "IsSubsetSet", [ IsList, IsList ] ); 97 98 99############################################################################# 100## 101#O AddSet( <set>, <obj> ) . . . . . . . . . . . . . . . add <obj> to <set> 102## 103## <#GAPDoc Label="AddSet"> 104## <ManSection> 105## <Oper Name="AddSet" Arg='set, obj'/> 106## 107## <Description> 108## <Index Subkey="an element to a set">add</Index> 109## adds the element <A>obj</A> to the proper set <A>set</A>. 110## If <A>obj</A> is already contained in <A>set</A> then <A>set</A> is not 111## changed. 112## Otherwise <A>obj</A> is inserted at the correct position such that 113## <A>set</A> is again a proper set afterwards. 114## <P/> 115## Note that <A>obj</A> must be in the same family as each element of 116## <A>set</A>. 117## <Example><![CDATA[ 118## gap> s := [2,3,7,11];; 119## gap> AddSet( s, 5 ); s; 120## [ 2, 3, 5, 7, 11 ] 121## gap> AddSet( s, 13 ); s; 122## [ 2, 3, 5, 7, 11, 13 ] 123## gap> AddSet( s, 3 ); s; 124## [ 2, 3, 5, 7, 11, 13 ] 125## ]]></Example> 126## </Description> 127## </ManSection> 128## <#/GAPDoc> 129## 130DeclareOperation( "AddSet", [ IsList and IsMutable, IsObject ] ); 131 132 133############################################################################# 134## 135#O RemoveSet( <set>, <obj> ) . . . . . . . . . . . . remove <obj> from <set> 136## 137## <#GAPDoc Label="RemoveSet"> 138## <ManSection> 139## <Oper Name="RemoveSet" Arg='set, obj'/> 140## 141## <Description> 142## <Index Subkey="an element from a set">remove</Index> 143## removes the element <A>obj</A> from the proper set <A>set</A>. 144## If <A>obj</A> is not contained in <A>set</A> then <A>set</A> is not 145## changed. 146## If <A>obj</A> is an element of <A>set</A> it is removed and all the 147## following elements in the list are moved one position forward. 148## <P/> 149## <Example><![CDATA[ 150## gap> s := [ 2, 3, 4, 5, 6, 7 ];; 151## gap> RemoveSet( s, 6 ); s; 152## [ 2, 3, 4, 5, 7 ] 153## gap> RemoveSet( s, 10 ); s; 154## [ 2, 3, 4, 5, 7 ] 155## ]]></Example> 156## </Description> 157## </ManSection> 158## <#/GAPDoc> 159## 160DeclareOperation( "RemoveSet", [ IsList and IsMutable, IsObject ] ); 161 162 163############################################################################# 164## 165#O UniteSet( <set>, <list> ) . . . . . . . . . . . . unite <set> with <list> 166## 167## <#GAPDoc Label="UniteSet"> 168## <ManSection> 169## <Oper Name="UniteSet" Arg='set, list'/> 170## 171## <Description> 172## <Index Subkey="of sets">union</Index> 173## unites the proper set <A>set</A> with <A>list</A>. 174## This is equivalent to adding all elements of <A>list</A> to <A>set</A> 175## (see <Ref Oper="AddSet"/>). 176## <P/> 177## <Example><![CDATA[ 178## gap> set := [ 2, 3, 5, 7, 11 ];; 179## gap> UniteSet( set, [ 4, 8, 9 ] ); set; 180## [ 2, 3, 4, 5, 7, 8, 9, 11 ] 181## gap> UniteSet( set, [ 16, 9, 25, 13, 16 ] ); set; 182## [ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 25 ] 183## ]]></Example> 184## </Description> 185## </ManSection> 186## <#/GAPDoc> 187## 188DeclareOperation( "UniteSet", [ IsList and IsMutable, IsList ] ); 189 190 191############################################################################# 192## 193#O IntersectSet( <set>, <list> ) . . . . . . . . intersect <set> with <list> 194## 195## <#GAPDoc Label="IntersectSet"> 196## <ManSection> 197## <Oper Name="IntersectSet" Arg='set, list'/> 198## 199## <Description> 200## <Index Subkey="of sets">intersection</Index> 201## intersects the proper set <A>set</A> with <A>list</A>. 202## This is equivalent to removing from <A>set</A> all elements of <A>set</A> 203## that are not contained in <A>list</A>. 204## <P/> 205## <Example><![CDATA[ 206## gap> set := [ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16 ];; 207## gap> IntersectSet( set, [ 3, 5, 7, 9, 11, 13, 15, 17 ] ); set; 208## [ 3, 5, 7, 9, 11, 13 ] 209## gap> IntersectSet( set, [ 9, 4, 6, 8 ] ); set; 210## [ 9 ] 211## ]]></Example> 212## </Description> 213## </ManSection> 214## <#/GAPDoc> 215## 216DeclareOperation( "IntersectSet", [ IsList and IsMutable, IsList ] ); 217 218 219############################################################################# 220## 221#O SubtractSet( <set>, <list> ) . . . . . remove <list> elements from <set> 222## 223## <#GAPDoc Label="SubtractSet"> 224## <ManSection> 225## <Oper Name="SubtractSet" Arg='set, list'/> 226## 227## <Description> 228## <Index Subkey="a set from another">subtract</Index> 229## subtracts <A>list</A> from the proper set <A>set</A>. 230## This is equivalent to removing from <A>set</A> all elements of 231## <A>list</A>. 232## <P/> 233## <Example><![CDATA[ 234## gap> set := [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ];; 235## gap> SubtractSet( set, [ 6, 10 ] ); set; 236## [ 2, 3, 4, 5, 7, 8, 9, 11 ] 237## gap> SubtractSet( set, [ 9, 4, 6, 8 ] ); set; 238## [ 2, 3, 5, 7, 11 ] 239## ]]></Example> 240## </Description> 241## </ManSection> 242## <#/GAPDoc> 243## 244DeclareOperation( "SubtractSet", [ IsList and IsMutable, IsList ] ); 245