FactorOracle.hpp
1 #pragma once
2 #include <ossia/detail/hash_map.hpp>
3 #include <ossia/detail/math.hpp>
4 #include <ossia/detail/ssize.hpp>
5 
6 #include <QDebug>
7 
8 #include <halp/controls.hpp>
9 #include <halp/meta.hpp>
10 #include <halp/midi.hpp>
11 #include <rnd/random.hpp>
12 #if !defined(NDEBUG) && !defined(_MSC_VER) && !defined(__clang__)
13 #include <debug/vector>
14 #define debug_vector_t __gnu_debug::vector
15 #else
16 #define debug_vector_t std::vector
17 #endif
18 namespace Nodes::FactorOracle
19 {
20 
21 template <typename T, T default_value>
23 {
24 public:
25  debug_vector_t<T> impl;
26 
27  T& operator[](int i_) { return (*this)[static_cast<std::size_t>(i_)]; }
28  T& operator[](std::size_t i_)
29  {
30  auto i = static_cast<std::size_t>(i_);
31  if(i < impl.size() && impl.size() != 0)
32  {
33  return impl[i];
34  }
35  impl.resize((i + 1) * 2, default_value);
36  return impl[i];
37  }
38 
39  const T& operator[](int i_) const { return (*this)[static_cast<std::size_t>(i_)]; }
40  const T& operator[](std::size_t i_) const
41  {
42  auto i = static_cast<std::size_t>(i_);
43  if(i < impl.size() && impl.size() != 0)
44  {
45  return impl[i];
46  }
47  static constexpr auto dval = default_value;
48  return dval;
49  }
50 };
51 template <typename T>
53 {
54 public:
55  debug_vector_t<T> impl;
56 
57  T& operator[](int i_) { return (*this)[static_cast<std::size_t>(i_)]; }
58  T& operator[](std::size_t i_)
59  {
60  auto i = static_cast<std::size_t>(i_);
61  if(i < impl.size() && impl.size() != 0)
62  {
63  return impl[i];
64  }
65  impl.resize((i + 1) * 2);
66  return impl[i];
67  }
68 };
69 
71 {
72 public:
73  int cur_alphabet_size = 0;
74  debug_vector_t<std::pair<int, ossia::value>> value_map;
75  FactorOracle(int sz = 0)
76  : m_forwardLink(sz + 1, debug_vector_t<int>{-1})
77  , m_rand_engine{}
78  {
79  m_sp.impl.resize(1000);
80  m_lrs.impl.resize(1000);
81  m_sp[0] = -1;
82  m_lrs[0] = 0;
83  }
84 
86  int LCS(int p1, int p2)
87  {
88  if(p2 == m_sp[p1])
89  return m_lrs[p1];
90 
91  while(m_sp[p2] != m_sp[p1])
92  p2 = m_sp[p2];
93 
94  return std::min(m_lrs[p1], m_lrs[p2]);
95  }
96 
97  void add_char(ossia::value c)
98  {
99  if(n < std::ssize(m_forwardLink) - 1)
100  {
101  m_sequence.push_back(std::move(c));
102  auto it = ossia::find_if(value_map, [&](const auto& pair) { return pair.second == c; });
103  if(it != value_map.end())
104  {
105  add_state(it->first);
106  }
107  else
108  {
109  value_map.push_back({cur_alphabet_size, m_sequence.back()});
110  add_state(cur_alphabet_size);
111  cur_alphabet_size++;
112  }
113  }
114  }
115 
116  void add_state(int c)
117  {
118  m_trans[n][c] = n + 1;
119  int p1 = n;
120  int j = m_sp[p1];
121  ++n;
122  while(j != -1 && m_trans[j][c] == -1)
123  {
124  int& m_trans_j_c = m_trans[j][c];
125  m_trans_j_c = n;
126  if(m_forwardLink[j][0] == -1)
127  {
128  m_forwardLink[j][0] = m_trans_j_c;
129  }
130  else
131  {
132  m_forwardLink[j].push_back(m_trans_j_c);
133  }
134  p1 = j;
135  j = m_sp[p1];
136  }
137  int& m_sp_n = m_sp[n];
138  m_sp_n = (j == -1 ? 0 : m_trans[j][c]);
139  m_lrs[n] = (m_sp_n == 0 ? 0 : LCS(p1, m_sp_n - 1) + 1);
140  }
141 
142  debug_vector_t<ossia::value> make_rand_sequence(float continuity, int seqSize) const
143  {
144  auto start = std::uniform_int_distribution<std::size_t>{0, m_sequence.size()}(m_rand_engine);
145  return make_sequence(continuity, start, seqSize);
146  }
147 
148  debug_vector_t<ossia::value> make_sequence(float continuity, std::size_t curState, std::size_t seqSize) const
149  {
150  if(curState > m_sequence.size())
151  {
152  qDebug() << "Le point initial de l'improvisation doit être comprise "
153  "dans la séquence";
154  return {};
155  }
156 
157  debug_vector_t<ossia::value> v;
158  v.reserve(seqSize);
159  for(std::size_t i = 0; i < seqSize; i++)
160  {
161  auto f = std::uniform_real_distribution<float>{}(m_rand_engine);
162  if(f <= continuity && curState < m_sequence.size() - 1)
163  {
164  curState++;
165  v.push_back(m_sequence[curState]);
166  }
167  else
168  {
169  do
170  {
171  int links = (curState == 0 ? 0 : 1);
172  if(m_forwardLink[curState][0] != -1)
173  {
174  links += m_forwardLink[curState].size();
175  }
176 
177  auto linkToFollow = std::uniform_int_distribution<int>{0, links - 1}(m_rand_engine);
178  if(linkToFollow == links - 1)
179  {
180  if(curState != 0)
181  {
182  curState = m_sp[curState];
183  }
184  }
185  else
186  {
187  curState = m_forwardLink[curState][linkToFollow];
188  }
189  } while(curState >= m_sequence.size());
190 
191  v.push_back(m_sequence[curState]);
192  }
193  }
194  return v;
195  }
196 
197 private:
198  int n{};
199  safe_vector<int, 0> m_sp;
200  safe_vector<int, 0> m_lrs;
201  safe_vector_simple<safe_vector<int, -1>> m_trans;
202  debug_vector_t<ossia::value> m_sequence;
203  debug_vector_t<debug_vector_t<int>> m_forwardLink;
204 
205  mutable rnd::pcg m_rand_engine;
206 };
207 
208 struct Node
209 {
210  halp_meta(name, "Factor Oracle")
211  halp_meta(c_name, "Factor Oracle")
212  halp_meta(category, "Control/Impro")
213  halp_meta(manual_url, "")
214  halp_meta(author, "Shlomo Dubnov, Ge Wang, Éric Meaux, Jean-Michaël Celerier")
215  halp_meta(description, "Factor Oracle algorithm .") // TODO cite
216  halp_meta(uuid, "d90284c0-4196-47e0-802d-7e07342029ec")
217 
218  struct
219  {
220 
221  } inputs;
222  struct
223  {
224 
225  } outputs;
226  static const constexpr auto controls = tuplet::make_tuple(Control::IntSlider{"Sequence length", 1, 64, 8});
227 
228  static const constexpr value_in value_ins[]{"in", "regen", "bang"};
229  static const constexpr value_out value_outs[]{"out"};
230 
231  struct State
232  {
233  FactorOracle oracle{64};
234  debug_vector_t<ossia::value> sequence;
235  std::size_t sequence_idx{};
236  };
237 
238  using control_policy = ossia::safe_nodes::last_tick;
239  static void run(const ossia::value_port& in, const ossia::value_port& regen, const ossia::value_port& bangs, int seq_len, ossia::value_port& out, ossia::token_request, ossia::exec_state_facade, State& self)
240  {
241  // Entrées sont dans p1
242  for(auto val : in.get_data())
243  {
244  self.oracle.add_char(val.value);
245  }
246 
247  if(!regen.get_data().empty())
248  {
249  self.sequence = self.oracle.make_rand_sequence(0.4, seq_len);
250  }
251 
252  if(!self.sequence.empty())
253  {
254  for(auto& bang : bangs.get_data())
255  {
256  self.sequence_idx = ossia::clamp<int64_t>((int64_t)self.sequence_idx, 0, (int64_t)self.sequence.size() - 1);
257  out.write_value(self.sequence[self.sequence_idx], bang.timestamp);
258  self.sequence_idx = (self.sequence_idx + 1) % self.sequence.size();
259  }
260  }
261  }
262 };
263 #undef debug_vector_t
264 }
Definition: FactorOracle.hpp:71
int LCS(int p1, int p2)
Function LCS (longest common suffix)
Definition: FactorOracle.hpp:86
Utilities for OSSIA data structures.
Definition: DeviceInterface.hpp:33
Definition: FactorOracle.hpp:209
Definition: FactorOracle.hpp:53
Definition: FactorOracle.hpp:23