Class: AbstractNode

AbstractNode

An AbstractNode represents an node in the model and contains references to the its parents and children, as well as the previous and next adjacent nodes. An AbstractGraph is made up of AbstractNodes.

Definitions of specific terms:

  • parent: x is a parent of y if and only if:
    • x happens before y and
    • their hosts are not the same and
    • there does not exist any node with x's host that happens after x and before y
  • child: x is a child of y if and only if:
    • x happens after y and
    • their hosts are not the same and
    • there does not exist any node with x's host that happens before x and after y
  • family: x is a family node of y if y is x's parent or child. This implies that x is a family node of y if and only if y is a family node of x
  • next node: x is the next node of y if and only if:
    • x happens after y and
    • their hosts are the same and
    • there does not exist any node that has the same host that happens before x and after y
  • prev/previous node: x is the previous node of y is and only if:
    • x happens before y and
    • their hosts are the same and
    • there does not exist and node that has the same host that happens after x and before y
  • between: A node n is between nodes x and y if n happens after x and before y OR n happens after y and before x. In addition, nodes x, y, and n must all belong to the same host
  • consecutive: a sequence S of nodes n_1, n_2 ... n_k are consecutive if n_i is the previous node of n_(i+1) for all i between 1 and k-1 inclusive
  • "happens before" and "happens after": There is a notion of ordering between nodes. More formally, there is a comparison function f(n1, n2) that indicates the ordering of two nodes n1 and n2. For a pair of nodes with the same host, n1 must either happen before (be ordered before) n2 or happens after (be ordered after) n1. If a pair of nodes have different hosts, it could also be the case that neither node happens before or after the other. A node x happens after node y if and only if node y happens before node x. This notion of ordering - this comparison function - may be different for each concrete class that extends node, and it is up to subclasses to precisely define their comparison function, subject to the restrictions above.
Pictorially:
|  |  |     -- C is a parent of X
A  C  E     -- X is a child of C
| /|  |     -- A is the previous node of X. A is NOT a parent of X
|/ |  |     -- B is the next node of X. B is NOT the child of X
X  D  F     -- C is NOT a parent of G nor is G a child of C
|  |\ |     -- A X B are consecutive nodes
|  | \|     -- X is between A and B
B  |  G
|  |  |

The AbstractNode class makes the following guarantees:
  • node.getID() is globally unique
  • if node.getNext() != false, then node == node.getNext().getPrev()
  • if node.getPrev() != false, then node == node.getPrev().getNext()
  • if and only if x is a child of y, then y is a parent of x
  • All the children of a node belong to different hosts
  • All the parents of a node belong to different hosts
  • Head and tail nodes have no family

Constructor

(abstract) new AbstractNode()

The constructor for this abstract class will typically be invoked by concrete sub-classes
Source:

Methods

addChild(node)

