1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
/*
* Copyright 2023 jacqueline <me@jacqueline.id.au>
*
* SPDX-License-Identifier: GPL-3.0-only
*/
#include "shuffler.hpp"
#include <algorithm>
#include <functional>
#include <memory>
#include <set>
#include <variant>
#include "bloom_filter.hpp"
#include "database.hpp"
#include "komihash.h"
#include "random.hpp"
#include "track.hpp"
static constexpr std::size_t kShufflerBufferSize = 32;
namespace playlist {
auto Shuffler::Create() -> Shuffler* {
return new Shuffler(util::sRandom,
std::make_unique<util::BloomFilter<database::TrackId>>(
[](database::TrackId id) {
return komihash(&id, sizeof(database::TrackId), 0);
}));
}
Shuffler::Shuffler(util::IRandom* random,
std::unique_ptr<util::BloomFilter<database::TrackId>> filter)
: random_(random), already_played_(std::move(filter)) {}
auto Shuffler::Current() -> std::optional<database::TrackId> {
if (shuffled_items_buffer_.empty()) {
return {};
}
return shuffled_items_buffer_.front();
}
auto Shuffler::Advance() -> std::optional<database::TrackId> {
if (shuffled_items_buffer_.empty() && !out_of_items_) {
RefillBuffer();
}
auto res = Current();
if (res) {
// Mark tracks off in the bloom filter only *after* they've been advanced
// past. This gives us the most flexibility for reshuffling when adding new
// items.
already_played_->Insert(*res);
shuffled_items_buffer_.pop_front();
}
return res;
}
auto Shuffler::Peek(std::size_t num, std::vector<database::TrackId>* out)
-> std::size_t {
if (shuffled_items_buffer_.size() < num) {
RefillBuffer();
}
for (int i = 0; i < num; i++) {
if (i >= shuffled_items_buffer_.size()) {
// We must be out of data, since the buffer didn't fill up.
return i;
}
out->push_back(shuffled_items_buffer_.at(i));
}
return num;
}
auto Shuffler::Add(Item item) -> void {
ordered_items_.push_back(item);
out_of_items_ = false;
// Empty out the buffer of already shuffled items, since we will need to
// shuffle again in order to incorporate the newly added item(s). We keep the
// current item however because we wouldn't want Add() to change the value of
// Current() unless we're completely out of items.
if (shuffled_items_buffer_.size() > 1) {
shuffled_items_buffer_.erase(shuffled_items_buffer_.begin() + 1,
shuffled_items_buffer_.end());
}
RefillBuffer();
}
auto Shuffler::Unshuffle() -> std::vector<Item> {
std::vector<Item> ret;
database::TrackId current = shuffled_items_buffer_.front();
bool has_found_current = false;
for (const Item& item : ordered_items_) {
if (!has_found_current) {
// TODO(jacqueline): *Should* this include previous items? What is the
// 'previous' button meant to do after unshuffling?
if (std::holds_alternative<database::TrackId>(item)) {
has_found_current = current == std::get<database::TrackId>(item);
} else {
auto source = std::get<std::shared_ptr<IResetableSource>>(item);
source->Reset();
has_found_current =
std::get<std::shared_ptr<IResetableSource>>(item)->AdvanceTo(
current);
}
} else {
ret.push_back(item);
}
}
return ret;
}
auto Shuffler::RefillBuffer() -> void {
// Don't waste time iterating if we know there's nothing new.
if (out_of_items_) {
return;
}
int num_to_sample = kShufflerBufferSize - shuffled_items_buffer_.size();
int resovoir_offset = shuffled_items_buffer_.size();
std::set<database::TrackId> in_buffer;
for (const database::TrackId& id : shuffled_items_buffer_) {
in_buffer.insert(id);
}
uint32_t i = 0;
auto consider_item = [&, this](const database::TrackId& item) {
if (already_played_->Contains(item) || in_buffer.contains(item)) {
return;
}
if (i < num_to_sample) {
shuffled_items_buffer_.push_back(item);
} else {
uint32_t index_to_replace = random_->RangeInclusive(0, i);
if (index_to_replace < num_to_sample) {
shuffled_items_buffer_[resovoir_offset + index_to_replace] = item;
}
}
i++;
};
for (const Item& item : ordered_items_) {
if (std::holds_alternative<database::TrackId>(item)) {
std::invoke(consider_item, std::get<database::TrackId>(item));
} else {
auto source = std::get<std::shared_ptr<IResetableSource>>(item);
source->Reset();
while (source->Advance()) {
std::invoke(consider_item, *source->Current());
}
}
}
out_of_items_ = i > num_to_sample;
// We've now got a random *selection*, but the order might be predictable
// (e.g. if there were only `num_to_sample` new items). Do a final in-memory
// shuffle.
std::random_shuffle(shuffled_items_buffer_.begin() + resovoir_offset,
shuffled_items_buffer_.end());
}
} // namespace playlist
|
