dictionary.zc

实现树形结构

//[of]:description
//[c]The hashtable class
//[c]
//[c]Abstract class for dictionaries. The class must be inherited to be used.
//[c]Implement the following methods:	
//[c]- hash ()   returns the hash code of a key	
//[c]- match ()  compare two keys
//[cf]
//[of]:imports
import "base/types"
import "base/numbers"
import "base/memory"
import "base/memory-allocator"
//[cf]
//[of]:types
//[c]
public typedef key = -> void
public typedef value = -> void
//[cf]
//[of]:structures
//[c]
private struct association
	key: key
	value: value
end
//[c]
public struct dictionary class
	hash: {key} int
	is equal: {key, key} bool
end
//[c]
//[c]
//[c]Instance variables:
//[c]
//[c]	associations
//[c]		buffer to all associations
//[c]	size
//[c]		total number of slots
//[c]	tally
//[c]		number of used slots
//[c]	collisions
//[c]		maximum of collisions occured
//[c]
//[c]collisions is an upper bound: after removing an association the
//[c]value may be wrong
//[c]
public struct dictionary

	private class: dictionary class
	private associations: [] local association
	private tally: size
	private allocated: size
	private collisions: int

end
//[cf]
//[c]
//[of]:initialize - release
//[of]:dictionary (class)
//[c]Initializes a new hastable
//[c]
public equ dictionary (class: dictionary class, d: dictionary) = initialize (d, class)
//[cf]
//[c]
//[of]:initialize (d, class)
//[c]
public func initialize (d: dictionary, class: dictionary class)

	class (d) = class
	collisions (d) = 0
	tally (d) = 0:d
	allocated (d) = default allocated
	associations (d) = new array of associations (default allocated)
	
	each (associations (d), default allocated) ? a
		key (a) = nil
	end

end
//[cf]
//[of]:release (d)
//[c]Deletes an hashtable
//[c]
public func release (d: dictionary)

	// it is the responsibility of the sub-class to free the keys and values
	free memory (associations(d))

end
//[cf]
//[cf]
//[of]:adding - removing
//[of]:add (d, key, value)
//[c]Puts value
//[c]
//[c]There must be at least one free slot.
//[c]If there were already a value at this slot, the old value is returned.
//[c]In such a case, the returned value, and the passed key are no more
//[c]referenced by the dictionary, it is the responsibility of the sub-class
//[c]to free them.
//[c]
public func add(d: dictionary, k: key, v: value)

	def location = slot (d, k)
	def count = 1
	
	repeat
		def a = associations(d)[location]
		if not empty (a)
			if is equal (d, k, key (a))
				def old = value (a)
				value (a) = v
				return old
			else
				circular inc (location, allocated (d))
				++count
			end
		else
			key (a) = k
			value (a) = v
			if count > collisions (d)
				collisions (d) = count
			end
			increase tally (d)
			return nil
		end
	end
	
	return nil // make compiler happy

end
//[cf]
//[of]:remove (d, key)
//[c]Removes an item
//[c]
//[c]Returns the item for the given key or nil if not found
//[c]
public func remove (d: dictionary, k: key)

	def location = slot (d, k)
	def count = collisions (d)

	while count > 0 && not empty (d, location)
		def a = associations(d)[location]
		if is equal (d, k, key (a))
			clear (a)
			circular inc (location, allocated (d))
			fill up (d, location) // useless if we are going to resize
			decrease tally (d)
			return
		end
		circular inc (location, allocated (d))
		--count
	end
	
end
//[cf]
//[cf]
//[of]:enumerating
//[of]:each key and value (d)
//[c]Enumerates keys and values
//[c]
public equ each key and value (d: dictionary)

	def i = 0:d
	def size = allocated (d)
	while i < size
		if not empty (d, i)
			def a = associations(d)[i]
			yield (key (a), value (a))
		end
		++i
	end

end
//[cf]
//[of]:each key (d)
//[c]Enumerates keys
//[c]
public equ each key (d: dictionary)

	def i = 0:d
	def size = allocated (d)
	while i<size
		if not empty(d, i)
			def v = key (associations(d)[i])
			yield (v)
		end
		++i
	end

end
//[cf]
//[of]:each value (d)
//[c]Enumerates values
//[c]
public equ each value (d: dictionary)

	def i = 0:d
	def size = allocated (d)
	while i<size
		if not empty(d, i)
			def v = value (associations(d)[i])
			yield (v)
		end
		++i
	end

end
//[cf]
//[cf]
//[of]:accessing
//[of]:size (d)
//[c]
public equ size (d: dictionary) = 
	tally (d)
//[cf]
//[of]:value (d, key)
//[c]Finds value
//[c]
//[c]	Returns the value for the given key
//[c]
public func value (d: dictionary, k: key)

	def location = slot (d, k)
	def count = collisions (d)
	
	while count>0 && not empty (d, location)
		def a = associations (d) [location]
		if is equal (d, key (a), k)
			return value (a)
		end
		circular inc (location, allocated (d))
		--count
	end
	
	return nil

