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

--DOC An implementation of `m_set' that is space efficient when there
--DOC are only a few elements, but scales well when there are a large
--DOC number of elements.  Elements of small sets are required to be
--DOC `hashable'.

-- This code assumes that 'absent_small_set_element' is never a set element
private concrete object absent_small_set_element;
private method elem_present(t@:absent_small_set_element):bool { false }
private method elem_present(t:any):bool { true }

concrete object empty_big_set[T <= hashable[T]]
	isa i_unordered_collection[T],
  	    functionally_extensible_removable_collection[T];
  method length(@:empty_big_set[`T]):int { 0 }
  method do(@:empty_big_set[`T], c:&(T):void):void {  }
  method includes(@:empty_big_set[`T], x:T):bool { false }
  method add_functional(@:empty_big_set[`T], x:T):m_set[T] {
      let new_set:m_set[T] := new_hash_set[T]();
      new_set.add(x);
      new_set }
  method remove(@:empty_big_set[`T], x:T, if_absent:&():void):void {
      eval(if_absent);
  }
  method remove_any(@:empty_big_set[`T], if_empty:&():`S):T|S { eval(if_empty) }
  method remove_all(@:empty_big_set[`T]):void {}
  method copy_empty(t@:empty_big_set[`T]):empty_big_set[T] { t }
  method copy(t@:empty_big_set[`T]):empty_big_set[T] { t }
  method print_string(t@:empty_big_set[`T]):string { t.collection_name }
  method collection_name(@:empty_big_set[`T]):string { "empty_big_set" }


template object small_set[T <= hashable[T]] isa m_set[T];
private var field elem1(@:small_set[`T]):T := cast[T](absent_small_set_element);
private var field elem2(@:small_set[`T]):T := cast[T](absent_small_set_element);
private var field elem3(@:small_set[`T]):T := cast[T](absent_small_set_element);
private var field big_set(@:small_set[`T])
     :functionally_extensible_removable_collection[T] := empty_big_set[T];

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

method length(t@:small_set[`T]):int {
    (t.elem1.elem_present).as_integer + (t.elem2.elem_present).as_integer +
    (t.elem3.elem_present).as_integer +  t.big_set.length }
method is_empty(t@:small_set[`T]):bool {
    t.elem1.elem_present.not & { t.elem2.elem_present.not } &
    { t.elem3.elem_present.not } & { t.big_set.is_empty } }
method includes(t@:small_set[`T], x:T):bool {
    if(t.elem1.elem_present & { t.elem1 = x }, { ^ true });
    if(t.elem2.elem_present & { t.elem2 = x }, { ^ true });
    if(t.elem3.elem_present & { t.elem3 = x }, { ^ true });
    t.big_set.includes(x) }
method add_nonmember(t@:small_set[`T], x:T):void {
    if_false(t.elem1.elem_present, { t.elem1 := x;  ^ });
    if_false(t.elem2.elem_present, { t.elem2 := x;  ^ });
    if_false(t.elem3.elem_present, { t.elem3 := x;  ^ });
    -- Bummer.  Now we have to actually make a real set
    t.big_set := t.big_set.add_functional(x);
}
method remove(t@:small_set[`T], x:T, if_absent:&():void):void {
    if(t.elem1.elem_present & { t.elem1 = x },
       { t.elem1 := cast[T](absent_small_set_element); ^ });
    if(t.elem2.elem_present & { t.elem2 = x },
       { t.elem2 := cast[T](absent_small_set_element); ^ });
    if(t.elem3.elem_present & { t.elem3 = x },
       { t.elem3 := cast[T](absent_small_set_element); ^ });
    t.big_set.remove(x, if_absent);
}
method remove_any(t@:small_set[`T], if_empty:&():`S):T|S {
    if(t.elem1.elem_present,
       { let x := t.elem1; t.elem1 := cast[T](absent_small_set_element); ^ x });
    if(t.elem2.elem_present,
       { let x := t.elem2; t.elem2 := cast[T](absent_small_set_element); ^ x });
    if(t.elem3.elem_present,
       { let x := t.elem3; t.elem3 := cast[T](absent_small_set_element); ^ x });
    t.big_set.remove_any(if_empty) }
method remove_all(t@:small_set[`T]):void {
    t.elem1 := cast[T](absent_small_set_element);
    t.elem2 := cast[T](absent_small_set_element);
    t.elem3 := cast[T](absent_small_set_element);
    t.big_set.remove_all;
}

method shrink_set(t@:small_set[`T]):void {
    let new_set:small_set[T] := new_small_set[T]();
    t.do(&(elem:T){
	new_set.add(elem);
    });
    t.elem1 := new_set.elem1;
    t.elem2 := new_set.elem2;
    t.elem3 := new_set.elem3;
    t.big_set := new_set.big_set;
}

method do(t@:small_set[`T], c:&(T):void):void {
    if(t.elem1.elem_present, { eval(c, t.elem1); });
    if(t.elem2.elem_present, { eval(c, t.elem2); });
    if(t.elem3.elem_present, { eval(c, t.elem3); });
    t.big_set.do(c)
}

method new_small_set[T <= hashable[T]]():small_set[T] {
    concrete object isa small_set[T] }

method copy_empty(t@:small_set[`T]):small_set[T] { new_small_set[T]() }

-- an optimization
method copy(t@:small_set[`T]):small_set[T] {
    let var c:small_set[T] := t.copy_empty;
    c.elem1 := t.elem1;
    c.elem2 := t.elem2;
    c.elem3 := t.elem3;
    c.big_set := t.big_set.copy;
    c }