-- Copyright 1993-1998, by the Cecil Project
-- Department of Computer Science and Engineering, University of Washington
-- See the LICENSE file for license information.

(--DOC
  A `bit_set' is an abstract class for bit-vector-based set representations.
  Concrete subclasses of `bit_set' must provide the `element_to_index' and
  `index_to_element' functions mapping between elements and bit
  positions. If the elements store their own set indices as an `id_num'
  field, the interface provided by the `caching_bit_set' subclass can be
  used. If a separate table mapping elements to indices is needed, the
  `hashing_bit_set' subclass can be used.
--)


abstract object bit_set[T <= comparable[T]] isa m_set[T], hashable[bit_set[T]];
  private var field members(@:bit_set[`T]):bit_vector := new_bit_vector(10);
  private var field cached_length(@:bit_set[`T]):int := -1;

  -- the following should be implemented for all kinds of bit sets
  signature element_to_index(bit_set[`T], T):int;
  signature index_to_element(bit_set[`T], int):T;

  -- This constructor is abstract because we don't have factory objects, and
  -- we have to include the first argument just to make sure that we call
  -- the correct constructor (i.e. dispatch on it, but don't use it).  Ugh.
  signature new_bit_set(bit_set[`T], bit_vector, cached_length:int):bit_set[T];

  -- this hash function is not completely correct: it won't necessarily
  -- enable bit_sets and other representations of sets to be intermixed as keys
  -- of a hash table, since the hash function for bit sets is computed
  -- differently than the hash function for other kinds of sets.  Yuck, but
  -- otherwise hashing on a bit set is really slow and probably gets lousy
  -- spread.
  method hash(a@:bit_set[`T], range:int):int {
      a.members.hash(range) }

  method copy(a@bit_set[`T]:`S <= bit_set[`T]):R
			where signature new_bit_set(S, bit_vector, int):`R {
      new_bit_set(a, a.members.copy, a.cached_length) }

  method union(a@bit_set[`T]:`S <= bit_set[`T], b@bit_set[`T]:`S):R
			where signature new_bit_set(S, bit_vector, int):`R {
      new_bit_set(a, a.members _bit_or b.members, -1) }

  method intersection(a@bit_set[`T]:`S <= bit_set[`T], b@bit_set[`T]:`S):R
			where signature new_bit_set(S, bit_vector, int):`R {
      new_bit_set(a, a.members _bit_and b.members, -1) }

  method difference(a@bit_set[`T]:`S <= bit_set[`T], b@bit_set[`T]:`S):R
			where signature new_bit_set(S, bit_vector, int):`R {
      new_bit_set(a, a.members _bit_difference b.members, -1) }

  method is_empty(a@:bit_set[`T]):bool {
      a.cached_length = 0 | { is_all_zeros(a.members) } }

  method =(a@:bit_set[`T], b@:bit_set[T]):bool {
      a == b | { a.members =_or_zero b.members } }

  method remove(a@:bit_set[`T], elem:T, if_absent:&():void):void {
      let idx:int := a.element_to_index(elem);
      let old_val:int := a.members.fetch(idx, { 0 });
      if(old_val = 0, if_absent, {
	  a.members.store(idx, 0, { });
	  if(a.cached_length != -1, {
	      a.cached_length := a.cached_length - 1;
	  });
      });
  }

  method includes(a@:bit_set[`T], elem:T):bool {
      let idx:int := a.element_to_index(elem);
      includes_id(a, idx) }
  -- an interface if the client knows the id of the element being tested
  method includes_id(a@:bit_set[`T], idx:int):bool {
      a.members.fetch(idx, { 0 }) = 1 }

  method includes_all(a@:bit_set[`T], b@:bit_set[T]):bool {
      a.members.includes_all(b.members) }

  method add(a@:bit_set[`T], elem:T):void {
      let idx:int := a.element_to_index(elem);
      add_id(a, idx);
  }
  -- an interface if the client knows the id of the element being added
  method add_id(a@:bit_set[`T], idx:int):void {
      if(a.members.fetch(idx, {
	  -- need to resize
	  let new_size:int := round_up(idx + 128, 32);
	  a.members.resize(new_size);
	  0
      }) = 0, {
	  a.members!idx := 1;
	  if(a.cached_length != -1, {
	      a.cached_length := a.cached_length + 1;
	  });
      });
  }

  method add_all(a@:bit_set[`T], b@:bit_set[T]):void {
      if(b.cached_length != 0, {
	  a.members := a.members _bit_or b.members;
	  a.cached_length := -1;
      });
  }

  method do(a@:bit_set[`T], cl:&(T):void):void {
      if(a.cached_length != 0, {
	  a.members.do_ones(&(idx:int){
	      eval(cl, a.index_to_element(idx));
	  });
      });
  }

  method is_disjoint(m1@:bit_set[`T], m2@:bit_set[T]):bool {
      m1.members.is_disjoint(m2.members) }

  method remove_any(a@:bit_set[`T], if_empty:&():`S):T|S {
      a.members.length.do(&(idx:int){
	  if(a.members!idx = 1, {
	      let result:T := a.index_to_element(idx);
	      a.members!idx := 0;
	      if(a.cached_length != -1,
		 { a.cached_length := a.cached_length - 1; });
	      ^ result
	  });
      });
      eval(if_empty) }

  method remove_all(a@:bit_set[`T]):void {
      a.members.clear_all_bits;
      a.cached_length := 0;
  }

  method length(a@:bit_set[`T]):int {
      if(a.cached_length = -1, {
	  let var len:int := 0;
	  a.members.do_ones(&(:int){
	      len := len.succ;
	  });
	  a.cached_length := len;
      });
      a.cached_length }

  method collection_name(@:bit_set[`T]):string { "bit_set" }


-- these kinds of bit sets and bit_set_id_managers can be used for
-- bit set elements that cache their own bit set id number
-- (the hashing_bit_set_id_manager can be used with caching_bit_set objects,
--  too, to perform canonicalization of multiple = but !== objects)

abstract object caching_bit_set_element[T <= hashable[T]]
				isa hashable[caching_bit_set_element[T]];
  signature id_manager(caching_bit_set_element[`T]
		       ):bit_set_id_manager[caching_bit_set_element[T]];
  var field id_num(t@:caching_bit_set_element[`T]):int :=
      t.id_manager.element_to_index(t);
  method reset_id_num(t@:caching_bit_set_element[`T]):void {
      t.id_num := t.id_manager.element_to_index(t);
  }

abstract object caching_bit_set[T <= caching_bit_set_element[T]] isa bit_set[T];
  -- the following should be implemented for all kinds of bit sets
  signature id_manager(caching_bit_set[`T]):bit_set_id_manager[T];

  method element_to_index(t@:caching_bit_set[`T], elem:T):int {
      elem.id_num }
  method index_to_element(t@:caching_bit_set[`T], idx:int):T {
      t.id_manager.index_to_element(idx) }


-- for things that have two cached id_nums, here's the interface to the
-- second one:
abstract object caching_bit_set_element_2[T <= hashable[T]]
				isa hashable[caching_bit_set_element_2[T]];
  signature id_manager_2(caching_bit_set_element_2[`T]
			 ):bit_set_id_manager[caching_bit_set_element_2[T]];
  var field id_num_2(t@:caching_bit_set_element_2[`T]):int :=
      t.id_manager_2.element_to_index(t);
  method reset_id_num_2(t@:caching_bit_set_element_2[`T]):void {
      t.id_num_2 := t.id_manager_2.element_to_index(t);
  }

abstract object caching_bit_set_2[T <= caching_bit_set_element_2[T]]
				isa bit_set[T];
  signature id_manager(caching_bit_set_2[`T]):bit_set_id_manager[T];

  method element_to_index(t@:caching_bit_set_2[`T], elem:T):int {
      elem.id_num_2 }
  method index_to_element(t@:caching_bit_set_2[`T], idx:int):T {
      t.id_manager.index_to_element(idx) }


template object bit_set_id_manager[T <= hashable[T]];
  private var field index_to_element(@:bit_set_id_manager[`T]):array[T]
	:= new_array[T]();

  method element_to_index(t@:bit_set_id_manager[`T], elem:T):int {
      let new_id:int := t.index_to_element.length;
      t.index_to_element.add_last(elem);
      new_id }
  method index_to_element(t@:bit_set_id_manager[`T], idx:int):T {
      t.index_to_element!idx }

  method reset_id_manager(t@:bit_set_id_manager[`T]):void {
      t.index_to_element := new_array[T]();
  }

  method length(t@:bit_set_id_manager[`T]):int {
      t.index_to_element.length }

  method new_bit_set_id_manager[T <= hashable[T]]()
     		:bit_set_id_manager[T] {
      concrete object isa bit_set_id_manager[T] }


-- these kinds of bit sets and bit_set_id_managers can be used for
-- any hashable bit set elements; the manager maintains the element->index
-- mapping externally

abstract object hashing_bit_set[T <= hashable[T]] isa bit_set[T];
  -- the following should be implemented for all kinds of bit sets
  signature id_manager(hashing_bit_set[`T]
		       ):hashing_bit_set_id_manager[T];

  method element_to_index(t@:hashing_bit_set[`T], elem:T):int {
      t.id_manager.element_to_index(elem) }
  method index_to_element(t@:hashing_bit_set[`T], idx:int):T {
      t.id_manager.index_to_element(idx) }


template object hashing_bit_set_id_manager[T <= hashable[T]]
						isa bit_set_id_manager[T];
  private var field element_to_index(@:hashing_bit_set_id_manager[`T]
				     ):m_table[T,int] :=
	new_hash_table[T,int]();

  method element_to_index(t@:hashing_bit_set_id_manager[`T], elem:T):int {
      t.element_to_index.fetch_or_init(elem, { resend }) }

  method reset_id_manager(t@:hashing_bit_set_id_manager[`T]):void {
      resend;
      t.element_to_index := new_hash_table[T,int](197);
  }

  method new_hashing_bit_set_id_manager[T <= hashable[T]]()
     		:hashing_bit_set_id_manager[T] {
      concrete object isa hashing_bit_set_id_manager[T] }