1use crate::hnsw::{DistanceMetric, SearchResult};
13use ipfrs_core::{Cid, Error, Result};
14use parking_lot::RwLock;
15use std::collections::HashMap;
16use std::sync::Arc;
17
18#[derive(Debug, Clone)]
20pub struct FederatedConfig {
21 pub max_concurrent_queries: usize,
23 pub query_timeout_ms: u64,
25 pub privacy_preserving: bool,
27 pub privacy_noise_level: f32,
29 pub aggregation_strategy: AggregationStrategy,
31 pub normalize_scores: bool,
33}
34
35impl Default for FederatedConfig {
36 fn default() -> Self {
37 Self {
38 max_concurrent_queries: 10,
39 query_timeout_ms: 5000,
40 privacy_preserving: false,
41 privacy_noise_level: 0.0,
42 aggregation_strategy: AggregationStrategy::RankFusion,
43 normalize_scores: true,
44 }
45 }
46}
47
48#[derive(Debug, Clone, Copy, PartialEq, Eq)]
50pub enum AggregationStrategy {
51 Simple,
53 RankFusion,
55 ScoreNormalization,
57 BordaCount,
59}
60
61#[async_trait::async_trait]
63pub trait QueryableIndex: Send + Sync {
64 async fn query(&self, embedding: &[f32], k: usize) -> Result<Vec<SearchResult>>;
66
67 fn distance_metric(&self) -> DistanceMetric;
69
70 fn index_id(&self) -> String;
72
73 fn size(&self) -> usize;
75}
76
77pub struct LocalIndexAdapter {
79 index: Arc<RwLock<crate::hnsw::VectorIndex>>,
80 index_id: String,
81}
82
83impl LocalIndexAdapter {
84 pub fn new(index: Arc<RwLock<crate::hnsw::VectorIndex>>, index_id: String) -> Self {
86 Self { index, index_id }
87 }
88}
89
90#[async_trait::async_trait]
91impl QueryableIndex for LocalIndexAdapter {
92 async fn query(&self, embedding: &[f32], k: usize) -> Result<Vec<SearchResult>> {
93 let index = self.index.read();
94 let ef_search = k * 10; index.search(embedding, k, ef_search)
96 }
97
98 fn distance_metric(&self) -> DistanceMetric {
99 let index = self.index.read();
100 index.metric()
101 }
102
103 fn index_id(&self) -> String {
104 self.index_id.clone()
105 }
106
107 fn size(&self) -> usize {
108 let index = self.index.read();
109 index.len()
110 }
111}
112
113#[derive(Debug, Clone)]
115pub struct FederatedSearchResult {
116 pub cid: Cid,
118 pub score: f32,
120 pub source_index_id: String,
122 pub source_rank: usize,
124 pub source_metric: DistanceMetric,
126}
127
128pub struct FederatedQueryExecutor {
130 config: FederatedConfig,
132 indices: Arc<RwLock<HashMap<String, Arc<dyn QueryableIndex>>>>,
134 stats: Arc<RwLock<FederatedQueryStats>>,
136}
137
138#[derive(Debug, Clone, Default)]
140pub struct FederatedQueryStats {
141 pub total_queries: u64,
143 pub total_indices_queried: u64,
145 pub avg_latency_ms: f64,
147 pub avg_results_per_query: f64,
149 pub timeouts: u64,
151}
152
153impl FederatedQueryExecutor {
154 pub fn new(config: FederatedConfig) -> Self {
156 Self {
157 config,
158 indices: Arc::new(RwLock::new(HashMap::new())),
159 stats: Arc::new(RwLock::new(FederatedQueryStats::default())),
160 }
161 }
162
163 pub fn register_index(&self, index: Arc<dyn QueryableIndex>) -> Result<()> {
165 let index_id = index.index_id();
166 let mut indices = self.indices.write();
167
168 if indices.contains_key(&index_id) {
169 return Err(Error::InvalidInput(format!(
170 "Index '{}' is already registered",
171 index_id
172 )));
173 }
174
175 indices.insert(index_id.clone(), index);
176 tracing::info!("Registered index '{}' for federated queries", index_id);
177 Ok(())
178 }
179
180 pub fn unregister_index(&self, index_id: &str) -> Result<()> {
182 let mut indices = self.indices.write();
183 if indices.remove(index_id).is_some() {
184 tracing::info!("Unregistered index '{}'", index_id);
185 Ok(())
186 } else {
187 Err(Error::NotFound(format!("Index '{}' not found", index_id)))
188 }
189 }
190
191 pub async fn query(&self, embedding: &[f32], k: usize) -> Result<Vec<FederatedSearchResult>> {
193 let start = std::time::Instant::now();
194
195 let indices = {
197 let indices_lock = self.indices.read();
198 indices_lock
199 .iter()
200 .map(|(id, idx)| (id.clone(), Arc::clone(idx)))
201 .collect::<Vec<_>>()
202 };
203
204 if indices.is_empty() {
205 return Err(Error::InvalidInput(
206 "No indices registered for federated query".to_string(),
207 ));
208 }
209
210 let query_embedding = if self.config.privacy_preserving {
212 self.apply_privacy_noise(embedding)
213 } else {
214 embedding.to_vec()
215 };
216
217 let mut tasks = Vec::new();
219 for (index_id, index) in indices {
220 let query_emb = query_embedding.clone();
221 let task = tokio::spawn(async move {
222 let result = index.query(&query_emb, k).await;
223 (index_id, index.distance_metric(), result)
224 });
225 tasks.push(task);
226 }
227
228 let mut all_results = Vec::new();
230 let mut indices_queried = 0;
231 let mut timeouts = 0;
232
233 for task in tasks {
234 match tokio::time::timeout(
235 std::time::Duration::from_millis(self.config.query_timeout_ms),
236 task,
237 )
238 .await
239 {
240 Ok(Ok((index_id, metric, Ok(results)))) => {
241 indices_queried += 1;
242 for (rank, result) in results.into_iter().enumerate() {
243 all_results.push((index_id.clone(), metric, rank, result));
244 }
245 }
246 Ok(Ok((index_id, _, Err(e)))) => {
247 tracing::warn!("Query failed for index '{}': {:?}", index_id, e);
248 }
249 Ok(Err(e)) => {
250 tracing::warn!("Task panicked: {:?}", e);
251 }
252 Err(_) => {
253 timeouts += 1;
254 tracing::warn!("Query timeout for an index");
255 }
256 }
257 }
258
259 let aggregated = self.aggregate_results(all_results, k)?;
261
262 let latency = start.elapsed().as_millis() as f64;
264 self.update_stats(indices_queried, aggregated.len(), latency, timeouts);
265
266 Ok(aggregated)
267 }
268
269 pub async fn query_indices(
271 &self,
272 embedding: &[f32],
273 k: usize,
274 index_ids: &[String],
275 ) -> Result<Vec<FederatedSearchResult>> {
276 let start = std::time::Instant::now();
277
278 let indices = {
280 let indices_lock = self.indices.read();
281 index_ids
282 .iter()
283 .filter_map(|id| {
284 indices_lock
285 .get(id)
286 .map(|idx| (id.clone(), Arc::clone(idx)))
287 })
288 .collect::<Vec<_>>()
289 };
290
291 if indices.is_empty() {
292 return Err(Error::InvalidInput(
293 "None of the requested indices are registered".to_string(),
294 ));
295 }
296
297 let query_embedding = if self.config.privacy_preserving {
299 self.apply_privacy_noise(embedding)
300 } else {
301 embedding.to_vec()
302 };
303
304 let mut tasks = Vec::new();
306 for (index_id, index) in indices {
307 let query_emb = query_embedding.clone();
308 let task = tokio::spawn(async move {
309 let result = index.query(&query_emb, k).await;
310 (index_id, index.distance_metric(), result)
311 });
312 tasks.push(task);
313 }
314
315 let mut all_results = Vec::new();
317 let mut indices_queried = 0;
318 let mut timeouts = 0;
319
320 for task in tasks {
321 match tokio::time::timeout(
322 std::time::Duration::from_millis(self.config.query_timeout_ms),
323 task,
324 )
325 .await
326 {
327 Ok(Ok((index_id, metric, Ok(results)))) => {
328 indices_queried += 1;
329 for (rank, result) in results.into_iter().enumerate() {
330 all_results.push((index_id.clone(), metric, rank, result));
331 }
332 }
333 Ok(Ok((index_id, _, Err(e)))) => {
334 tracing::warn!("Query failed for index '{}': {:?}", index_id, e);
335 }
336 Ok(Err(e)) => {
337 tracing::warn!("Task panicked: {:?}", e);
338 }
339 Err(_) => {
340 timeouts += 1;
341 tracing::warn!("Query timeout for an index");
342 }
343 }
344 }
345
346 let aggregated = self.aggregate_results(all_results, k)?;
347
348 let latency = start.elapsed().as_millis() as f64;
349 self.update_stats(indices_queried, aggregated.len(), latency, timeouts);
350
351 Ok(aggregated)
352 }
353
354 fn apply_privacy_noise(&self, embedding: &[f32]) -> Vec<f32> {
356 use rand::RngExt;
357 let mut rng = rand::rng();
358
359 embedding
360 .iter()
361 .map(|&x| {
362 let noise = rng.random_range(
363 -self.config.privacy_noise_level..self.config.privacy_noise_level,
364 );
365 x + noise
366 })
367 .collect()
368 }
369
370 fn aggregate_results(
372 &self,
373 results: Vec<(String, DistanceMetric, usize, SearchResult)>,
374 k: usize,
375 ) -> Result<Vec<FederatedSearchResult>> {
376 match self.config.aggregation_strategy {
377 AggregationStrategy::Simple => self.aggregate_simple(results, k),
378 AggregationStrategy::RankFusion => self.aggregate_rank_fusion(results, k),
379 AggregationStrategy::ScoreNormalization => {
380 self.aggregate_score_normalization(results, k)
381 }
382 AggregationStrategy::BordaCount => self.aggregate_borda_count(results, k),
383 }
384 }
385
386 fn aggregate_simple(
388 &self,
389 results: Vec<(String, DistanceMetric, usize, SearchResult)>,
390 k: usize,
391 ) -> Result<Vec<FederatedSearchResult>> {
392 let mut federated: Vec<_> = results
393 .into_iter()
394 .map(|(index_id, metric, rank, result)| FederatedSearchResult {
395 cid: result.cid,
396 score: result.score,
397 source_index_id: index_id,
398 source_rank: rank,
399 source_metric: metric,
400 })
401 .collect();
402
403 federated.sort_by(|a, b| {
405 a.score
406 .partial_cmp(&b.score)
407 .unwrap_or(std::cmp::Ordering::Equal)
408 });
409 federated.truncate(k);
410
411 Ok(federated)
412 }
413
414 fn aggregate_rank_fusion(
416 &self,
417 results: Vec<(String, DistanceMetric, usize, SearchResult)>,
418 k: usize,
419 ) -> Result<Vec<FederatedSearchResult>> {
420 let mut scores: HashMap<Cid, (f32, String, usize, DistanceMetric)> = HashMap::new();
421 const RRF_K: f32 = 60.0;
422
423 for (index_id, metric, rank, result) in results {
424 let rrf_score = 1.0 / (RRF_K + rank as f32);
425
426 scores
427 .entry(result.cid)
428 .and_modify(|(score, _, _, _)| *score += rrf_score)
429 .or_insert((rrf_score, index_id.clone(), rank, metric));
430 }
431
432 let mut federated: Vec<_> = scores
433 .into_iter()
434 .map(
435 |(cid, (score, index_id, rank, metric))| FederatedSearchResult {
436 cid,
437 score,
438 source_index_id: index_id,
439 source_rank: rank,
440 source_metric: metric,
441 },
442 )
443 .collect();
444
445 federated.sort_by(|a, b| {
447 b.score
448 .partial_cmp(&a.score)
449 .unwrap_or(std::cmp::Ordering::Equal)
450 });
451 federated.truncate(k);
452
453 Ok(federated)
454 }
455
456 fn aggregate_score_normalization(
458 &self,
459 results: Vec<(String, DistanceMetric, usize, SearchResult)>,
460 k: usize,
461 ) -> Result<Vec<FederatedSearchResult>> {
462 let mut by_index: HashMap<String, Vec<(DistanceMetric, usize, SearchResult)>> =
464 HashMap::new();
465
466 for (index_id, metric, rank, result) in results {
467 by_index
468 .entry(index_id)
469 .or_default()
470 .push((metric, rank, result));
471 }
472
473 let mut normalized = Vec::new();
475 for (index_id, index_results) in by_index {
476 if index_results.is_empty() {
477 continue;
478 }
479
480 let scores: Vec<f32> = index_results.iter().map(|(_, _, r)| r.score).collect();
482 let min_score = scores.iter().copied().fold(f32::INFINITY, f32::min);
483 let max_score = scores.iter().copied().fold(f32::NEG_INFINITY, f32::max);
484 let range = max_score - min_score;
485
486 for (metric, rank, result) in index_results {
487 let normalized_score = if range > 1e-6 {
488 (result.score - min_score) / range
489 } else {
490 0.5 };
492
493 normalized.push(FederatedSearchResult {
494 cid: result.cid,
495 score: normalized_score,
496 source_index_id: index_id.clone(),
497 source_rank: rank,
498 source_metric: metric,
499 });
500 }
501 }
502
503 normalized.sort_by(|a, b| {
505 a.score
506 .partial_cmp(&b.score)
507 .unwrap_or(std::cmp::Ordering::Equal)
508 });
509 normalized.truncate(k);
510
511 Ok(normalized)
512 }
513
514 fn aggregate_borda_count(
516 &self,
517 results: Vec<(String, DistanceMetric, usize, SearchResult)>,
518 k: usize,
519 ) -> Result<Vec<FederatedSearchResult>> {
520 let mut borda_scores: HashMap<Cid, (usize, String, usize, DistanceMetric)> = HashMap::new();
521
522 let max_rank = results
524 .iter()
525 .map(|(_, _, rank, _)| *rank)
526 .max()
527 .unwrap_or(0);
528
529 for (index_id, metric, rank, result) in results {
530 let borda_points = max_rank.saturating_sub(rank);
531
532 borda_scores
533 .entry(result.cid)
534 .and_modify(|(points, _, _, _)| *points += borda_points)
535 .or_insert((borda_points, index_id.clone(), rank, metric));
536 }
537
538 let mut federated: Vec<_> = borda_scores
539 .into_iter()
540 .map(
541 |(cid, (points, index_id, rank, metric))| FederatedSearchResult {
542 cid,
543 score: points as f32,
544 source_index_id: index_id,
545 source_rank: rank,
546 source_metric: metric,
547 },
548 )
549 .collect();
550
551 federated.sort_by(|a, b| {
553 b.score
554 .partial_cmp(&a.score)
555 .unwrap_or(std::cmp::Ordering::Equal)
556 });
557 federated.truncate(k);
558
559 Ok(federated)
560 }
561
562 fn update_stats(&self, indices_queried: u64, num_results: usize, latency: f64, timeouts: u64) {
564 let mut stats = self.stats.write();
565 stats.total_queries += 1;
566 stats.total_indices_queried += indices_queried;
567 stats.timeouts += timeouts;
568
569 let alpha = 0.1;
571 stats.avg_latency_ms = alpha * latency + (1.0 - alpha) * stats.avg_latency_ms;
572 stats.avg_results_per_query =
573 alpha * num_results as f64 + (1.0 - alpha) * stats.avg_results_per_query;
574 }
575
576 pub fn stats(&self) -> FederatedQueryStats {
578 self.stats.read().clone()
579 }
580
581 pub fn registered_indices(&self) -> Vec<String> {
583 let indices = self.indices.read();
584 indices.keys().cloned().collect()
585 }
586
587 pub fn total_size(&self) -> usize {
589 let indices = self.indices.read();
590 indices.values().map(|idx| idx.size()).sum()
591 }
592}
593
594#[cfg(test)]
595mod tests {
596 use super::*;
597 use crate::hnsw::VectorIndex;
598 use multihash_codetable::{Code, MultihashDigest};
599
600 #[tokio::test]
601 async fn test_federated_executor_creation() {
602 let config = FederatedConfig::default();
603 let executor = FederatedQueryExecutor::new(config);
604 assert_eq!(executor.registered_indices().len(), 0);
605 }
606
607 #[tokio::test]
608 async fn test_register_and_unregister_index() {
609 let executor = FederatedQueryExecutor::new(FederatedConfig::default());
610
611 let index = VectorIndex::new(128, DistanceMetric::Cosine, 16, 200)
612 .expect("test: create cosine index");
613 let adapter =
614 LocalIndexAdapter::new(Arc::new(RwLock::new(index)), "test_index".to_string());
615
616 executor
617 .register_index(Arc::new(adapter))
618 .expect("test: register test index");
619 assert_eq!(executor.registered_indices().len(), 1);
620
621 executor
622 .unregister_index("test_index")
623 .expect("test: unregister test index");
624 assert_eq!(executor.registered_indices().len(), 0);
625 }
626
627 #[tokio::test]
628 async fn test_federated_query_single_index() {
629 let executor = FederatedQueryExecutor::new(FederatedConfig::default());
630
631 let index = VectorIndex::new(128, DistanceMetric::Cosine, 16, 200)
633 .expect("test: create cosine index for single query");
634 let index_lock = Arc::new(RwLock::new(index));
635
636 for i in 0..100 {
638 let data = format!("vector_{}", i);
639 let hash = Code::Sha2_256.digest(data.as_bytes());
640 let cid = Cid::new_v1(0x55, hash);
641 let embedding: Vec<f32> = (0..128).map(|j| (i + j) as f32 * 0.01).collect();
642 index_lock
643 .write()
644 .insert(&cid, &embedding)
645 .expect("test: insert vector into index");
646 }
647
648 let adapter = LocalIndexAdapter::new(Arc::clone(&index_lock), "index1".to_string());
649 executor
650 .register_index(Arc::new(adapter))
651 .expect("test: register index1");
652
653 let query_emb: Vec<f32> = (0..128).map(|i| i as f32 * 0.01).collect();
655 let results = executor
656 .query(&query_emb, 10)
657 .await
658 .expect("test: federated query single index");
659
660 assert!(!results.is_empty());
661 assert!(results.len() <= 10);
662 }
663
664 #[tokio::test]
665 async fn test_federated_query_multiple_indices() {
666 let config = FederatedConfig {
667 aggregation_strategy: AggregationStrategy::RankFusion,
668 ..Default::default()
669 };
670 let executor = FederatedQueryExecutor::new(config);
671
672 let index1 = VectorIndex::new(128, DistanceMetric::Cosine, 16, 200)
674 .expect("test: create cosine index1");
675 let index2 =
676 VectorIndex::new(128, DistanceMetric::L2, 16, 200).expect("test: create l2 index2");
677
678 let lock1 = Arc::new(RwLock::new(index1));
679 let lock2 = Arc::new(RwLock::new(index2));
680
681 for i in 0..50 {
683 let data = format!("vector_a_{}", i);
684 let hash = Code::Sha2_256.digest(data.as_bytes());
685 let cid = Cid::new_v1(0x55, hash);
686 let embedding: Vec<f32> = (0..128).map(|j| (i + j) as f32 * 0.01).collect();
687 lock1
688 .write()
689 .insert(&cid, &embedding)
690 .expect("test: insert into index1");
691 }
692
693 for i in 25..75 {
694 let data = format!("vector_b_{}", i);
696 let hash = Code::Sha2_256.digest(data.as_bytes());
697 let cid = Cid::new_v1(0x55, hash);
698 let embedding: Vec<f32> = (0..128).map(|j| (i + j) as f32 * 0.01).collect();
699 lock2
700 .write()
701 .insert(&cid, &embedding)
702 .expect("test: insert into index2");
703 }
704
705 executor
706 .register_index(Arc::new(LocalIndexAdapter::new(
707 Arc::clone(&lock1),
708 "index1".to_string(),
709 )))
710 .expect("test: register index1 for multi");
711 executor
712 .register_index(Arc::new(LocalIndexAdapter::new(
713 Arc::clone(&lock2),
714 "index2".to_string(),
715 )))
716 .expect("test: register index2 for multi");
717
718 let query_emb: Vec<f32> = (0..128).map(|i| i as f32 * 0.02).collect();
720 let results = executor
721 .query(&query_emb, 10)
722 .await
723 .expect("test: federated query multiple indices");
724
725 assert!(!results.is_empty());
726 assert!(results.len() <= 10);
727
728 let stats = executor.stats();
730 assert_eq!(stats.total_queries, 1);
731 assert!(stats.total_indices_queried >= 1);
732 }
733
734 #[tokio::test]
735 async fn test_different_aggregation_strategies() {
736 for strategy in &[
737 AggregationStrategy::Simple,
738 AggregationStrategy::RankFusion,
739 AggregationStrategy::ScoreNormalization,
740 AggregationStrategy::BordaCount,
741 ] {
742 let config = FederatedConfig {
743 aggregation_strategy: *strategy,
744 ..Default::default()
745 };
746 let executor = FederatedQueryExecutor::new(config);
747
748 let index = VectorIndex::new(128, DistanceMetric::Cosine, 16, 200)
749 .expect("test: create index for strategy test");
750 let lock = Arc::new(RwLock::new(index));
751
752 for i in 0..20 {
754 let data = format!("vec_{}", i);
755 let hash = Code::Sha2_256.digest(data.as_bytes());
756 let cid = Cid::new_v1(0x55, hash);
757 let embedding: Vec<f32> = (0..128).map(|j| (i + j) as f32 * 0.01).collect();
758 lock.write()
759 .insert(&cid, &embedding)
760 .expect("test: insert vector for strategy test");
761 }
762
763 executor
764 .register_index(Arc::new(LocalIndexAdapter::new(
765 lock,
766 format!("index_{:?}", strategy),
767 )))
768 .expect("test: register index for strategy");
769
770 let query_emb: Vec<f32> = (0..128).map(|i| i as f32 * 0.01).collect();
771 let results = executor
772 .query(&query_emb, 5)
773 .await
774 .expect("test: strategy query");
775
776 assert!(!results.is_empty(), "Strategy {:?} failed", strategy);
777 }
778 }
779
780 #[tokio::test]
781 async fn test_privacy_preserving_mode() {
782 let config = FederatedConfig {
783 privacy_preserving: true,
784 privacy_noise_level: 0.1,
785 ..Default::default()
786 };
787
788 let executor = FederatedQueryExecutor::new(config);
789
790 let index = VectorIndex::new(128, DistanceMetric::Cosine, 16, 200)
791 .expect("test: create cosine index for privacy test");
792 let lock = Arc::new(RwLock::new(index));
793
794 for i in 0..30 {
795 let data = format!("private_vec_{}", i);
796 let hash = Code::Sha2_256.digest(data.as_bytes());
797 let cid = Cid::new_v1(0x55, hash);
798 let embedding: Vec<f32> = (0..128).map(|j| (i + j) as f32 * 0.01).collect();
799 lock.write()
800 .insert(&cid, &embedding)
801 .expect("test: insert private vector");
802 }
803
804 executor
805 .register_index(Arc::new(LocalIndexAdapter::new(
806 lock,
807 "private_index".to_string(),
808 )))
809 .expect("test: register private index");
810
811 let query_emb: Vec<f32> = (0..128).map(|i| i as f32 * 0.01).collect();
812 let results = executor
813 .query(&query_emb, 5)
814 .await
815 .expect("test: privacy preserving query");
816
817 assert!(!results.is_empty());
819 }
820
821 #[tokio::test]
822 async fn test_query_specific_indices() {
823 let executor = FederatedQueryExecutor::new(FederatedConfig::default());
824
825 for idx_num in 0..3 {
827 let index = VectorIndex::new(128, DistanceMetric::Cosine, 16, 200)
828 .expect("test: create cosine index for specific indices test");
829 let lock = Arc::new(RwLock::new(index));
830
831 for i in 0..20 {
832 let data = format!("vec_{}_{}", idx_num, i);
833 let hash = Code::Sha2_256.digest(data.as_bytes());
834 let cid = Cid::new_v1(0x55, hash);
835 let embedding: Vec<f32> =
836 (0..128).map(|j| (i + j + idx_num) as f32 * 0.01).collect();
837 lock.write()
838 .insert(&cid, &embedding)
839 .expect("test: insert vector into specific index");
840 }
841
842 executor
843 .register_index(Arc::new(LocalIndexAdapter::new(
844 lock,
845 format!("index_{}", idx_num),
846 )))
847 .expect("test: register specific index");
848 }
849
850 let query_emb: Vec<f32> = (0..128).map(|i| i as f32 * 0.01).collect();
852 let results = executor
853 .query_indices(
854 &query_emb,
855 10,
856 &["index_0".to_string(), "index_2".to_string()],
857 )
858 .await
859 .expect("test: query specific indices");
860
861 assert!(!results.is_empty());
862
863 for result in results {
865 assert!(result.source_index_id == "index_0" || result.source_index_id == "index_2");
866 }
867 }
868}