| HTML::Tree::AboutTrees |
HTML::Tree::AboutTrees -- article on tree-shaped data structures in Perl
# This an article, not a module.
The following article by Sean M. Burke first appeared in The Perl Journal #18 and is copyright 2000 The Perl Journal. It appears courtesy of Jon Orwant and The Perl Journal. This document may be distributed under the same terms as Perl itself.
-- Sean M. Burke
"AaaAAAaauugh! Watch out for that tree!" -- George of the Jungle theme
Perl's facility with references, combined with its automatic management of memory allocation, makes it straightforward to write programs that store data in structures of arbitrary form and complexity.
But I've noticed that many programmers, especially those who started out with more restrictive languages, seem at home with complex but uniform data structures -- N-dimensional arrays, or more struct-like things like hashes-of-arrays(-of-hashes(-of-hashes), etc.) -- but they're often uneasy with building more freeform, less tabular structures, like tree-shaped data structures.
But trees are easy to build and manage in Perl, as I'll demonstrate by showing off how the HTML::Element class manages elements in an HTML document tree, and by walking you through a from-scratch implementation of game trees. But first we need to nail down what we mean by a "tree".
My first brush with tree-shaped structures was in linguistics classes, where tree diagrams are used to describe the syntax underlying natural language sentences. After learning my way around those trees, I started to wonder -- are what I'm used to calling "trees" the same as what programmers call "trees"? So I asked lots of helpful and patient programmers how they would define a tree. Many replied with a answer in jargon that they could not really explain (understandable, since explaining things, especially defining things, is harder than people think):
-- So what is a "tree", a tree-shaped data structure?
-- A tree is a special case of an acyclic directed graph!
-- What's a "graph"?
-- Um... lines... and... you draw it... with... arcs! nodes! um...
The most helpful were folks who couldn't explain directly, but with whom I could get into a rather Socratic dialog (where I asked the half-dim half-earnest questions), often with much doodling of illustrations...
Question: so what's a tree?
Answer: A tree is a collection of nodes that are linked together in a, well, tree-like way! Like this [drawing on a napkin]:
A / \ B C / | \ D E F
Q: So what do these letters represent?
 Maybe C is a bunch of data that stores a number, maybe a hash table, maybe nothing at all besides the fact that it links to D, E, and F (which are other nodes).
Q: So what're the lines between the nodes?
A: Links. Also called "arcs". They just symbolize the fact that each node holds a list of nodes it links to.
Q: So what if I draw nodes and links, like this...
B -- E / \ / \ A C \ / E
Is that still a tree?
A: No, not at all. There's a lot of un-treelike things about that. First off, E has a link coming off of it going into nowhere. You can't have a link to nothing -- you can only link to another node. Second off, I don't know what that sideways link between B and E means...
Q: Okay, let's work our way up from something simpler. Is this a tree...?
A
A: Yes, I suppose. It's a tree of just one node.
Q: And how about...
A B A: No, you can't just have nodes floating there, unattached.
Q: Okay, I'll link A and B. How's this?
A | B
A: Yup, that's a tree. There's a node A, and a node B, and they're linked.
Q: How is that tree any different from this one...?
B | A
A: Well, in both cases A and B are linked. But it's in a different direction.
Q: Direction? What does the direction mean?
A: Well, it depends what the tree represents. If it represents a categorization, like this:
citrus / | \ orange lemon kumquat ...
then you mean to say that oranges, lemons, kumquats, etc., are a kind of citrus. But if you drew it upside down, you'd be saying, falsely, that citrus is a kind of kumquat, a kind of lemon, and a kind of orange. If the tree represented cause-and-effect (or at least what situations could follow others), or represented what's a part of what, you wouldn't want to get those backwards, either. So with the nodes you draw together on paper, one has to be over the other, so you can tell which way the relationship in the tree works.
Q: So are these two trees the same?
A A / \ / \ B C B \ C
A: Yes, although by convention we often try to line up things in the same generation, like it is in the diagram on the left.
Q: "generation"? This is a family tree?
A: No, not unless it's a family tree for just yeast cells or something else that reproduces asexually. But for sake of having lots of terms to use, we just pretend that links in the tree represent the "is a child of" relationship, instead of "is a kind of" or "is a part of", or "could result from", or whatever the real relationship is. So we get to borrow a lot of kinship words for describing trees -- B and C are "children" (or "daughters") of A; A is the "parent" (or "mother") of B and C. Node C is a "sibling" (or "sister") of node C; and so on, with terms like "descendants" (a node's children, children's children, etc.), and "generation" (all the nodes at the same "level" in the tree, i.e., are either all grandchildren of the top node, or all great-grand-children, etc.), and "lineage" or "ancestors" (parents, and parent's parents, etc., all the way to the topmost node).
So then we get to express rules in terms like "A node cannot have more than one parent", which means that this is not a valid tree:
A / \ B C \ / E
And: "A node can't be its own parent", which excludes this looped-up connection:
/\ A | \/
Or, put more generally: "A node can't be its own ancestor", which excludes the above loop, as well as the one here:
/\ Z | / | A | / \ | B C | \/
That tree is excluded because A is a child of Z, and Z is a child of C, and C is a child of A, which means A is its own great-grandparent. So this whole network can't be a tree, because it breaks the sort of meta-rule: once any node in the supposed tree breaks the rules for trees, you don't have a tree anymore.
Q: Okay, now, are these two trees the same?
A A / | \ / | \ B C D D C B
A: It depends whether you're basing your concept of trees on each node having a set (unordered list) of children, or an (ordered) list of children. It's a question of whether ordering is important for what you're doing. With my diagram of citrus types, ordering isn't important, so these tree diagrams express the same thing:
citrus / | \ orange lemon kumquat
citrus / | \ kumquat orange lemon
because it doesn't make sense to say that oranges are "before" or "after" kumquats in the whole botanical scheme of things. (Unless, of course, you are using ordering to mean something, like a degree of genetic similarity.)
But consider a tree that's a diagram of what steps are comprised in an activity, to some degree of specificity:
make tea / | \ pour infuse serve hot water / \ in cup/pot / \ add let tea sit leaves
This means that making tea consists of putting hot water in a cup or put, infusing it (which itself consists of adding tea leaves and letting it sit), then serving it -- in that order. If you serve an empty dry pot (sipping from empty cups, etc.), let it sit, add tea leaves, and pour in hot water, then what you're doing is performance art, not tea preparation:
performance art / | \ serve infuse pour / \ hot water / \ in cup/pot let add sit tea leaves
Except for my having renamed the root, this tree is the same as the making-tea tree as far as what's under what, but it differs in order, and what the tree means makes the order important.
Q: Wait -- "root"? What's a root?
A: Besides kinship terms like "mother" and "daughter", the jargon for tree parts also has terms from real-life tree parts: the part that everything else grows from is called the root; and nodes that don't have nodes attached to them (i.e., childless nodes) are called "leaves".
Q: But you've been drawing all your trees with the root at the top and leaves at the bottom.
A: Yes, but for some reason, that's the way everyone seems to think of trees. They can draw trees as above; or they can draw them sort of sideways with indenting representing what nodes are children of what:
* make tea * pour hot water in cup/pot * infuse * add tea leaves * let sit * serve
...but folks almost never seem to draw trees with the root at the bottom. So imagine it's based on spider plant in a hanging pot. Unfortunately, spider plants aren't botanically trees, they're plants; but "spider plant diagram" is rather a mouthful, so let's just call them trees.
In time, I digested all these assorted facts about programmers' ideas of trees (which turned out to be just a more general case of linguistic ideas of trees) into a single rule:
* A node is an item that contains ("is over", "is parent of", etc.) zero or more other nodes.
From this you can build up formal definitions for useful terms, like so:
* A node's descendants are defined as all its children, and all their children, and so on. Or, stated recursively: a node's descendants are all its children, and all its children's descendants. (And if it has no children, it has no descendants.)
* A node's ancestors consist of its parent, and its parent's parent, etc, up to the root. Or, recursively: a node's ancestors consist of its parent and its parent's ancestors. (If it has no parent, it has no ancestors.)
* A tree is a root node and all the root's descendants.
And you can add a proviso or two to clarify exactly what I impute to the word "other" in "other nodes":
* A node cannot contain itself, or contain any node that contains it, etc. Looking at it the other way: a node cannot be its own parent or ancestor.
* A node can be root (i.e., no other node contains it) or can be contained by only one parent; no node can be the child of two or more parents.
Add to this the idea that children are sometimes ordered, and sometimes not, and that's about all you need to know about defining what a tree is. From there it's a matter of using them.
While not all markup languages are inherently tree-like, the best-known family of markup languages, HTML, SGML, and XML, are about as tree-like as you can get. In these languages, a document consists of elements and character data in a tree structure where there is one root element, and elements can contain either other elements, or character data.
Footnote: For sake of simplicity, I'm glossing over comments (), processing instructions (<?xml version='1.0'>), and declarations (<!ELEMENT ...>, <!DOCTYPE ...>). And I'm not bothering to distinguish entity references (<, @) or CDATA sections (<![CDATA[ ...]]>) from normal text.
For example, consider this HTML document:
  <title> Blank Document! </title>   I've got  something to saaaaay  !
