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


-- an open-hash-table-based keyed-set implementation

module HashKeyedSet extends OpenHashTableImpl {

template object hash_keyed_set[Key <= hashable[Key],
			       Value <= keyed_hashable[Key]]
		    isa m_keyed_set[Key,Value], open_table[Value];

method collection_name(@:hash_keyed_set[`Key,`Value]):string {
    "hash_keyed_set" }

method do(t@:hash_keyed_set[`Key,`Value], c:&(Value):void):void {
    t.key_vector.do(&(x:Value){
	if(x.is_valid_bucket_element, { eval(c, x); });
    });
}

method do_allowing_updates(t@:hash_keyed_set[`Key,`Value],
			   c:&(Value):void):void {
    -- disable resizing during iteration
    allowing_updates.begin_allowing_updates(t);
    unwind_protect({
	do(t, c);
    }, {
	allowing_updates.done_allowing_updates(t);
	if(t.should_grow, {
	    t.resize(t.grown_size);
	}, {
	    if(t.should_shrink, {
		t.resize(t.shrunk_size);
	    });
	});
    });
}

method includes(t@:hash_keyed_set[`Key,`Value <= comparable[Value]],
		val:Value):bool {
    t.key_vector.buckets_in_probing_order_do(hash_key(val, t.key_vector.length),
					     &(i:int,v:Value){
	if(v !== empty_hash_bucket, {
	    if(v !== removed_hash_bucket & { val = v }, {
		^ true
	    });
	}, {
	    ^ false
	});
    });
    false }

method fetch(t@:hash_keyed_set[`Key,`Value], key:Key,
	     if_absent:&():Value):Value {
    t.key_vector.buckets_in_probing_order_do(hash(key, t.key_vector.length),
					     &(i:int,v:Value){
        if(v !== empty_hash_bucket, {
	    if(v !== removed_hash_bucket & { key = v.key }, {
		^ v
	    });
        }, {
	    ^ eval(if_absent)
	});
    });
    eval(if_absent) }

method match(t@:hash_keyed_set[`Key,`Value], val:Value,
	     if_absent:&():Value):Value {
    t.fetch(val.key, if_absent) }

method add(t@:hash_keyed_set[`Key,`Value], val:Value):void {
    let var store_pos:int := -1;
    let key:Key := val.key;
    t.key_vector.buckets_in_probing_order_do(hash(key, t.key_vector.length),
					     &(i:int,v:Value){
	if(v !== empty_hash_bucket, {
	    if(v !== removed_hash_bucket, {
		if(key = v.key, { t.key_vector.store(i, val); ^ });
	    }, {
	        if(store_pos < 0, { store_pos := i; });
	    });
	}, {
	    t.length := t.length.succ;
	    t.key_vector.store(if(store_pos < 0, { i }, { store_pos }), val);
	    if(t.should_grow, { t.resize(t.grown_size); });
	    ^
	});
    });
    assert(store_pos >= 0, "should have found a free bucket somewhere");
    t.length := t.length.succ;
    t.key_vector.store(store_pos, val);
    if(t.should_grow, { t.resize(t.grown_size); });
}

method remove_key(t@:hash_keyed_set[`Key,`Value], key:Key,
		  if_absent:&():`Else):Value|Else {
    t.key_vector.buckets_in_probing_order_do(hash(key, t.key_vector.length),
					     &(i:int,v:Value){
	if(v !== empty_hash_bucket, {
	    if(v !== removed_hash_bucket & { key = v.key }, {
		t.remove_bucket(i);
		t.length := t.length.pred;
		if(t.should_shrink, { t.resize(t.shrunk_size); });
		^ v
	    });
	}, {
	    ^ eval(if_absent)
	});
    });
    eval(if_absent) }

method remove_match(t@:hash_keyed_set[`Key,`Value], val:Value,
		       if_absent:&():`Else):Value|Else {
    t.remove_key(val.key, if_absent) }

method remove(t@:hash_keyed_set[`Key,`Value <= comparable[Value]], val:Value,
	      if_absent:&():void):void {
    t.key_vector.buckets_in_probing_order_do(hash_key(val, t.key_vector.length),
					     &(i:int,v:Value){
	if(v !== empty_hash_bucket, {
	    if(v !== removed_hash_bucket & { val = v }, {
		t.remove_bucket(i);
		t.length := t.length.pred;
		if(t.should_shrink, { t.resize(t.shrunk_size); });
		^ v
	    });
	}, {
	    ^ eval(if_absent)
	});
    });
    eval(if_absent) }

method remove_any(t@:hash_keyed_set[`Key,`Value],
		  if_empty:&():`Else):Value|Else {
    t.key_vector.do_associations(&(i:int, v:Value){
	if(v.is_valid_bucket_element, {
	    let result:Value := v;
	    t.remove_bucket(i);
	    t.length := t.length.pred;
	    if(t.should_shrink, { t.resize(t.shrunk_size); });
	    ^ result
	});
    });
    eval(if_empty) }

method remove_all(t@:hash_keyed_set[`Key,`Value]):void {
    resend(t@open_table[Value]) }

method remove_if(t@:hash_keyed_set[`Key,`Value], pred:&(Value):bool):int {
    let var count:int := 0;
    t.key_vector.do_associations(&(i:int, v:Value){
	if(v.is_valid_bucket_element & { eval(pred, v) }, {
	    t.remove_bucket(i);
	    t.length := t.length.pred;
	    count := count + 1;
	});
    });
    if(t.should_shrink, { t.resize(t.shrunk_size); });
    count
}

method remove_keys_if(t@:hash_keyed_set[`Key,`Value],
		       pred:&(Key):bool):int {
    let var count:int := 0;
    t.key_vector.do_associations(&(i:int, v:Value){
	if(v.is_valid_bucket_element & { eval(pred, v.key) }, {
	    t.remove_bucket(i);
	    t.length := t.length.pred;
	    count := count + 1;
	});
    });
    if(t.should_shrink, { t.resize(t.shrunk_size); });
    count
}

private method resize(t@:hash_keyed_set[`Key,`Value], new_size:int):void {
    let old_len:int := t.length;
    let old_key_vector:m_vector[Value] := t.key_vector;
    t.key_vector :=
      new_m_vector[Value](new_size, cast[Value](empty_hash_bucket));
    t.length := 0;
    old_key_vector.do(&(k:Value){
	if(k.is_valid_bucket_element, { t.add_nonmember(k); });
    });
    assert(old_len = t.length, "should have the same elements");
}

let var default_hash_keyed_set_size:int := 4;

method new_hash_keyed_set[Key <= hashable[Key], Value <= keyed_hashable[Key]](
      ):hash_keyed_set[Key,Value] {
    new_hash_keyed_set[Key,Value](default_hash_keyed_set_size) }
method new_hash_keyed_set[Key <= hashable[Key], Value <= keyed_hashable[Key]](
      size:int):hash_keyed_set[Key,Value] {
    let real_size := prime_table_size(size);
    concrete object isa hash_keyed_set[Key,Value] {
       key_vector :=
	 new_m_vector[Value](real_size, cast[Value](empty_hash_bucket)) } }

method copy_empty(c@:hash_keyed_set[`Key,`Value]):hash_keyed_set[Key,Value] {
    new_hash_keyed_set[Key,Value]() }
method copy(t@:hash_keyed_set[`Key,`Value]):hash_keyed_set[Key,Value] {
    concrete object isa hash_keyed_set[Key,Value] {
	key_vector := t.key_vector.copy,
	length := t.length } }

} -- end module HashKeyedSet