› Async › Source › Async › List

class List

A general doublely linked list. This is used internally by class Async::Barrier and class Async::Condition to manage child tasks.

Nested

Definitions

def initialize

Initialize a new, empty, list.

Implementation

 
def initialize
	@head = self
	@tail = self
	@size = 0
end

def to_s

Signature
returns　String

A short summary of the list.

Implementation

 
def to_s
	sprintf("#<%s:0x%x size=%d>", self.class.name, object_id, @size)
end

def to_a

Fast, safe, unbounded accumulation of children.

Implementation

 
def to_a
	items = []
	current = self
	
	while current.tail != self
		unless current.tail.is_a?(Iterator)
			items << current.tail
		end
		
		current = current.tail
	end
	
	return items
end

attr_accessor :head

Signature
attribute　Node | Nil

Points at the end of the list.

attr_accessor :tail

Signature
attribute　Node | Nil

Points at the start of the list.

attr :size

Signature
attribute　Integer

The number of nodes in the list.

def added(node)

A callback that is invoked when an item is added to the list.

Implementation

 
def added(node)
	@size += 1
	return node
end

def append(node)

Append a node to the end of the list.

Implementation

 
def append(node)
	if node.head
		raise ArgumentError, "Node is already in a list!"
	end
	
	node.tail = self
	@head.tail = node
	node.head = @head
	@head = node
	
	return added(node)
end

def prepend(node)

Prepend a node to the start of the list.

Implementation

 
def prepend(node)
	if node.head
		raise ArgumentError, "Node is already in a list!"
	end
	
	node.head = self
	@tail.head = node
	node.tail = @tail
	@tail = node
	
	return added(node)
end

def stack(node, &block)

Add the node, yield, and the remove the node.

Signature
yields　{|node| ...}

Yields the node.

returns　Object

Returns the result of the block.

Implementation

 
def stack(node, &block)
	append(node)
	return yield(node)
ensure
	remove!(node)
end

def removed(node)

A callback that is invoked when an item is removed from the list.

Implementation

 
def removed(node)
	@size -= 1
	return node
end

def remove?(node)

Remove the node if it is in a list.

You should be careful to only remove nodes that are part of this list.

Signature
returns　Node

Returns the node if it was removed, otherwise nil.

Implementation

 
def remove?(node)
	if node.head
		return remove!(node)
	end
	
	return nil
end

def remove(node)

Remove the node. If it was already removed, this will raise an error.

You should be careful to only remove nodes that are part of this list.

Signature
raises　ArgumentError

If the node is not part of this list.

returns　Node

Returns the node if it was removed, otherwise nil.

Implementation

 
def remove(node)
	# One downside of this interface is we don't actually check if the node is part of the list defined by `self`. This means that there is a potential for a node to be removed from a different list using this method, which in can throw off book-keeping when lists track size, etc.
	unless node.head
		raise ArgumentError, "Node is not in a list!"
	end
	
	remove!(node)
end

def empty?

Signature
returns　Boolean

Returns true if the list is empty.

Implementation

 
def empty?
	@size == 0
end

def each(&block)

Iterate over each node in the linked list. It is generally safe to remove the current node, any previous node or any future node during iteration.

Signature
yields　{|node| ...}

Yields each node in the list.

returns　List

Returns self.

Implementation

 
def each(&block)
	return to_enum unless block_given?
	
	Iterator.each(self, &block)
	
	return self
end

def include?(needle)

Determine whether the given node is included in the list.

Signature
parameter　needle　Node

The node to search for.

returns　Boolean

Returns true if the node is in the list.

Implementation

 
def include?(needle)
	self.each do |item|
		return true if needle.equal?(item)
	end
	
	return false
end

def first

Signature
returns　Node

Returns the first node in the list, if it is not empty.

Implementation

 
def first
	# validate!
	
	current = @tail
	
	while !current.equal?(self)
		if current.is_a?(Iterator)
			current = current.tail
		else
			return current
		end
	end
	
	return nil
end

def last

Signature
returns　Node

Returns the last node in the list, if it is not empty.

Implementation

 
def last
	# validate!
	
	current = @head
	
	while !current.equal?(self)
		if current.is_a?(Iterator)
			current = current.head
		else
			return current
		end
	end
	
	return nil
end

def shift

Shift the first node off the list, if it is not empty.

Implementation

 
def shift
	if node = first
		remove!(node)
	end
end

Discussion