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

--DOC chained_hash_table is an implementation of tables using a closed
--DOC hashing algorithm.

module ChainedHashTable {

template object chained_hash_table[Key <= hashable[Key], Value]
					isa m_removable_table[Key,Value];
private var field buckets(t@:chained_hash_table[`Key,`Value]
			  ):m_indexed[m_removable_table[Key,Value]] :=
	     t.new_buckets(default_chained_hash_table_size);
private put var field length(t@:chained_hash_table[`Key,`Value]):int := 0;

method do_associations(t@:chained_hash_table[`Key,`Value],
		       c:&(Key,Value):void):void {
    do(t.buckets, &(b:m_removable_table[Key,Value]){
	do_associations(b, c);
    });
}

method do_associations_allowing_updates(t@:chained_hash_table[`Key,`Value],
					c:&(Key,Value):void):void {
    -- disable resizing during iteration
    allowing_updates.begin_allowing_updates(t);
    unwind_protect({
	do_associations(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);
	    });
	});
    });
}

private method bucket(t@:chained_hash_table[`Key,`Value], key:Key)
     		     :m_removable_table[Key,Value] {
    t.buckets ! hash(key, t.buckets.length) }

method fetch(t@:chained_hash_table[`Key,`Value], key:Key,
	     if_absent:&():`Else):Value|Else {
    fetch(bucket(t, key), key, if_absent) }

method store(t@:chained_hash_table[`Key,`Value], key:Key, value:Value,
	     if_absent:&():void):void {
    let b:m_removable_table[Key,Value] := bucket(t, key);
    let old_length:int := b.length;
    store(b, key, value);
    t.length := t.length - old_length + b.length;
    if(t.should_grow, { t.resize(t.grown_size); });
}

method remove_key(t@:chained_hash_table[`Key,`Value], key:Key,
		  if_absent:&():`Else):Value|Else {
    let b:m_removable_table[Key,Value] := bucket(t, key);
    let old_length:int := b.length;
    let x:Value := remove_key(b, key, { ^ eval(if_absent) });
    t.length := t.length - old_length + b.length;
    if(t.should_shrink, { t.resize(t.shrunk_size); });
    x }

method remove_keys_if(t@:chained_hash_table[`Key,`Value],
			pred:&(Key):bool):int {
    let var count:int := 0;
    t.buckets.do(&(b:m_removable_table[Key,Value]){
	count = count + b.remove_keys_if(pred);
    });
    t.length = t.length - count;
    if(t.should_shrink, { t.resize(t.shrunk_size); });
    count
}

method remove_all(t@:chained_hash_table[`Key,`Value]):void {
    t.length := 0;
    if(t.should_shrink, {
	-- will create fresh, empty buckets
	t.buckets := t.new_buckets(t.shrunk_size);
    }, {
	-- need to clear those buckets that remain
	t.buckets.do(&(ms:m_removable_table[Key,Value]){ ms.remove_all; });
    });
}

private method should_grow(t@:chained_hash_table[`Key,`Value]):bool {
    -- more than one elem per bucket...
    allowing_updates.updates_allowed(t).not &
      { t.length > 5 & { t.length > t.buckets.length } } }
private method grown_size(t@:chained_hash_table[`Key,`Value]):int {
    average(t.buckets.length * 2, t.length) }

private method should_shrink(t@:chained_hash_table[`Key,`Value]):bool {
    -- less than 1/5 full...
    allowing_updates.updates_allowed(t).not &
      { t.buckets.length > 8 & { t.length * 5 < t.buckets.length } } }
private method shrunk_size(t@:chained_hash_table[`Key,`Value]):int {
    average(t.buckets.length / 2, t.length) }

private method resize(t@:chained_hash_table[`Key,`Value], new_size:int):void {
    let old_len:int := t.length;
    let old_buckets:indexed[m_removable_table[Key,Value]] := t.buckets;
    t.buckets := t.new_buckets(new_size);
    t.length := 0;
    old_buckets.do(&(bucket_table:m_removable_table[Key,Value]){
	bucket_table.do_associations(&(k:Key, v:Value){ t.store(k,v); });
    });
    assert(old_len = t.length, "should have the same elements");
}

protected method new_buckets(t@:chained_hash_table[`Key,`Value], size:int
			     ):m_indexed[m_removable_table[Key,Value]] {
    new_m_vector_init[m_removable_table[Key,Value]](max(1,size),
						    &(i:int){ t.new_bucket }) }
protected method new_bucket(t@:chained_hash_table[`Key,`Value]
			     ):m_removable_table[Key,Value] {
    new_assoc_table[Key,Value]() }

let var default_chained_hash_table_size:int := 11;

method new_chained_hash_table[Key <= hashable[Key], Value]()
     :chained_hash_table[Key,Value] {
    new_chained_hash_table[Key,Value](default_chained_hash_table_size) }
method new_chained_hash_table[Key <= hashable[Key], Value](size:int)
     :chained_hash_table[Key,Value] {
    let t:chained_hash_table[Key,Value] :=
      concrete object isa chained_hash_table[Key,Value];
    t.buckets := t.new_buckets(size);
    t }

method copy_empty(t@:chained_hash_table[`Key,`Value]
		  ):chained_hash_table[Key,Value] {
    new_chained_hash_table[Key,Value](t.buckets.length) }
method copy(t@:chained_hash_table[`Key,`Value]):chained_hash_table[Key,Value] {
    let c:chained_hash_table[Key,Value] := t.copy_empty;
    t.buckets.do_associations(&(i:int,b:m_removable_table[Key,Value]){
	c.buckets!i := b.copy;
    });
    c.length := t.length;
    c }


-- return a histogram computing, for each key in the table, how many
-- probes are necessary to find it.  this gives a sense of how many conflicts
-- there are in the table
method probe_histogram(t@:chained_hash_table[`Key,`Value]):histogram[int] {
    let h := new_histogram[int]();
    t.buckets.do(&(b:m_removable_table[Key,Value]){
        -- for the i'th entry in the bucket (origin 1), there'll be i probes
	for(1, b.length, &(i:int){
	    h.increment(i);
	});
    });
    h }


--
-- table data structure with different printing behavior
--
template object chained_hash_CR_table[Key <= hashable[Key], Value]
	isa chained_hash_table[Key,Value];

method elem_separator(t@:chained_hash_CR_table[`Key,`Value]):string { "\n" }

method new_chained_hash_CR_table[Key <= hashable[Key], Value]()
     :chained_hash_CR_table[Key,Value] {
    new_chained_hash_CR_table[Key,Value](default_chained_hash_table_size) }
method new_chained_hash_CR_table[Key <= hashable[Key], Value](size:int)
     					     :chained_hash_CR_table[Key,Value]{
    let t:chained_hash_CR_table[Key,Value] :=
      concrete object isa chained_hash_CR_table[Key,Value];
    t.buckets := t.new_buckets(size);
    t }

method copy_empty(c@:chained_hash_CR_table[`Key,`Value]
		  ):chained_hash_CR_table[Key,Value] {
    new_chained_hash_CR_table[Key,Value](c.buckets.length) }

protected method new_bucket(t@:chained_hash_CR_table[`Key,`Value]
			    ):m_removable_table[Key,Value] {
    new_assoc_CR_table[Key,Value]() }

} -- end module ChainedHashTable