import std.dsa.collection.Collection
func sort<T is Comparable>(list<T> items) returns list<T> {
auto out = items
int n = out.size()
if n <= 1 {
return out
}
int low = 0
int high = n - 1
list<int> stack = []
stack.push_back(low)
stack.push_back(high)
while stack.size() > 0 {
int h = stack[stack.size() - 1]
stack.pop_back()
int l = stack[stack.size() - 1]
stack.pop_back()
if l < h {
auto pivot = out[h]
int i = l - 1
int j = l
while j < h {
if out[j] <= pivot {
i = i + 1
auto tmp = out[i]
out[i] = out[j]
out[j] = tmp
}
j = j + 1
}
auto tmp = out[i + 1]
out[i + 1] = out[h]
out[h] = tmp
int p = i + 1
if p - 1 > l {
stack.push_back(l)
stack.push_back(p - 1)
}
if p + 1 < h {
stack.push_back(p + 1)
stack.push_back(h)
}
}
}
return out
}
func binary_search<T is Comparable, E is Collection<T>>(E items, T target) returns int {
auto values = sort(items.to_list())
int left = 0
int right = values.size() - 1
while left <= right {
int mid = (left + right) / 2
auto value = values[mid]
if value == target {
return mid
}
if value < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
func max<T is Comparable & Stringable, E is Collection<T>>(E collection) returns optional<T> {
if collection.is_empty() {
return none
}
auto values = collection.to_list()
auto best = values[0]
int i = 1
while i < values.size() {
if best < values[i] {
best = values[i]
}
i = i + 1
}
return some(best)
}
func min<T is Comparable & Stringable, E is Collection<T>>(E collection) returns optional<T> {
if collection.is_empty() {
return none
}
auto values = collection.to_list()
auto best = values[0]
int i = 1
while i < values.size() {
if values[i] < best {
best = values[i]
}
i = i + 1
}
return some(best)
}
func reverse<T, E is Collection<T>>(E collection) returns list<T> {
auto values = collection.to_list()
list<T> out = []
int i = values.size() - 1
while i >= 0 {
out.push_back(values[i])
i = i - 1
}
return out
}
func sort_by<T>(list<T> items, func(T, T) returns int cmp) returns list<T> {
auto out = items
int n = out.size()
if n <= 1 {
return out
}
int low = 0
int high = n - 1
list<int> stack = []
stack.push_back(low)
stack.push_back(high)
while stack.size() > 0 {
int h = stack[stack.size() - 1]
stack.pop_back()
int l = stack[stack.size() - 1]
stack.pop_back()
if l < h {
auto pivot = out[h]
int i = l - 1
int j = l
while j < h {
if cmp(out[j], pivot) <= 0 {
i = i + 1
auto tmp = out[i]
out[i] = out[j]
out[j] = tmp
}
j = j + 1
}
auto tmp = out[i + 1]
out[i + 1] = out[h]
out[h] = tmp
int p = i + 1
if p - 1 > l {
stack.push_back(l)
stack.push_back(p - 1)
}
if p + 1 < h {
stack.push_back(p + 1)
stack.push_back(h)
}
}
}
return out
}
func index_of<T, E is Collection<T>>(E collection, T target) returns int {
auto values = collection.to_list()
int i = 0
while i < values.size() {
if values[i] == target {
return i
}
i = i + 1
}
return -1
}
func unique<T, E is Collection<T>>(E collection) returns list<T> {
auto values = collection.to_list()
list<T> out = []
int i = 0
while i < values.size() {
auto candidate = values[i]
bool seen = false
int j = 0
while j < out.size() {
if out[j] == candidate {
seen = true
}
j = j + 1
}
if !seen {
out.push_back(candidate)
}
i = i + 1
}
return out
}
func any<T, E is Collection<T>>(E collection, func(T) returns bool predicate) returns bool {
auto values = collection.to_list()
int i = 0
while i < values.size() {
if predicate(values[i]) {
return true
}
i = i + 1
}
return false
}
func all<T, E is Collection<T>>(E collection, func(T) returns bool predicate) returns bool {
auto values = collection.to_list()
int i = 0
while i < values.size() {
if !predicate(values[i]) {
return false
}
i = i + 1
}
return true
}
func count<T, E is Collection<T>>(E collection, func(T) returns bool predicate) returns int {
auto values = collection.to_list()
int total = 0
int i = 0
while i < values.size() {
if predicate(values[i]) {
total = total + 1
}
i = i + 1
}
return total
}
func sum_ints<E is Collection<int>>(E collection) returns int {
auto values = collection.to_list()
int total = 0
int i = 0
while i < values.size() {
total = total + values[i]
i = i + 1
}
return total
}
func sum_floats<E is Collection<float>>(E collection) returns float {
auto values = collection.to_list()
float total = 0.0
int i = 0
while i < values.size() {
total = total + values[i]
i = i + 1
}
return total
}