Adds a child to this node, preserving the invariants described at the top of this document. Specifically:

  • if and only if x is a child of y, then y is a parent of x
  • All the children of a node belong to different hosts
  • All the parents of a node belong to different hosts

    • The last two invariants are preserved by calling removeChild or removeParent on any existing children or parents that violate the invariants.

    A node x cannot be the child of a node y if they have the same host.

    Parameters:
    Name Type Description
    node AbstractNode The child node to add
    Source:

    addParent(node)

    Adds a parent to this node, preserving the invariants described at the top of this document. Specifically:

  • if and only if x is a child of y, then y is a parent of x
  • All the children of a node belong to different hosts
  • All the parents of a node belong to different hosts

    • The last two invariants are preserved by calling removeChild or removeParent on any existing children or parents that violate the invariants.

    A node x cannot be the parent of a node y if they have the same host.

    Parameters:
    Name Type Description
    node AbstractNode The node to add as a parent to this
    Source:

    clearChildren()

    Removes all of this node's children while preserving the invariants described at the top of this document.
    Source:

    clearFamily()

    Removes all of this node's family while preserving the invariants described at the top of this document.
    Source:

    clearParents()

    Removes all of this node's parents while preserving the invariants described at the top of this document.
    Source:

    getChildByHost(host) → {AbstractNode}

    Returns the child of this node that belongs to a specific host.
    Parameters:
    Name Type Description
    host String The target host
    Source:
    Returns:
    The child node or null if no child belongs to host.
    Type
    AbstractNode

    getChildren() → {Array.<AbstractNode>}

    Returns children of this node as an array

    This function makes no guarantees about the ordering of nodes in the array returned. Also note that a new array is created to prevent modification of the underlying private data structure, so this function takes linear rather than constant time on the number of children.

    Source:
    Returns:
    Array of child nodes.
    Type
    Array.<AbstractNode>

    getConnections() → {Array.<AbstractNode>}

    Returns the nodes this one is connected to as an array. In the context of this function, a node is said to be connected to this one if it's the previous node, the next node, a parent, or a child. Note that if prev or next is a head or tail or null, it will still be returned.

    This function makes no guarantees about the ordering of nodes in the array returned. Also note that a new array is created to prevent modification of the underlying private data structure, so this function takes linear rather than constant time on the number of connections.

    Source:
    Returns:
    an array of connected nodes
    Type
    Array.<AbstractNode>

    getFamily() → {Array.<AbstractNode>}

    Returns the family nodes of this node as an array.

    This function makes no guarantees about the ordering of nodes in the array returned. Also note that a new array is created to prevent modification of the underlying private data structure, so this function takes linear rather than constant time on the number of family nodes.

    Source:
    Returns:
    an array of connected nodes
    Type
    Array.<AbstractNode>

    getFamily() → {Array.<AbstractNode>}

    Returns family of this node as an array

    This function makes no guarantees about the ordering of nodes in the array returned. Also note that a new array is created to prevent modification of the underlying private data structure, so this function takes linear rather than constant time on the number of family.

    Source:
    Returns:
    Array of family nodes.
    Type
    Array.<AbstractNode>

    getHost() → {String}

    Gets the node's host
    Source:
    Returns:
    the name of the host
    Type
    String

    getId() → {Number}

    Gets the globally unique ID of the node
    Source:
    Returns:
    the ID
    Type
    Number

    getNext() → {AbstractNode}

    Gets the next node. The next node is the node having the same host as the current one that comes directly after the current node. Note: the next node may be a dummy node (e.g., an isTail node).
    Source:
    Returns:
    the next node or null if there is no next node
    Type
    AbstractNode

    getParentByHost(host) → {AbstractNode}

    Returns the parent of this node that belongs to a specific host.
    Parameters:
    Name Type Description
    host String The target host
    Source:
    Returns:
    The parent node or null if no parent belongs to host.
    Type
    AbstractNode

    getParents() → {Array.<AbstractNode>}

    Returns parents of this node as an array

    This function makes no guarantees about the ordering of nodes in the array returned. Also note that a new array is created to prevent modification of the underlying private data structure, so this function takes linear rather than constant time on the number of parents.

    Source:
    Returns:
    Array of parent nodes.
    Type
    Array.<AbstractNode>

    getPrev() → {AbstractNode}

    Gets the previous node. The previous node is the node having the same host as the current one that comes directly before the current node.
    Source:
    Returns:
    the previous node or null if there is no previous node
    Type
    AbstractNode

    hasChildren() → {Boolean}

    Determines whether the node has children.
    Source:
    Returns:
    True if the node has children
    Type
    Boolean

    hasFamily() → {Boolean}

    Determines whether the node has family
    Source:
    Returns:
    True if the node has family
    Type
    Boolean

    hasParents() → {Boolean}

    Determines whether the node has parents
    Source:
    Returns:
    True if the node has parents
    Type
    Boolean

    insertNext(node)

    Inserts a node after this one, preserving the invariants described at the top of this document. The node to insert is first removed from its previous location (i.e by calling AbstractNode#remove). You cannot insert a node after a tail node.

    Parameters:
    Name Type Description
    node AbstractNode The node to insert
    Source:

    insertPrev(node)

    Inserts a node before this one, preserving the invariants described at the top of this document. The node to insert is first removed from its previous location (i.e by calling AbstractNode#remove). You cannot insert a node before a head node.

    Parameters:
    Name Type Description
    node AbstractNode The node to insert
    Source:

    isDummy() → {Boolean}

    Determines whether the node is a dummy head or tail node
    Source:
    Returns:
    True if node is dummy
    Type
    Boolean

    isHead() → {Boolean}

    Determines whether the node is a dummy head node
    Source:
    Returns:
    True if node is head
    Type
    Boolean

    isTail() → {Boolean}

    Determines whether the node is a dummy tail node
    Source:
    Returns:
    True if node is tail
    Type
    Boolean

    remove()

    Removes a node, preserving the invariants described at the top of this document. This method will also remove all connections to the node. Head and tail nodes cannot be removed. This function does nothing if it is called on a node that had already been removed.

    Because this method essentially removes all links to and from the node, be careful when using this inside a loop. For example, consider the following code: 

    var node = this.getHead(host).getNext();
while (!curr.isTail()) {
    curr.remove();
    curr = curr.getNext(); // sets curr to null! curr.getNext() == null after removal
}
    Source:

    removeChild(node)

    Removes the target node from this's children, preserving the invariants described at the top of this document. If the argument is not one of this' children, this method does nothing.
    Parameters:
    Name Type Description
    node AbstractNode
    Source:

    removeChildByHost(host)

    Removes the child of this node that belongs to a specific host. If there is no child that belongs to host, then this method does nothing.
    Parameters:
    Name Type Description
    host String
    Source:

    removeFamily(node)

    Removes the target node from this's parents or children, preserving the invariants described at the top of this document. If the argument is not one of this' parents or children, this method does nothing
    Parameters:
    Name Type Description
    node AbstractNode
    Source:

    removeParent(node)

    Removes the target node from this's parents, preserving the invariants described at the top of this document. If the argument is not one of this' parents, this method does nothing.
    Parameters:
    Name Type Description
    node AbstractNode
    Source:

    removeParentByHost(host)

    Removes the parent of this node that belongs to a specific host. If there is no parent that belongs to host, then this method does nothing.
    Parameters:
    Name Type Description
    host String
    Source: