Module: @QName: Util:ManakaiNode @FullName: @@lang: en @@@: Manakai Generic Node Implementation @Namespace: http://suika.fam.cx/~wakaba/archive/2005/manakai/Util/ManakaiNode# @Description: @@lang:en @@@: The module provides a basic implementation for glaph (perhaps tree) structures. @Author: @@FullName: Wakaba @@Mail: w@suika.fam.cx @License: license:Perl+MPL @Date: @@@: $Date: 2005/05/07 13:56:36 $ @@ContentType: dis:Date.RCS @Require: @@Module: @@@Name: DISPerl @@@QName: DISlib:DISPerl @@@WithFor: ManakaiDOM:all @@Module: @@@Name: ManakaiNode @@@WithFor: ManakaiDOM:Perl @DefaultFor: ManakaiDOM:Perl Namespace: @dis: http://suika.fam.cx/~wakaba/archive/2004/8/18/lang#dis-- @dis2pm: http://suika.fam.cx/~wakaba/archive/2004/11/8/dis2pm# @DISlib: http://suika.fam.cx/~wakaba/archive/2004/dis/ @lang: http://suika.fam.cx/~wakaba/archive/2004/8/18/lang# @license: http://suika.fam.cx/~wakaba/archive/2004/8/18/license# @ManakaiDOM: http://suika.fam.cx/~wakaba/archive/2004/8/18/manakai-dom# @owl: http://www.w3.org/2002/07/owl# @Perl: http://suika.fam.cx/~wakaba/archive/2004/8/18/lang#Perl-- @rdf: http://www.w3.org/1999/02/22-rdf-syntax-ns# @rdfs: http://www.w3.org/2000/01/rdf-schema# @TreeCore:\ @Util: http://suika.fam.cx/~wakaba/archive/2005/manakai/Util/ ResourceDef: @QName: Util: @rdf:type: dis:ModuleGroup @FullName: @@lang:en @@@: The manakai support modules @AppName: Message::Util:: ## -- Internal node object ClassDef: @QName: ManakaiDOM:ManakaiDOMNodeObject @Description: @@lang:en @@@: Internal (actual) node objects that is accessed via objects referring it. @ImplNote: @@lang:en @@@: No public interface should be defined for any class inheriting this class - applications should access to nodes only via objects. @ImplNote: @@lang:en @@@: A is a blessed hash reference. Each hash key and value pair is called as a . Currently, several core properties are defined as listed below. Applications for this class, including , defines additional properties for their purpose and scope. \ {FIG:: Core node properties \ - ::: The global-unique identifier for this node object. \ - ::: The global-unique identifier for the tree containing this node object. \ - ::: The number that denotes how many reference to this node there are. \ - ::: An array reference, containing hash key names of properties for this node. \ - ::: An array reference, containing hash key names of properties for this node. \ - ::: An array reference, containing hash key names of list properties for this node. \ - ::: An array reference, containing hash key names of (two steps) list properties for this node. \ - ::: An array reference, containing hash key names of properties for this node. \ - ::: An array reference, containing hash key names of list properties for this node. \ - ::: An array reference, containing hash key names of (two steps) list properties for this node. \ } @IntMethod: @@Name: new @@Description: @@@lang:en @@@@: Constructs a new instance of and returns it. @@Return: @@@Type: ManakaiDOM:ManakaiDOMNodeObject @@@Description: @@@@lang:en @@@@@: The newly created instance. @@@PerlDef: $r = bless { => [], => [], => [], => [], => [], => [], => [], => 0, => , => , }, ref $self || $self; @IntMethod: @@Name: newReference @@Description: @@@lang:en @@@@: Creates a new reference to this node and returns it. @@DISCore:isDeprecated: @@@@:1 @@@DISCore:alt: getNewReference @@Param: @@@Name: class @@@Type: Perl:package-name::ManakaiDOM:all @@@Description: @@@@lang:en @@@@@: A Perl class package name with which the newly created reference is blessed. The class must be a subclass of . @@Return: @@@Type: ManakaiDOM:ManakaiDOMNodeReference @@@Description: @@@@lang:en @@@@@: The newly created node reference. @@@PerlDef: $r = bless { => $self, }, ref $class ? ref $class : defined $class ? $class : ; $self->{}++; @ResourceDef: @@QName: getNewReference @@rdf:type: dis2pm:BlockCode @@Description: @@@lang:en @@@@: Creates a new node reference object. @@ResourceDef: @@@rdf:type: DISPerl:CodeParameter @@@Name: $object @@@Type: ManakaiDOM:ManakaiDOMNodeObject @@@In:1 @@@enDesc: A node object for which a reference is created. @@@DISPerl:paramStyle: var @@ResourceDef: @@@rdf:type: DISPerl:CodeParameter @@@Name: $ref @@@Type: ManakaiDOM:ManakaiDOMNodeReferemce @@@Out:1 @@@enDesc: A node reference for . It may or may not be same as . @@@DISPerl:paramStyle: var @@ResourceDef: @@@rdf:type: DISPerl:CodeParameter @@@Name: $class @@@Type: Perl:package-name::ManakaiDOM:all @@@enDesc: A package name with which is blessed. @@@In:1 @@@DISPerl:paramStyle: any @@PerlDef: $object->{}++; $ref = bless { => $object, }, $class; @ResourceDef: @@QName: getWeakReference @@rdf:type: dis2pm:BlockCode @@Description: @@@lang:en @@@@: Creates a new weak node reference object. \ The weak node reference is actually a node reference except that this code fragment does not increment the reference count of the object. When all non-weak references to the object are destructed, then the object is destructed and any operation via weak references will lead unexpected result. \ {NOTE:: It is intended that internal code creates a weak reference so that it gets access to public interface. \ } @@ResourceDef: @@@rdf:type: DISPerl:CodeParameter @@@Name: $object @@@Type: ManakaiDOM:ManakaiDOMNodeObject @@@In:1 @@@enDesc: A node object for which a reference is created. @@@DISPerl:paramStyle: var @@ResourceDef: @@@rdf:type: DISPerl:CodeParameter @@@Name: $ref @@@Type: ManakaiDOM:ManakaiDOMNodeReferemce @@@Out:1 @@@enDesc: A node reference for . It may or may not be same as . @@@DISPerl:paramStyle: var @@ResourceDef: @@@rdf:type: DISPerl:CodeParameter @@@Name: $class @@@Type: Perl:package-name::ManakaiDOM:all @@@enDesc: A package name with which is blessed. @@@In:1 @@@DISPerl:paramStyle: any @@PerlDef: $ref = bless { => $object, => true, }, $class; @ResourceDef: @@QName: getWeakRef @@rdf:type: dis2pm:InlineCode @@Description: @@@lang:en @@@@: Creates a new weak node reference object. \ The weak node reference is actually a node reference except that this code fragment does not increment the reference count of the object. When all non-weak references to the object are destructed, then the object is destructed and any operation via weak references will lead unexpected result. \ {NOTE:: It is intended that internal code creates a weak reference so that it gets access to public interface. \ } @@ResourceDef: @@@rdf:type: DISPerl:CodeParameter @@@Name: $object @@@Type: ManakaiDOM:ManakaiDOMNodeObject @@@In:1 @@@enDesc: A node object for which a reference is created. @@@DISPerl:paramStyle: var @@ResourceDef: @@@rdf:type: DISPerl:CodeParameter @@@Name: $class @@@Type: Perl:package-name::ManakaiDOM:all @@@enDesc: A package name with which is blessed. @@@In:1 @@@DISPerl:paramStyle: any @@PerlDef: bless { => $object, => true, }, $class; @IntMethod: @@Name: isExternallyReferred @@Description: @@@lang:en @@@@: Checks whether the tree containing this node has been referred from the outside of the tree or not. @@Return: @@@Type: DISPerl:Boolean::ManakaiDOM:all @@@InCase: @@@@Value: true @@@@Type: DISPerl:Boolean::ManakaiDOM:all @@@@Description: @@@@@lang:en @@@@@@: There is one or more nodes in the tree that has been referred via objects. @@@InCase: @@@@Value: false @@@@Type: DISPerl:Boolean::ManakaiDOM:all @@@@Description: @@@@@lang:en @@@@@@: No external reference found. @@@PerlDef: if ($self->{}) { $r = true; } else { my @node = ($self); my %checked; NODES: while (my $node = shift @node) { next unless ref $node eq ; if ($node->{}) { $r = true; last NODES; } elsif ($checked{$node->{}}) { next NODES; } my @n; for my $p (@{$node->{}}) { if (ref $node->{$p} eq 'ARRAY') { push @n, @{$node->{$p}}; } elsif (ref $node->{$p} eq 'HASH') { push @n, values %{$node->{$p}}; } } for my $p (@n, map {$node->{$_}} @{$node->{}}) { if (ref $p eq 'ARRAY') { push @node, @$p; } elsif (ref $p eq 'HASH') { push @node, values %$p; } } for my $p (@{$node->{}}) { unshift @node, $node->{$p} if $node->{$p}; ## NOTE: Puts the top of the list, ## since upper-level nodes are expected to be referred ## more than lower-levels. } for my $p (@{$node->{}}) { push @node, $node->{$p} if $node->{$p}; } $checked{$node->{}} = 1; } } @IntMethod: @@Name: destroy @@Description: @@@lang:en @@@@: Destructs the tree containing this node. @@Return: @@@PerlDef: my @node = ($self); NODES: while (my $node = shift @node) { my @n; for my $p (@{$node->{}}) { if (ref $node->{$p} eq 'ARRAY') { push @n, @{$node->{$p}}; } elsif (ref $node->{$p} eq 'HASH') { push @n, values %{$node->{$p}}; } } for my $p (@n, map {$node->{$_}} @{$node->{}}) { if (ref $p eq 'ARRAY') { push @node, grep {ref $_ eq and defined $_->{}} @$p; } elsif (ref $p eq 'HASH') { push @node, grep {ref $_ eq and defined $_->{}} values %$p; } } for my $p (@{$node->{}}, \ @{$node->{}}) { push @node, $node->{$p} if defined $node->{$p} and defined $node->{$p}->{}; } %$node = (); } @@ImplNote: @@@lang:en @@@@: This method is different from Perl special purpose method. \ An warning in this method might mean some method puts an into a list of nodes. @IntMethod: @@Name: importTree @@Description: @@@lang:en @@@@: Changes the tree identifier of the nodes belong to another tree to be same as this node's tree identifier. @@Param: @@@Name: node @@@Type: ManakaiDOM:ManakaiDOMNodeObject @@@Description: @@@@lang:en @@@@@: Any node from the tree to change its identifier. @@Return: @@@PerlDef: unless ($node->{} eq $self->{}) { my @node = ($node); NODES: while (my $node = shift @node) { next unless ref $node eq ; my @n; for my $p (@{$node->{}}) { if (ref $node->{$p} eq 'ARRAY') { push @n, @{$node->{$p}}; } elsif (ref $node->{$p} eq 'HASH') { push @n, values %{$node->{$p}}; } } for my $p (@n, map {$node->{$_}} @{$node->{}}) { if (ref $p eq 'ARRAY') { push @node, grep {ref $_ eq and $_->{} ne $self->{}} @$p; } elsif (ref $p eq 'HASH') { push @node, grep {ref $_ eq and $_->{} ne $self->{}} values %$p; } } for my $p (@{$node->{}}, \ @{$node->{}}) { push @node, $node->{$p} if defined $node->{$p} and $node->{$p}->{} ne $self->{}; } $node->{} = $self->{}; } } @IntMethod: @@Name: changeTreeID @@Description: @@@lang:en @@@@: Changes tree identifier of all nodes traversable from this node. @@Param: @@@Name: treeID @@@Type: DISPerl:String::ManakaiDOM:all @@@Description: @@@@lang:en @@@@@: The new tree identifier. @@Return: @@@PerlDef: unless ($self->{} eq $treeID) { my @node = ($self); NODES: while (my $node = shift @node) { next unless ref $node eq ; my @n; for my $p (@{$node->{}}) { if (ref $node->{$p} eq 'ARRAY') { push @n, @{$node->{$p}}; } elsif (ref $node->{$p} eq 'HASH') { push @n, values %{$node->{$p}}; } } for my $p (@n, map {$node->{$_}} @{$node->{}}) { if (ref $p eq 'ARRAY') { push @node, grep {ref $_ eq and $_->{} ne $treeID} @$p; } elsif (ref $p eq 'HASH') { push @node, grep {ref $_ eq and $_->{} ne $treeID} values %$p; } } for my $p (@{$node->{}}, \ @{$node->{}}) { push @node, $node->{$p} if defined $node->{$p} and $node->{$p}->{} ne $treeID; } $node->{} = $treeID; } } @IntMethod: @@Name: getRootNodes @@Description: @@@lang:en @@@@: Gets root nodes in the tree to which this node belongs, at level than this node. \ {NOTE:: The manakai internal tree structure may have more than one tree root node - it is a set of tree sharing their nodes rather than a single tree. In this method is defined as the nodes that have no their node. There is at least one such node by definition of the manakai tree structure. in this context means that the node is reachable by only traversing relationships from this node. \ } @@Return: @@@Type: Perl:ARRAY::ManakaiDOM:all @@@PerlDef: my %result; my @node = ($self); NODES: while (my $node = shift @node) { my $i = 0; ORIGINS: for my $o (@{$node->{}}) { next ORIGINS unless $node->{$o}; $i++; push @node, $node->{$o}; } if ($i == 0) { $result{$node->{}} = $node; } } \ @$r = (grep {defined $_->{}} values %result); @IntMethod: @@Name: isSameNode @@Description: @@@lang:en @@@@: Returns whether a node is the same as this node or not. \ {NOTE:: The sameness is different from the equality; two nodes are same iff they are same hash reference. \ } @@Operator: @@@ContentType: lang:Perl @@@@: eq @@Param: @@@Name: node @@@Type: ManakaiDOM:ManakaiDOMNodeObject @@@Description: @@@@lang:en @@@@@: A node to compare with. @@Return: @@@Type: DISPerl:Boolean::ManakaiDOM:all @@@Description: @@@@lang:en @@@@@: Whether the two nodes are same or not. @@@PerlDef: if (ref $node and UNIVERSAL::isa ($node, ) and $node->{} eq $self->{}) { $r = true; } @IntMethod: @@Name: orphanate @@Description: @@@lang:en @@@@: Notifies that this node (and its neibors if any) is no longer part of the main tree. If the new tree containing this node has been referred yet, then the tree is preserved except its tree identifier has changed. Otherwise, i.e. the tree is useless any more, then it is destructed. \ {NOTE:: Interaction on deleting a relationship from multiply organized (such as DOM tree and styled displaying tree) is less studied. This method might be modified or addition of another method(s) might be required when style sheet, XBL, or other technologies has been implemented. \ } @@Return: @@@PerlDef: if ($self->) { $self-> (); } else { $self->; } ##Class:ManakaiDOMNodeObject ## -- Public node object ClassDef: @QName: ManakaiDOM:ManakaiDOMNodeReference @Description: @@lang:en @@@: References to the node object corresponding to it. From applications' view, any node object is hidden and seems as if the node itself. @ImplNote: @@lang:en @@@: A is a blessed hash reference; currently there is a hash key defined: \ - ::: A node object () to which this is referring. @IntMethod: @@Name: destroy @@Description: @@@lang:en @@@@: Destroy this reference object. @@Operator: @@@ContentType: lang:Perl @@@@: DESTROY @@Return: @@@PerlDef: @@@@@: my $node = $self->{}; if ($node) { CORE::delete $self->{}; unless ($self->{}) { $node->{}--; unless ($node->) { $node->; } } } else { warn ref ($self) . q{->DESTROY: there is no associated }. q{node object - you have a global variable or }. qq{potential memory-leak detected\n}; } @@@@ImplNote: @@@@@lang:en @@@@@@: {P::Warning during the global destruction might mean: \ - there be a loop in the manakai internal implementation - it should be a bug. \ - there be a loop created by application, e.g. event handler containing a reference to any node belonging to the same tree. \ - there be a global variable that contains a node reference and it is not altered or ed until the global destruction. \ - or other unknown bad situation. \ } @@ImplNote: @@@lang:en @@@@: Don't override this method unintentionally - for example, inheritting would hide this method from that class, since that module defines its own destructor. ##Class:ManakaiDOMNodeReference PropDef: @QName: isWeak @enDesc: Whether a reference is weak or not. @rdfs:range: ManakaiDOM:ManakaiDONNodeReference @Type: DOMMain:boolean::ManakaiDOM:all ElementTypeBinding: @Name:PropDef @ElementType: dis:ResourceDef @ShadowContent: @@rdf:type: rdf:Property ElementTypeBinding: @Name:enDesc @ElementType: dis:Description @ShadowContent: @@lang:en ## -- Frequently used code fragments ResourceDef: @QName: ManakaiDOM:generateUniqueID @rdf:type: dis2pm:InlineCode @Description: @@lang:en @@@: Generates a global-unique opaque string. \ {NOTE:: A URI reference is generated by this code. \ } @AliasFor: @@@: ::ManakaiDOM:all @@For: !=ManakaiDOM:all @PerlDef: ( sprintf 'mid:%d.%d.%s.dom.manakai@suika.fam.cx#', time, $$, ['A'..'Z', 'a'..'z', '0'..'9']->[rand 62] . ['A'..'Z', 'a'..'z', '0'..'9']->[rand 62] . ['A'..'Z', 'a'..'z', '0'..'9']->[rand 62] . ['A'..'Z', 'a'..'z', '0'..'9']->[rand 62] . ['A'..'Z', 'a'..'z', '0'..'9']->[rand 62] ) ##ManakaiDOM:generateUniqueID ## -- lang:dis vocabulary TreeElementType: @QName: dis:GetProp @dataType: dis:TypeQName @rdfs:range: rdf:Property @Description: @@lang:en @@@: Gets the non-nodal value of a property (actualy property). TreeElementType: @QName: dis:SetProp @dataType: dis:TypeQName @rdfs:range: rdf:Property @Description: @@lang:en @@@: Sets the non-nodal value of a property (actualy property). ## -- Syntax sugar ElementTypeBinding: @Name: TreeElementType @ElementType: dis:ResourceDef @ShadowContent: @@rdf:type: DISLang:TreeElementType @@AliasFor: @@@@: ::ManakaiDOM:all @@@For: !=ManakaiDOM:all ElementTypeBinding: @Name: ClassDef @ElementType: dis:ResourceDef @ShadowContent: @@rdf:type: ManakaiDOM:Class @@AliasFor: @@@@: ::ManakaiDOM:Perl @@@For: !=ManakaiDOM:Perl @@ForCheck: ManakaiDOM:Perl ElementTypeBinding: @Name: IntMethod @ElementType: dis:ResourceDef @ShadowContent: @@rdf:type: DISLang:Method @@ManakaiDOM:isForInternal:1 ElementTypeBinding: @Name: Return @ElementType: dis:ResourceDef @ShadowContent: @@rdf:type: DISLang:MethodReturn ElementTypeBinding: @Name: Param @ElementType: dis:ResourceDef @ShadowContent: @@rdf:type: DISLang:MethodParameter ElementTypeBinding: @Name: PerlDef @ElementType: dis:Def @ShadowContent: @@ContentType: lang:Perl ElementTypeBinding: @Name: InCase @ElementType: dis:ResourceDef @ShadowContent: @@rdf:type: ManakaiDOM:InCase ## ManakaiNode.dis ends here