Lines Matching refs:node
42 // Huffman tree node.
43 struct Node {
44 Node() {}
46 // Creates Node from serialization leaving weight and id undefined.
47 Node(const Val& in_value, uint32_t in_left, uint32_t in_right)
72 // The queue is sorted in ascending order by weight (or by node id if
84 const uint32_t node = CreateNode();
85 MutableValueOf(node) = pair.first;
86 MutableWeightOf(node) = pair.second;
87 assert(WeightOf(node));
88 queue.push(node);
94 // We push a node at the end of each iteration, so the queue is never
101 // If the queue is empty at this point, then the last node is
125 // |root_handle| is the index of the root node.
126 HuffmanCodec(uint32_t root_handle, std::vector<Node>&& nodes) {
154 for (const Node& node : nodes_) {
158 code << node.value;
161 code << ", " << node.left << ", " << node.right << "},\n";
172 // Where w stands for the weight of the node.
180 // and optionally node weight for every leaf.
186 const uint32_t node = queue.front().first;
189 if (!RightOf(node) && !LeftOf(node)) {
190 out << ValueOf(node);
192 out << " " << WeightOf(node);
195 if (LeftOf(node))
196 queue.emplace(LeftOf(node), code + "0");
198 if (RightOf(node))
199 queue.emplace(RightOf(node), code + "1");
229 uint32_t node = root_;
231 assert(node);
233 if (!RightOf(node) && !LeftOf(node)) {
234 *val = ValueOf(node);
243 node = RightOf(node);
245 node = LeftOf(node);
253 // Returns value of the node referenced by |handle|.
254 Val ValueOf(uint32_t node) const {
255 return nodes_.at(node).value;
258 // Returns left child of |node|.
259 uint32_t LeftOf(uint32_t node) const {
260 return nodes_.at(node).left;
263 // Returns right child of |node|.
264 uint32_t RightOf(uint32_t node) const {
265 return nodes_.at(node).right;
268 // Returns weight of |node|.
269 uint32_t WeightOf(uint32_t node) const {
270 return nodes_.at(node).weight;
273 // Returns id of |node|.
274 uint32_t IdOf(uint32_t node) const {
275 return nodes_.at(node).id;
278 // Returns mutable reference to value of |node|.
279 Val& MutableValueOf(uint32_t node) {
280 assert(node);
281 return nodes_.at(node).value;
284 // Returns mutable reference to handle of left child of |node|.
285 uint32_t& MutableLeftOf(uint32_t node) {
286 assert(node);
287 return nodes_.at(node).left;
290 // Returns mutable reference to handle of right child of |node|.
291 uint32_t& MutableRightOf(uint32_t node) {
292 assert(node);
293 return nodes_.at(node).right;
296 // Returns mutable reference to weight of |node|.
297 uint32_t& MutableWeightOf(uint32_t node) {
298 return nodes_.at(node).weight;
301 // Returns mutable reference to id of |node|.
302 uint32_t& MutableIdOf(uint32_t node) {
303 return nodes_.at(node).id;
306 // Returns true if |left| has bigger weight than |right|. Node ids are
317 void PrintTreeInternal(std::ostream& out, uint32_t node, size_t depth) const {
318 if (!node)
323 if (!RightOf(node) && !LeftOf(node)) {
324 out << ValueOf(node) << std::endl;
326 if (RightOf(node)) {
329 << WeightOf(RightOf(node));
331 PrintTreeInternal(out, RightOf(node), depth + 1);
334 if (LeftOf(node)) {
338 << WeightOf(LeftOf(node));
340 PrintTreeInternal(out, LeftOf(node), depth + 1);
350 : node(in_node), bits(in_bits), depth(in_depth) {}
351 uint32_t node;
364 const uint32_t node = context.node;
369 if (!RightOf(node) && !LeftOf(node)) {
371 ValueOf(node), std::pair<uint64_t, size_t>(bits, depth));
375 if (LeftOf(node))
376 queue.emplace(LeftOf(node), bits, depth + 1);
378 if (RightOf(node))
379 queue.emplace(RightOf(node), bits | (1ULL << depth), depth + 1);
384 // Creates new Huffman tree node and stores it in the deleter array.
387 nodes_.emplace_back(Node());
396 std::vector<Node> nodes_;
403 // Next node id issued by CreateNode();
