15.4.758  src/lib/graph/bit-set.pkg

## bit-set.pkg
#
# Non growable dense set in bitvector format.
# 
# -- Allen Leung

# Compiled by:
#     src/lib/graph/graphs.lib

# This package is used in:
#
#     src/lib/graph/graph-dfs.pkg
#     src/lib/graph/dominator-tree-g.pkg
#     src/lib/graph/graph-breadth-first-search.pkg
#     src/lib/graph/graph-is-cyclic.pkg
#
package bit_set
:       Bit_Set                                         # Bit_Set                       is from   src/lib/graph/bit-set.api
{
    package a =  rw_vector_of_one_byte_unts;            # rw_vector_of_one_byte_unts    is from   src/lib/std/src/rw-vector-of-one-byte-unts.pkg
    package w =  one_byte_unt;                          # one_byte_unt                  is from   src/lib/std/one-byte-unt.pkg

    include package   a;

    infix my  << >> & | ;

    Bitset = Rw_Vector; 

    word =  unt::from_int; 
    int  =  unt::to_int;

    my (&)  =  unt::bitwise_and;
    my (>>) =  unt::(>>);
    my (<<) =  w::(<<);

    fun create n
        =
        make_rw_vector((n+7) / 8,  0ux0);


    fun size a
        =
        length a * 8;


    fun set (a, i)
        =
        {   byte = int ((word i) >> 0u3);
            mask = w::(<<) (0u1, (word i) & 0u7);
            a::set (a, byte, w::bitwise_or (a[byte], mask));
        };


    fun reset (a, i)
        =
        {   byte = int((word i) >> 0u3);
            mask = w::bitwise_not (w::(<<) (0u1, (word i) & 0u7));
            a::set (a, byte, w::bitwise_and (a[byte], mask));
        };


    fun clear a
        =
        map_in_place
            (\\ _ =  0ux0)
            a;


    fun copy a
        =
        a::from_fn  (length a,  \\ i =  a[i]);


    fun to_string a
        = 
        {   fun f i
                =
                if (i < length a)   w::to_string (a[i]) ! f (i+1);
                else                [];
                fi;

            s =   string::cat (f 0);

            "[" + s + "]";
        };


    fun contains (a, i)
        = 
        {   byte =  int((word i) >> 0u3);
            mask =  w::(<<) (0u1, (word i) & 0u7);

            w::bitwise_and (a::get (a, byte), mask) != 0ux0;
        };


    fun mark_and_test (a, i)
        =
        {   byte =  int((word i) >> 0u3);
            mask =  w::(<<) (0u1, (word i) & 0u7);
            word =  a::get (a, byte);

            if   (w::bitwise_and (word, mask) != 0ux0)
                
                 TRUE;
            else 
                 a::set (a, byte, w::bitwise_or (word, mask));
                 FALSE;
            fi;
        };


    fun unmark_and_test (a, i)
        =
        {   byte =  int (word i >> 0u3);
            mask =  w::(<<) (0u1, (word i) & 0u7);
            word =  a::get (a, byte);

            if   (w::bitwise_and (word, mask) != 0ux0)
                
                 a::set (a, byte, w::bitwise_and (word, w::bitwise_not mask));
                 TRUE;
            else 
                 FALSE;
            fi;
        }; 

};