I've indented this to point out what nodes (elements or text items) are children of what, with each node on a line of its own.
The HTML::TreeBuilder module (in the CPAN distribution HTML-Tree) does the work of taking HTML source and building in memory the tree that the document source represents.
Footnote: it requires the HTML::Parser module, which tokenizes the source -- i.e., identifies each tag, bit of text, comment, etc.
The trees structures that it builds represent bits of text with
normal Perl scalar string values; but elements are represented with
objects -- that is, chunks of data that belong to a
class (in this case, HTML::Element), a class that provides methods
(routines) for accessing the pieces of data in each element, and
otherwise doing things with elements. (See my article in TPJ#17 for a
quick explanation of objects, the POD document perltoot
for a longer
explanation, or Damian Conway's excellent book Object-Oriented Perl
for the full story.)
Each HTML::Element object contains a number of pieces of data:
* its element name ("html", "h1", etc., accessed as $element->tag)
* a list of elements (or text segments) that it contains, if any (accessed as $element->content_list or $element->content, depending on whether you want a list, or an arrayref)
* what element, if any, contains it (accessed as $element->parent)
* and any SGML attributes that the element has,
such as lang="en-US"
, align="center"
, etc. (accessed as
$element->attr('lang'), $element->attr('center'), etc.)
So, for example, when HTML::TreeBuilder builds the tree for the above HTML document source, the object for the "body" element has these pieces of data:
* element name: "body" * nodes it contains: the string "I've got " the object for the "em" element the string "!" * its parent: the object for the "html" element * bgcolor: "#d010ff"
Now, once you have this tree of objects, almost anything you'd want to do with it starts with searching the tree for some bit of information in some element.
Accessing a piece of information in, say, a hash of hashes of hashes, is straightforward:
$password{'sean'}{'sburke1'}{'hpux'}
because you know that all data points in that structure are accessible with that syntax, but with just different keys. Now, the "em" element in the above HTML tree does happen to be accessible as the root's child #1's child #1:
$root->content->[1]->content->[1]
But with trees, you typically don't know the exact location (via
indexes) of the data you're looking for. Instead, finding what you want
will typically involve searching through the tree, seeing if every node is
the kind you want. Searching the whole tree is simple enough -- look at
a given node, and if it's not what you want, look at its children, and
so on. HTML-Tree provides several methods that do this for you, such as
find_by_tag_name
, which returns the elements (or the first element, if
called in scalar context) under a given node (typically the root) whose
tag name is whatever you specify.
For example, that "em" node can be found as:
my $that_em = $root->find_by_tag_name('em');
or as:
@ems = $root->find_by_tag_name('em'); # will only have one element for this particular tree
Now, given an HTML document of whatever structure and complexity, if you wanted to do something like change every
stuff
to
 [- stuff -]
