linked-collection.zc

实现树形结构

//[of]:description
//[c]Linked collection is like a collection but it is a double linked list.
//[c]
//[c]The double linked list allow fast removal of any element (o(1)).
//[cf]
//[of]:imports
//[c]
import "base/types"
import "base/memory-allocator"
import "collection/collection"
//[cf]
//[of]:structures
//[c]
public struct linked element
	next: linked element
	prev: linked element
end	
//[c]
public struct linked collection
	first: linked element
	last: linked element
end
//[cf]
//[c]
//[of]:initialize - release
//[of]:linked collection
//[c]
public equ linked collection (return list: linked collection) = initialize (list)
//[cf]
//[of]:initialize (list)
//[c]
public func initialize (list: linked collection)
	first (list) = nil
	last (list) = nil
end
//[cf]
//[cf]
//[of]:enumerating
//[of]:each (list)
//[c]
public equ each (list: linked collection)

	def e = first (list)
	while not nil (e)
		yield (e)
		e = next (e)
	end

end
//[cf]
//[cf]
//[of]:adding - removing
//[of]:append (list, e)
//[c]Appends an element
//[c]
public func append (list: linked collection, e: linked element)

	next (e) = nil
	prev (e) = last (list)
	
	// update the head of the list
	if is nil (first (list))
		first (list) = e
	end
	
	// update successor
	def last = last (list)
	if not nil (last)
		next (last) = e
	end

	// update the tail of the list
	last (list) = e

end
//[cf]
//[of]:add (list, e)
//[c]
public equ add (list: linked collection, e: linked element) = 
	append (list, e)
//[cf]
//[of]:remove (list, e)
//[c]Removes an element
//[c]
public func remove (list: linked collection, e: linked element)

	if first (list) == e
		first (list) = next (e)
	end
	
	if last (list) == e
		last (list) = prev (e)
	end

	if not nil (prev (e))
		next (prev (e)) = next (e)
	end

	if not nil (next (e))
		prev (next (e)) = prev (e)
	end

end
//[cf]
//[cf]
//[of]:testing
//[of]:is empty (list)
//[c]
public equ is empty (list: linked collection) = is nil (first (list))
//[cf]
//[of]:not empty (list)
//[c]
public equ not empty (list: linked collection) = not nil (first (list))
//[cf]
//[cf]