From f9ef0293ff882b97cfe650e92fe0844c8920f4e3 Mon Sep 17 00:00:00 2001 From: Magnus Auvinen Date: Mon, 15 Jun 2009 06:50:47 +0000 Subject: renamed algorithms.hpp to algotithm.hpp --- src/base/tl/algorithm.hpp | 135 +++++++++++++++++++++++++++++++++++++++++++ src/base/tl/algorithms.hpp | 135 ------------------------------------------- src/base/tl/sorted_array.hpp | 2 +- 3 files changed, 136 insertions(+), 136 deletions(-) create mode 100644 src/base/tl/algorithm.hpp delete mode 100644 src/base/tl/algorithms.hpp (limited to 'src/base/tl') diff --git a/src/base/tl/algorithm.hpp b/src/base/tl/algorithm.hpp new file mode 100644 index 00000000..9d78810b --- /dev/null +++ b/src/base/tl/algorithm.hpp @@ -0,0 +1,135 @@ +#ifndef TL_FILE_ALGORITHM_HPP +#define TL_FILE_ALGORITHM_HPP + +#include "range.hpp" + + +/* + insert 4 + v + 1 2 3 4 5 6 + +*/ + + +template +R partition_linear(R range, T value) +{ + concept_empty::check(range); + concept_forwarditeration::check(range); + concept_sorted::check(range); + + for(; !range.empty(); range.pop_front()) + { + if(!(range.front() < value)) + return range; + } + return range; +} + + +template +R partition_binary(R range, T value) +{ + concept_empty::check(range); + concept_index::check(range); + concept_size::check(range); + concept_slice::check(range); + concept_sorted::check(range); + + if(range.empty()) + return range; + if(range.back() < value) + return R(); + + while(range.size() > 1) + { + unsigned pivot = (range.size()-1)/2; + if(range.index(pivot) < value) + range = range.slice(pivot+1, range.size()-1); + else + range = range.slice(0, pivot+1); + } + return range; +} + +template +R find_linear(R range, T value) +{ + concept_empty::check(range); + concept_forwarditeration::check(range); + for(; !range.empty(); range.pop_front()) + if(value < range.front()) + break; + return range; +} + +template +R find_binary(R range, T value) +{ + range = partition_linear(range, value); + if(range.empty()) return range; + if(range.front() == value) return range; + return R(); +} + + +template +void sort_bubble(R range) +{ + concept_empty::check(range); + concept_forwarditeration::check(range); + concept_backwarditeration::check(range); + + // slow bubblesort :/ + for(; !range.empty(); range.pop_back()) + { + R section = range; + typename R::type *prev = §ion.front(); + section.pop_front(); + for(; !section.empty(); section.pop_front()) + { + typename R::type *cur = §ion.front(); + if(*cur < *prev) + swap(*cur, *prev); + prev = cur; + } + } +} + +/* +template +void sort_quick(R range) +{ + concept_index::check(range); +}*/ + + +template +void sort(R range) +{ + sort_bubble(range); +} + + +template +bool sort_verify(R range) +{ + concept_empty::check(range); + concept_forwarditeration::check(range); + + typename R::type *prev = &range.front(); + range.pop_front(); + for(; !range.empty(); range.pop_front()) + { + typename R::type *cur = &range.front(); + + if(*cur < *prev) + return false; + prev = cur; + } + + return true; +} + +#endif // TL_FILE_ALGORITHMS_HPP diff --git a/src/base/tl/algorithms.hpp b/src/base/tl/algorithms.hpp deleted file mode 100644 index 15e8e8a9..00000000 --- a/src/base/tl/algorithms.hpp +++ /dev/null @@ -1,135 +0,0 @@ -#ifndef TL_FILE_ALGORITHMS_HPP -#define TL_FILE_ALGORITHMS_HPP - -#include "range.hpp" - - -/* - insert 4 - v - 1 2 3 4 5 6 - -*/ - - -template -R partition_linear(R range, T value) -{ - concept_empty::check(range); - concept_forwarditeration::check(range); - concept_sorted::check(range); - - for(; !range.empty(); range.pop_front()) - { - if(!(range.front() < value)) - return range; - } - return range; -} - - -template -R partition_binary(R range, T value) -{ - concept_empty::check(range); - concept_index::check(range); - concept_size::check(range); - concept_slice::check(range); - concept_sorted::check(range); - - if(range.empty()) - return range; - if(range.back() < value) - return R(); - - while(range.size() > 1) - { - unsigned pivot = (range.size()-1)/2; - if(range.index(pivot) < value) - range = range.slice(pivot+1, range.size()-1); - else - range = range.slice(0, pivot+1); - } - return range; -} - -template -R find_linear(R range, T value) -{ - concept_empty::check(range); - concept_forwarditeration::check(range); - for(; !range.empty(); range.pop_front()) - if(value < range.front()) - break; - return range; -} - -template -R find_binary(R range, T value) -{ - range = partition_linear(range, value); - if(range.empty()) return range; - if(range.front() == value) return range; - return R(); -} - - -template -void sort_bubble(R range) -{ - concept_empty::check(range); - concept_forwarditeration::check(range); - concept_backwarditeration::check(range); - - // slow bubblesort :/ - for(; !range.empty(); range.pop_back()) - { - R section = range; - typename R::type *prev = §ion.front(); - section.pop_front(); - for(; !section.empty(); section.pop_front()) - { - typename R::type *cur = §ion.front(); - if(*cur < *prev) - swap(*cur, *prev); - prev = cur; - } - } -} - -/* -template -void sort_quick(R range) -{ - concept_index::check(range); -}*/ - - -template -void sort(R range) -{ - sort_bubble(range); -} - - -template -bool sort_verify(R range) -{ - concept_empty::check(range); - concept_forwarditeration::check(range); - - typename R::type *prev = &range.front(); - range.pop_front(); - for(; !range.empty(); range.pop_front()) - { - typename R::type *cur = &range.front(); - - if(*cur < *prev) - return false; - prev = cur; - } - - return true; -} - -#endif // TL_FILE_ALGORITHMS_HPP diff --git a/src/base/tl/sorted_array.hpp b/src/base/tl/sorted_array.hpp index bb09aba9..30c1df24 100644 --- a/src/base/tl/sorted_array.hpp +++ b/src/base/tl/sorted_array.hpp @@ -1,7 +1,7 @@ #ifndef TL_FILE_SORTED_ARRAY_HPP #define TL_FILE_SORTED_ARRAY_HPP -#include "algorithms.hpp" +#include "algorithm.hpp" #include "array.hpp" template > -- cgit 1.4.1