FIX: Handling spaces in path during mismatch correction.
+ +FIX: Python3 support in rnaSPAdes.
+ +FIX: K value estimation for long reads.
+ +FIX: Processing long reads alignments.
+ +NEW: Support for strand-specific RNA-Seq data in rnaSPAdes.
+ +NEW: Coverage based isoform detection in rnaSPAdes.
+ +NEW: Reworked IonHammer read error correction module.
+ +CHANGE: Improved tandem repeat resolution accuracy.
+ +CHANGE: Better performance of exSPAnder module.
+ +CHANGE: metaSPAdes pipeline improvements.
+ +CHANGE: Better running time and RAM consumption for the entire pipeline.
+ +FIX: Incomplete paths in GFA output.
+ +FIX: Mismatch and indel rate in careful mode for isolate datasets (esp. low covered ones).
+ +FIX: Occasional hanging of edge disconnection procedure in metaSPAdes.
+FIX: Build for MacOS.
@@ -29,7 +61,6 @@CHANGE: Improved isoform detection algorithm in rnaSPAdes.
-FIX: macOS Sierra crash.
diff -Nru spades-3.10.1+dfsg/configs/corrector/corrector.info spades-3.11.1+dfsg/configs/corrector/corrector.info --- spades-3.10.1+dfsg/configs/corrector/corrector.info 2017-02-28 14:55:38.000000000 +0000 +++ spades-3.11.1+dfsg/configs/corrector/corrector.info 2017-09-28 09:05:14.000000000 +0000 @@ -3,5 +3,6 @@ work_dir: ./test_dataset/input/corrected/tmp, output_dir: ./test_dataset/input/corrected, max_nthreads: 16, -strategy: mapped_squared +strategy: mapped_squared, +log_filename: log.properties } diff -Nru spades-3.10.1+dfsg/configs/corrector/log.properties spades-3.11.1+dfsg/configs/corrector/log.properties --- spades-3.10.1+dfsg/configs/corrector/log.properties 1970-01-01 00:00:00.000000000 +0000 +++ spades-3.11.1+dfsg/configs/corrector/log.properties 2017-09-28 09:05:14.000000000 +0000 @@ -0,0 +1,2 @@ +default=INFO +ContigProcessor=INFO diff -Nru spades-3.10.1+dfsg/configs/debruijn/careful_mda_mode.info spades-3.11.1+dfsg/configs/debruijn/careful_mda_mode.info --- spades-3.10.1+dfsg/configs/debruijn/careful_mda_mode.info 1970-01-01 00:00:00.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/careful_mda_mode.info 2017-09-28 09:05:14.000000000 +0000 @@ -0,0 +1,39 @@ +simp +{ + ; bulge remover: + br + { + max_relative_coverage 1.1 ; bulge_cov < this * not_bulge_cov + } + + ; complex bulge remover + cbr + { + enabled false + } + + final_tc + { + condition "" + } + + ; bulge remover: + final_br + { + enabled false + } + + init_clean + { + early_it_only true + + activation_cov -1. + ier + { + enabled false + } + + tip_condition "" + ec_condition "" + } +} diff -Nru spades-3.10.1+dfsg/configs/debruijn/careful_mode.info spades-3.11.1+dfsg/configs/debruijn/careful_mode.info --- spades-3.10.1+dfsg/configs/debruijn/careful_mode.info 2017-02-28 14:55:38.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/careful_mode.info 2017-09-28 09:05:14.000000000 +0000 @@ -1,12 +1,10 @@ - simp { ; bulge remover: br { - max_coverage 1000000.0 - max_relative_coverage 1.5 ; bulge_cov < this * not_bulge_cov - parallel false + max_relative_coverage 0.5 ; bulge_cov < this * not_bulge_cov + ; parallel false } ; complex bulge remover @@ -14,6 +12,12 @@ { enabled false } + + ; bulge remover: + final_br + { + enabled false + } ; relative coverage erroneous component remover: rcc diff -Nru spades-3.10.1+dfsg/configs/debruijn/config.info spades-3.11.1+dfsg/configs/debruijn/config.info --- spades-3.10.1+dfsg/configs/debruijn/config.info 2017-02-28 14:55:38.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/config.info 2017-09-28 09:05:14.000000000 +0000 @@ -14,10 +14,10 @@ ;FIXME remove! run_mode false project_name TOY_DATASET -dataset ./configs/debruijn/datasets_archive/toy.info +dataset ./configs/debruijn/toy.info log_filename log.properties -output_base ./data/debruijn/ +output_base ./spades_output tmp_dir spades_tmp/ main_iteration true @@ -30,11 +30,11 @@ temp_bin_reads_dir .bin_reads/ max_threads 8 max_memory 120; in Gigabytes -buffer_size 512; in Megabytes +buffer_size 512; in Megabytes entry_point construction ;entry_point simplification -;entry_point pacbio_aligning +;entry_point hybrid_aligning ;entry_point late_pair_info_count ;entry_point distance_estimation ;entry_point repeat_resolving @@ -69,9 +69,6 @@ ; End of developer_mode parameters -; use unipaths as additional contigs instead of just graph edges -use_unipaths false - ;if true simple mismatches are corrected correct_mismatches true @@ -95,6 +92,12 @@ avoid_rc_connections true +calculate_coverage_for_each_lib false +strand_specificity { + ss_enabled false + antisense false +} + contig_output { contigs_name final_contigs scaffolds_name scaffolds @@ -133,6 +136,13 @@ coverage_threshold 10.0 } +; low covered edges remover +lcer +{ + lcer_enabled false + lcer_coverage_threshold 0.0 +} + pacbio_processor { ;align and traverse. @@ -172,3 +182,4 @@ ;flanking coverage range flanking_range 55 series_analysis "" +save_gp false diff -Nru spades-3.10.1+dfsg/configs/debruijn/log.properties spades-3.11.1+dfsg/configs/debruijn/log.properties --- spades-3.10.1+dfsg/configs/debruijn/log.properties 2017-02-28 14:55:38.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/log.properties 2017-09-28 09:05:14.000000000 +0000 @@ -50,6 +50,8 @@ #LoopDetectingPathExtender=DEBUG #SimpleExtender=DEBUG #ScaffoldingPathExtender=DEBUG +#CoordCoverageExtensionChooser=DEBUG +#SimpleCoverageExtensionChooser=DEBUG #BWAPairInfo=TRACE #LongReadMapper=TRACE diff -Nru spades-3.10.1+dfsg/configs/debruijn/mda_mode.info spades-3.11.1+dfsg/configs/debruijn/mda_mode.info --- spades-3.10.1+dfsg/configs/debruijn/mda_mode.info 2017-02-28 14:55:38.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/mda_mode.info 2017-09-28 09:05:14.000000000 +0000 @@ -39,7 +39,7 @@ rcc { enabled true - coverage_gap 20. + coverage_gap 10. max_length_coeff 2.0 max_length_with_tips_coeff 3.0 max_vertex_cnt 30 diff -Nru spades-3.10.1+dfsg/configs/debruijn/meta_mode.info spades-3.11.1+dfsg/configs/debruijn/meta_mode.info --- spades-3.10.1+dfsg/configs/debruijn/meta_mode.info 2017-02-28 14:55:38.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/meta_mode.info 2017-09-28 09:05:14.000000000 +0000 @@ -32,7 +32,7 @@ { ; rctc: tip_cov < rctc * not_tip_cov ; tc_lb: max_tip_length = max((min(k, read_length / 2) * tc_lb), read_length); - condition "{ tc_lb 3.5, , cb 1000000, rctc 2.0 } { tc_lb 6., cb 2.5, rctc 1.0 }" + condition "{ tc_lb 3.5, cb 1000000, rctc 2.0 } { tc_lb 6., cb 2.5, rctc 1.0 }" } ; relative coverage erroneous component remover: @@ -57,16 +57,17 @@ relative_ed { enabled true - diff_mult 10. + diff_mult 5. } ; bulge remover: br { max_coverage 1000000.0 - max_relative_coverage 100000. ; bulge_cov < this * not_bulge_cov + max_relative_coverage 5. ; bulge_cov < this * not_bulge_cov max_delta 10 max_relative_delta 0.1 + dijkstra_vertex_limit 3000 parallel true } @@ -90,14 +91,6 @@ max_relative_delta 0.1 } - ; second final bulge remover: - ; only in meta mode, inherits settings of final_br - second_final_br - { - max_delta 1500 - max_number_edges 3 - } - ; hidden ec remover her { @@ -169,8 +162,10 @@ } params { - remove_overlaps true - cut_all_overlaps true + overlap_removal { + enabled true + cut_all true + } scaffolding_mode old_pe_2015 @@ -187,6 +182,12 @@ } use_coordinated_coverage true + + coordinated_coverage + { + min_path_len 10000 + } + } } @@ -195,6 +196,10 @@ params { scaffolding_mode old + overlap_removal { + enabled false + } + use_coordinated_coverage false remove_overlaps false scaffolding2015 { diff -Nru spades-3.10.1+dfsg/configs/debruijn/moleculo_mode.info spades-3.11.1+dfsg/configs/debruijn/moleculo_mode.info --- spades-3.10.1+dfsg/configs/debruijn/moleculo_mode.info 2017-02-28 14:55:38.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/moleculo_mode.info 2017-09-28 09:05:14.000000000 +0000 @@ -101,7 +101,11 @@ pe { params { normalize_weight true - cut_all_overlaps true + + overlap_removal { + enabled true + cut_all true + } scaffolding_mode old diff -Nru spades-3.10.1+dfsg/configs/debruijn/pe_params.info spades-3.11.1+dfsg/configs/debruijn/pe_params.info --- spades-3.10.1+dfsg/configs/debruijn/pe_params.info 2017-02-28 14:55:38.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/pe_params.info 2017-09-28 09:05:14.000000000 +0000 @@ -18,9 +18,12 @@ multi_path_extend false ; old | 2015 | combined | old_pe_2015 scaffolding_mode old_pe_2015 - - remove_overlaps true - cut_all_overlaps false + + overlap_removal { + enabled true + end_start_only false + cut_all false + } split_edge_length 99 normalize_weight true @@ -61,25 +64,20 @@ ;next param should be 0.51 - 1.0 if use_old_score = true and 3.0 otherwise min_gap_score 0.7 - max_must_overlap -2 - max_can_overlap 0.5 + max_can_overlap 1. short_overlap 6 artificial_gap 10 - use_old_score true min_overlap_length 10 - flank_addition_coefficient -5.9 - flank_multiplication_coefficient 0.97 + flank_multiplication_coefficient .5 + flank_addition_coefficient 5 var_coeff 3.0 basic_overlap_coeff 2.0 } - path_cleaning - { - enabled false - } - + path_cleaning_presets "" + use_coordinated_coverage false coordinated_coverage { @@ -88,6 +86,14 @@ min_path_len 1000 } + + simple_coverage_resolver { + enabled false + coverage_delta 0.5 + min_upper_coverage 5 + } + + scaffolding2015 { ; (median * (1+variation) > unique > median * (1 - variation)) relative_weight_cutoff 2.0 @@ -112,6 +118,9 @@ genome_consistency_checker { max_gap 1000 relative_max_gap 0.2 + use_main_storage true ; if set to true, next two parameters are set to min_unique_length + unresolvable_jump 1000 ; length of unresolvable repeats + unique_length 500 ; spelling genome in the alphabet of edges longer than this } uniqueness_analyser { diff -Nru spades-3.10.1+dfsg/configs/debruijn/rna_fast_mode.info spades-3.11.1+dfsg/configs/debruijn/rna_fast_mode.info --- spades-3.10.1+dfsg/configs/debruijn/rna_fast_mode.info 1970-01-01 00:00:00.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/rna_fast_mode.info 2017-09-28 09:05:14.000000000 +0000 @@ -0,0 +1,12 @@ +simp +{ + ier + { + enabled true + use_rl_for_max_length true ; max_length will be taken max with read_length + use_rl_for_max_length_any_cov false ; use_rl_for_max_length_any_cov will be taken max with read_length + max_length 110 + max_coverage 2 + max_length_any_cov 0 + } +} diff -Nru spades-3.10.1+dfsg/configs/debruijn/rna_mode.info spades-3.11.1+dfsg/configs/debruijn/rna_mode.info --- spades-3.10.1+dfsg/configs/debruijn/rna_mode.info 2017-02-28 14:55:38.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/rna_mode.info 2017-09-28 09:05:14.000000000 +0000 @@ -2,6 +2,13 @@ preserve_raw_paired_index true +calculate_coverage_for_each_lib true +strand_specificity { + ss_enabled false + antisense false +} + + contig_output { scaffolds_name transcripts ; none --- do not output broken scaffolds | break_gaps --- break only by N steches | break_all --- break all with overlap < k @@ -62,14 +69,13 @@ max_ec_length_coefficient 30 max_coverage_coeff 5.0 } + ;all topology based erroneous connection removers are off ier { enabled false - max_length 100 - max_coverage 2 - max_length_any_cov 0 ; will be taken max with read_length } + ; hidden ec remover her { @@ -100,12 +106,19 @@ } pe { +debug_output true + params { multi_path_extend true - remove_overlaps false scaffolding_mode old + overlap_removal { + enabled true + end_start_only true + cut_all true + } + extension_options { use_default_single_threshold true @@ -115,20 +128,65 @@ scaffolder { cutoff 1 hard_cutoff 10 - - cluster_info false - - min_overlap_for_rna_scaffolding 10 + cluster_info false + min_overlap_for_rna_scaffolding 10 } + path_cleaning_presets "default soft hard" + ; All length cutoffs presented in nucleotides + ; So edges less than or equal to (relative cutoff * RL - K) or (absolute cutoff - K) will be deleted path_cleaning { enabled true - min_length 30 - isolated_min_length 50 - min_length_for_low_covered 150 + min_length 110 + isolated_min_length 130 + isolated_min_cov 4 + min_length_for_low_covered 140 + rel_cutoff 1.3 + rel_isolated_cutoff 1.5 + rel_low_covered_cutoff 1.6 min_coverage 2 } + ; All length cutoffs presented in nucleotides + hard_path_cleaning + { + enabled true + min_length 130 + isolated_min_length 180 + isolated_min_cov 8 + min_length_for_low_covered 180 + rel_cutoff 1.5 + rel_isolated_cutoff 2.0 + rel_low_covered_cutoff 2.0 + min_coverage 3 + } + + ; All length cutoffs presented in nucleotides + soft_path_cleaning + { + enabled true + min_length 85 + isolated_min_length 100 + isolated_min_cov 2 + min_length_for_low_covered 130 + rel_cutoff 1.05 + rel_isolated_cutoff 1.2 + rel_low_covered_cutoff 1.5 + min_coverage 1 + } + + use_coordinated_coverage false + coordinated_coverage { + max_edge_length_repeat 1000 + delta 0.5 + min_path_len 300 + } + + simple_coverage_resolver { + enabled true + coverage_delta 0.5 + min_upper_coverage 2 + } } } diff -Nru spades-3.10.1+dfsg/configs/debruijn/simplification.info spades-3.11.1+dfsg/configs/debruijn/simplification.info --- spades-3.10.1+dfsg/configs/debruijn/simplification.info 2017-02-28 14:55:38.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/simplification.info 2017-09-28 09:05:14.000000000 +0000 @@ -20,23 +20,24 @@ condition "{ tc_lb 3.5, cb 1000000, rctc 2.0 } { tc_lb 10., cb auto }" } - ; bulge remover: - br - { - enabled true + ; bulge remover: + br + { + enabled true main_iteration_only false - max_bulge_length_coefficient 3. ; max_bulge_length = max_bulge_length_coefficient * k - max_additive_length_coefficient 100 - max_coverage 1000.0 - max_relative_coverage 1.1 ; bulge_cov < this * not_bulge_cov - max_delta 3 - max_relative_delta 0.1 + max_bulge_length_coefficient 3. ; max_bulge_length = max_bulge_length_coefficient * k + max_additive_length_coefficient 100 + max_coverage 1000.0 + max_relative_coverage 1.1 ; bulge_cov < this * not_bulge_cov + max_delta 3 + max_relative_delta 0.1 max_number_edges 1000 + dijkstra_vertex_limit 3000 parallel true buff_size 10000 buff_cov_diff 2. buff_cov_rel_diff 0.2 - } + } ; erroneous connections remover: ec @@ -94,6 +95,7 @@ max_delta 3 max_relative_delta 0.1 max_number_edges 1000 + dijkstra_vertex_limit 3000 parallel true buff_size 10000 buff_cov_diff 2. @@ -143,9 +145,11 @@ ier { enabled true - max_length 0 + use_rl_for_max_length false ; max_length will be taken max with read_length + use_rl_for_max_length_any_cov true ; use_rl_for_max_length_any_cov will be taken max with read_length + max_length 0 ; will be taken max with read_length if option above is set max_coverage 2 - max_length_any_cov 150 ; will be taken max with read_length + max_length_any_cov 150 ; will be taken max with read_length if option above is set } ; topology tip clipper: @@ -193,9 +197,11 @@ ier { enabled true - max_length 0 + use_rl_for_max_length false ; max_length will be taken max with read_length + use_rl_for_max_length_any_cov true ; use_rl_for_max_length_any_cov will be taken max with read_length + max_length 0 ; will be taken max with read_length if option above is set max_coverage 0 - max_length_any_cov 0 ; will be taken max with read_length + max_length_any_cov 0 ; will be taken max with read_length if option above is set } tip_condition "{ tc_lb 3.5, cb auto }" diff -Nru spades-3.10.1+dfsg/configs/debruijn/toy.info spades-3.11.1+dfsg/configs/debruijn/toy.info --- spades-3.10.1+dfsg/configs/debruijn/toy.info 1970-01-01 00:00:00.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/toy.info 2017-09-28 09:05:14.000000000 +0000 @@ -0,0 +1,4 @@ +reads toy.yaml +single_cell false +; RL 100 + diff -Nru spades-3.10.1+dfsg/configs/debruijn/toy.yaml spades-3.11.1+dfsg/configs/debruijn/toy.yaml --- spades-3.10.1+dfsg/configs/debruijn/toy.yaml 1970-01-01 00:00:00.000000000 +0000 +++ spades-3.11.1+dfsg/configs/debruijn/toy.yaml 2017-09-28 09:05:14.000000000 +0000 @@ -0,0 +1,4 @@ +- left reads: [../../test_dataset/ecoli_1K_1.fq.gz] + orientation: fr + right reads: [../../test_dataset/ecoli_1K_2.fq.gz] + type: paired-end diff -Nru spades-3.10.1+dfsg/debian/changelog spades-3.11.1+dfsg/debian/changelog --- spades-3.10.1+dfsg/debian/changelog 2017-08-10 14:39:50.000000000 +0000 +++ spades-3.11.1+dfsg/debian/changelog 2017-12-18 00:29:26.000000000 +0000 @@ -1,3 +1,18 @@ +spades (3.11.1+dfsg-1) unstable; urgency=medium + + [ Sascha Steinbiss ] + * New upstream release. + * Bump Standards-Version. + * Remove obsolete Testsuite: entry in d/control + * Add d/copyright entry for new included BBHash headers. + + [ Steffen Moeller ] + * debian/upstream/metadata: + - added references to registries + - yamllint cleanliness + + -- Sascha Steinbiss@@ -11,7 +11,7 @@
lib_pe1_left_1.fastq
-@@ -989,7 +989,7 @@
+@@ -990,7 +990,7 @@
@@ -20,7 +20,7 @@
-@@ -1138,7 +1138,7 @@
+@@ -1139,7 +1139,7 @@
@@ -29,8 +29,8 @@
NODE_3_length_237403_cov_243.207_ID_45
---- spades.orig/src/common/assembly_graph/stats/picture_dump.hpp
-+++ spades/src/common/assembly_graph/stats/picture_dump.hpp
+--- a/src/common/assembly_graph/stats/picture_dump.hpp
++++ b/src/common/assembly_graph/stats/picture_dump.hpp
@@ -123,7 +123,7 @@
INFO("Genome mapping results:");
INFO("Covered k+1-mers:" << covered_kp1mers << " of " << (genome_.size() - k_) << " which is "
@@ -40,9 +40,9 @@
INFO("Continuity failtures " << fail);
}
};
---- spades.orig/src/common/modules/alignment/pacbio/pac_index.hpp
-+++ spades/src/common/modules/alignment/pacbio/pac_index.hpp
-@@ -581,7 +581,7 @@
+--- a/src/common/modules/alignment/pacbio/pac_index.hpp
++++ b/src/common/modules/alignment/pacbio/pac_index.hpp
+@@ -593,7 +593,7 @@
|| !IsConsistent(*(iter->second),
*(next_iter->second))) {
if (next_iter != cur_cluster.end()) {
@@ -51,8 +51,8 @@
DEBUG("on "<< iter->second->str(g_));
DEBUG("and " << next_iter->second->str(g_));
}
---- spades.orig/src/projects/dipspades/kmer_gluing/equal_sequence_gluer.hpp
-+++ spades/src/projects/dipspades/kmer_gluing/equal_sequence_gluer.hpp
+--- a/src/projects/dipspades/kmer_gluing/equal_sequence_gluer.hpp
++++ b/src/projects/dipspades/kmer_gluing/equal_sequence_gluer.hpp
@@ -74,9 +74,9 @@
pos2 = graph_.length(edge1) - tmp - 1;
}
@@ -65,8 +65,8 @@
TRACE("New edge1: " << graph_.int_id(split_edges.first) << ", length: " << graph_.length(split_edges.first));
TRACE("New edge2: " << graph_.int_id(split_edges.second) << ", length: " << graph_.length(split_edges.second));
edge1 = split_edges.first;
---- spades.orig/src/projects/dipspades/polymorphic_bulge_remover/bulge_gluer.hpp
-+++ spades/src/projects/dipspades/polymorphic_bulge_remover/bulge_gluer.hpp
+--- a/src/projects/dipspades/polymorphic_bulge_remover/bulge_gluer.hpp
++++ b/src/projects/dipspades/polymorphic_bulge_remover/bulge_gluer.hpp
@@ -74,7 +74,7 @@
auto splitted_bulge = splitter_.SplitBulge(directed_bulge, glue_def_res);
@@ -76,8 +76,8 @@
GlueSplittedBulge(splitted_bulge);
return true;
}
---- spades.orig/src/projects/dipspades/polymorphic_bulge_remover/bulge_splitter.hpp
-+++ spades/src/projects/dipspades/polymorphic_bulge_remover/bulge_splitter.hpp
+--- a/src/projects/dipspades/polymorphic_bulge_remover/bulge_splitter.hpp
++++ b/src/projects/dipspades/polymorphic_bulge_remover/bulge_splitter.hpp
@@ -260,7 +260,7 @@
SplitOppositeEdge(split_res, split_paths.second, split_partlens.second);
diff -Nru spades-3.10.1+dfsg/debian/upstream/metadata spades-3.11.1+dfsg/debian/upstream/metadata
--- spades-3.10.1+dfsg/debian/upstream/metadata 2017-08-08 14:54:45.000000000 +0000
+++ spades-3.11.1+dfsg/debian/upstream/metadata 2017-12-18 00:25:26.000000000 +0000
@@ -1,6 +1,13 @@
Reference:
- - Author: Anton Bankevich and Sergey Nurk and Dmitry Antipov and Alexey A. Gurevich and Mikhail Dvorkin and Alexander S. Kulikov and Valery M. Lesin and Sergey I. Nikolenko and Son Pham and Andrey D. Prjibelski and Alexey V. Pyshkin and Alexander V. Sirotkin and Nikolay Vyahhi and Glenn Tesler and Max A. Alekseyev and Pavel A. Pevzner
- Title: "SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing"
+ - Author: >
+ Anton Bankevich and Sergey Nurk and Dmitry Antipov and Alexey
+ A. Gurevich and Mikhail Dvorkin and Alexander S. Kulikov and Valery
+ M. Lesin and Sergey I. Nikolenko and Son Pham and Andrey D. Prjibelski
+ and Alexey V. Pyshkin and Alexander V. Sirotkin and Nikolay Vyahhi
+ and Glenn Tesler and Max A. Alekseyev and Pavel A. Pevzner
+ Title: >
+ SPAdes: A New Genome Assembly Algorithm and Its Applications to
+ Single-Cell Sequencing
Journal: Journal of Computational Biology
Year: 2012
Volume: 19
@@ -10,7 +17,12 @@
PMID: 22506599
URL: http://online.liebertpub.com/doi/abs/10.1089/cmb.2012.0021
eprint: http://online.liebertpub.com/doi/pdfplus/10.1089/cmb.2012.0021
- - Author: Sergey Nurk and Anton Bankevich and Dmitry Antipov and Alexey Gurevich and Anton Korobeynikov and Alla Lapidus and Andrey Prjibelsky and Alexey Pyshkin and Alexander Sirotkin and Yakov Sirotkin and Ramunas Stepanauskas and Jeffrey McLean and Roger Lasken and Scott Clingenpeel and Tanja Woyke and Glenn Tesler and Max Alekseyev and Pavel Pevzner
+ - Author: >
+ Sergey Nurk and Anton Bankevich and Dmitry Antipov and Alexey Gurevich
+ and Anton Korobeynikov and Alla Lapidus and Andrey Prjibelsky and
+ Alexey Pyshkin and Alexander Sirotkin and Yakov Sirotkin and Ramunas
+ Stepanauskas and Jeffrey McLean and Roger Lasken and Scott Clingenpeel
+ and Tanja Woyke and Glenn Tesler and Max Alekseyev and Pavel Pevzner
Title: Assembling Genomes and Mini-metagenomes from Highly Chimeric Reads
Journal: Lecture Notes in Computer Science
Year: 2013
@@ -18,4 +30,10 @@
Pages: 158-170
DOI: 10.1007/978-3-642-37195-0_13
URL: http://link.springer.com/chapter/10.1007%2F978-3-642-37195-0_13
-
+Registry:
+ - Name: RRID
+ Entry: SCR_000131
+ - Name: OMICtools
+ Entry: OMICS_01502
+ - Name: bio.tools
+ Entry: Spades
diff -Nru spades-3.10.1+dfsg/ext/include/boomphf/BooPHF.h spades-3.11.1+dfsg/ext/include/boomphf/BooPHF.h
--- spades-3.10.1+dfsg/ext/include/boomphf/BooPHF.h 1970-01-01 00:00:00.000000000 +0000
+++ spades-3.11.1+dfsg/ext/include/boomphf/BooPHF.h 2017-09-28 09:05:18.000000000 +0000
@@ -0,0 +1,1422 @@
+// BooPHF library
+// intended to be a minimal perfect hash function with fast and low memory
+// construction, at the cost of (slightly) higher bits/elem than other state of
+// the art libraries once built. should work with arbitray large number of
+// elements, based on a cascade of "collision-free" bit arrays
+
+#pragma once
+#include
+#include
+#include
+#include
+#include
+
+#include
+#include
+#include
+#include
+#include
+#include
+#include // for make_shared
+#include
+
+//#define CCDEBUG
+//#define PDEBUG
+
+namespace boomphf {
+
+inline uint64_t printPt( pthread_t pt) {
+ unsigned char *ptc = (unsigned char*)(void*)(&pt);
+ uint64_t res =0;
+ for (size_t i=0; i
+class bfile_iterator : public std::iterator{
+ public:
+
+ bfile_iterator()
+ : _is(nullptr)
+ , _pos(0) ,_inbuff (0), _cptread(0)
+ {
+ _buffsize = 10000;
+ _buffer = (basetype *) malloc(_buffsize*sizeof(basetype));
+ }
+
+ bfile_iterator(const bfile_iterator& cr)
+ {
+ _buffsize = cr._buffsize;
+ _pos = cr._pos;
+ _is = cr._is;
+ _buffer = (basetype *) malloc(_buffsize*sizeof(basetype));
+ memcpy(_buffer,cr._buffer,_buffsize*sizeof(basetype) );
+ _inbuff = cr._inbuff;
+ _cptread = cr._cptread;
+ _elem = cr._elem;
+ }
+
+ bfile_iterator(FILE* is): _is(is) , _pos(0) ,_inbuff (0), _cptread(0)
+ {
+ //printf("bf it %p\n",_is);
+ _buffsize = 10000;
+ _buffer = (basetype *) malloc(_buffsize*sizeof(basetype));
+ int reso = fseek(_is,0,SEEK_SET);
+ advance();
+ }
+
+ ~bfile_iterator()
+ {
+ if(_buffer!=NULL)
+ free(_buffer);
+ }
+
+
+ basetype const& operator*() { return _elem; }
+
+ bfile_iterator& operator++()
+ {
+ advance();
+ return *this;
+ }
+
+ friend bool operator==(bfile_iterator const& lhs, bfile_iterator const& rhs)
+ {
+ if (!lhs._is || !rhs._is) { if (!lhs._is && !rhs._is) { return true; } else { return false; } }
+ assert(lhs._is == rhs._is);
+ return rhs._pos == lhs._pos;
+ }
+
+ friend bool operator!=(bfile_iterator const& lhs, bfile_iterator const& rhs) { return !(lhs == rhs); }
+
+ private:
+ void advance()
+ {
+
+ //printf("_cptread %i _inbuff %i \n",_cptread,_inbuff);
+
+ _pos++;
+
+ if(_cptread >= _inbuff)
+ {
+
+ int res = fread(_buffer,sizeof(basetype),_buffsize,_is);
+
+ //printf("read %i new elem last %llu %p\n",res,_buffer[res-1],_is);
+ _inbuff = res; _cptread = 0;
+
+ if(res == 0)
+ {
+ _is = nullptr;
+ _pos = 0;
+ return;
+ }
+ }
+
+ _elem = _buffer[_cptread];
+ _cptread ++;
+ }
+ basetype _elem;
+ FILE * _is;
+ unsigned long _pos;
+
+ basetype * _buffer; // for buffered read
+ int _inbuff, _cptread;
+ int _buffsize;
+};
+
+
+template
+class file_binary{
+ public:
+
+ file_binary(const char* filename)
+ {
+ _is = fopen(filename, "rb");
+
+ if (!_is) {
+ throw std::invalid_argument("Error opening " + std::string(filename));
+ }
+ }
+
+ ~file_binary()
+ {
+ fclose(_is);
+ }
+
+ bfile_iterator begin() const
+ {
+ return bfile_iterator(_is);
+ }
+
+ bfile_iterator end() const {return bfile_iterator(); }
+
+ size_t size () const { return 0; }//todo ?
+
+ private:
+ FILE * _is;
+};
+
+
+#define L8 0x0101010101010101ULL // Every lowest 8th bit set: 00000001...
+#define G2 0xAAAAAAAAAAAAAAAAULL // Every highest 2nd bit: 101010...
+#define G4 0x3333333333333333ULL // 00110011 ... used to group the sum of 4 bits.
+#define G8 0x0F0F0F0F0F0F0F0FULL
+
+static inline unsigned popcount_64(uint64_t x) {
+ // Step 1: 00 - 00 = 0; 01 - 00 = 01; 10 - 01 = 01; 11 - 01 = 10;
+ x = x - ((x & G2) >> 1);
+ // step 2: add 2 groups of 2.
+ x = (x & G4) + ((x >> 2) & G4);
+ // 2 groups of 4.
+ x = (x + (x >> 4)) & G8;
+ // Using a multiply to collect the 8 groups of 8 together.
+ x = x * L8 >> 56;
+ return x;
+}
+
+///// progress bar
+class Progress
+{
+ public:
+ int timer_mode;
+ struct timeval timestamp;
+ double heure_debut, heure_actuelle ;
+ std::string message;
+
+ uint64_t done;
+ uint64_t todo;
+ int subdiv ; // progress printed every 1/subdiv of total to do
+ double partial;
+ int _nthreads;
+ std::vector partial_threaded;
+ std::vector done_threaded;
+
+ double steps ; //steps = todo/subidv
+
+ void init(uint64_t ntasks, const char * msg,int nthreads =1)
+ {
+ _nthreads = nthreads;
+ message = std::string(msg);
+ gettimeofday(×tamp, NULL);
+ heure_debut = timestamp.tv_sec +(timestamp.tv_usec/1000000.0);
+
+ //fprintf(stderr,"| %-*s |\n",98,msg);
+
+ todo= ntasks;
+ done = 0;
+ partial =0;
+
+ partial_threaded.resize(_nthreads);
+ done_threaded.resize(_nthreads);
+
+ for (int ii=0; ii<_nthreads;ii++) partial_threaded[ii]=0;
+ for (int ii=0; ii<_nthreads;ii++) done_threaded[ii]=0;
+ subdiv= 1000;
+ steps = (double)todo / (double)subdiv;
+
+ if(!timer_mode)
+ {
+ fprintf(stderr,"[");fflush(stderr);
+ }
+ }
+
+ void finish()
+ {
+ set(todo);
+ if(timer_mode)
+ fprintf(stderr,"\n");
+ else
+ fprintf(stderr,"]\n");
+
+ fflush(stderr);
+ todo= 0;
+ done = 0;
+ partial =0;
+
+ }
+ void finish_threaded()// called by only one of the threads
+ {
+ done = 0;
+ double rem = 0;
+ for (int ii=0; ii<_nthreads;ii++) done += (done_threaded[ii] );
+ for (int ii=0; ii<_nthreads;ii++) partial += (partial_threaded[ii] );
+
+ finish();
+
+ }
+ void inc(uint64_t ntasks_done)
+ {
+ done += ntasks_done;
+ partial += ntasks_done;
+
+
+ while(partial >= steps)
+ {
+ if(timer_mode)
+ {
+ gettimeofday(×tamp, NULL);
+ heure_actuelle = timestamp.tv_sec +(timestamp.tv_usec/1000000.0);
+ double elapsed = heure_actuelle - heure_debut;
+ double speed = done / elapsed;
+ double rem = (todo-done) / speed;
+ if(done>todo) rem=0;
+ int min_e = (int)(elapsed / 60) ;
+ elapsed -= min_e*60;
+ int min_r = (int)(rem / 60) ;
+ rem -= min_r*60;
+
+ fprintf(stderr,"%c[%s] %-5.3g%% elapsed: %3i min %-2.0f sec remaining: %3i min %-2.0f sec",13,
+ message.c_str(),
+ 100*(double)done/todo,
+ min_e,elapsed,min_r,rem);
+
+ }
+ else
+ {
+ fprintf(stderr,"-");fflush(stderr);
+ }
+ partial -= steps;
+ }
+
+
+ }
+
+ void inc(uint64_t ntasks_done, int tid) //threads collaborate to this same progress bar
+ {
+ partial_threaded[tid] += ntasks_done;
+ done_threaded[tid] += ntasks_done;
+ while(partial_threaded[tid] >= steps)
+ {
+ if(timer_mode)
+ {
+ struct timeval timet;
+ double now;
+ gettimeofday(&timet, NULL);
+ now = timet.tv_sec +(timet.tv_usec/1000000.0);
+ uint64_t total_done = 0;
+ for (int ii=0; ii<_nthreads;ii++) total_done += (done_threaded[ii] );
+ double elapsed = now - heure_debut;
+ double speed = total_done / elapsed;
+ double rem = (todo-total_done) / speed;
+ if(total_done > todo) rem =0;
+ int min_e = (int)(elapsed / 60) ;
+ elapsed -= min_e*60;
+ int min_r = (int)(rem / 60) ;
+ rem -= min_r*60;
+
+ fprintf(stderr,"%c[%s] %-5.3g%% elapsed: %3i min %-2.0f sec remaining: %3i min %-2.0f sec",13,
+ message.c_str(),
+ 100*(double)total_done/todo,
+ min_e,elapsed,min_r,rem);
+ }
+ else
+ {
+ fprintf(stderr,"-");fflush(stderr);
+ }
+ partial_threaded[tid] -= steps;
+
+ }
+
+ }
+
+ void set(uint64_t ntasks_done) {
+ if (ntasks_done > done)
+ inc(ntasks_done-done);
+ }
+ Progress () : timer_mode(0) {}
+ //include timer, to print ETA ?
+};
+
+
+
+////////////////////////////////////////////////////////////////
+#pragma mark -
+#pragma mark hasher
+////////////////////////////////////////////////////////////////
+
+typedef std::array hash_pair_t;
+
+typedef hash_pair_t internal_hash_t; // ou hash_pair_t directement ? __uint128_t
+
+typedef decltype(std::declval >().begin()) diskit_hash128_t;
+typedef decltype(std::declval< std::vector< internal_hash_t> >().begin()) vectorit_hash128_t;
+
+struct internalHasher {
+ uint64_t operator()(const internal_hash_t& key) const {
+ uint64_t s0 = key[0];
+ uint64_t s1 = key[1];
+ s1 ^= s1 << 23;
+ return (s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26)) + s0;
+ }
+};
+
+template class XorshiftHashFunctors {
+ /* Xorshift128*
+ Written in 2014 by Sebastiano Vigna (vigna@acm.org)
+
+ To the extent possible under law, the author has dedicated all copyright
+ and related and neighboring rights to this software to the public domain
+ worldwide. This software is distributed without any warranty.
+
+ See
+ hash_pair_t hashpair128(const Item& key) const {
+ auto h = singleHasher(key);
+ return { h.first, h.second };
+ }
+
+ //return next hash an update state s
+ uint64_t next(hash_pair_t &s) const {
+ uint64_t s1 = s[0];
+ const uint64_t s0 = s[1];
+ s[0] = s0;
+ s1 ^= s1 << 23; // a
+ return (s[1] = (s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26))) + s0; // b, c
+ }
+
+ private:
+ SingleHasher_t singleHasher;
+};
+
+
+////////////////////////////////////////////////////////////////
+#pragma mark -
+#pragma mark iterators
+////////////////////////////////////////////////////////////////
+
+template
+struct iter_range {
+ iter_range(Iterator b, Iterator e)
+ : m_begin(b), m_end(e) {}
+
+ Iterator begin() const { return m_begin; }
+ Iterator end() const { return m_end; }
+
+ Iterator m_begin, m_end;
+};
+
+template
+iter_range range(Iterator begin, Iterator end) {
+ return iter_range(begin, end);
+}
+
+////////////////////////////////////////////////////////////////
+#pragma mark -
+#pragma mark BitVector
+////////////////////////////////////////////////////////////////
+
+class bitVector {
+
+ public:
+
+ bitVector() : _size(0)
+ {
+ _bitArray = nullptr;
+ }
+
+ bitVector(uint64_t n) : _size(n)
+ {
+ _nchar = (1ULL+n/64ULL);
+ _bitArray = (uint64_t *) calloc (_nchar,sizeof(uint64_t));
+ }
+
+ ~bitVector()
+ {
+ if(_bitArray != nullptr)
+ free(_bitArray);
+ }
+
+ //copy constructor
+ bitVector(bitVector const &r)
+ {
+ _size = r._size;
+ _nchar = r._nchar;
+ _ranks = r._ranks;
+ _bitArray = (uint64_t *) calloc (_nchar,sizeof(uint64_t));
+ memcpy(_bitArray, r._bitArray, _nchar*sizeof(uint64_t) );
+ }
+
+ // Copy assignment operator
+ bitVector &operator=(bitVector const &r)
+ {
+ if (&r != this)
+ {
+ _size = r._size;
+ _nchar = r._nchar;
+ _ranks = r._ranks;
+ if(_bitArray != nullptr)
+ free(_bitArray);
+ _bitArray = (uint64_t *) calloc (_nchar,sizeof(uint64_t));
+ memcpy(_bitArray, r._bitArray, _nchar*sizeof(uint64_t) );
+ }
+ return *this;
+ }
+
+ // Move assignment operator
+ bitVector &operator=(bitVector &&r)
+ {
+ //printf("bitVector move assignment \n");
+ if (&r != this)
+ {
+ if(_bitArray != nullptr)
+ free(_bitArray);
+
+ _size = std::move (r._size);
+ _nchar = std::move (r._nchar);
+ _ranks = std::move (r._ranks);
+ _bitArray = r._bitArray;
+ r._bitArray = nullptr;
+ }
+ return *this;
+ }
+ // Move constructor
+ bitVector(bitVector &&r) : _bitArray ( nullptr),_size(0)
+ {
+ *this = std::move(r);
+ }
+
+
+ void resize(uint64_t newsize)
+ {
+ //printf("bitvector resize from %llu bits to %llu \n",_size,newsize);
+ _nchar = (1ULL+newsize/64ULL);
+ _bitArray = (uint64_t *) realloc(_bitArray,_nchar*sizeof(uint64_t));
+ _size = newsize;
+ }
+
+ size_t size() const
+ {
+ return _size;
+ }
+
+ uint64_t bitSize() const {return (_nchar*64ULL + _ranks.capacity()*64ULL );}
+
+ //clear whole array
+ void clear()
+ {
+ memset(_bitArray,0,_nchar*sizeof(uint64_t));
+ }
+
+ //clear collisions in interval, only works with start and size multiple of 64
+ void clearCollisions(uint64_t start, size_t size, bitVector * cc)
+ {
+ assert( (start & 63) ==0);
+ assert( (size & 63) ==0);
+ uint64_t ids = (start/64ULL);
+ for(uint64_t ii =0; ii< (size/64ULL); ii++ )
+ {
+ _bitArray[ids+ii] = _bitArray[ids+ii] & (~ (cc->get64(ii)) );
+ }
+
+ cc->clear();
+ }
+
+
+ //clear interval, only works with start and size multiple of 64
+ void clear(uint64_t start, size_t size)
+ {
+ assert( (start & 63) ==0);
+ assert( (size & 63) ==0);
+ memset(_bitArray + (start/64ULL),0,(size/64ULL)*sizeof(uint64_t));
+ }
+
+ //for debug purposes
+ void print() const
+ {
+ printf("bit array of size %lli: \n",_size);
+ for(uint64_t ii = 0; ii< _size; ii++)
+ {
+ if(ii%10==0)
+ printf(" (%llu) ",ii);
+ int val = (_bitArray[ii >> 6] >> (ii & 63 ) ) & 1;
+ printf("%i",val);
+ }
+ printf("\n");
+
+ printf("rank array : size %lu \n",_ranks.size());
+ for (uint64_t ii = 0; ii< _ranks.size(); ii++)
+ {
+ printf("%llu : %lli, ",ii,_ranks[ii]);
+ }
+ printf("\n");
+ }
+
+ // return value at pos
+ uint64_t operator[](uint64_t pos) const {
+ //unsigned char * _bitArray8 = (unsigned char *) _bitArray;
+ //return (_bitArray8[pos >> 3ULL] >> (pos & 7 ) ) & 1;
+ return (_bitArray[pos >> 6ULL] >> (pos & 63)) & 1;
+ }
+
+ //atomically return old val and set to 1
+ uint64_t atomic_test_and_set(uint64_t pos) {
+ uint64_t oldval = __sync_fetch_and_or(_bitArray + (pos >> 6), (uint64_t) (1ULL << (pos & 63)) );
+ return (oldval >> (pos & 63)) & 1;
+ }
+
+
+ uint64_t get(uint64_t pos) const {
+ return (*this)[pos];
+ }
+
+ uint64_t get64(uint64_t cell64) const {
+ return _bitArray[cell64];
+ }
+
+ //set bit pos to 1
+ void set(uint64_t pos) {
+ assert(pos<_size);
+ //_bitArray [pos >> 6] |= (1ULL << (pos & 63) ) ;
+ __sync_fetch_and_or (_bitArray + (pos >> 6ULL), (1ULL << (pos & 63)) );
+ }
+
+ //set bit pos to 0
+ void reset(uint64_t pos) {
+ //_bitArray [pos >> 6] &= ~(1ULL << (pos & 63) ) ;
+ __sync_fetch_and_and (_bitArray + (pos >> 6ULL), ~(1ULL << (pos & 63) ));
+ }
+
+ // return value of last rank
+ // add offset to all ranks computed
+ uint64_t build_ranks(uint64_t offset = 0) {
+ _ranks.reserve(2 + _size/_nb_bits_per_rank_sample);
+
+ uint64_t curent_rank = offset;
+ for (size_t ii = 0; ii < _nchar; ii++) {
+ if (((ii*64) % _nb_bits_per_rank_sample) == 0) {
+ _ranks.push_back(curent_rank);
+ }
+ curent_rank += popcount_64(_bitArray[ii]);
+ }
+
+ return curent_rank;
+ }
+
+ uint64_t rank(uint64_t pos) const {
+ uint64_t word_idx = pos / 64ULL;
+ uint64_t word_offset = pos % 64;
+ uint64_t block = pos / _nb_bits_per_rank_sample;
+ uint64_t r = _ranks[block];
+ for (uint64_t w = block * _nb_bits_per_rank_sample / 64; w < word_idx; ++w)
+ r += popcount_64(_bitArray[w]);
+ uint64_t mask = (uint64_t(1) << word_offset ) - 1;
+ r += popcount_64( _bitArray[word_idx] & mask);
+
+ return r;
+ }
+
+
+
+ void save(std::ostream& os) const {
+ os.write(reinterpret_cast(&_size), sizeof(_size));
+ os.write(reinterpret_cast(&_nchar), sizeof(_nchar));
+ os.write(reinterpret_cast(_bitArray), (std::streamsize)(sizeof(uint64_t) * _nchar));
+ size_t sizer = _ranks.size();
+ os.write(reinterpret_cast(&sizer), sizeof(size_t));
+ os.write(reinterpret_cast(_ranks.data()), (std::streamsize)(sizeof(_ranks[0]) * _ranks.size()));
+ }
+
+ void load(std::istream& is) {
+ is.read(reinterpret_cast(&_size), sizeof(_size));
+ is.read(reinterpret_cast(&_nchar), sizeof(_nchar));
+ this->resize(_size);
+ is.read(reinterpret_cast(_bitArray), (std::streamsize)(sizeof(uint64_t) * _nchar));
+
+ size_t sizer;
+ is.read(reinterpret_cast(&sizer), sizeof(size_t));
+ _ranks.resize(sizer);
+ is.read(reinterpret_cast(_ranks.data()), (std::streamsize)(sizeof(_ranks[0]) * _ranks.size()));
+ }
+
+
+ protected:
+ uint64_t* _bitArray;
+ //uint64_t* _bitArray;
+ uint64_t _size;
+ uint64_t _nchar;
+
+ // epsilon = 64 / _nb_bits_per_rank_sample bits
+ // additional size for rank is epsilon * _size
+ static const uint64_t _nb_bits_per_rank_sample = 512; //512 seems ok
+ std::vector _ranks;
+};
+
+////////////////////////////////////////////////////////////////
+#pragma mark -
+#pragma mark level
+////////////////////////////////////////////////////////////////
+
+
+static inline uint64_t fastrange64(uint64_t word, uint64_t p) {
+ //return word % p;
+ return (uint64_t)(((__uint128_t)word * (__uint128_t)p) >> 64);
+}
+
+class level{
+ public:
+ level() {}
+
+ ~level() {}
+
+ uint64_t get(uint64_t hash_raw) const {
+ // uint64_t hashi = hash_raw % hash_domain; //
+ //uint64_t hashi = (uint64_t)( ((__uint128_t) hash_raw * (__uint128_t) hash_domain) >> 64ULL);
+ uint64_t hashi = fastrange64(hash_raw,hash_domain);
+ return bitset.get(hashi);
+ }
+
+ uint64_t idx_begin;
+ uint64_t hash_domain;
+ bitVector bitset;
+};
+
+
+////////////////////////////////////////////////////////////////
+#pragma mark -
+#pragma mark mphf
+////////////////////////////////////////////////////////////////
+
+#define NBBUFF 10000
+//#define NBBUFF 2
+
+template
+struct thread_args {
+ void * boophf;
+ Range const * range;
+ std::shared_ptr it_p; /* used to be "Iterator it" but because of fastmode, iterator is polymorphic; TODO: think about whether it should be a unique_ptr actually */
+ std::shared_ptr until_p; /* to cache the "until" variable */
+ int level;
+};
+
+//forward declaration
+
+template
+void * thread_processLevel(void * args);
+
+/* Hasher_t returns a single hash when operator()(elem_t key) is called.
+ if used with XorshiftHashFunctors, it must have the following operator: operator()(elem_t key, uint64_t seed) */
+template
+class mphf {
+ /* this mechanisms gets P hashes out of Hasher_t */
+ typedef XorshiftHashFunctors MultiHasher_t ;
+
+ public:
+ mphf()
+ : _built(false) {}
+
+ ~mphf() {}
+
+ // allow perc_elem_loaded elements to be loaded in ram for faster construction (default 3%), set to 0 to desactivate
+ template
+ mphf(size_t n, const Range &input_range,
+ int num_thread = 1,
+ double gamma = 2.0,
+ bool writeEach = true, bool progress =true, float perc_elem_loaded = 0.03)
+ :
+ _nb_levels(0), _gamma(gamma), _hash_domain(size_t(ceil(double(n) * gamma))), _nelem(n), _num_thread(num_thread), _percent_elem_loaded_for_fastMode (perc_elem_loaded), _withprogress(progress) {
+ if (n ==0)
+ return;
+
+ _fastmode = false;
+ if (_percent_elem_loaded_for_fastMode > 0.0)
+ _fastmode =true;
+
+ if (writeEach) {
+ _writeEachLevel =true;
+ _fastmode = false;
+ } else {
+ _writeEachLevel = false;
+ }
+
+ setup();
+
+ if (_withprogress) {
+ _progressBar.timer_mode=1;
+
+ double total_raw = _nb_levels;
+
+ double sum_geom_read = ( 1.0 / (1.0 - _proba_collision));
+ double total_writeEach = sum_geom_read + 1.0;
+
+ double total_fastmode_ram = (_fastModeLevel+1) + ( pow(_proba_collision,_fastModeLevel)) * (_nb_levels-(_fastModeLevel+1)) ;
+
+ printf("for info, total work write each : %.3f total work inram from level %i : %.3f total work raw : %.3f \n",total_writeEach,_fastModeLevel,total_fastmode_ram,total_raw);
+
+ if(writeEach)
+ {
+ _progressBar.init(_nelem * total_writeEach, "Building BooPHF",num_thread);
+ }
+ else if(_fastmode)
+ _progressBar.init( _nelem * total_fastmode_ram, "Building BooPHF",num_thread);
+ else
+ _progressBar.init( _nelem * _nb_levels ,"Building BooPHF",num_thread);
+ }
+
+ uint64_t offset = 0;
+ for(int ii = 0; ii< _nb_levels; ii++)
+ {
+ _tempBitset = new bitVector(_levels[ii].hash_domain); // temp collision bitarray for this level
+
+ processLevel(input_range,ii);
+
+ _levels[ii].bitset.clearCollisions(0 , _levels[ii].hash_domain , _tempBitset);
+
+ offset = _levels[ii].bitset.build_ranks(offset);
+
+ delete _tempBitset;
+ }
+
+ if(_withprogress)
+ _progressBar.finish_threaded();
+
+
+ _lastbitsetrank = offset ;
+
+ //printf("used temp ram for construction : %lli MB \n",setLevelFastmode.capacity()* sizeof(elem_t) /1024ULL/1024ULL);
+
+ std::vector().swap(setLevelFastmode); // clear setLevelFastmode reallocating
+
+
+ pthread_mutex_destroy(&_mutex);
+
+ _built = true;
+ }
+
+
+ template
+ uint64_t lookup(elem_t elem) {
+ if (!_built) return ULLONG_MAX;
+
+ //auto hashes = _hasher(elem);
+ uint64_t non_minimal_hp,minimal_hp;
+ int level;
+
+ hash_pair_t bbhash = _hasher.hashpair128(elem);
+ uint64_t level_hash = getLevel(bbhash, elem, &level);
+
+ if (level == (_nb_levels-1)) {
+ //auto in_final_map = _final_hash.find (elem);
+ auto in_final_map = _final_hash.find(bbhash);
+ if (in_final_map == _final_hash.end()) {
+ //elem was not in orignal set of keys
+ return ULLONG_MAX; // means elem not in set
+ } else {
+ minimal_hp = in_final_map->second + _lastbitsetrank;
+ //printf("lookup %llu level %i --> %llu \n",elem,level,minimal_hp);
+ return minimal_hp;
+ }
+ // minimal_hp = _final_hash[elem] + _lastbitsetrank;
+ // return minimal_hp;
+ } else {
+ //non_minimal_hp = level_hash % _levels[level].hash_domain; // in fact non minimal hp would be + _levels[level]->idx_begin
+ non_minimal_hp = fastrange64(level_hash,_levels[level].hash_domain);
+ }
+ minimal_hp = _levels[level].bitset.rank(non_minimal_hp);
+ // printf("lookup %llu level %i --> %llu \n",elem,level,minimal_hp);
+
+ return minimal_hp;
+ }
+
+ uint64_t size() const {
+ return _nelem;
+ }
+
+ uint64_t mem_size() const {
+ uint64_t totalsizeBitset = 0;
+ for (int ii = 0; ii < _nb_levels; ii++)
+ totalsizeBitset += _levels[ii].bitset.bitSize();
+
+ uint64_t totalsize = totalsizeBitset + _final_hash.size()*42*8 ; // unordered map takes approx 42B per elem [personal test] (42B with uint64_t key, would be larger for other type of elem)
+
+ /*
+ printf("Bitarray %12llu bits (%.2f %%) (array + ranks )\n",
+ totalsizeBitset, 100*(float)totalsizeBitset/totalsize);
+ printf("final hash %12lu bits (%.2f %%) (nb in final hash %lu)\n",
+ _final_hash.size()*42*8, 100*(float)(_final_hash.size()*42*8)/totalsize,
+ _final_hash.size() );
+ */
+
+ return totalsize / 8;
+ }
+
+ template void fillBuffer(std::vector &buffer, std::shared_ptr shared_it, std::shared_ptr until_p,
+ uint64_t &inbuff, bool & isRunning) {
+ auto until = *until_p;
+ pthread_mutex_lock(&_mutex);
+ for (; inbuff &buffer,
+ std::shared_ptr shared_it, std::shared_ptr until_p, uint64_t & inbuff, bool & isRunning) {
+ fillBufferCommon128(buffer,shared_it,until_p,inbuff,isRunning);
+ }
+ void fillBuffer (std::vector & buffer,std::shared_ptr shared_it, std::shared_ptr until_p,uint64_t & inbuff, bool & isRunning) {
+ fillBufferCommon128(buffer,shared_it,until_p,inbuff,isRunning);
+ }
+
+ template void fillBufferCommon128(std::vector & buffer,std::shared_ptr shared_it, std::shared_ptr until_p,
+ uint64_t &inbuff, bool &isRunning) {
+ auto until = *until_p;
+ pthread_mutex_lock(&_mutex);
+ for (; inbuff //typename Range,
+ void pthread_processLevel(std::vector &buffer, std::shared_ptr shared_it, std::shared_ptr until_p, int i) {
+ uint64_t nb_done =0;
+ int tid = __sync_fetch_and_add (&_nb_living, 1);
+ uint64_t inbuff =0;
+
+ uint64_t writebuff =0;
+ std::vector< internal_hash_t > & myWriteBuff = bufferperThread[tid];
+ for (bool isRunning=true; isRunning ; ) {
+ //safely copy n items into buffer
+ //call to specialized function accordin to iterator type (may be iterator over keys (first 2 levels), or iterator over 128 bit hashes)
+ fillBuffer(buffer,shared_it,until_p,inbuff,isRunning);
+
+ //do work on the n elems of the buffer
+ for (uint64_t ii=0; ii= setLevelFastmode.size())
+ _fastmode = false;
+ else
+ setLevelFastmode[idxl2] = val; // create set for fast mode
+ }
+
+ //insert to level i+1 : either next level of the cascade or final hash if last level reached
+ if(i == _nb_levels-1) //stop cascade here, insert into exact hash
+ {
+
+ uint64_t hashidx = __sync_fetch_and_add(&_hashidx, 1);
+
+ pthread_mutex_lock(&_mutex); //see later if possible to avoid this, mais pas bcp item vont la
+ // calc rank de fin precedent level qq part, puis init hashidx avec ce rank, direct minimal, pas besoin inser ds bitset et rank
+
+ if (_final_hash.count(val)) // key already in final hash
+ {
+ fprintf(stderr,"The impossible happened : collision on 128 bit hashes... please switch to safe branch, and play the lottery.");
+ fprintf(stderr,"Another more likely explanation might be that you have duplicate keys in your input.\
+ If so, you can ignore this message, but be aware that too many duplicate keys will increase ram usage\n");
+ }
+ _final_hash[val] = hashidx;
+
+
+ pthread_mutex_unlock(&_mutex);
+ }
+ else
+ {
+
+ //ils ont reach ce level
+ //insert elem into curr level on disk --> sera utilise au level+1 , (mais encore besoin filtre)
+
+ if(_writeEachLevel && i > 0 && i < _nb_levels -1)
+ {
+ if(writebuff>=NBBUFF)
+ {
+ //flush buffer
+ flockfile(_currlevelFile);
+ fwrite(myWriteBuff.data(),sizeof(internal_hash_t),writebuff,_currlevelFile);
+ funlockfile(_currlevelFile);
+ writebuff = 0;
+
+ }
+
+ myWriteBuff[writebuff++] = val;
+
+ }
+
+
+
+ //#ifdef PDEBUG
+ // printf("inserting into level %i ",i);
+ //#endif
+
+
+ // computes next hash
+ if (level == 0)
+ level_hash = bbhash[0];
+ else if (level == 1)
+ level_hash = bbhash[1];
+ else
+ level_hash = _hasher.next(bbhash);
+ insertIntoLevel(level_hash,i); //should be safe
+ }
+ }
+
+ nb_done++;
+ if ((nb_done&1023) ==0 && _withprogress) {_progressBar.inc(nb_done,tid);nb_done=0; }
+
+ }
+
+ inbuff = 0;
+ }
+
+ if(_writeEachLevel && writebuff>0) {
+ //flush buffer
+ flockfile(_currlevelFile);
+ fwrite(myWriteBuff.data(),sizeof(internal_hash_t),writebuff,_currlevelFile);
+ funlockfile(_currlevelFile);
+ writebuff = 0;
+ }
+
+ }
+
+
+ void save(std::ostream& os) const {
+ os.write(reinterpret_cast(&_gamma), sizeof(_gamma));
+ os.write(reinterpret_cast(&_nb_levels), sizeof(_nb_levels));
+ os.write(reinterpret_cast(&_lastbitsetrank), sizeof(_lastbitsetrank));
+ os.write(reinterpret_cast(&_nelem), sizeof(_nelem));
+ for(int ii=0; ii<_nb_levels; ii++)
+ {
+ _levels[ii].bitset.save(os);
+ }
+
+ //save final hash
+ size_t final_hash_size = _final_hash.size();
+
+ os.write(reinterpret_cast(&final_hash_size), sizeof(size_t));
+
+ for (auto it = _final_hash.begin(); it != _final_hash.end(); ++it )
+ {
+ os.write(reinterpret_cast(&(it->first)), sizeof(internal_hash_t));
+ os.write(reinterpret_cast(&(it->second)), sizeof(uint64_t));
+ }
+
+ }
+
+ void load(std::istream& is) {
+ is.read(reinterpret_cast(&_gamma), sizeof(_gamma));
+ is.read(reinterpret_cast(&_nb_levels), sizeof(_nb_levels));
+ is.read(reinterpret_cast(&_lastbitsetrank), sizeof(_lastbitsetrank));
+ is.read(reinterpret_cast(&_nelem), sizeof(_nelem));
+
+ _levels.resize(_nb_levels);
+
+
+ for(int ii=0; ii<_nb_levels; ii++)
+ {
+ //_levels[ii].bitset = new bitVector();
+ _levels[ii].bitset.load(is);
+ }
+
+
+
+ //mini setup, recompute size of each level
+ _proba_collision = 1.0 - pow(((_gamma*(double)_nelem -1 ) / (_gamma*(double)_nelem)),_nelem-1);
+ uint64_t previous_idx =0;
+ _hash_domain = (size_t) (ceil(double(_nelem) * _gamma)) ;
+ for(int ii=0; ii<_nb_levels; ii++)
+ {
+ //_levels[ii] = new level();
+ _levels[ii].idx_begin = previous_idx;
+ _levels[ii].hash_domain = (( (uint64_t) (_hash_domain * pow(_proba_collision,ii)) + 63) / 64 ) * 64;
+ if(_levels[ii].hash_domain == 0 )
+ _levels[ii].hash_domain = 64 ;
+ previous_idx += _levels[ii].hash_domain;
+ }
+
+ //restore final hash
+
+ _final_hash.clear();
+ size_t final_hash_size ;
+
+ is.read(reinterpret_cast(&final_hash_size), sizeof(size_t));
+
+ for(unsigned int ii=0; ii(&key), sizeof(internal_hash_t));
+ is.read(reinterpret_cast(&value), sizeof(uint64_t));
+
+ _final_hash[key] = value;
+ }
+ _built = true;
+ }
+
+
+ private :
+
+ void setup()
+ {
+ pthread_mutex_init(&_mutex, NULL);
+
+ _pid = getpid() + printPt(pthread_self()) ;// + pthread_self();
+ //printf("pt self %llu pid %i \n",printPt(pthread_self()),_pid);
+
+ _cptTotalProcessed=0;
+
+
+ if(_fastmode)
+ {
+ setLevelFastmode.resize(_percent_elem_loaded_for_fastMode * (double)_nelem );
+ }
+
+
+ bufferperThread.resize(_num_thread);
+ if(_writeEachLevel)
+ {
+ for(int ii=0; ii<_num_thread; ii++)
+ {
+ bufferperThread[ii].resize(NBBUFF);
+ }
+ }
+
+ _proba_collision = 1.0 - pow(((_gamma*(double)_nelem -1 ) / (_gamma*(double)_nelem)),_nelem-1);
+
+ double sum_geom =_gamma * ( 1.0 + _proba_collision / (1.0 - _proba_collision));
+ //printf("proba collision %f sum_geom %f \n",_proba_collision,sum_geom);
+
+ _nb_levels = 25; // 25
+ _levels.resize(_nb_levels);
+
+ //build levels
+ uint64_t previous_idx =0;
+ for(int ii=0; ii<_nb_levels; ii++)
+ {
+
+ _levels[ii].idx_begin = previous_idx;
+
+ // round size to nearest superior multiple of 64, makes it easier to clear a level
+ _levels[ii].hash_domain = (( (uint64_t) (_hash_domain * pow(_proba_collision,ii)) + 63) / 64 ) * 64;
+ if(_levels[ii].hash_domain == 0 ) _levels[ii].hash_domain = 64 ;
+ previous_idx += _levels[ii].hash_domain;
+
+ //printf("build level %i bit array : start %12llu, size %12llu ",ii,_levels[ii]->idx_begin,_levels[ii]->hash_domain );
+ //printf(" expected elems : %.2f %% total \n",100.0*pow(_proba_collision,ii));
+
+ }
+
+ for(int ii=0; ii<_nb_levels; ii++)
+ {
+ if(pow(_proba_collision,ii) < _percent_elem_loaded_for_fastMode)
+ {
+ _fastModeLevel = ii;
+ //printf("fast mode level : %i \n",ii);
+ break;
+ }
+ }
+ }
+
+ //overload getLevel with either elem_t or internal_hash_t
+ template
+ uint64_t getLevel(hash_pair_t bbhash, elem_t val, int *res_level, int maxlevel = 100, int minlevel = 0) const {
+ int level = 0;
+ uint64_t hash_raw=0;
+
+ for (int ii = 0; ii < (_nb_levels-1) && ii < maxlevel ; ii++) {
+ //calc le hash suivant
+ if (ii == 0)
+ hash_raw = bbhash[0];
+ else if (ii == 1)
+ hash_raw = bbhash[1];
+ else
+ hash_raw = _hasher.next(bbhash);
+
+ if (ii >= minlevel && _levels[ii].get(hash_raw))
+ break;
+
+ level++;
+ }
+
+ *res_level = level;
+ return hash_raw;
+ }
+
+
+ // compute level and returns hash of last level reached
+ // FIXME: The usage of getLevel here is *super* confusing, really.
+ uint64_t getLevel(internal_hash_t &bbhash,int * res_level, int maxlevel = 100, int minlevel =0) const {
+ int level = 0;
+ uint64_t hash_raw=0;
+
+ for (int ii = 0; ii<(_nb_levels-1) && ii < maxlevel ; ii++) {
+ //calc le hash suivant
+ if (ii == 0)
+ hash_raw = bbhash[0];
+ else if (ii == 1)
+ hash_raw = bbhash[1];
+ else
+ hash_raw = _hasher.next(bbhash);
+
+ if (ii >= minlevel && _levels[ii].get(hash_raw))
+ break;
+
+ level++;
+ }
+
+ *res_level = level;
+ return hash_raw;
+ }
+
+
+ //insert into bitarray
+ void insertIntoLevel(uint64_t level_hash, int i) {
+ // uint64_t hashl = level_hash % _levels[i].hash_domain;
+ uint64_t hashl = fastrange64( level_hash,_levels[i].hash_domain);
+
+ //#ifdef PDEBUG
+ // printf(" : %llu / %llu \n ",hashl,_levels[i].hash_domain);
+ //#endif
+
+ if (_levels[i].bitset.atomic_test_and_set(hashl))
+ _tempBitset->atomic_test_and_set(hashl);
+ }
+
+ //loop to insert into level i
+ template
+ void processLevel(Range const& input_range,int i) {
+ ////alloc the bitset for this level
+ _levels[i].bitset = bitVector(_levels[i].hash_domain);
+
+ //printf("---process level %i wr %i fast %i ---\n",i,_writeEachLevel,_fastmode);
+
+ char fname_old[1000];
+ sprintf(fname_old,"temp_p%i_level_%i",_pid,i-2);
+
+ char fname_curr[1000];
+ sprintf(fname_curr,"temp_p%i_level_%i",_pid,i);
+
+ char fname_prev[1000];
+ sprintf(fname_prev,"temp_p%i_level_%i",_pid,i-1);
+
+ if (_writeEachLevel) {
+ //file management :
+ if(i>2) //delete previous file
+ {
+ unlink(fname_old);
+ }
+
+ if(i< _nb_levels-1 && i > 0 ) //create curr file
+ {
+ _currlevelFile = fopen(fname_curr,"w");
+ }
+ }
+
+
+ _cptLevel = 0;
+ _hashidx = 0;
+ _idxLevelsetLevelFastmode =0;
+ _nb_living =0;
+ //create threads
+ pthread_t *tab_threads= new pthread_t [_num_thread];
+ typedef decltype(input_range.begin()) it_type;
+ thread_args t_arg; // meme arg pour tous
+ t_arg.boophf = this;
+ t_arg.range = &input_range;
+ t_arg.it_p = std::static_pointer_cast(std::make_shared(input_range.begin()));
+ t_arg.until_p = std::static_pointer_cast(std::make_shared(input_range.end()));
+
+ t_arg.level = i;
+
+ if (_writeEachLevel && (i > 1)) {
+
+ auto data_iterator_level = file_binary(fname_prev);
+
+ //typedef decltype(data_iterator_level.begin()) disklevel_it_type;
+ //diskit_hash128_t
+
+ //data_iterator_level.begin();
+
+ t_arg.it_p = std::static_pointer_cast(std::make_shared(data_iterator_level.begin()));
+ t_arg.until_p = std::static_pointer_cast(std::make_shared(data_iterator_level.end()));
+
+ for (int ii=0;ii<_num_thread;ii++)
+ pthread_create(&tab_threads[ii], NULL, thread_processLevel, &t_arg); //&t_arg[ii]
+
+
+ //must join here before the block is closed and file_binary is destroyed (and closes the file)
+ for(int ii=0;ii<_num_thread;ii++)
+ {
+ pthread_join(tab_threads[ii], NULL);
+ }
+
+ } else {
+ if (_fastmode && i >= (_fastModeLevel+1)) {
+ // we'd like to do t_arg.it = data_iterator.begin() but types are different;
+ // so, casting to (void*) because of that; and we remember the type in the template
+ // typedef decltype(setLevelFastmode.begin()) fastmode_it_type; // vectorit_hash128_t
+ t_arg.it_p = std::static_pointer_cast(std::make_shared(setLevelFastmode.begin()));
+ t_arg.until_p = std::static_pointer_cast(std::make_shared(setLevelFastmode.end()));
+
+ // we'd like to do t_arg.it = data_iterator.begin() but types are different;
+ // so, casting to (void*) because of that; and we remember the type in the template
+
+ for (int ii=0;ii<_num_thread;ii++)
+ pthread_create (&tab_threads[ii], NULL, thread_processLevel, &t_arg); //&t_arg[ii]
+
+ } else {
+ //printf(" _ _ basic mode \n");
+ for(int ii=0;ii<_num_thread;ii++)
+ pthread_create (&tab_threads[ii], NULL, thread_processLevel, &t_arg); //&t_arg[ii]
+ }
+ //joining
+ for(int ii=0;ii<_num_thread;ii++)
+ {
+ pthread_join(tab_threads[ii], NULL);
+ }
+ }
+
+#ifdef CCDEBUG
+ printf("\ngoing to level %i : %llu elems %.2f %% expected : %.2f %% \n",i,_cptLevel,100.0* _cptLevel/(float)_nelem,100.0* pow(_proba_collision,i) );
+#endif
+ //printf("\ncpt total processed %llu \n",_cptTotalProcessed);
+ if(_fastmode && i == _fastModeLevel) //shrink to actual number of elements in set
+ {
+ //printf("\nresize setLevelFastmode to %lli \n",_idxLevelsetLevelFastmode);
+ setLevelFastmode.resize(_idxLevelsetLevelFastmode);
+ }
+ delete [] tab_threads;
+
+ if(_writeEachLevel)
+ {
+ if(i< _nb_levels-1 && i>0)
+ {
+ fflush(_currlevelFile);
+ fclose(_currlevelFile);
+ }
+
+ if(i== _nb_levels- 1) //delete last file
+ {
+ unlink(fname_prev);
+ }
+ }
+
+ }
+
+ private:
+ std::vector _levels;
+ int _nb_levels;
+ MultiHasher_t _hasher;
+ bitVector * _tempBitset;
+
+ double _gamma;
+ uint64_t _hash_domain;
+ uint64_t _nelem;
+ std::unordered_map _final_hash; // internalHasher Hasher_t
+ Progress _progressBar;
+ int _nb_living;
+ int _num_thread;
+ uint64_t _hashidx;
+ double _proba_collision;
+ uint64_t _lastbitsetrank;
+ uint64_t _idxLevelsetLevelFastmode;
+ uint64_t _cptLevel;
+ uint64_t _cptTotalProcessed;
+
+ // fast build mode , requires that _percent_elem_loaded_for_fastMode % elems are loaded in ram
+ float _percent_elem_loaded_for_fastMode ;
+ bool _fastmode;
+ std::vector< internal_hash_t > setLevelFastmode;
+ // std::vector< internal_hash_t > setLevelFastmode_next; // todo shrinker le set e nram a chaque niveau ?
+
+ std::vector< std::vector< internal_hash_t > > bufferperThread;
+
+ int _fastModeLevel;
+ bool _withprogress;
+ bool _built;
+ bool _writeEachLevel;
+ FILE * _currlevelFile;
+ int _pid;
+ public:
+ pthread_mutex_t _mutex;
+};
+
+////////////////////////////////////////////////////////////////
+#pragma mark -
+#pragma mark threading
+////////////////////////////////////////////////////////////////
+
+template
+void *thread_processLevel(void * args) {
+ if (args ==NULL) return NULL;
+
+ thread_args *targ = (thread_args*) args;
+ mphf * obw = (mphf *) targ->boophf;
+ int level = targ->level;
+ std::vector buffer;
+ buffer.resize(NBBUFF);
+
+ pthread_mutex_t * mutex = & obw->_mutex;
+
+ pthread_mutex_lock(mutex); // from comment above: "//get starting iterator for this thread, must be protected (must not be currently used by other thread to copy elems in buff)"
+ std::shared_ptr startit = std::static_pointer_cast(targ->it_p);
+ std::shared_ptr until_p = std::static_pointer_cast(targ->until_p);
+ pthread_mutex_unlock(mutex);
+
+ obw->pthread_processLevel(buffer, startit, until_p, level);
+
+ return NULL;
+}
+}
diff -Nru spades-3.10.1+dfsg/ext/include/ConsensusCore/Feature.hpp spades-3.11.1+dfsg/ext/include/ConsensusCore/Feature.hpp
--- spades-3.10.1+dfsg/ext/include/ConsensusCore/Feature.hpp 2017-02-28 14:55:42.000000000 +0000
+++ spades-3.11.1+dfsg/ext/include/ConsensusCore/Feature.hpp 1970-01-01 00:00:00.000000000 +0000
@@ -1,166 +0,0 @@
-// Copyright (c) 2011-2013, Pacific Biosciences of California, Inc.
-//
-// All rights reserved.
-//
-// Redistribution and use in source and binary forms, with or without
-// modification, are permitted (subject to the limitations in the
-// disclaimer below) provided that the following conditions are met:
-//
-// * Redistributions of source code must retain the above copyright
-// notice, this list of conditions and the following disclaimer.
-//
-// * Redistributions in binary form must reproduce the above
-// copyright notice, this list of conditions and the following
-// disclaimer in the documentation and/or other materials provided
-// with the distribution.
-//
-// * Neither the name of Pacific Biosciences nor the names of its
-// contributors may be used to endorse or promote products derived
-// from this software without specific prior written permission.
-//
-// NO EXPRESS OR IMPLIED LICENSES TO ANY PARTY'S PATENT RIGHTS ARE
-// GRANTED BY THIS LICENSE. THIS SOFTWARE IS PROVIDED BY PACIFIC
-// BIOSCIENCES AND ITS CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
-// WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
-// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-// DISCLAIMED. IN NO EVENT SHALL PACIFIC BIOSCIENCES OR ITS
-// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
-// USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
-// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
-// OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
-// SUCH DAMAGE.
-
-// Author: David Alexander
-
-#pragma once
-
-#include
-#include
-#include
-#include
-#include
-#include
-#include
-
-#include "Types.hpp"
-
-namespace ConsensusCore
-{
- // Feature/Features object usage caveats:
- // - Feature and Features objects _must_ be stored by value, not reference
- // - The underlying array must be allocated using new[]
- template
- class Feature : private boost::shared_array
- {
- public:
- // \brief Allocate a new feature object, copying content from ptr.
- Feature(const T* ptr, int length)
- : boost::shared_array(new T[length]),
- length_(length)
- {
- assert(length >= 0);
- std::copy(ptr, ptr + length, get());
- }
-
- // \brief Allocate and zero-fill a new feature object of given length.
- explicit Feature(int length)
- : boost::shared_array(new T[length]()),
- length_(length)
- {
- assert(length >= 0);
- }
-
- int Length() const
- {
- return length_;
- }
-
- const T& operator[](int i) const
- {
- return this->boost::shared_array::operator[](i);
- }
-
- T& operator[](int i)
- {
- return this->boost::shared_array::operator[](i);
- }
-
- T ElementAt(int i) const
- {
- return (*this)[i];
- }
-
- private:
- int length_;
-
-#ifndef SWIG
- public:
- T* get()
- {
- return this->boost::shared_array::get();
- }
-
- const T* get() const
- {
- return this->boost::shared_array::get();
- }
-
- operator std::string() const;
-#endif // !SWIG
- };
-
-
-#ifndef SWIG
- //
- // Support for boost::foreach
- //
- template
- inline const T* range_begin(const Feature& f)
- {
- return f.get();
- }
-
- template
- inline const T* range_end(const Feature& f)
- {
- return f.get() + f.Length();
- }
-
- template
- inline T* range_begin(Feature& f) // NOLINT
- {
- return f.get();
- }
-
- template
- inline T* range_end(Feature& f) // NOLINT
- {
- return f.get() + f.Length();
- }
-#endif // !SWIG
-
- typedef Feature FloatFeature;
- typedef Feature CharFeature;
- typedef Feature IntFeature;
-}
-
-
-#ifndef SWIG
-namespace boost
-{
- template
- struct range_const_iterator >
- {
- typedef const T* type;
- };
-
- template
- struct range_mutable_iterator >
- {
- typedef T* type;
- };
-}
-#endif // !SWIG
diff -Nru spades-3.10.1+dfsg/ext/include/ConsensusCore/Features.hpp spades-3.11.1+dfsg/ext/include/ConsensusCore/Features.hpp
--- spades-3.10.1+dfsg/ext/include/ConsensusCore/Features.hpp 2017-02-28 14:55:42.000000000 +0000
+++ spades-3.11.1+dfsg/ext/include/ConsensusCore/Features.hpp 1970-01-01 00:00:00.000000000 +0000
@@ -1,68 +0,0 @@
-// Copyright (c) 2011-2013, Pacific Biosciences of California, Inc.
-//
-// All rights reserved.
-//
-// Redistribution and use in source and binary forms, with or without
-// modification, are permitted (subject to the limitations in the
-// disclaimer below) provided that the following conditions are met:
-//
-// * Redistributions of source code must retain the above copyright
-// notice, this list of conditions and the following disclaimer.
-//
-// * Redistributions in binary form must reproduce the above
-// copyright notice, this list of conditions and the following
-// disclaimer in the documentation and/or other materials provided
-// with the distribution.
-//
-// * Neither the name of Pacific Biosciences nor the names of its
-// contributors may be used to endorse or promote products derived
-// from this software without specific prior written permission.
-//
-// NO EXPRESS OR IMPLIED LICENSES TO ANY PARTY'S PATENT RIGHTS ARE
-// GRANTED BY THIS LICENSE. THIS SOFTWARE IS PROVIDED BY PACIFIC
-// BIOSCIENCES AND ITS CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
-// WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
-// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-// DISCLAIMED. IN NO EVENT SHALL PACIFIC BIOSCIENCES OR ITS
-// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
-// USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
-// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
-// OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
-// SUCH DAMAGE.
-
-// Author: David Alexander
-
-#pragma once
-
-#include
-#include
-#include
-#include
-#include
-
-#include "Feature.hpp"
-#include "Types.hpp"
-
-namespace ConsensusCore
-{
- /// \brief An object containing observed features from a sequencing run.
- struct SequenceFeatures
- {
- public:
- explicit SequenceFeatures(const std::string& seq);
- int Length() const { return sequence_.Length(); }
- Feature Sequence() const { return sequence_; }
-
- /// Access to the sequence bases
- const char& operator[] (int i) const { return sequence_[i]; }
- char ElementAt(int i) const { return (*this)[i]; }
-
-
- private:
- Feature sequence_;
- };
-}
-
diff -Nru spades-3.10.1+dfsg/ext/include/ConsensusCore/Matrix/SparseMatrix-inl.hpp spades-3.11.1+dfsg/ext/include/ConsensusCore/Matrix/SparseMatrix-inl.hpp
--- spades-3.10.1+dfsg/ext/include/ConsensusCore/Matrix/SparseMatrix-inl.hpp 2017-02-28 14:55:42.000000000 +0000
+++ spades-3.11.1+dfsg/ext/include/ConsensusCore/Matrix/SparseMatrix-inl.hpp 2017-09-28 09:05:19.000000000 +0000
@@ -38,7 +38,6 @@
#pragma once
#include
-#include
#include
#include
diff -Nru spades-3.10.1+dfsg/ext/include/ConsensusCore/Poa/PoaGraph.hpp spades-3.11.1+dfsg/ext/include/ConsensusCore/Poa/PoaGraph.hpp
--- spades-3.10.1+dfsg/ext/include/ConsensusCore/Poa/PoaGraph.hpp 2017-02-28 14:55:42.000000000 +0000
+++ spades-3.11.1+dfsg/ext/include/ConsensusCore/Poa/PoaGraph.hpp 2017-09-28 09:05:19.000000000 +0000
@@ -37,10 +37,10 @@
#pragma once
-#include
#include
#include
#include
+#include
#include "Types.hpp"
#include "Mutation.hpp"
@@ -65,7 +65,7 @@
// TODO(dalexander): move this method to PoaConsensus so we don't have to use a tuple
// interface here (which was done to avoid a circular dep on PoaConsensus).
#ifndef SWIG
- boost::tuple >* >
+ std::tuple >* >
FindConsensus(const PoaConfig& config) const;
#endif // !SWIG
diff -Nru spades-3.10.1+dfsg/ext/include/ConsensusCore/Version.hpp spades-3.11.1+dfsg/ext/include/ConsensusCore/Version.hpp
--- spades-3.10.1+dfsg/ext/include/ConsensusCore/Version.hpp 2017-02-28 14:55:42.000000000 +0000
+++ spades-3.11.1+dfsg/ext/include/ConsensusCore/Version.hpp 2017-09-28 09:05:19.000000000 +0000
@@ -37,7 +37,6 @@
#include
#include
-#include
#pragma once
diff -Nru spades-3.10.1+dfsg/ext/include/llvm/ADT/IntrusiveRefCntPtr.h spades-3.11.1+dfsg/ext/include/llvm/ADT/IntrusiveRefCntPtr.h
--- spades-3.10.1+dfsg/ext/include/llvm/ADT/IntrusiveRefCntPtr.h 2017-02-28 14:55:41.000000000 +0000
+++ spades-3.11.1+dfsg/ext/include/llvm/ADT/IntrusiveRefCntPtr.h 2017-09-28 09:05:17.000000000 +0000
@@ -108,7 +108,7 @@
void Release() const {
int NewRefCount = --RefCount;
- assert(NewRefCount >= 0 && "Reference count was already zero.");
+ // assert(NewRefCount >= 0 && "Reference count was already zero.");
if (NewRefCount == 0)
delete static_cast(this);
}
diff -Nru spades-3.10.1+dfsg/ext/include/llvm/Support/MathExtras.h spades-3.11.1+dfsg/ext/include/llvm/Support/MathExtras.h
--- spades-3.10.1+dfsg/ext/include/llvm/Support/MathExtras.h 2017-02-28 14:55:41.000000000 +0000
+++ spades-3.11.1+dfsg/ext/include/llvm/Support/MathExtras.h 2017-09-28 09:05:17.000000000 +0000
@@ -579,6 +579,52 @@
///
/// Examples:
/// \code
+/// alignTo(5, 8) = 8
+/// alignTo(17, 8) = 24
+/// alignTo(~0LL, 8) = 0
+/// alignTo(321, 255) = 510
+///
+/// alignTo(5, 8, 7) = 7
+/// alignTo(17, 8, 1) = 17
+/// alignTo(~0LL, 8, 3) = 3
+/// alignTo(321, 255, 42) = 552
+/// \endcode
+inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
+ assert(Align != 0u && "Align can't be 0.");
+ Skew %= Align;
+ return (Value + Align - 1 - Skew) / Align * Align + Skew;
+}
+
+/// Returns the next integer (mod 2**64) that is greater than or equal to
+/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
+template constexpr inline uint64_t alignTo(uint64_t Value) {
+ static_assert(Align != 0u, "Align must be non-zero");
+ return (Value + Align - 1) / Align * Align;
+}
+
+/// \c alignTo for contexts where a constant expression is required.
+/// \sa alignTo
+///
+/// \todo FIXME: remove when \c constexpr becomes really \c constexpr
+template
+struct AlignTo {
+ static_assert(Align != 0u, "Align must be non-zero");
+ template
+ struct from_value {
+ static const uint64_t value = (Value + Align - 1) / Align * Align;
+ };
+};
+
+/// Returns the next integer (mod 2**64) that is greater than or equal to
+/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
+///
+/// If non-zero \p Skew is specified, the return value will be a minimal
+/// integer that is greater than or equal to \p Value and equal to
+/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
+/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
+///
+/// Examples:
+/// \code
/// RoundUpToAlignment(5, 8) = 8
/// RoundUpToAlignment(17, 8) = 24
/// RoundUpToAlignment(~0LL, 8) = 0
diff -Nru spades-3.10.1+dfsg/ext/include/llvm/Support/TrailingObjects.h spades-3.11.1+dfsg/ext/include/llvm/Support/TrailingObjects.h
--- spades-3.10.1+dfsg/ext/include/llvm/Support/TrailingObjects.h 1970-01-01 00:00:00.000000000 +0000
+++ spades-3.11.1+dfsg/ext/include/llvm/Support/TrailingObjects.h 2017-09-28 09:05:18.000000000 +0000
@@ -0,0 +1,401 @@
+//===--- TrailingObjects.h - Variable-length classes ------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This header defines support for implementing classes that have
+/// some trailing object (or arrays of objects) appended to them. The
+/// main purpose is to make it obvious where this idiom is being used,
+/// and to make the usage more idiomatic and more difficult to get
+/// wrong.
+///
+/// The TrailingObject template abstracts away the reinterpret_cast,
+/// pointer arithmetic, and size calculations used for the allocation
+/// and access of appended arrays of objects, and takes care that they
+/// are all allocated at their required alignment. Additionally, it
+/// ensures that the base type is final -- deriving from a class that
+/// expects data appended immediately after it is typically not safe.
+///
+/// Users are expected to derive from this template, and provide
+/// numTrailingObjects implementations for each trailing type except
+/// the last, e.g. like this sample:
+///
+/// \code
+/// class VarLengthObj : private TrailingObjects {
+/// friend TrailingObjects;
+///
+/// unsigned NumInts, NumDoubles;
+/// size_t numTrailingObjects(OverloadToken) const { return NumInts; }
+/// };
+/// \endcode
+///
+/// You can access the appended arrays via 'getTrailingObjects', and
+/// determine the size needed for allocation via
+/// 'additionalSizeToAlloc' and 'totalSizeToAlloc'.
+///
+/// All the methods implemented by this class are are intended for use
+/// by the implementation of the class, not as part of its interface
+/// (thus, private inheritance is suggested).
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_TRAILINGOBJECTS_H
+#define LLVM_SUPPORT_TRAILINGOBJECTS_H
+
+#include "llvm/Support/AlignOf.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/MathExtras.h"
+#include "llvm/Support/type_traits.h"
+#include
+#include
+
+namespace llvm {
+
+namespace trailing_objects_internal {
+/// Helper template to calculate the max alignment requirement for a set of
+/// objects.
+template class AlignmentCalcHelper {
+private:
+ enum {
+ FirstAlignment = alignof(First),
+ RestAlignment = AlignmentCalcHelper::Alignment,
+ };
+
+public:
+ enum {
+ Alignment = FirstAlignment > RestAlignment ? FirstAlignment : RestAlignment
+ };
+};
+
+template class AlignmentCalcHelper {
+public:
+ enum { Alignment = alignof(First) };
+};
+
+/// The base class for TrailingObjects* classes.
+class TrailingObjectsBase {
+protected:
+ /// OverloadToken's purpose is to allow specifying function overloads
+ /// for different types, without actually taking the types as
+ /// parameters. (Necessary because member function templates cannot
+ /// be specialized, so overloads must be used instead of
+ /// specialization.)
+ template struct OverloadToken {};
+};
+
+/// This helper template works-around MSVC 2013's lack of useful
+/// alignas() support. The argument to LLVM_ALIGNAS(), in MSVC, is
+/// required to be a literal integer. But, you *can* use template
+/// specialization to select between a bunch of different LLVM_ALIGNAS
+/// expressions...
+template
+class TrailingObjectsAligner : public TrailingObjectsBase {};
+template <>
+class LLVM_ALIGNAS(1) TrailingObjectsAligner<1> : public TrailingObjectsBase {};
+template <>
+class LLVM_ALIGNAS(2) TrailingObjectsAligner<2> : public TrailingObjectsBase {};
+template <>
+class LLVM_ALIGNAS(4) TrailingObjectsAligner<4> : public TrailingObjectsBase {};
+template <>
+class LLVM_ALIGNAS(8) TrailingObjectsAligner<8> : public TrailingObjectsBase {};
+template <>
+class LLVM_ALIGNAS(16) TrailingObjectsAligner<16> : public TrailingObjectsBase {
+};
+template <>
+class LLVM_ALIGNAS(32) TrailingObjectsAligner<32> : public TrailingObjectsBase {
+};
+
+// Just a little helper for transforming a type pack into the same
+// number of a different type. e.g.:
+// ExtractSecondType::type
+template struct ExtractSecondType {
+ typedef Ty2 type;
+};
+
+// TrailingObjectsImpl is somewhat complicated, because it is a
+// recursively inheriting template, in order to handle the template
+// varargs. Each level of inheritance picks off a single trailing type
+// then recurses on the rest. The "Align", "BaseTy", and
+// "TopTrailingObj" arguments are passed through unchanged through the
+// recursion. "PrevTy" is, at each level, the type handled by the
+// level right above it.
+
+template
+class TrailingObjectsImpl {
+ // The main template definition is never used -- the two
+ // specializations cover all possibilities.
+};
+
+template
+class TrailingObjectsImpl
+ : public TrailingObjectsImpl {
+
+ typedef TrailingObjectsImpl
+ ParentType;
+
+ struct RequiresRealignment {
+ static const bool value = alignof(PrevTy) < alignof(NextTy);
+ };
+
+ static constexpr bool requiresRealignment() {
+ return RequiresRealignment::value;
+ }
+
+protected:
+ // Ensure the inherited getTrailingObjectsImpl is not hidden.
+ using ParentType::getTrailingObjectsImpl;
+
+ // These two functions are helper functions for
+ // TrailingObjects::getTrailingObjects. They recurse to the left --
+ // the result for each type in the list of trailing types depends on
+ // the result of calling the function on the type to the
+ // left. However, the function for the type to the left is
+ // implemented by a *subclass* of this class, so we invoke it via
+ // the TopTrailingObj, which is, via the
+ // curiously-recurring-template-pattern, the most-derived type in
+ // this recursion, and thus, contains all the overloads.
+ static const NextTy *
+ getTrailingObjectsImpl(const BaseTy *Obj,
+ TrailingObjectsBase::OverloadToken) {
+ auto *Ptr = TopTrailingObj::getTrailingObjectsImpl(
+ Obj, TrailingObjectsBase::OverloadToken()) +
+ TopTrailingObj::callNumTrailingObjects(
+ Obj, TrailingObjectsBase::OverloadToken());
+
+ if (requiresRealignment())
+ return reinterpret_cast(
+ llvm::alignAddr(Ptr, alignof(NextTy)));
+ else
+ return reinterpret_cast(Ptr);
+ }
+
+ static NextTy *
+ getTrailingObjectsImpl(BaseTy *Obj,
+ TrailingObjectsBase::OverloadToken) {
+ auto *Ptr = TopTrailingObj::getTrailingObjectsImpl(
+ Obj, TrailingObjectsBase::OverloadToken()) +
+ TopTrailingObj::callNumTrailingObjects(
+ Obj, TrailingObjectsBase::OverloadToken());
+
+ if (requiresRealignment())
+ return reinterpret_cast(llvm::alignAddr(Ptr, alignof(NextTy)));
+ else
+ return reinterpret_cast(Ptr);
+ }
+
+ // Helper function for TrailingObjects::additionalSizeToAlloc: this
+ // function recurses to superclasses, each of which requires one
+ // fewer size_t argument, and adds its own size.
+ static constexpr size_t additionalSizeToAllocImpl(
+ size_t SizeSoFar, size_t Count1,
+ typename ExtractSecondType::type... MoreCounts) {
+ return ParentType::additionalSizeToAllocImpl(
+ (requiresRealignment() ? llvm::alignTo(SizeSoFar)
+ : SizeSoFar) +
+ sizeof(NextTy) * Count1,
+ MoreCounts...);
+ }
+};
+
+// The base case of the TrailingObjectsImpl inheritance recursion,
+// when there's no more trailing types.
+template
+class TrailingObjectsImpl
+ : public TrailingObjectsAligner {
+protected:
+ // This is a dummy method, only here so the "using" doesn't fail --
+ // it will never be called, because this function recurses backwards
+ // up the inheritance chain to subclasses.
+ static void getTrailingObjectsImpl();
+
+ static constexpr size_t additionalSizeToAllocImpl(size_t SizeSoFar) {
+ return SizeSoFar;
+ }
+
+ template static void verifyTrailingObjectsAlignment() {}
+};
+
+} // end namespace trailing_objects_internal
+
+// Finally, the main type defined in this file, the one intended for users...
+
+/// See the file comment for details on the usage of the
+/// TrailingObjects type.
+template
+class TrailingObjects : private trailing_objects_internal::TrailingObjectsImpl<
+ trailing_objects_internal::AlignmentCalcHelper<
+ TrailingTys...>::Alignment,
+ BaseTy, TrailingObjects,
+ BaseTy, TrailingTys...> {
+
+ template
+ friend class trailing_objects_internal::TrailingObjectsImpl;
+
+ template class Foo {};
+
+ typedef trailing_objects_internal::TrailingObjectsImpl<
+ trailing_objects_internal::AlignmentCalcHelper::Alignment,
+ BaseTy, TrailingObjects, BaseTy, TrailingTys...>
+ ParentType;
+ using TrailingObjectsBase = trailing_objects_internal::TrailingObjectsBase;
+
+ using ParentType::getTrailingObjectsImpl;
+
+ // This function contains only a static_assert BaseTy is final. The
+ // static_assert must be in a function, and not at class-level
+ // because BaseTy isn't complete at class instantiation time, but
+ // will be by the time this function is instantiated.
+ static void verifyTrailingObjectsAssertions() {
+#ifdef LLVM_IS_FINAL
+ static_assert(LLVM_IS_FINAL(BaseTy), "BaseTy must be final.");
+#endif
+ }
+
+ // These two methods are the base of the recursion for this method.
+ static const BaseTy *
+ getTrailingObjectsImpl(const BaseTy *Obj,
+ TrailingObjectsBase::OverloadToken) {
+ return Obj;
+ }
+
+ static BaseTy *
+ getTrailingObjectsImpl(BaseTy *Obj,
+ TrailingObjectsBase::OverloadToken) {
+ return Obj;
+ }
+
+ // callNumTrailingObjects simply calls numTrailingObjects on the
+ // provided Obj -- except when the type being queried is BaseTy
+ // itself. There is always only one of the base object, so that case
+ // is handled here. (An additional benefit of indirecting through
+ // this function is that consumers only say "friend
+ // TrailingObjects", and thus, only this class itself can call the
+ // numTrailingObjects function.)
+ static size_t
+ callNumTrailingObjects(const BaseTy *Obj,
+ TrailingObjectsBase::OverloadToken) {
+ return 1;
+ }
+
+ template
+ static size_t callNumTrailingObjects(const BaseTy *Obj,
+ TrailingObjectsBase::OverloadToken) {
+ return Obj->numTrailingObjects(TrailingObjectsBase::OverloadToken());
+ }
+
+public:
+ // Make this (privately inherited) member public.
+#ifndef _MSC_VER
+ using ParentType::OverloadToken;
+#else
+ // MSVC bug prevents the above from working, at least up through CL
+ // 19.10.24629.
+ template
+ using OverloadToken = typename ParentType::template OverloadToken;
+#endif
+
+ /// Returns a pointer to the trailing object array of the given type
+ /// (which must be one of those specified in the class template). The
+ /// array may have zero or more elements in it.
+ template const T *getTrailingObjects() const {
+ verifyTrailingObjectsAssertions();
+ // Forwards to an impl function with overloads, since member
+ // function templates can't be specialized.
+ return this->getTrailingObjectsImpl(
+ static_cast