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&nbsp;<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&nbsp;<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