Arrays

[t3h j1mb0]

Can someone clarify what the purpose of each of the three arrays is
(i.e. what is stored there, how it is stored, etc.)?
-Jimbo

[eruhk]

treeData[] contains the actual weighted nodes/leaves in the tree, and or
OptAdaptive at least should be ordered as you might expect it to be,
0-node, then by weight, with leaves coming before nodes. the lookupTable
is used to to look up character data for nodes (i think) and the
parentTable to look up parents. for OptAdaptive and i'm pretty sure
RevAdaptive, the only one you should need to use directly is treeData,
as the helper functions take care of everything else. thank god.

but dig around yourself, i'm not done yet and could very possibly be
horribly wrong.

Post by t3h j1mb0
Can someone clarify what the purpose of each of the three arrays is
(i.e. what is stored there, how it is stored, etc.)?
-Jimbo

[t3h j1mb0]

Post by eruhk
treeData[] contains the actual weighted nodes/leaves in the tree, and or
OptAdaptive at least should be ordered as you might expect it to be,
0-node, then by weight, with leaves coming before nodes. the lookupTable
is used to to look up character data for nodes (i think) and the
parentTable to look up parents. for OptAdaptive and i'm pretty sure
RevAdaptive, the only one you should need to use directly is treeData,
as the helper functions take care of everything else. thank god.
but dig around yourself, i'm not done yet and could very possibly be
horribly wrong.

Post by t3h j1mb0
Can someone clarify what the purpose of each of the three arrays is
(i.e. what is stored there, how it is stored, etc.)?
-Jimbo

One more thing...
When swapping two nodes, what is keeping track of parents/children?
-Jimbo

[Adrian Mayorga]

Look st the place() method, not sure this gives answers ur question, but it
sure doesnt hurt.

Post by t3h j1mb0
One more thing...
When swapping two nodes, what is keeping track of parents/children?
-Jimbo

[Tarun]

Post by t3h j1mb0
Can someone clarify what the purpose of each of the three arrays is
(i.e. what is stored there, how it is stored, etc.)?
-Jimbo

TreeData is the array which represents the tree, and is ordered by the
implicit numbering system, See :
http://www.cs.utexas.edu/users/whunt/project1/arraytree.pdf
Should contain weights, and character data

ParentTable is the array that lets you quickly find the parent of any
given node. You can find the node number: #n by (n/2 + 1), but that
doesnt tell you where the node is located. You'll have to traverse the
array. Instead you can store the positions of the internal nodes in the
parent table. for eg: Array position zero would hold the position of
node #0 in the TreeData.

And here's what Warren said about the lookup table:
"The lookup table lets you find blocks
quickly. So say you're looking for the leaf that corresponds to the
byte 'a'. You could scan the list, or just use the lookup table."

And here is What he said about Blocks:
"A block is implicitly a contiguous array of weightednodes that
are equivelant, meaning A.compareTo(B) == 0 for all nodes in the block.
To find the leader of a block, you simple move a pointer up in address
until you find something not equivelant to what you're comparing with,
then take one step back (you took one step to many when you found
something that wasn't in your block). The beginning fo the next block
is just the leader's address + 1"