• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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