1 /* 2 * Copyright (c) 2013 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 #ifndef WEBRTC_MODULES_AUDIO_PROCESSING_TRANSIENT_WPD_TREE_H_ 12 #define WEBRTC_MODULES_AUDIO_PROCESSING_TRANSIENT_WPD_TREE_H_ 13 14 #include "webrtc/base/scoped_ptr.h" 15 #include "webrtc/modules/audio_processing/transient/wpd_node.h" 16 17 namespace webrtc { 18 19 // Tree of a Wavelet Packet Decomposition (WPD). 20 // 21 // The root node contains all the data provided; for each node in the tree, the 22 // left child contains the approximation coefficients extracted from the node, 23 // and the right child contains the detail coefficients. 24 // It preserves its state, so it can be multiple-called. 25 // 26 // The number of nodes in the tree will be 2 ^ levels - 1. 27 // 28 // Implementation details: Since the tree always will be a complete binary tree, 29 // it is implemented using a single linear array instead of managing the 30 // relationships in each node. For convience is better to use a array that 31 // starts in 1 (instead of 0). Taking that into account, the following formulas 32 // apply: 33 // Root node index: 1. 34 // Node(Level, Index in that level): 2 ^ Level + (Index in that level). 35 // Left Child: Current node index * 2. 36 // Right Child: Current node index * 2 + 1. 37 // Parent: Current Node Index / 2 (Integer division). 38 class WPDTree { 39 public: 40 // Creates a WPD tree using the data length and coefficients provided. 41 WPDTree(size_t data_length, 42 const float* high_pass_coefficients, 43 const float* low_pass_coefficients, 44 size_t coefficients_length, 45 int levels); 46 ~WPDTree(); 47 48 // Returns the number of nodes at any given level. NumberOfNodesAtLevel(int level)49 static int NumberOfNodesAtLevel(int level) { 50 return 1 << level; 51 } 52 53 // Returns a pointer to the node at the given level and index(of that level). 54 // Level goes from 0 to levels(). 55 // Index goes from 0 to the number of NumberOfNodesAtLevel(level) - 1. 56 // 57 // You can use the following formulas to get any node within the tree: 58 // Notation: (Level, Index of node in that level). 59 // Root node: (0/0). 60 // Left Child: (Current node level + 1, Current node index * 2). 61 // Right Child: (Current node level + 1, Current node index * 2 + 1). 62 // Parent: (Current node level - 1, Current node index / 2) (Integer division) 63 // 64 // If level or index are out of bounds the function will return NULL. 65 WPDNode* NodeAt(int level, int index); 66 67 // Updates all the nodes of the tree with the new data. |data_length| must be 68 // teh same that was used for the creation of the tree. 69 // Returns 0 if correct, and -1 otherwise. 70 int Update(const float* data, size_t data_length); 71 72 // Returns the total number of levels below the root. Root is cosidered level 73 // 0. levels()74 int levels() const { return levels_; } 75 76 // Returns the total number of nodes. num_nodes()77 int num_nodes() const { return num_nodes_; } 78 79 // Returns the total number of leaves. num_leaves()80 int num_leaves() const { return 1 << levels_; } 81 82 private: 83 size_t data_length_; 84 int levels_; 85 int num_nodes_; 86 rtc::scoped_ptr<rtc::scoped_ptr<WPDNode>[]> nodes_; 87 }; 88 89 } // namespace webrtc 90 91 #endif // WEBRTC_MODULES_AUDIO_PROCESSING_TRANSIENT_WPD_TREE_H_ 92