PreviousUpNext

15.4.887  src/lib/src/int-list-set.pkg

## int-list-set.pkg

# Compiled by:
#     src/lib/std/standard.lib

# An implementation of finite sets of integers, which uses a sorted list
# representation.


###    "Solitary trees, if they grow at all, grow strong."
###
###                             -- Winston Churchill


package int_list_set : Set              # Set   is from   src/lib/src/set.api
where
    key::Key == int::Int
=
package {
    package key {
        Key = Int;
        compare = int::compare;
    };

    # Sets are represented as
    # ordered lists of integers:
    #
    Item = key::Key;
    Set = List( Item );

    empty = [];

    fun all_invariants_hold set = TRUE;         # Placeholder.

    fun singleton x = [x];

    fun add (l, item)
        =
        {  fun f [] => [item];

               f (element ! r)
                   =>
                   case (key::compare (item, element))
                     
                        LESS    =>  item ! element ! r;
                        EQUAL   =>  item ! r;
                        GREATER =>  element ! (f r);
                   esac;
           end;
          
            f l;
        };

    fun add' (s, x)
        =
        add (x, s);

    fun union (s1, s2)
        =
        merge (s1, s2)
        where
            fun merge ([], l2) => l2;
                merge (l1, []) => l1;
                merge (x ! r1, y ! r2)
                    =>
                    case (key::compare (x, y))
                      
                         LESS    =>  x ! merge (r1, y ! r2);
                         EQUAL   =>  x ! merge (r1,     r2);
                         GREATER =>  y ! merge (x ! r1, r2);
                    esac;
            end;
        end;  

    fun intersection (s1, s2)
        =
        merge (s1, s2)
        where
            fun merge ([], l2) =>  [];
                merge (l1, []) =>  [];

                merge (x ! r1, y ! r2)
                    =>
                    case (key::compare (x, y))
                      
                         LESS    =>  merge (r1, y ! r2);
                         EQUAL   =>  x ! merge (r1, r2);
                         GREATER =>  merge (x ! r1, r2);
                    esac;
            end;
        end;

    fun difference (s1, s2)
        =
        merge (s1, s2)
        where

            fun merge ([], l2) =>  [];
                merge (l1, []) =>  l1;

                merge (x ! r1, y ! r2)
                    =>
                    case (key::compare (x, y))
                      
                         LESS    =>  x ! merge (r1, y ! r2);
                         EQUAL   =>  merge (r1, r2);
                         GREATER =>  merge (x ! r1, r2);
                    esac;
            end;
        end;

    fun add_list (l, items)
        =
        union (l, items')
        where
            items' =  list::fold_forward   (fn (x, set) =  add (set, x))   []   items;
        end;


    # Remove an item, returning new map and value removed.
    # Raise lib_base::NOT_FOUND if not found.
    #
    fun delete (l, element)
        =
        f ([], l)
        where
            fun f (_, [])
                    =>
                    raise exception lib_base::NOT_FOUND;

                f (prefix, element' ! r)
                    =>
                    case (key::compare (element, element'))
                      
                         LESS    =>  raise exception lib_base::NOT_FOUND;
                         EQUAL   =>  list::reverse_and_prepend (prefix, r);
                         GREATER =>  f (element' ! prefix, r);
                     esac;
            end;
          
        end;


    fun member (l, item)
        =
        f l
        where
            fun f [] =>   FALSE;

                f (element ! r)
                    =>
                    case (key::compare (item, element))
                       
                         LESS    =>  FALSE;
                         EQUAL   =>  TRUE;
                         GREATER =>  f r;
                     esac;
            end;
        end;

    fun is_empty [] =>  TRUE;
        is_empty _  =>  FALSE;
    end;

    fun equal (s1, s2)
        =
        f (s1, s2)
        where
            fun f ([], [])                   =>   TRUE;
                f ((x:  Int) ! r1, y ! r2)   =>   x == y  and  f (r1, r2);
                f _                          =>   FALSE;
            end;
        end;

    fun compare ([], []) =>  EQUAL;
        compare ([], _)  =>  LESS;
        compare (_, [])  =>  GREATER;

        compare (x1 ! r1, x2 ! r2)
            =>
            case (key::compare (x1, x2))
              
                 EQUAL =>  compare (r1, r2);
                 order =>  order;
            esac;
    end;


    # Return TRUE if and only if
    # the first set is a subset
    # of the second 
    #
    fun is_subset (s1, s2)
        =
        f (s1, s2)
        where
            fun f ([], _) =>  TRUE;
                f (_, []) =>  FALSE;

                f (x ! r1, y ! r2)
                    =>
                    case (key::compare (x, y))
                      
                         LESS    => FALSE;
                         EQUAL   => f (r1, r2);
                         GREATER => f (x ! r1, r2);
                    esac;
            end;
        end;


    #  Return the number of items in the set 
    #
    fun vals_count l
        =
        list::length l;


    # Return a list of the items in the set 
    #
    fun vals_list l
        =
        l;

    apply = list::apply;

    fun map f s1
        =
        list::fold_forward   (fn (x, s) = add (s, f x))   []   s1;

    fold_backward =  list::fold_backward;
    fold_forward  =  list::fold_forward;
    filter     =  list::filter;
    partition  =  list::partition;
    exists     =  list::exists;
    find       =  list::find;

};      #  int_list_map 



Comments and suggestions to: bugs@mythryl.org

PreviousUpNext