vector-of-integers.zc

实现树形结构

//[of]:imports
import "base/types"
import "base/memory"
import "base/memory-allocator"
//[cf]
//[of]:structures
public struct vector of integers

	private allocated: size
	private array: [] cell
	public size: size

end
//[cf]
//[c]
//[of]:instance creation
//[of]:new vector of integers (initial allocated)
public func new vector of integers (initial allocated: size)

	def v = allocate memory (sizeof local vector of integers): vector of integers
	initialize (v, initial allocated)
	return v

end
//[cf]
//[of]:new vector of integers (src vector)
public func new vector of integers (src: vector of integers)

	def v = allocate memory (sizeof local vector of integers): vector of integers
	initialize (v, src)
	return v

end
//[cf]
//[of]:delete
public func delete (v: vector of integers)
	if not nil (v)
		release (v)
		free memory (v)
	end
end
//[cf]
//[cf]
//[of]:initialize - release
//[of]:vector (src vector)
public equ vector of integers (src: vector of integers, return v: vector of integers) = initialize (v, src)
//[cf]
//[of]:vector (initial allocated)
//[c]Initializes (empty)
//[c]
public equ vector of integers (initial allocated: size, return v: vector of integers) = initialize (v, initial allocated)
//[cf]
//[c]
//[of]:initialize (src vector)
//[c]
public func initialize (v: vector of integers, src: vector of integers)

	size (v) = size (src)
	allocated (v) = allocated (src)
	array (v) = allocate memory (allocated (src) * sizeof cell): []cell
	copy (array (v):mem, array (src):mem, size (src) * sizeof cell)

end
//[cf]
//[of]:initialize (initial allocated)
//[c]
public func initialize (v: vector of integers, initial allocated: size)

	size (v) = 0
	allocated (v) = initial allocated
	array (v) = allocate memory (initial allocated * sizeof cell): []cell

end
//[cf]
//[of]:initialize
//[c]
public func initialize (v: vector of integers)
	initialize (v, default vector size)
end
//[cf]
//[c]
//[of]:release
//[c]
public func release (v: vector of integers)
	free memory (array (v))
end
//[cf]
//[cf]
//[of]:adding - removing
//[of]:append (value)
//[c]Appends an element
//[c]
public func append (v: vector of integers, value: cell)

	def index = size (v)
	if allocated (v) == index
		reserve (v)
	end
	
	array (v) [index] = value
	
	++size (v)
end
//[cf]
//[of]:add (value)
//[c]
public equ add (v: vector of integers, value: cell) = 
	
	append (v, value)

//[cf]
//[of]:add first (value)
//[c]Adds an element at the beginning
//[c]
public func add first (v: vector of integers, value: cell)
	add (v, value, 0)
end
//[cf]
//[of]:add (value, index)
//[c]Adds an element at index
//[c]
public func add (v: vector of integers, value: cell, index: dword)

	def n = size (v)
	if allocated (v) == n
		reserve (v)
	end

	def base = array (v) + index
	move ((base+1):mem, base:mem, sizeof cell * (n-index))

	array (v) [index] = value

	++ size (v)
end
//[cf]
//[c]
//[of]:remove (index)
//[c]Removes an element at index
//[c]
public func remove (v: vector of integers, index: dword)

	def base = array (v) + index
	def n = size (v)
	move (base:mem, (base + 1):mem, sizeof cell * (n-index-1))
	-- size (v)

end
//[cf]
//[of]:remove (value)
//[c]Removes an element
//[c]
public func remove (v: vector of integers, value: cell)

	def i = 0:dword
	def n = size (v)
	while i < n
		if v[i] == value
			remove (v, i)
			return
		end
		++i
	end
end
//[cf]
//[of]:remove all
//[c]Removes all elements
//[c]
public func remove all (v: vector of integers)
	size (v) = 0
end
//[cf]
//[c]
//[of]:replace (index, n1, n2)
//[c]Replaces the n1 slots at index by n2 slots 
//[c]
//[c]Values are unchanged/uninitialized
//[c]
public func replace (v: vector of integers, index: dword, n1: size, n2: size)

	def delta = n2 - n1

	if delta == 0
		return
	end
	
	def size = size (v)
	def new size = size + delta

	if delta > 0 && allocated (v) < new size
		allocate (v, new size * 5 / 4)
	end

	def base = array (v) + index
	move (
		(base+n2) : mem, 
		(base+n1) : mem,
		sizeof cell * (size - index - n1))
	size (v) += delta
			
end
//[cf]
//[of]:reserve (n)
//[c]Reserves space for n elements
//[c]
//[c]This method is for optimization only: it avoids to much re-allocations 
//[c]while filling the vector.
//[c]
public func reserve (v: vector of integers, n: size)

	if allocated (v) < n
		allocate (v, n)
	end

end
//[cf]
//[cf]
//[of]:searching
//[of]:index
//[c]Finds an element
//[c]
//[c]Returns its index or -1 if not found
//[c]
public func index (v: vector of integers, value: cell)

	def i = 0:dword
	def n = size (v)
	while i < n
		if v[i] == value
			return i:int
		end
		++i
	end
	return -1

end
//[cf]
//[cf]
//[of]:enumerating
//[of]:each
//[c]Enumerates all elements
//[c]
public equ each (v: vector of integers)

	def i = 0:dword
	def n = size (v)
	while i < n
		yield (v[i])
		++i
	end

end
//[cf]
//[cf]
//[of]:accessing
//[of]:[]
//[c]Returns an element
//[c]
public equ @at (v: vector of integers, i: dword) = array (v) [i]
//[cf]
//[cf]
//[of]:testing
//[of]:contains (value)
//[c]Tests if the vector contains an item
//[c]
public func contains (v: vector of integers, value: cell)

	each (v) ? e
		if e == value
			return true
		end
	end
	return false

end
//[cf]
//[of]:is empty
//[c]
public equ is empty (v: vector of integers) = size(v) == 0
//[cf]
//[of]:not empty
//[c]
public equ not empty (v: vector of integers) = size(v) <> 0
//[cf]
//[cf]
//[c]
//[of]:private
//[of]:reserve
//[c]Reserves space
//[c]
func reserve (v: vector of integers)

	allocate (v, allocated (v) * 5 / 4 + 1)

end
//[cf]
//[of]:allocate
//[c]Reserves space
//[c]
public func allocate (v: vector of integers, new allocated: size)

	// Create new array
	def new array = allocate memory (new allocated * sizeof cell):[]cell
	
	// Copy content of old array into the new one
	copy (new array, array (v), allocated (v) * sizeof cell)

	// Delete the old array
	free memory (array (v))

	allocated (v) = new allocated
	array (v) = new array

end
//[cf]
//[c]
//[of]:types
//[c]
private typedef cell = int
//[cf]
//[of]:constants
//[c]
equ default vector size = 8
//[cf]
//[c]
//[cf]