the first step is to frame this operation in terms of what you're doing to the tree. You're changing this:
em | ...
to this:
em / | \ b ... b | | "[-" "-]"
In other words, you're finding all elements whose tag name is "em", setting its class attribute to "funky", and adding one child to the start of its content list -- a new "b" element whose content is the text string "[-" -- and one to the end of its content list -- a new "b" element whose content is the text string "-]".
Once you've got it in these terms, it's just a matter of running to the HTML::Element documentation, and coding this up with calls to the appropriate methods, like so:
use HTML::Element 1.53; use HTML::TreeBuilder 2.96; # Build the tree by parsing the document my $root = HTML::TreeBuilder->new; $root->parse_file('whatever.html'); # source file # Now make new nodes where needed foreach my $em ($root->find_by_tag_name('em')) { $em->attr('class', 'funky'); # Set that attribute # Make the two new B nodes my $new1 = HTML::Element->new('b'); my $new2 = HTML::Element->new('b'); # Give them content (they have none at first) $new1->push_content('[-'); $new2->push_content('-]'); # And put 'em in place! $em->unshift_content($new1); $em->push_content($new2); } print "\n", $root->as_HTML(), "\n";
The class HTML::Element provides just about every method I can image you needing, for manipulating trees made of HTML::Element objects. (And what it doesn't directly provide, it will give you the components to build it with.)
Theoretically, any tree is pretty much like any other tree, so you could use HTML::Element for anything you'd ever want to do with tree-arranged objects. However, as its name implies, HTML::Element is basically for HTML elements; it has lots of features that make sense only for HTML elements (like the idea that every element must have a tag-name). And it lacks some features that might be useful for general applications -- such as any sort of checking to make sure that you're not trying to arrange objects in a non-treelike way. For a general-purpose tree class that does have such features, you can use Tree::DAG_Node, also available from CPAN.
However, if your task is simple enough, you might find it overkill to bother using Tree::DAG_Node. And, in any case, I find that the best way to learn how something works is to implement it (or something like it, but simpler) yourself. So I'll here discuss how you'd implement a tree structure, without using any of the existing classes for tree nodes.
Suppose that the task at hand is to write a program that can play against a human opponent at a strategic board game (as opposed to a board game where there's an element of chance). For most such games, a "game tree" is an essential part of the program (as I will argue, below), and this will be our test case for implementing a tree structure from scratch.
For sake of simplicity, our game is not chess or backgammon, but instead a much simpler game called Alak. Alak was invented by the mathematician A. K. Dewdney, and described in his 1984 book Planiverse. The rules of Alak are simple:
Footnote: Actually, I'm describing only my interpretation of the rules Dewdney describes in Planiverse. Many other interpretations are possible.
* Alak is a two-player game played on a one-dimensional board with eleven slots on it. Each slot can hold at most one piece at a time. There's two kinds of pieces, which I represent here as "x" and "o" -- x's belong to one player (called X), o's to the other (called O).
* The initial configuration of the board is:
xxxx___oooo For sake of the article, the slots are numbered from 1 (on the left) to 11 (on the right), and X always has the first move.
* The players take turns moving. At each turn, each player can move only one piece, once. (This unlike checkers, where you move one piece per move but get to keep moving it if you jump an your opponent's piece.) A player cannot pass up on his turn. A player can move any one of his pieces to the next unoccupied slot to its right or left, which may involve jumping over occupied slots. A player cannot move a piece off the side of the board.
* If a move creates a pattern where the opponent's pieces are surrounded, on both sides, by two pieces of the mover's color (with no intervening unoccupied blank slot), then those surrounded pieces are removed from the board.
* The goal of the game is to remove all of your opponent's pieces, at which point the game ends. Removing all-but-one ends the game as well, since the opponent can't surround you with one piece, and so will always lose within a few moves anyway.
Consider, then, this rather short game where X starts:
xxxx___oooo ^ Move 1: X moves from 3 (shown with caret) to 5 (Note that any of X's pieces could move, but that the only place they could move to is 5.) xx_xx__oooo ^ Move 2: O moves from 9 to 7. xx_xx_oo_oo ^ Move 3: X moves from 4 to 6. xx__xxoo_oo ^ Move 4: O (stupidly) moves from 10 to 9. xx__xxooo_o ^ Move 5: X moves from 5 to 10, making the board "xx___xoooxo". The three o's that X just surrounded are removed. xx___x___xo O has only one piece, so has lost.
Now, move 4 could have gone quite the other way:
xx__xxoo_oo Move 4: O moves from 8 to 4, making the board "xx_oxxo__oo". The surrounded x's are removed. xx_o__o__oo ^ Move 5: X moves from 1 to 2. _xxo__o__oo ^ Move 6: O moves from 7 to 6. _xxo_o___oo ^ Move 7: X moves from 2 to 5, removing the o at 4. __x_xo___oo ...and so on.
To teach a computer program to play Alak (as player X, say), it needs to be able to look at the configuration of the board, figure out what moves it can make, and weigh the benefit or costs, immediate or eventual, of those moves.
So consider the board from just before move 3, and figure all the possible moves X could make. X has pieces in slots 1, 2, 4, and 5. The leftmost two x's (at 1 and 2) are up against the end of the board, so they can move only right. The other two x's (at 4 and 5) can move either right or left:
Starting board: xx_xx_oo_oo moving 1 to 3 gives _xxxx_oo_oo moving 2 to 3 gives x_xxx_oo_oo moving 4 to 3 gives xxx_x_oo_oo moving 5 to 3 gives xxxx__oo_oo moving 4 to 6 gives xx__xxoo_oo moving 5 to 6 gives xx_x_xoo_oo
For the computer to decide which of these is the best move to make, it needs to quantify the benefit of these moves as a number -- call that the "payoff". The payoff of a move can be figured as just the number of x pieces removed by the most recent move, minus the number of o pieces removed by the most recent move. (It so happens that the rules of the game mean that no move can delete both o's and x's, but the formula still applies.) Since none of these moves removed any pieces, all these moves have the same immediate payoff: 0.
Now, we could race ahead and write an Alak-playing program that could use the immediate payoff to decide which is the best move to make. And when there's more than one best move (as here, where all the moves are equally good), it could choose randomly between the good alternatives. This strategy is simple to implement; but it makes for a very dumb program. Consider what O's response to each of the potential moves (above) could be. Nothing immediately suggests itself for the first four possibilities (X having moved something to position 3), but either of the last two (illustrated below) are pretty perilous, because in either case O has the obvious option (which he would be foolish to pass up) of removing x's from the board:
xx_xx_oo_oo ^ X moves 4 to 6. xx__xxoo_oo ^ O moves 8 to 4, giving "xx_oxxo__oo". The two surrounded x's are removed. xx_o__o__oo
or
xx_xx_oo_oo ^ X moves 5 to 6. xx_x_xoo_oo ^ O moves 8 to 5, giving "xx_xoxo__oo". The one surrounded x is removed. xx_xo_o__oo
Both contingencies are quite bad for X -- but this is not captured by the fact that they start out with X thinking his move will be harmless, having a payoff of zero.
So what's needed is for X to think more than one step ahead -- to consider not merely what it can do in this move, and what the payoff is, but to consider what O might do in response, and the payoff of those potential moves, and so on with X's possible responses to those cases could be. All these possibilities form a game tree -- a tree where each node is a board, and its children are successors of that node -- i.e., the boards that could result from every move possible, given the parent's board.
But how to represent the tree, and how to represent the nodes?
Well, consider that a node holds several pieces of data:
1) the configuration of the board, which, being nice and simple and one-dimensional, can be stored as just a string, like "xx_xx_oo_oo".
2) whose turn it is, X or O. (Or: who moved last, from which we can figure whose turn it is).
3) the successors (child nodes).
4) the immediate payoff of having moved to this board position from its predecessor (parent node).
5) and what move gets us from our predecessor node to here. (Granted, knowing the board configuration before and after the move, it's easy to figure out the move; but it's easier still to store it as one is figuring out a node's successors.)
6) whatever else we might want to add later.
These could be stored equally well in an array or in a hash, but it's my experience that hashes are best for cases where you have more than just two or three bits of data, or especially when you might need to add new bits of data. Moreover, hash key names are mnemonic -- $node->{'last_move_payoff'} is plain as day, whereas it's not so easy having to remember with an array that $node->[3] is where you decided to keep the payoff.
Footnote: Of course, there are ways around that problem: just swear you'll never use a real numeric index to access data in the array, and instead use constants with mnemonic names:
use strict; use constant idx_PAYOFF => 3; ... $n->[idx_PAYOFF]
Or use a pseudohash. But I prefer to keep it simple, and use a hash.
These are, incidentally, the same arguments that people weigh when trying to decide whether their object-oriented modules should be based on blessed hashes, blessed arrays, or what. Essentially the only difference here is that we're not blessing our nodes or talking in terms of classes and methods.
[end footnote]
So, we might as well represent nodes like so:
$node = { # hashref 'board' => ...board string, e.g., "xx_x_xoo_oo" 'last_move_payoff' => ...payoff of the move that got us here. 'last_move_from' => ...the start... 'last_move_to' => ...and end point of the move that got us here. E.g., 5 and 6, representing a move from 5 to 6.
'whose_turn' => ...whose move it then becomes. just an 'x' or 'o'. 'successors' => ...the successors };
Note that we could have a field called something like 'last_move_who' to denote who last moved, but since turns in Alak always alternate (and no-one can pass), storing whose move it is now and who last moved is redundant -- if X last moved, it's O turn now, and vice versa. I chose to have a 'whose_turn' field instead of a 'last_move_who', but it doesn't really matter. Either way, we'll end up inferring one from the other at several points in the program.
When we want to store the successors of a node, should we use an array or a hash? On the one hand, the successors to $node aren't essentially ordered, so there's no reason to use an array per se; on the other hand, if we used a hash, with successor nodes as values, we don't have anything particularly meaningful to use as keys. (And we can't use the successors themselves as keys, since the nodes are referred to by hash references, and you can't use a reference as a hash key.) Given no particularly compelling reason to do otherwise, I choose to just use an array to store all a node's successors, although the order is never actually used for anything:
$node = { ... 'successors' => [ ...nodes... ], ... };
In any case, now that we've settled on what should be in a node, let's make a little sample tree out of a few nodes and see what we can do with it:
# Board just before move 3 in above game my $n0 = { 'board' => 'xx_xx_oo_oo', 'last_move_payoff' => 0, 'last_move_from' => 9, 'last_move_to' => 7, 'whose_turn' => 'x', 'successors' => [], };
# And, for now, just two of the successors: # X moves 4 to 6, giving xx__xxoo_oo my $n1 = { 'board' => 'xx__xxoo_oo', 'last_move_payoff' => 0, 'last_move_from' => 4, 'last_move_to' => 6, 'whose_turn' => 'o', 'successors' => [], };
# or X moves 5 to 6, giving xx_x_xoo_oo my $n2 = { 'board' => 'xx_x_xoo_oo', 'last_move_payoff' => 0, 'last_move_from' => 5, 'last_move_to' => 6, 'whose_turn' => 'o', 'successors' => [], };
# Now connect them... push @{$n0->{'successors'}}, $n1, $n2;
In comparing what we store in an Alak game tree node to what HTML::Element stores in HTML element nodes, you'll note one big difference: every HTML::Element node contains a link to its parent, whereas we don't have our Alak nodes keeping a link to theirs.
The reason this can be an important difference is because it can affect how Perl knows when you're not using pieces of memory anymore. Consider the tree we just built, above:
node 0 / \ node 1 node 2
There's two ways Perl knows you're using a piece of memory:
1) it's memory that belongs directly to a variable (i.e., is necessary
to hold that variable's value, or values in the case of a hash or
array), or 2) it's a piece of memory that something holds a reference
to. In the above code, Perl knows that the hash for node 0 (for board
"xx_xx_oo_oo") is in use because something (namely, the variable
$n0
) holds a reference to it. Now, even if you followed the above
code with this:
$n1 = $n2 = 'whatever';
to make your variables $n1
and $n2
stop holding references to
the hashes for the two successors of node 0, Perl would still know that
those hashes are still in use, because node 0's successors array holds
a reference to those hashes. And Perl knows that node 0 is still in
use because something still holds a reference to it. Now, if you
added:
my $root = $n0;
This would change nothing -- there's just be two things holding a reference to the node 0 hash, which in turn holds a reference to the node 1 and node 2 hashes. And if you then added:
$n0 = 'stuff';
still nothing would change, because something ($root
) still holds a
reference to the node 0 hash. But once nothing holds a reference to
the node 0 hash, Perl will know it can destroy that hash (and reclaim
the memory for later use, say), and once it does that, nothing will hold
a reference to the node 1 or the node 2 hashes, and those will be
destroyed too.
But consider if the node 1 and node 2 hashes each had an attribute "parent" (or "predecessor") that held a reference to node 0. If your program stopped holding a reference to the node 0 hash, Perl could not then say that nothing holds a reference to node 0 -- because node 1 and node 2 still do. So, the memory for nodes 0, 1, and 2 would never get reclaimed (until your program ended, at which point Perl destroys everything). If your program grew and discarded lots of nodes in the game tree, but didn't let Perl know it could reclaim their memory, your program could grow to use immense amounts of memory -- never a nice thing to have happen. There's three ways around this:
1) When you're finished with a node, delete the reference each of its children have to it (in this case, deleting $n1->{'parent'}, say). When you're finished with a whole tree, just go through the whole tree erasing links that children have to their children.
2) Reconsider whether you really need to have each node hold a reference to its parent. Just not having those links will avoid the whole problem.
3) use the WeakRef module with Perl 5.6 or later. This allows you to "weaken" some references (like the references that node 1 and 2 could hold to their parent) so that they don't count when Perl goes asking whether anything holds a reference to a given piece of memory. This wonderful new module eliminates the headaches that can often crop up with either of the two previous methods.
It so happens that our Alak program is simple enough that we don't need for our nodes to have links to their parents, so the second solution is fine. But in a more advanced program, the first or third solutions might be unavoidable.
I don't like working blind -- if I have any kind of a complex data
structure in memory for a program I'm working on, the first thing I do
is write something that can dump that structure to the screen so I can
make sure that what I think is in memory really is what's in
memory. Now, I could just use the "x" pretty-printer command in Perl's
interactive debugger, or I could have the program use the
Data::Dumper
module. But in this case, I think the output from those
is rather too verbose. Once we have trees with dozens of nodes in them,
we'll really want a dump of the tree to be as concise as possible,
hopefully just one line per node. What I'd like is something that can
print $n0
and its successors (see above) as something like:
xx_xx_oo_oo (O moved 9 to 7, 0 payoff) xx__xxoo_oo (X moved 4 to 6, 0 payoff) xx_x_xoo_oo (X moved 5 to 6, 0 payoff)
A subroutine to print a line for a given node, and then do that again for each successor, would look something like:
sub dump_tree { my $n = $_[0]; # "n" is for node print ...something expressing $n'n content... foreach my $s (@{$n->{'successors'}}) { # "s for successor dump($s); } }
And we could just start that out with a call to dump_tree($n0)
.
Since this routine...
Footnote:
I first wrote this routine starting out with "sub dump {". But when
I tried actually calling dump($n0)
, Perl would dump core! Imagine
my shock when I discovered that this is absolutely to be expected --
Perl provides a built-in function called dump
, the purpose of which
is to, yes, make Perl dump core. Calling our routine "dump_tree"
instead of "dump" neatly avoids that problem.
...does its work (dumping the subtree at and under the given node) by calling itself, it's recursive. However, there's a special term for this kind of recursion across a tree: traversal. To traverse a tree means to do something to a node, and to traverse its children. There's two prototypical ways to do this, depending on what happens when:
traversing X in pre-order: * do something to X * then traverse X's children
traversing X in post-order: * traverse X's children * then do something to X
Dumping the tree to the screen the way we want it happens to be a matter of pre-order traversal, since the thing we do (print a description of the node) happens before we recurse into the successors.
When we try writing the print
statement for our above dump_tree
,
we can get something like:
sub dump_tree { my $n = $_[0];
# "xx_xx_oo_oo (O moved 9 to 7, 0 payoff)" print $n->{'board'}, " (", ($n->{'whose_turn'} eq 'o' ? 'X' : 'O'), # Infer who last moved from whose turn it is now. " moved ", $n->{'last_move_from'}, " to ", $n->{'last_move_to'}, ", ", $n->{'last_move_payoff'}, " payoff)\n", ;
foreach my $s (@{$n->{'successors'}}) { dump_tree($s); } }
If we run this on $n0 from above, we get this:
xx_xx_oo_oo (O moved 9 to 7, 0 payoff) xx__xxoo_oo (X moved 4 to 6, 0 payoff) xx_x_xoo_oo (X moved 5 to 6, 0 payoff)
Each line on its own is fine, but we forget to allow for indenting, and
without that we can't tell what's a child of what. (Imagine if the
first successor had successors of its own -- you wouldn't be able to
tell if it were a child, or a sibling.) To get indenting, we'll need
to have the instances of the dump_tree
routine know how far down in
the tree they're being called, by passing a depth parameter between
them:
sub dump_tree { my $n = $_[0]; my $depth = $_[1]; $depth = 0 unless defined $depth; print " " x $depth, ...stuff... foreach my $s (@{$n->{'successors'}}) { dump_tree($s, $depth + 1); } }
When we call dump_tree($n0)
, $depth
(from $_[1]
) is undefined, so
gets set to 0, which translates into an indenting of no spaces. But when
dump_tree
invokes itself on $n0
's children, those instances see
$depth
+ 1 as their $_[1]
, giving appropriate indenting.
Footnote:
Passing values around between different invocations of a recursive
routine, as shown, is a decent way to share the data. Another way
to share the data is by keeping it in a global variable, like $Depth
,
initially set to 0. Each time dump_tree
is about to recurse, it must
++$Depth
, and when it's back, it must --$Depth
.
Or, if the reader is familiar with closures, consider this approach:
sub dump_tree { # A wrapper around calls to a recursive closure: my $start_node = $_[0]; my $depth = 0; # to be shared across calls to $recursor. my $recursor; $recursor = sub { my $n = $_[0]; print " " x $depth, ...stuff... ++$depth; foreach my $s (@{$n->{'successors'}}) { $recursor->($s); } --$depth; } $recursor->($start_node); # start recursing undef $recursor; }
The reader with an advanced understanding of Perl's reference-count-based garbage collection is invited to consider why it is currently necessary to undef $recursor (or otherwise change its value) after all recursion is done.
The reader whose mind is perverse in other ways is invited to consider
how (or when!) passing a depth parameter around is unnecessary because
of information that Perl's caller(N)
function reports!
[end footnote]
Our dump_tree
routine works fine for the sample tree we've got, so
now we should get the program working on making its own trees, starting
from a given board.
In Games::Alak
(the CPAN-released version of Alak that uses
essentially the same code that we're currently discussing the
tree-related parts of), there is a routine called figure_successors
that, given one childless node, will figure out all its possible
successors. That is, it looks at the current board, looks at every piece
belonging to the player whose turn it is, and considers the effect of
moving each piece every possible way -- notably, it figures out the
immediate payoff, and if that move would end the game, it notes that by
setting an "endgame" entry in that node's hash. (That way, we know that
that's a node that can't have successors.)
In the code for Games::Alak
, figure_successors
does all these things,
in a rather straightforward way. I won't walk you through the details
of the figure_successors
code I've written, since the code has
nothing much to do with trees, and is all just implementation of the Alak
rules for what can move where, with what result. Especially interested
readers can puzzle over that part of code in the source listing in the
archive from CPAN, but others can just assume that it works as described
above.
But consider that figure_successors
, regardless of its inner
workings, does not grow the tree; it only makes one set of successors
for one node at a time. It has to be up to a different routine to call
figure_successors
, and to keep applying it as needed, in order to
make a nice big tree that our game-playing program can base its
decisions on.
Now, we could do this by just starting from one node, applying
figure_successors
to it, then applying figure_successors
on all
the resulting children, and so on:
sub grow { # Just a first attempt at this! my $n = $_[0]; figure_successors($n); unless @{$n->{'successors'}} # already has successors. or $n->{'endgame'} # can't have successors. } foreach my $s (@{$n->{'successors'}}) { grow($s); # recurse } }
If you have a game tree for tic-tac-toe, and you grow it without limitation (as above), you will soon enough have a fully "solved" tree, where every node that can have successors does, and all the leaves of the tree are all the possible endgames (where, in each case, the board is filled). But a game of Alak is different from tic-tac-toe, because it can, in theory, go on forever. For example, the following sequence of moves is quite possible:
xxxx___oooo xxx_x__oooo xxx_x_o_ooo xxxx__o_ooo (x moved back) xxxx___oooo (o moved back) ...repeat forever...
So if you tried using our above attempt at a grow
routine, Perl would
happily start trying to construct an infinitely deep tree, containing
an infinite number of nodes, consuming an infinite amount of memory, and
requiring an infinite amount of time. As the old saying goes: "You
can't have everything -- where would you put it?" So we have to place
limits on how much we'll grow the tree.
There's more than one way to do this:
1. We could grow the tree until we hit some limit on the number of nodes we'll allow in the tree.
2. We could grow the tree until we hit some limit on the amount of time we're willing to spend.
3. Or we could grow the tree until it is fully fleshed out to a certain depth.
Since we already know to track depth (as we did in writing dump_tree
),
we'll do it that way, the third way. The implementation for that third
approach is also pretty straightforward:
$Max_depth = 3; sub grow { my $n = $_[0]; my $depth = $_[1] || 0; figure_successors($n) unless $depth >= $Max_depth or @{$n->{'successors'}} or $n->{'endgame'} } foreach my $s (@{$n->{'successors'}}) { grow($s, $depth + 1); } # If we're at $Max_depth, then figure_successors # didn't get called, so there's no successors # to recurse under -- that's what stops recursion. }
If we start from a single node (whether it's a node for the starting board
"xxxx___oooo", or for whatever board the computer is faced with), set
$Max_depth
to 4, and apply grow
to it, it will grow the tree to
include several hundred nodes.
Footnote: If at each move there are four pieces that can move, and they can each move right or left, the "branching factor" of the tree is eight, giving a tree with 1 (depth 0) + 8 (depth 1) + 8 ** 2 + 8 ** 3 + 8 ** 4 = 4681 nodes in it. But, in practice, not all pieces can move in both directions (none of the x pieces in "xxxx___oooo" can move left, for example), and there may be fewer than four pieces, if some were lost. For example, there are 801 nodes in a tree of depth four starting from "xxxx___oooo", suggesting an average branching factor of about five (801 ** (1/4) is about 5.3), not eight.
What we need to derive from that tree is the information about what are the best moves for X. The simplest way to consider the payoff of different successors is to just average them -- but what we average isn't always their immediate payoffs (because that'd leave us using only one generation of information), but the average payoff of their successors, if any. We can formalize this as:
To figure a node's average payoff: If the node has successors: Figure each successor's average payoff. My average payoff is the average of theirs. Otherwise: My average payoff is my immediate payoff.
Since this involves recursing into the successors before doing anything with the current node, this will traverse the tree in post-order.
We could work that up as a routine of its own, and apply that to the
tree after we've applied grow
to it. But since we'd never
grow the tree without also figuring the average benefit, we might as well
make that figuring part of the grow
routine itself:
$Max_depth = 3; sub grow { my $n = $_[0]; my $depth = $_[1] || 0; figure_successors($n); unless $depth >= $Max_depth or @{$n->{'successors'}} or $n->{'endgame'} }
if(@{$n->{'successors'}}) { my $a_payoff_sum = 0; foreach my $s (@{$n->{'successors'}}) { grow($s, $depth + 1); # RECURSE $a_payoff_sum += $s->{'average_payoff'}; } $n->{'average_payoff'} = $a_payoff_sum / @{$n->{'successors'}}; } else { $n->{'average_payoff'} = $n->{'last_move_payoff'}; } }
So, by time grow
has applied to a node (wherever in the tree it is),
it will have figured successors if possible (which, in turn, sets
last_move_payoff
for each node it creates), and will have set
average_benefit
.
Beyond this, all that's needed is to start the board out with a root
note of "xxxx___oooo", and have the computer (X) take turns with the
user (O) until someone wins. Whenever it's O's turn, Games::Alak
presents a prompt to the user, letting him know the state of the current
board, and asking what move he selects. When it's X's turn, the
computer grows the game tree as necessary (using just the grow
routine from above), then selects the move with the highest average
payoff (or one of the highest, in case of a tie).
In either case, "selecting" a move means just setting that move's node as the new root of the program's game tree. Its sibling nodes and their descendants (the boards that didn't get selected) and its parent node will be erased from memory, since they will no longer be in use (as Perl can tell by the fact that nothing holds references to them anymore).
The interface code in Games::Alak
(the code that prompts the user for
his move) actually supports quite a few options besides just moving --
including dumping the game tree to a specified depth (using a slightly
fancier version of dump_tree
, above), resetting the game, changing
$Max_depth
in the middle of the game, and quitting the game. Like
figure_successors
, it's a bit too long to print here, but interested
users are welcome to peruse (and freely modify) the code, as well as to
enjoy just playing the game.
Now, in practice, there's more to game trees than this: for games with a larger branching factor than Alak has (which is most!), game trees of depth four or larger would contain too many nodes to be manageable, most of those nodes being strategically quite uninteresting for either player; dealing with game trees specifically is therefore a matter of recognizing uninteresting contingencies and not bothering to grow the tree under them.
Footnote: For example, to choose a straightforward case: if O has a choice between moves that put him in immediate danger of X winning and moves that don't, then O won't ever choose the dangerous moves (and if he does, the computer will know enough to end the game), so there's no point in growing the tree any further beneath those nodes.
But this sample implementation should illustrate the basics of how to build and manipulate a simple tree structure in memory. And once you've understood the basics of tree storage here, you should be ready to better understand the complexities and peculiarities of other systems for creating, accessing, and changing trees, including Tree::DAG_Node, HTML::Element, XML::DOM, or related formalisms like XPath and XSL.
[end body of article]
Sean M. Burke<EMAIL_ADDRESS>) is a tree-dwelling hominid.
Dewdney, A[lexander] K[eewatin]. 1984. Planiverse: Computer Contact with a Two-Dimensional World. Poseidon Press, New York.
Knuth, Donald Ervin. 1997. Art of Computer Programming, Volume 1, Third Edition: Fundamental Algorithms. Addison-Wesley, Reading, MA.
Wirth, Niklaus. 1976. Algorithms + Data Structures = Programs Prentice-Hall, Englewood Cliffs, NJ.
Worth, Stan and Allman Sheldon. Circa 1967. George of the Jungle theme. [music by Jay Ward.]
Wirth's classic, currently and lamentably out of print, has a good
section on trees. I find it clearer than Knuth's (if not quite as
encyclopedic), probably because Wirth's example code is in a
block-structured high-level language (basically Pascal), instead
of in assembler (MIX). I believe the book was re-issued in the
1980s under the titles Algorithms and Data Structures and, in a
German edition, Algorithmen und Datenstrukturen. Cheap copies
of these editions should be available through used book services
such as abebooks.com
.
Worth's classic, however, is available on the soundtrack to the 1997 George of the Jungle movie, as performed by The Presidents of the United States of America.
Return to the HTML::Tree docs.
| HTML::Tree::AboutTrees |


|
VirtualSCADA
1.0
VirtualSCADA Senior Design Project
|
Public Member Functions | |
| __construct () | |
| leaveNode (Node $node) | |
| Public Member Functions inherited from NamespaceAwarePass | |
| beforeTraverse (array $nodes) | |
| enterNode (Node $node) | |
| Public Member Functions inherited from NodeVisitorAbstract | |
| beforeTraverse (array $nodes) | |
| enterNode (Node $node) | |
| leaveNode (Node $node) | |
| afterTraverse (array $nodes) | |
Data Fields | |
| const | CLASS_TYPE = 'class' |
| const | INTERFACE_TYPE = 'interface' |
| const | TRAIT_TYPE = 'trait' |
Protected Member Functions | |
| validateClassStatement (ClassStmt $stmt) | |
| validateInterfaceStatement (InterfaceStmt $stmt) | |
| validateTraitStatement (TraitStmt $stmt) | |
| validateNewExpression (NewExpr $stmt) | |
| validateClassConstFetchExpression (ClassConstFetch $stmt) | |
| validateStaticCallExpression (StaticCall $stmt) | |
| ensureCanDefine (Stmt $stmt) | |
| ensureClassExists ($name, $stmt) | |
| ensureMethodExists ($class, $name, $stmt) | |
| getScopeType (Stmt $stmt) | |
| classExists ($name) | |
| interfaceExists ($name) | |
| traitExists ($name) | |
| findInScope ($name) | |
| createError ($msg, $stmt) | |
| Protected Member Functions inherited from NamespaceAwarePass | |
| getFullyQualifiedName ($name) | |
Protected Attributes | |
| $checkTraits | |
| Protected Attributes inherited from NamespaceAwarePass | |
| $namespace | |
| $currentScope | |
Validate that classes exist.
This pass throws a FatalErrorException rather than letting PHP run headfirst into a real fatal error and die.
Definition at line 31 of file ValidClassNamePass.php.
| __construct | ( | ) |
Definition at line 39 of file ValidClassNamePass.php.
|
protected |
Check whether a class exists, or has been defined in the current code snippet.
| string | $name |
Definition at line 258 of file ValidClassNamePass.php.
|
protected |
Error creation factory.
| string | $msg | |
| Stmt | $stmt |
Definition at line 310 of file ValidClassNamePass.php.
|
protected |
Ensure that no class, interface or trait name collides with a new definition.
| FatalErrorException |
| Stmt | $stmt |
Definition at line 153 of file ValidClassNamePass.php.
|
protected |
Ensure that a referenced class exists.
| FatalErrorException |
| string | $name | |
| Stmt | $stmt |
Definition at line 184 of file ValidClassNamePass.php.
|
protected |
Ensure that a statically called method exists.
| FatalErrorException |
| string | $class | |
| string | $name | |
| Stmt | $stmt |
Definition at line 200 of file ValidClassNamePass.php.
|
protected |
Find a symbol in the current code snippet scope.
| string | $name |
Definition at line 294 of file ValidClassNamePass.php.
|
protected |
Get a symbol type key for storing in the scope name cache.
| Stmt | $stmt |
Definition at line 240 of file ValidClassNamePass.php.
|
protected |
Check whether an interface exists, or has been defined in the current code snippet.
| string | $name |
Definition at line 270 of file ValidClassNamePass.php.
| leaveNode | ( | Node | $node | ) |
Validate class, interface and trait statements, and new
expressions.
| FatalErrorException | if a class, interface or trait is referenced which does not exist. |
| FatalErrorException | if a class extends something that is not a class. |
| FatalErrorException | if a class implements something that is not an interface. |
| FatalErrorException | if an interface extends something that is not an interface. |
| FatalErrorException | if a class, interface or trait redefines an existing class, interface or trait name. |
| Node | $node |
Implements NodeVisitor.
Definition at line 55 of file ValidClassNamePass.php.
|
protected |
Check whether a trait exists, or has been defined in the current code snippet.
| string | $name |
Definition at line 282 of file ValidClassNamePass.php.
|
protected |
Validate a class constant fetch expression's class.
| ClassConstFetch | $stmt |
Definition at line 125 of file ValidClassNamePass.php.
|
protected |
Validate a class definition statement.
| ClassStmt | $stmt |
Definition at line 77 of file ValidClassNamePass.php.
|
protected |
Validate an interface definition statement.
| InterfaceStmt | $stmt |
Definition at line 91 of file ValidClassNamePass.php.
|
protected |
Validate a new
expression.
| NewExpr | $stmt |
Definition at line 112 of file ValidClassNamePass.php.
|
protected |
Validate a class constant fetch expression's class.
| StaticCall | $stmt |
Definition at line 138 of file ValidClassNamePass.php.
|
protected |
Validate a trait definition statement.
| TraitStmt | $stmt |
Definition at line 102 of file ValidClassNamePass.php.
|
protected |
Definition at line 37 of file ValidClassNamePass.php.
| const CLASS_TYPE = 'class' |
Definition at line 33 of file ValidClassNamePass.php.
| const INTERFACE_TYPE = 'interface' |
Definition at line 34 of file ValidClassNamePass.php.
| const TRAIT_TYPE = 'trait' |
Definition at line 35 of file ValidClassNamePass.php.


Choose a playlist
Loading...
← Choose a playlist
Correct!
Nope!
artist
–
track
from
album
Next round


Hi, I'm Ogbonnaya Chimdimma Ngwu
I'm a senior majoring in Software Engineering at Florida Institute of Technology. As a Software Engineer, I'm interested in the fields of security, quality assurance and artificial intelligence. Currently working on CryptoArb (a cryptocurency arbitragin software), I focus on front end delevopment, data analysis and UI design for the CryptoArb project. In my free time, I enjoy programming and light reading.


Smart
Bartender
Drink List
Ingredient List
Pump Config
Settings
About
Random
Boozy
Sweet
Acidic
Welcome to Smart Bartender!
Select a Drink or another option
Make It!
Make It A Double!
Info


Week 3
The main topic this week is building map-based apps backed by realtime data.
Team Learning
Teaming
We will make new teaming arrangements this week. Thank your current teammates
for their contributions during the past two weeks. Say hello to your new teammates.
Objective
Designing and building a parking app for the city of San Francisco.
Resources
Due
Friday @ 11:59pm, 1/29/2016
Requirements
- [ ] There should be a page providing a list view of all the garages and
their current statuses (garages.html).
- Nicely display and organize key information about each garage using
a styling toolkit (e.g., materializecss or something similar).
- [ ] There should be a page providing a map view of all the garage sand
their current statuses (garages_map.html).
- Use a combination of the sizes, colors, and types of markers, and text labels to visualize
important information such as the number of open parking spaces, cost …etc.
- [ ] There should be an index page that serves as a landing page to these
two pages (index.html).
- [ ] The information on these two pages should be updated / refreshed in realtime.
Individual Learning
Objective
Add a My Favorite Cities that will display the
weather of the five major US cities that are your favorites.
Resources
Due
Sunday @ 11:59pm, 1/31/2016
Requirements
- [ ] On the cities page (cities.html), show FIVE of your favorite cities’ weather information.
- [ ] For each city, show the weather details of this city as an item inside
<div id="cities">
. Provide as much useful weather information as possible. It must look nice.
- [ ] For each city, show a marker to indicate the location of this city on the
US map. Use colors, symbols, or sizes to visualize its current weather.
- [ ] The information on the cities page should get refreshed automatically
in realtime when there’s an update. Hint: You may need to add
markersLayerGroup.clearLayers()
somewhere to clear all the markers before redrawing the markers.
Submission
- Commit/Push your source code to Github.
- Deploy your resume app to Firebase


Sufi Views
Toggle navigation
Home
video
Prophet
news
Forum
Faq
Twitter
Facebook
Dribbble
Google+
Home
Single
Sufi Views Video
Up Next
Nullam interdum metus
John Maniya
2,114,200 views
Nullam interdum metus
John Maniya
2,114,200 views
Nullam interdum metus
John Maniya
2,114,200 views
Nullam interdum metus
John Maniya
2,114,200 views
Nullam interdum metus
John Maniya
2,114,200 views
Nullam interdum metus
John Maniya
2,114,200 views
Nullam interdum metus
By
John Maniya
2,114,200 views
Nullam interdum metus
By
John Maniya
2,114,200 views
Citizen Soldier
2016
NEW
X-Men
2016
NEW
Greater
2016
NEW
Light B/t Oceans
2016
NEW
The BFG
2016
NEW
Central Intelligence
2016
NEW
Don't Think Twice
2016
NEW
Peter
2016
NEW
God’s Compass
2016
NEW


|
iDreamSky Game Engine
v1.0.0
|
#include <Material.h>
公開方法(Public Methods) | |
| ShaderState () | |
| ShaderState Constructor. 更多... | |
| virtual | ~ShaderState () |
| ShaderState Destructor. 更多... | |
| ShaderState (Material::ShaderState &other) | |
| Copy Constructor. 更多... | |
| Material::ShaderState & | operator= (const Material::ShaderState &other) |
| Assigned operator. 更多... | |
| GXShaderProgram & | getShaderProgram () |
| int | getNumSamplerStates () const |
| int | getSamplerStateIdx (const char *name_) const |
| Material::SamplerState & | getSamplerState (int i) |
| const char * | getSamplerStateName (int i_) const |
| int | getNumUniforms () const |
| int | getUniformIdx (const char *name_) const |
| GXUniform & | getUniform (int i) |
| const char * | getUniformName (int i_) const |
| void | apply () |
| apply all the RenderStates of this RenderStates | |
| void | restore () |
| restore all the RenderState of this RenderStates | |
| void | read (InputStream &is) |
| void | write (OutputStream &os) const |
類別朋友(Friends) | |
| class | Material |
| class | Material::Resource |
| class | Material::ResourceImporter |
ShaderState. This is the ShaderState, Uniform Information of this ShaderState
| Material::ShaderState::ShaderState | ( | ) |
ShaderState Constructor.
To Construct the ShaderState for the Material.
|
virtual |
ShaderState Destructor.
To Destruct ShaderState.
| IDreamSky::Material::ShaderState::ShaderState | ( | Material::ShaderState & | other | ) |
Copy Constructor.
| Material::ShaderState & Material::ShaderState::operator= | ( | const Material::ShaderState & | other | ) |
Assigned operator.


Stocks options
Payoff Charts
Option prices
About
This tool has been created with F#, Fable, VueJs, D3 and NVD3.


--- # @formatter:off layout: archive permalink: /about/ title: "About" excerpt: "" author_profile: true header: overlay_image: /assets/images/25241.jpg overlay_filter: 0.5 # @formatter:on ---
A software engineer from Rotterdam in the Netherlands. Currently, I'm studying Computer Science in the Technical University of Delft.


- onActivityCreated(Bundle) - Method in class com.example.booksies.controller.HomeFragment
-
It is useful for modifying UI elements.
- onActivityCreated(Bundle) - Method in class com.example.booksies.controller.RequestListFragment
-
Run on Activity created
- onActivityResult(int, int, Intent) - Method in class com.example.booksies.controller.AddBookFragment
-
Gets data from camera intent or from gallery and sets the image into imageView in AddBookFragment
- onActivityResult(int, int, Intent) - Method in class com.example.booksies.controller.EditBookActivity
-
- onActivityResult(int, int, Intent) - Method in class com.example.booksies.controller.ScanFragment
-
Run when ScannerActivity Activity returns ISBN code after scanning
- onBackPressed() - Method in class com.example.booksies.controller.MainActivity
-
Method overrides to disable device back button
- onBackPressed() - Method in class com.example.booksies.controller.NavigationActivity
-
Method overrides to disable device back button
- onBindViewHolder(BooksListAdapter.BooksListViewHolder, int) - Method in class com.example.booksies.model.adapters.BooksListAdapter
-
Bind's the view holder
- onBindViewHolder(Map_Adapter.MapAdapterViewHolder, int) - Method in class com.example.booksies.model.adapters.Map_Adapter
-
Replace the contents of a view (invoked by the layout manager)
- onBindViewHolder(RequestListAdapter.RequestListViewHolder, int) - Method in class com.example.booksies.model.adapters.RequestListAdapter
-
Replace the contents of a view (invoked by the layout manager)
- onBindViewHolder(SearchAdapter.MyViewHolder, int) - Method in class com.example.booksies.model.adapters.SearchAdapter
-
Helps to replace the contents of a view (invoked by the layout manager)
- onCreate(Bundle) - Method in class com.example.booksies.controller.EditBookActivity
-
creates activity
- onCreate(Bundle) - Method in class com.example.booksies.controller.EditUserProfileActivity
-
Inflates edit profile page
- onCreate(Bundle) - Method in class com.example.booksies.controller.MainActivity
-
This function is called when the activity is created and sets the layout
- onCreate(Bundle) - Method in class com.example.booksies.controller.NavigationActivity
-
Responsible for creating activity when first launched
- onCreate(Bundle) - Method in class com.example.booksies.controller.RegisterActivity
-
Set content view and context and set onClick Listeners for various buttons in
activity_register layout.
- onCreate(Bundle) - Method in class com.example.booksies.controller.ScannerActivity
-
Set content view and use ToneGenerator before scanning
- onCreate(Bundle) - Method in class com.example.booksies.controller.SearchActivity
-
Responsible for creating activity when first launched
- onCreate(Bundle) - Method in class com.example.booksies.controller.SetLocationActivity
-
This function is called when the activity is created and sets the layout
- onCreate(Bundle) - Method in class com.example.booksies.controller.ViewMapsActivity
-
creates the maps activity
- onCreate(Bundle) - Method in class com.example.booksies.controller.ViewPhotoActivity
-
- onCreate(Bundle) - Method in class com.example.booksies.controller.ViewProfileActivity
-
Inflates view user profile page
- onCreateOptionsMenu(Menu) - Method in class com.example.booksies.controller.NavigationActivity
-
onCreateOptionsMenu is useful for creating a new Menu.
- onCreateView(LayoutInflater, ViewGroup, Bundle) - Method in class com.example.booksies.controller.AddBookFragment
-
This function is called to show the layout and buttons of adding a book
- onCreateView(LayoutInflater, ViewGroup, Bundle) - Method in class com.example.booksies.controller.HomeFragment
-
Responsible for creating view when first launched
- onCreateView(LayoutInflater, ViewGroup, Bundle) - Method in class com.example.booksies.controller.RequestListFragment
-
Set content view and context and set onClick Listeners for various buttons in
fragment_requestlist layout.
- onCreateView(LayoutInflater, ViewGroup, Bundle) - Method in class com.example.booksies.controller.ScanFragment
-
Set content view and context and set onClick Listeners for various buttons in
activity_scan_books layout.
- onCreateView(LayoutInflater, ViewGroup, Bundle) - Method in class com.example.booksies.controller.UserProfileFragment
-
Inflates user profile page
- onCreateViewHolder(ViewGroup, int) - Method in class com.example.booksies.model.adapters.BooksListAdapter
-
Create view holder for list item
- onCreateViewHolder(ViewGroup, int) - Method in class com.example.booksies.model.adapters.Map_Adapter
-
Create new views (invoked by the layout manager)
- onCreateViewHolder(ViewGroup, int) - Method in class com.example.booksies.model.adapters.RequestListAdapter
-
Create new views (invoked by the layout manager)
- onCreateViewHolder(ViewGroup, int) - Method in class com.example.booksies.model.adapters.SearchAdapter
-
Useful for create new views (invoked by the layout manager)
- onMapReady(GoogleMap) - Method in class com.example.booksies.controller.SetLocationActivity
-
when the map is ready this function is called
- onMapReady(GoogleMap) - Method in class com.example.booksies.controller.ViewMapsActivity
-
gets the map ready
- onOptionsItemSelected(MenuItem) - Method in class com.example.booksies.controller.NavigationActivity
-
If Menu Item and in this case action_logout is selected, the instance of FirebaseAuth is
signed out and this logs out the current user and a new user can thus login.
- onPause() - Method in class com.example.booksies.controller.ScannerActivity
-
Works on pause
- onPostExecute(String) - Method in class com.example.booksies.controller.AutofillBookDescription
-
Converts results of API call in JSON to separate strings and binds to UI
- onResume() - Method in class com.example.booksies.controller.ScannerActivity
-
Works on resume
- onStart() - Method in class com.example.booksies.controller.MainActivity
-
Called when activity is started
- onSupportNavigateUp() - Method in class com.example.booksies.controller.EditUserProfileActivity
-
Go back to the previous activity
- onSupportNavigateUp() - Method in class com.example.booksies.controller.SetLocationActivity
-
Go back to whatever opened this activity
- onSupportNavigateUp() - Method in class com.example.booksies.controller.ViewMapsActivity
-
Go back to whatever opened this activity
- onSupportNavigateUp() - Method in class com.example.booksies.controller.ViewPhotoActivity
-
- onSupportNavigateUp() - Method in class com.example.booksies.controller.ViewProfileActivity
-
Go back to the previous activity
- ownerView - Variable in class com.example.booksies.model.adapters.RequestListAdapter.RequestListViewHolder
-
- ownerView - Variable in class com.example.booksies.model.adapters.SearchAdapter.MyViewHolder
-


Upload your retinal fundus images to see if you are suffering from diabetic retinopathy.
Just upload your cardiac MRI images and see if your heart is healthy.
© Credits : Deep Learning & DeploymentSweta Rani Sahu Swati Priya Smita Prakash


404 - Page not found The content you're looking for doesn't seem to exist. Read more GOLANG REST Service My First Post


Music Object Extension - Callbacks (version 1.2.0)
RELEASE DATE: 2000-12-28
|
|
|
What's New In This Version
|
UPDATE - Music Object 3.3.0 Compatibility
Changes have been made in this version of this extension to allow it to work correctly with version 3.3.0 of the core Music Object API. To avoid compatibility problems, this version of this extension should not be used with Music Object versions earlier than 3.3.0.
IMPROVEMENT - Smaller File Size
This version of this extension has been modified as necessary in order to reduce the size of its JavaScript file using Beatnik's proprietary code "scrunching" process (see the section Smaller Size JavaScript Files in the version history entry for Music Object 3.3.0).
BUG FIX - Meta Event Support
A bug was found where, unless a meta event callback handler was already registered using the onMetaEvent method, the Callback extension's addOnMetaEvent and addMetaEventHandler methods would have no effect. There is a performance optimization within Music Object that results in the player's meta event reporting mechanism being disabled when no meta event handler is registered. This optimization did not take into account the fact that meta event handlers can also be registered exclusively through the addOnMetaEvent and addMetaEventHandler methods of the Callbacks extension, bypassing the core Music Object onMetaEvent method. This bug has been fixed.
BUG FIX - No Meta Event Parameters When Using addMetaEventHandler
A bug was found where, even when a meta event callback handler was already registered using the onMetaEvent method (see previous bug) and meta event handlers added using the Callback extension's addMetaEventHandler method were being called, no meta event type and value parameters were being passed to the handlers registered using this method. This bug has been fixed.
NEW INSTANCE METHOD - addOnAudibleStateChange
The new addOnAudibleStateChange instance method lets you add an event handler to a Music Object instance's list of handlers for the onAudibleStateChange instance callback type that was introduced in Music Object version 3.3.0.
NEW INSTANCE METHOD - addOnOutputVolumeChange
The new addOnOutputVolumeChange instance method lets you add an event handler to a Music Object instance's list of handlers for the onOutputVolumeChange instance callback type that was introduced in Music Object version 3.3.0.
NEW INSTANCE METHOD - clearOnAudibleStateChange
The new clearOnAudibleStateChange instance method lets you clear a Music Object instance's list of handlers for the onAudibleStateChange instance callback type that was introduced in Music Object version 3.3.0.
NEW INSTANCE METHOD - clearOnOutputVolumeChange
The new clearOnOutputVolumeChange instance method lets you clear a Music Object instance's list of handlers for the onOutputVolumeChange instance callback type that was introduced in Music Object version 3.3.0.
NEW INSTANCE METHOD - removeOnAudibleStateChange
The new removeOnAudibleStateChange instance method lets you remove a specific callback handler (or handlers) from a Music Object instance's list of handlers for the onAudibleStateChange instance callback type that was introduced in Music Object version 3.3.0.
NEW INSTANCE METHOD - removeOnOutputVolumeChange
The new removeOnOutputVolumeChange instance method lets you remove a specific callback handler (or handlers) from a Music Object instance's list of handlers for the onOutputVolumeChange instance callback type that was introduced in Music Object version 3.3.0.
NEW STATIC METHOD - Music.removeCallbackHandlers
The new Music.removeCallbackHandlers static method lets you remove a specific callback handler (or handlers) from a specific static callback type (or types). In particular, this method is useful for removing handlers registered for the onAudioEngagedChange static callback type that was introduced in Music Object version 3.3.0, for which no dedicated static method has been provided for removing handlers.


Text Overlay
Keyboard Shortcuts
j/k
Cycle through eigenvectors.
h/l
Increase/decrease eigenvector translation scale.
g/;
Increase/decrease eigenvector rotation scale.
p
Toggle scene point visibility.
?
Toggle keyboard shortcut cheatsheet.


The NativeWindow class (org.bhavaya.ui.NativeWindow) allows a frame to be set (or unset) to be always on top. An instance of the class is obtained for each frame to be controlled. Adjustments to a frame's on-top state should only be made from the Event Dispatch Thread with a command similar to:
NativeWindow.getInstance(frame).setAlwaysOnTop(true);
There is a demo available via JavaWebStart, or if you have downloaded and extracted examples.zip it can be run with: ant ontopdemo. The source code for an example usage is also available and its API is given in the table below.
| Function | Return type | Usage |
|---|---|---|
| isLibraryLoaded | boolean | reports whether the external native library was successfully loaded |
| getInstance(Frame) | NativeWindow | returns an instance of the NativeWindow class for use with the supplied Frame |
| setAlwaysOnTop(boolean) | void | set boolean to true to cause the window to be always on top, false otherwise |
| isAlwaysOnTop() | boolean | returns true if the window is set to be always on top, false otherwise |
When using this component, it is necessary to ensure that the VM knows the location of the native library, by using an appropriately modified command line argument (see library error) similar to:
-Djava.library.path="C:/extract/location/bhavaya/lib"
(Also remember to add Bhavaya's jar files to your classpath (extract_location/bhavaya/bin/bhavaya.jar and extract_location/bhavaya/lib/log4j-1.2.15-patched.jar).)


STRATEGIC ADVISORY FOR ENTERPRISE ARCHITECTURE
MAKE THE RIGHT DECISIONS FOR THE RIGHT REASONS.
Technology enables your business to be who you are today and who you want to be in the future. Our Enterprise Architecture
provides a framework for expansion supporting the business with technology and process.
WHY REVIEW AND INVEST IN ENTERPRISE ARCHITECTURE?
IT is the backbone to every company. Access and utilization of information is critical for the success of the organization.
An understood technology stack can be modified, molded or moved to better meet the needs of the business.
Current IT systems are typically inefficient for your staff and your money. Often comprised of legacy equipment, processes, and poorly understood, many existing systems are inflexible, fragmented or duplicated.
Investment is often in the maintenance of aging systems instead of toward tactical or strategic initiatives.
DELIVERABLES
AS WE GUIDE OUR CUSTOMERS THROUGH AN ARCHITECTURE ENGAGEMENT WE PROVIDE THE FOLLOWING
DELIVERABLES.
TECHNOLOGY MAP
We help you to understand the penetration of your current technology tool set and define your future tool set. This Technology Map will help you to understand where you are and a general idea of where you are going as a technology organization.
BUSINESS INITIATIVES
We define your current Business
Initiatives helping your technology
organization understand where your
business is looking to go in the future.
ARCHITECTURE DIAGRAM
The largest deliverable from these engagements is an Architecture Diagram this will help you to bring increased visibility to your technology stacks for your organization (both inside and outside of your technology teams).
ROADMAP
The final deliverable is a Roadmap providing you with the short, medium and long term steps to move closer to your end state. This will be used to define tactical plans of achievement for your organization.


Dagbani keyboard based on US
Unshifted
shifted
See this document for all the key combinations.
©2021-2022 SIL International