perform_split.hpp
Go to the documentation of this file.
1 
16 #ifndef MLPACK_CORE_TREE_PERFORM_SPLIT_HPP
17 #define MLPACK_CORE_TREE_PERFORM_SPLIT_HPP
18 
19 namespace mlpack {
20 namespace tree {
21 namespace split {
22 
35 template<typename MatType, typename SplitType>
36 size_t PerformSplit(MatType& data,
37  const size_t begin,
38  const size_t count,
39  const typename SplitType::SplitInfo& splitInfo)
40 {
41  // This method modifies the input dataset. We loop both from the left and
42  // right sides of the points contained in this node.
43  size_t left = begin;
44  size_t right = begin + count - 1;
45 
46  // First half-iteration of the loop is out here because the termination
47  // condition is in the middle.
48  while ((left <= right) &&
49  (SplitType::AssignToLeftNode(data.col(left), splitInfo)))
50  left++;
51  while ((!SplitType::AssignToLeftNode(data.col(right), splitInfo)) &&
52  (left <= right) && (right > 0))
53  right--;
54 
55  // Shortcut for when all points are on the right.
56  if (left == right && right == 0)
57  return left;
58 
59  while (left <= right)
60  {
61  // Swap columns.
62  data.swap_cols(left, right);
63 
64  // See how many points on the left are correct. When they are correct,
65  // increase the left counter accordingly. When we encounter one that isn't
66  // correct, stop. We will switch it later.
67  while (SplitType::AssignToLeftNode(data.col(left), splitInfo) &&
68  (left <= right))
69  left++;
70 
71  // Now see how many points on the right are correct. When they are correct,
72  // decrease the right counter accordingly. When we encounter one that isn't
73  // correct, stop. We will switch it with the wrong point we found in the
74  // previous loop.
75  while ((!SplitType::AssignToLeftNode(data.col(right), splitInfo)) &&
76  (left <= right))
77  right--;
78  }
79 
80  Log::Assert(left == right + 1);
81 
82  return left;
83 }
84 
100 template<typename MatType, typename SplitType>
101 size_t PerformSplit(MatType& data,
102  const size_t begin,
103  const size_t count,
104  const typename SplitType::SplitInfo& splitInfo,
105  std::vector<size_t>& oldFromNew)
106 {
107  // This method modifies the input dataset. We loop both from the left and
108  // right sides of the points contained in this node.
109  size_t left = begin;
110  size_t right = begin + count - 1;
111 
112  // First half-iteration of the loop is out here because the termination
113  // condition is in the middle.
114  while ((left <= right) &&
115  (SplitType::AssignToLeftNode(data.col(left), splitInfo)))
116  left++;
117  while ((!SplitType::AssignToLeftNode(data.col(right), splitInfo)) &&
118  (left <= right) && (right > 0))
119  right--;
120 
121  // Shortcut for when all points are on the right.
122  if (left == right && right == 0)
123  return left;
124 
125  while (left <= right)
126  {
127  // Swap columns.
128  data.swap_cols(left, right);
129 
130  // Update the indices for what we changed.
131  size_t t = oldFromNew[left];
132  oldFromNew[left] = oldFromNew[right];
133  oldFromNew[right] = t;
134 
135  // See how many points on the left are correct. When they are correct,
136  // increase the left counter accordingly. When we encounter one that isn't
137  // correct, stop. We will switch it later.
138  while (SplitType::AssignToLeftNode(data.col(left), splitInfo) &&
139  (left <= right))
140  left++;
141 
142  // Now see how many points on the right are correct. When they are correct,
143  // decrease the right counter accordingly. When we encounter one that isn't
144  // correct, stop. We will switch it with the wrong point we found in the
145  // previous loop.
146  while ((!SplitType::AssignToLeftNode(data.col(right), splitInfo)) &&
147  (left <= right))
148  right--;
149  }
150 
151  Log::Assert(left == right + 1);
152  return left;
153 }
154 
155 } // namespace split
156 } // namespace tree
157 } // namespace mlpack
158 
159 
160 #endif // MLPACK_CORE_TREE_BINARY_SPACE_TREE_PERFORM_SPLIT_HPP
Linear algebra utility functions, generally performed on matrices or vectors.
void Assert(bool condition, const std::string &message="Assert Failed.")
Checks if the specified condition is true.
size_t PerformSplit(MatType &data, const size_t begin, const size_t count, const typename SplitType::SplitInfo &splitInfo)
This function implements the default split behavior i.e.
constexpr auto data(Container const &container) noexcept -> decltype(container.data())
Definition: iterator.hpp:79
auto count(Range &&rng, T const &value) -> enable_if_t< is_range< Range >::value, decltype(::std::count(::std::begin(::core::forward< Range >(rng)), ::std::end(::core::forward< Range >(rng)), value)) >
Definition: algorithm.hpp:225