#############################################################################
##
#W  set.gi                        GAP library                Martin Schoenert
##
#H  @(#)$Id: set.gi,v 4.4 2002/04/15 10:05:22 sal Exp $
##
#Y  Copyright (C)  1997,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
#Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
#Y  Copyright (C) 2002 The GAP Group
##
Revision.set_gi :=
    "@(#)$Id: set.gi,v 4.4 2002/04/15 10:05:22 sal Exp $";


#############################################################################
##
#M  IsEqualSet( <list1>, <list2> )  . . . . . . . . . . . . . . for two lists
##
InstallMethod( IsEqualSet,
    "for two lists",
    true,
    [ IsList, IsList ], 0,
    function( list1, list2 )
    return Set( list1 ) = Set( list2 );
    end );


#############################################################################
##
#M  IsEqualSet( <list1>, <list2> )  . .  for two internally represented lists
##
InstallMethod( IsEqualSet,
    "for two internally represented lists",
    true,
    [ IsList and IsInternalRep, IsList and IsInternalRep ], 0,
    IS_EQUAL_SET );


#############################################################################
##
#M  IsSubsetSet( <list1>, <list2> ) . . . . . . . . . . . . . . for two lists
##
InstallMethod( IsSubsetSet,
    "for two lists",
    true,
    [ IsList, IsList ], 0,
    function( list1, list2 )
    list1:= Set( list1 );
    return ForAll( Set( list2 ), x -> x in list1 );
    end );


#############################################################################
##
#M  IsSubsetSet( <list1>, <list2> ) . .  for two internally represented lists
##
InstallMethod( IsSubsetSet,
    "for two internally represented lists",
    true,
    [ IsList and IsInternalRep, IsList and IsInternalRep ], 0,
    IS_SUBSET_SET );


#############################################################################
##
#M  AddSet( <set>, <obj> )  . . . . . . . . . .  for mutable list, and object
##
InstallMethod( AddSet,
    "for mutable list, and object",
    true,
    [ IsList and IsMutable, IsObject ], 0,
    function( set, obj )
    local pos, len;
    if not IsSSortedList( set ) then
      Error( "<set> must be a mutable proper set" );
    fi;
    pos:= PositionSorted( set, obj );
    if set[ pos ] <> obj then
      len:= Length( set );
      set{ [ pos+1 .. len+1 ] }:= set{ [ pos .. len ] };
      set[ pos ]:= obj;
    fi;
    end );


#############################################################################
##
#M  AddSet( <set>, <obj> )  . . . . . for mutable int. repr. list, and object
##
InstallMethod( AddSet,
    "for mutable internally represented list, and object",
    true,
    [ IsList and IsInternalRep and IsMutable, IsObject ], 0,
    ADD_SET );


#############################################################################
##
#M  RemoveSet( <set>, <obj> ) . . . . for mutable int. repr. list, and object
##
InstallMethod( RemoveSet,
    "for mutable internally represented list, and object",
    true,
    [ IsList and IsInternalRep and IsMutable, IsObject ], 0,
    REM_SET );


#############################################################################
##
#M  RemoveSet( <set>, <obj> ) . . . . . . . . .  for mutable list, and object
##
InstallMethod( RemoveSet,
    "for mutable list, and object",
    true,
    [ IsList and IsMutable, IsObject ], 0,
    function( set, obj )
    local pos, len;
    if not IsSSortedList( set ) then
      Error( "<set> must be a mutable proper set" );
    fi;
    pos:= PositionSorted( set, obj );
    len:= Length( set );
    if pos <= len and set[ pos ] = obj then
      set{ [ pos .. len-1 ] }:= set{ [ pos+1 .. len ] };
      Unbind( set[ len ] );
    fi;
    end );


#############################################################################
##
#M  UniteSet( <set>, <list> ) . . . . .  for two internally represented lists
##
InstallMethod( UniteSet,
    "for two internally represented lists, the first being mutable",
    true,
    [ IsList and IsInternalRep and IsMutable, IsList and IsInternalRep ], 0,
    UNITE_SET );


#############################################################################
##
#M  UniteSet( <set>, <list> ) . . . . . . .  for two lists, the first mutable
##
InstallMethod( UniteSet,
    "for two lists, the first being mutable",
    true,
    [ IsList and IsMutable, IsList ], 0,
    function( set, list )
    local obj;
    if not IsSSortedList( set ) then
      Error( "<set> must be a mutable proper set" );
    fi;
    for obj in list do
      AddSet( set, obj );
    od;
    end );


#############################################################################
##
#M  IntersectSet( <set>, <list> ) . . .  for two internally represented lists
##
InstallMethod( IntersectSet,
    "for two internally represented lists, the first being mutable",
    true,
    [ IsList and IsInternalRep and IsMutable, IsList and IsInternalRep ], 0,
    INTER_SET );


#############################################################################
##
#M  IntersectSet( <set>, <list> ) . . . . .  for two lists, the first mutable
##
InstallMethod( IntersectSet,
    "for two lists, the first being mutable",
    true,
    [ IsList and IsMutable, IsList ], 0,
    function( set, list )
    local obj,i;
    if not IsSSortedList( set ) then
      Error( "<set> must be a mutable proper set" );
    fi;
    i:= 1;
    while i <= Length( set ) do
      obj:= set[i];
      if not obj in list then
          RemoveSet( set, obj );
      else
          i:= i+1;
      fi;
    od;
    
    end );


#############################################################################
##
#M  SubtractSet( <set>, <list> )  . . .  for two internally represented lists
##
InstallMethod( SubtractSet,
    "for two internally represented lists, the first being mutable",
    true,
    [ IsList and IsInternalRep and IsMutable, IsList and IsInternalRep ], 0,
    SUBTR_SET );


#############################################################################
##
#M  SubtractSet( <set>, <list> )  . . . . .  for two lists, the first mutable
##
InstallMethod( SubtractSet,
    "for two lists, the first being mutable",
    true,
    [ IsList and IsMutable, IsList ], 0,
    function( set, list )
    local obj;
    if not IsSSortedList( set ) then
      Error( "<set> must be a mutable proper set" );
    fi;
    for obj in list do
      RemoveSet( set, obj );
    od;
    end );


#############################################################################
##
#E