end
//[cf]
//[of]:d [key]
//[c]
public equ @at (d: dictionary, k: key) = value (d, k)
//[cf]
//[cf]
//[of]:testing
//[of]:is empty (d)
//[c]
public equ is empty (d: dictionary) = 
	tally (d) == 0:d
//[cf]
//[of]:not empty (d)
//[c]
public equ not empty (d: dictionary) = 
	tally (d) <> 0:d
//[cf]
//[cf]
//[c]
//[of]:private
//[c]private
//[c]
//[of]:constants
//[c]
equ default allocated = 10
//[cf]
//[c]
//[of]:resize (d, size)
//[c]Resizes the list of associations
//[c]
func resize (d: dictionary, s: size)

	def c = 0
	def a = new array of associations (s)
	
	each (a, s) ? e
		key(e) = nil
	end

	each key and value (d) ? key, value
	
		def count = 1
		def location = hash (d, key):dword % s
		while not nil (a[location].key)
			circular inc (location, s)
			++ count
		end
		
		key (a[location]) = key
		value (a[location]) = value
		c = max(count, c)
	
	end
	
	free memory (associations (d))
	collisions (d) = c
	associations (d) = a
	allocated (d) = s

end
//[cf]
//[of]:increase tally (d)
//[c]Increases the counter of items
//[c]Grow the array if more than 75% of slots are used
//[c]
func increase tally (d: dictionary)

	++ tally (d)
	if 4 * tally (d) > 3 * allocated (d)
		resize (d, allocated (d) * 3 / 2)
	end

end
//[cf]
//[of]:decrease tally (d)
//[c]Decreases the counter of items
//[c]Reduce the array if less than 30% of slots are used
//[c]
func decrease tally (d: dictionary)

	++tally (d)
	if 3 * tally (d) < allocated (d)
		resize (d, max (default allocated, 2 * allocated (d) / 3))
	end

end
//[cf]
//[of]:fill up (d, current)
//[c]Fixes collisions after freeing a slot
//[c]
func fill up (d: dictionary, current: dword)

	while not empty (d, current)
		def best = slot (d, key (d, current))
		def count = 0
		if current <> best
			while not empty (d, best)
				circular inc (best, allocated (d))
				++count
			end
		end
		if current <> best
			copy (associations(d)[best], associations(d)[current])
			clear (d, current)
			collisions (d) = max (collisions (d), count)
		end
		circular inc (current, allocated (d))
	end

end
//[cf]
//[c]
//[of]:key (d, index)
//[c]
equ key (d: dictionary, i: dword) = 
	key (associations(d) [i])
//[cf]
//[of]:value (d, index)
//[c]
equ value (d: dictionary, i: dword) = 
	value (associations (d) [i])
//[cf]
//[of]:is empty (d, index)
//[c]
equ is empty (d: dictionary, i: dword) = 
	is nil (key (associations(d) [i]))
//[cf]
//[of]:not empty (d, index)
//[c]
equ not empty (d: dictionary, i: dword) = 
	not nil (key (associations(d) [i]))
//[cf]
//[of]:set key (d, index, key)
//[c]
equ set key (d: dictionary, i: dword, k: key) = 
	key (associations(d) [i]) = k
//[cf]
//[of]:set value (d, index, value)
//[c]
equ set value (d: dictionary, i: dword, v: value) = 
	value (associations(d) [i]) = v
//[cf]
//[of]:clear (d, index)
//[c]
equ clear (d: dictionary, i: dword) = 
	set key (d, i, nil)
//[cf]
//[c]
//[of]:hash (d, key)
//[c]
equ hash (d: dictionary, k: key) = 
	hash (class (d)) {k}
//[cf]
//[of]:is equal (d, key1, key2)
//[c]
equ is equal (d: dictionary, k1: key, k2: key) = 
	is equal (class (d)) {k1, k2}
//[cf]
//[of]:slot (d, key)
//[c]
equ slot (d: dictionary, k:key) = 
	hash (d, k) : dword % allocated (d)
//[cf]
//[c]
//[c]association
//[of]:is empty (a)
//[c]
equ is empty (a: association) = is nil (key (a))
//[cf]
//[of]:not empty (a)
//[c]
equ not empty (a: association) = not nil (key (a))
//[cf]
//[of]:clear (a)
//[c]
equ clear (a: association) = key (a) = nil
//[cf]
//[of]:each ([] local association, size)
//[c]
equ each (a: [] local association, s: size)

	def i = 0:d
	while i < s
		yield (a[i])
		++i
	end

end
//[cf]
//[of]:copy (src)
//[c]
equ copy (dst: association, src: association)
	key (dst) = key (src)
	value (dst) = value (src)
end
//[cf]
//[of]:new array of associations (size)
//[c]
equ new array of associations (s: size) =  
	
	allocate memory (s * sizeof local association) : [] local association

//[cf]
//[c]
//[c]integer
//[of]:circular inc (x, size)
//[c]
equ circular inc (x: dword, s: size)

	++x
	if x==s
		x = 0
	end

end
//[cf]
//[cf]