export module containers;

import ranges; // provides trait range_of, trait iterator_for, trait sentinel

// would probably be builtin
export enum order{equal=0, less=-1, greater=1}
alias None = ();

// __intN are special basic integer types that can be used within the compiler
//  for the implementations of these program-facing templates
// Note: Parameters to compile-time entities are automatically considered
//  'const' without needing annotation
struct int(width : __int32) {}
struct unsigned (width : __int32) {}

struct add_carry_t(Rep : Type) {
	carry : bool;
	result : Rep;
}

// UB on overflow
fn (+)(a : int($N1), b : int($N2)) -> int(max(N1, N2));
fn (-)(a : int($N1), b : int($N2)) -> int(max(N1, N2));

fn (*)(a : int($N1), b : int($N2)) -> int(N1 + N2);
fn (/)(a : int($N1), b : int($N2)) -> int(N1);
fn (%)(a : int($N1), b : int($N2)) -> int(N2);

// No UB on overflow
// Wrapping with carry-out (no information loss)
fn (+?)(a : int($N1), b : int($N2)) -> add_carry_t(int(max(N1, N2)));
fn (-?)(a : int($N1), b : int($N2)) -> add_carry_t(int(max(N1, N2)));
// Wrapping, no carry-out
fn (+%)(a : int($N1), b : int($N2)) -> int(max(N1, N2));
fn (-%)(a : int($N1), b : int($N2)) -> int(max(N1, N2));


// UB on overflow
fn (+)(a : unsigned($N1), b : unsigned($N2)) -> unsigned(max(N1, N2));
fn (-)(a : unsigned($N1), b : unsigned($N2))
	= error("a - b may have a negative result which cannot be represented in an\
 unsigned type. Do you mean signed_diff(a, b) or wrap_diff(a, b)?");

fn (*)(a : unsigned($N1), b : unsigned($N2)) -> unsigned(2 * max(N1, N2));
fn (/)(a : unsigned($N1), b : unsigned($N2)) -> unsigned(N1);
fn (%)(a : unsigned($N1), b : unsigned($N2)) -> unsigned(N2);

// No UB on overflow
// Wrapping with carry-out (no information loss)
fn (+?)(a : unsigned($N1), b : unsigned($N2)) -> add_carry_t(unsigned(max(N1, N2)));
fn (-?)(a : unsigned($N1), b : unsigned($N2)) -> add_carry_t(unsigned(max(N1, N2)));
// Wrapping, no carry-out
fn (+%)(a : unsigned($N1), b : unsigned($N2)) -> unsigned(max(N1, N2));
fn (-%)(a : unsigned($N1), b : unsigned($N2)) -> unsigned(max(N1, N2));


struct float(exponent_w : __int32, mantissa_w : __int32, radix : __int32 = 2) {}
// The unary prefix ? operator returns a union of its input type and None
fn (?_)(const T : Type) -> Type = T | None;
// The binary | operator returns a union of its input types
fn (|)(const T : Type, const U : Type) -> Type
	= union(unique_unsorted(T, U)...);
// A | A -> A
fn (|)(const T : Type, const _ == T) -> Type
	= T;
// Chaining A | B | C... is flattened
//! Review syntax
fn (|)(const _ == union($T...), const U : Type) -> Type
	= union(unique_unsorted(T..., U)...);
fn (|)(const T : Type, const _ == union($U...)) -> Type
	= union(unique_unsorted(T, U...)...);
fn (|)(const _ == union($T...), const _ == union($U...)) -> Type
	= union(unique_unsorted(T..., U...)...);
// The type Noreturn is always erased from unions unless it is the only alternative
fn (|)(const _ == Noreturn, const U :  Type    ) -> Type = U;
fn (|)(const T :  Type,     const _ == Noreturn) -> Type = T;
fn (|)(const _ == Noreturn, const _ == Noreturn) -> Type = Noreturn;

fn unique_unsorted(, cmp = (==)) {
}

struct union(const T : Type, const U... : Type)
	= map(__union, unique_unsorted(T, U...));

/**
 * A = i32
 * B = None
 * C = Noreturn
 * D = (float | None)
 * 
 * T = A | B | C | D
 *   = i32 | None | Noreturn | (float | None)
 *   = ((i32 | None) | Noreturn) | (float | None)
 *   = (union(i32, None) | Noreturn) | (float | None)
 *   = ((|)(union(i32, None), Noreturn) | (float | None)
 *   = union(i32, None) | (float | None)
 *   = union(i32, None) | (|)(float, None)
 *   = union(i32, None) | union(float, None)
 *   = union(i32, None, float, None)
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 */

fn alloc(const T : Type, args : $Args...) -> owner(T);
fn alloc_array(const T : Type, Count, args : $Args...) -> owner([]T);

fn try_alloc(const T : Type, args : $Args...) -> ?owner(T);
fn try_alloc_array(const T : Type, Count, args : $Args...) -> ?owner([]T);

// typeof is simply a macro instead of an operator, requiring no magic
fn typeof(#_ : $T) = T;

struct Type {
	let const name : str {public};
	let const namespace {public};
	let const size : iSize {public};
	// struct/tuple types
	let const members : ?[]Variable {public};
	// array types
	let const dimensions : ?[](iSize | Dynamic) {public};
	// union types
	let const alternatives : ?[]Type {public};
	let const enumerators : ?[] {public};
}

// A type implementing Failure must explicitly declare that it does, merely providing the required interface is not enough
trait explicit Failure {
	fn code(self) -> err_code;
}

struct Fail {
	implements Failure;
	let code : err_code {public}
}

// try expr() will evaluate expr(), then check if the result is an error and return it if so, otherwise it will evaluate to the unwrapped type of expr
// Still working on the syntax for macros
macro try:$label (expr : !$T) -> T 
	= (expr ?? result:@label expr);
macro try:$label (expr)
	(: expr {expr result:@label} ?? :)
macro try(expr : !$T, label : Label = fn) -> T
	= match expr {
		(e : Failure) -> result:@label e,
		(v) -> v
	};

// implement trait array for builtin sized arrays
export fn begin(self : &[$Size]$) {
	return array_iterator(self, 0)
}
export fn begin(self : &[]$) {
	return array_iterator(self, 0)
}
export fn end(self : &[$Size]$) {
	return array_iterator(self, Size)
}
export fn end(self : &[]$) {
	return array_iterator(self, self.size)
}

// builtin arrays support this trait
export trait array(Data : Type) {
	implements range_of(Data);
	
	fn size(&self) -> i64;
	fn ([])(&self, i : i64) -> &Data;
	
	// Using a union type here doesn't mean the implementation must; this
	// interface can be implemented by an overload set as well.
	fn ([:])(
			&self,
			lb : ?i64, rb : ?i64)
		-> range_of(Data);
	
	fn begin(&self) -> iterator_for(Data);
	fn end(&self) -> sentinel;
	
	fn (==)(lhs : &This, rhs : &This) -> bool;
	fn (<=>)(lhs : &This, rhs : &This) -> order;
}

export trait list(Data : Type) {
	// requires everything in trait array as well
	implements array(Data);
	
	fn new() -> This;
	fn new(other : &This) -> This;
	fn new(arr :*[$Size : i64]Data) -> This;
	
	// these functions have no required return type
	fn push_back(&mut self, val : Data);
	fn append(&mut self, r : range_of(Data));
	fn pop_back(&mut self) -> Data;
}

export struct vector(Data : Type) {
	// completely unoptimized dynamic array implementation
	let data : *[]Data {private mut}
	
	defer array(Data) to data;
	
	// assertions (no effect besides trait checking)
	implements list(Data);
	
	public fn new() -> This = default;
	public fn new(other : &This) -> This = default;
	public fn new(arr :*[$Size]Data) -> This 
		= new(data : arr);
	
	public fn push_back(&mut self, val : Data) {
		self.data := {self.data..., val}
	}
	public fn append(&mut self, r : range_of(Data)) {
		self.data := {self.data..., r...}
	}
	public fn pop_back(&mut self) -> Data {
		let back = self[self.size - 1].move
		let tmp : []Data [self.size - 1]
		for (let i : range(self.size - 1)) {
			tmp[i] := self.data[i].move
		}
		self.data := tmp.move
		return back
	}
}

export struct string {
	let chars : vector(u8) {public mut}
	// defer a trait to a member, instead of using inheritance
	defer list(u8) to chars;
}

export fn (+)(lhs : string, rhs : &string) -> string {
	lhs.append(rhs)
	return lhs
}

export fn icompare(lhs : &string, rhs : &string) -> order {
	for (a, b) in zip(lhs, rhs) {
		match(a.tolower <=> b.tolower) {
			case order::equal -> none,
			(o)               -> return o
		}
	}
	// _ is an implicit lambda parameter
	// calls map(zip(lhs, rhs), _[0] <=> _[1])
	return zip(lhs.tolower, rhs.tolower)
	       .map((<=>))
	       .filter(_ != order::equal)
	       .front_or(order::equal)
	// Equivalent to:
	return front_or(filter(map(zip(lhs.tolower, rhs.tolower),
	                           (<=>)),
	                       _ != order::equal),
	                order::equal)
}

export struct Enum(Variants : [](#Name : Identifier, Attribute : Type = None)) {
	enum tags { @(#Variants).Name... };
	
	data : union(
			@(const id = @(#tags).Enumerators, value : @(#Variants).Attribute)...
		) { public; private mut }
}

fn loop_demo(val, array : &[,]$T, cmp = (==)) {
	// pos is an optional tuple with the position of the first found element
	// 'for:L1' is a labeled loop
	let pos = for:L1 row in range(array.size[0]) {
		for col in range(array.size[1]) {
			// break can carry a value, like return. This lets pos be constant			
			break:L1 (row,col) if cmp(val, array[row, col])
		}
	} // if no value is returned with a 'break', None is returned
	// do something with pos
}

// I'm not quite sure what operators will be used for these operations
trait Iterator(T : Type) {
	fn deref(self : Iterator(T)) -> ?&T;
	fn next(self  : Iterator(T)) -> Iterator(T);
	fn prev(self  : Iterator(T)) -> Iterator(T);
}

fn foldl(op, init != None, iter : Iterator)
	= #[tail] foldl(op, op(init, iter.deref)?, iter.next);
fn foldr(op, init, iter : Iterator)
	=         op(iter.deref, foldr(op, init, iter.next))?;

struct list_node(T : Type) {
	let data : T            {public mut};
	let next : ?owner(This) {public, module mut};
	let prev : ?&This       {public, module mut};
	
	public fn new = default;
}

struct linked_list(T : Type) {
	alias Node = list_node(T);
	alias List = linked_list(T);
	
	struct end_sentinel(Mut : bool) {
		implements Iterator(T);
		let list : &mut(Mut) List {module mut};
		
		public fn deref(self) = None;
		public fn next(self) = None;
		public fn prev(self) -> ?iterator(Mut)
			= iterator::new(self.list, self.list.tail)?;

		public fn new = default;
		public fn end_sentinel(false)::new(other : &end_sentinel(true))
			= end_sentinel(false)::new(other.list);
	}
	struct iterator(Mut : bool) {
		implements Iterator(T);
		let list : &mut(Mut) List {module mut};
		let it   : &mut(Mut) Node {module mut};
		
		public fn deref(self) -> &T = it.data;
		public fn next(self) -> iterator | end_sentinel
			= new(self.list, self.it.next) ?? end_sentinel(Mut)::new(self.list);
		public fn prev(self) -> ?iterator
			= new(self.list, self.it.prev)?;

		public fn new = default;
		public fn iterator(false)::new(other : &iterator(true))
			= iterator(false)::new(other.list, other.it);
	}
	
	let head : ?owner(Node) {module mut};
	let tail : ?&Node       {module mut};
	
	public fn new() -> This = {none, none};
	
	public fn begin(&self) -> Iterator(T)
		= iterator(false)::new(self, self.head)
			?? end_sentinel(false)::new(self);
	public fn m_begin(&mut self) -> Iterator(T)
		= iterator(true)::new(self, self.head)
			?? end_sentinel(true)::new(self);
	
	public fn end(&self) = end_sentinel(false)::new(self);
	public fn m_end(&mut self) = end_sentinel(true)::new(self);
	
	// I'm not sure about this syntax for casting/conversion
	public fn is_empty(self) -> bool = bool(head);
	
	public fn size(&self) -> iSize {
		fn sz(node : &Node, count : iSize) {
			if node {
				return #[tail] sz(node.next, count + 1);
			} else {
				return count;
			}
		}
		return sz(self.head, 0);
	}
	
	public fn insert_front(&mut self, data : T) -> None {
		if self.head {
			self.head := std::alloc(Node, consume(data), consume(self.head), none);
			self.head.next.prev := self.head;
		} else {
			// empty list
			self.tail := self.head := std::alloc(Node, consume(data), none, none);
		}
	}
	public fn insert_back(&mut self, data : T) -> None {
		if self.tail {
			self.tail := self.tail.next := std::alloc(Node, consume(data), none, self.tail);
		} else {
			// empty list
			self.tail := self.head := std::alloc(Node, consume(data), none, none);
		}
	}
	
	public fn insert(&mut self, data : T, pos : iterator($)) -> None {
		assert(self == pos.list);
		if pos.prev() {
			let n = std::alloc(Node, consume(data), none, none);
			n.next := consume(pos.prev.next);
			n.prev := pos.prev;
			
			let N = n;
			pos.prev.next := consume(n);
			pos.prev := N;
		} else {
			insert_front(consume(data));
			
			n.next := consume(self.head);
			pos.prev := n;
			self.tail := self.head := consume(n);
		}
	}
	public fn insert(&mut self, data : &T, _ : end_sentinel($)) -> None {
		assert(self == pos.list);
		self.insert_back(data);
	}
	
	public fn erase(&mut self, pos : iterator($)) -> None {
		assert(self == pos.list);
		
		let mut node : owner(Node);
		if pos.prev {
			node := consume(pos.prev.next)?;
			pos.prev.next := consume(pos.next)?;
		} else {
			node := consume(self.head)?;
			self.head := consume(node.next)?;
		}
		if node.next {
			node.next.prev := node.prev;
		} else {
			self.tail := node.prev;
		}
	}
	
	public fn erase_front(&mut self) -> None {
		if self.head {
			node := consume(self.head)?;
			self.head := consume(node.next)?;
			if not self.head {
				self.tail := none;
			}
		}
	}
	
	public fn clear(&mut self) {
		// RAII handles all cleanup
		self.tail := none;
		self.head := none;
	}
	
	public fn merge(mut left : This, mut right : This, comp = (<)) -> This {
		if right.is_empty {
			// nothing to merge
			return consume(left);
		} else if left.is_empty() {
			// left is empty, so just take the entirety of right
			return consume(right)
		} else {
			// do an actual merge
			
			// clear out the objects
			let mut a : ?owner(Node) = consume(left.head);
			left.tail := none;
			let mut b : ?owner(Node) = consume(right.head);
			right.tail := none;
			
			// guided NRVO via attribute
			let #[return] ret : This;
			
			// set up the first element
			if (a.data.comp(b.data)) {
				ret.head := consume(a);
				a := consume(ret.head.next);
				a.prev := none;
			} else {
				ret.head := consume(b);
				b := consume(ret.head.next);
				b.prev := none;
			}
			ret.tail := ret.head;
			
			// local function is an implicit closure (non-returnable)
			fn append(n : &mut) {
				ret.tail.next := consume(n);
				n := consume(ret.tail.next.next);
				ret.tail.next.prev := ret.tail;
				ret.tail := ret.tail.next;
			}
			
			// perform the merge
			while a and b {
				if (a.data.comp(b.data)) {
					append(&a);
				} else {
					append(&b);
				}
			}
			// clean up the remaining elements and ensure ret.tail is set
			// only at most one of these can run
			// (this could be optimized somewhat)
			while a {
				append(&a);
			}
			while b {
				append(&b);
			}
		}
		
		// other functions provided by C++ std::list, may or may not fit in
		// with this language's paradigms
		public fn splice(&mut self, pos : iterator(false),
		                 other : &mut This) -> None;
		public fn splice(&mut self, pos : iterator(false),
		                 other : &mut This, it : iterator(false)) -> None;
		public fn splice(&mut self, pos : iterator(false),
		                 other : &mut This, first : iterator(false),
		                 last : iterator(false)) -> None;
		
		public fn remove(&mut self, value : &T) -> iSize;
		public fn remove_if(&mut self, pred) -> iSize;
		
		public fn reverse(self) -> This;
		
		public fn unique(self, pred = (==)) -> This;
		
		public fn sort(self, comp = (<)) -> This;
	}
}


// old iterator design, kept just because it used some additional features (mostly involving optionals):

struct iterator {
	let type : enum(node, beg, end);
	let it : &Node {module};
	
	// Some languages have &self.it?.data instead
	fn deref(self) -> ?&T = &self.it.data?;
	fn next(self) -> ?This
		= match self.type {
			case node -> 
				{node, self.it.next}
				// if self.it.next is null, this constructor fails, so
				// the ?? operator evaluates the next option
				?? {end, self.it},
			case beg  -> {node, self.it},
			// incrementing the end sentinel fails
			case end  -> none;
		};
	fn prev(self) -> ?This
		= match self.type {
			case node -> 
				{node, self.it.next}
				// if self.it.next is null, this constructor fails, so
				// the ?? operator evaluates the next option
				?? {end, self.it},
			// incrementing the end sentinel fails
			case beg  -> none;
			case end  -> {node, self.it},
		};
}
struct mut_iterator {
	let type : enum(node, beg, end);
	let it : &mut Node;
	
	fn deref(&self) -> ?&mut T
		= self.it.?;
	fn next(&self) -> ?This
		= match self.type {
			case node -> 
				{node, self.it.next}
				// if self.it.next is null, this constructor fails, so
				// the ?? operator evaluates the next option
				?? {end, self.it},
			case beg  -> {node, self.it},
			// incrementing the end sentinel fails
			case end  -> none;
		};
	fn prev(&self) -> ?This
		= match self.type {
			case node -> 
				{node, self.it.prev}
				// if self.it.prev is null, this constructor fails, so
				// the ?? operator evaluates the next option
				?? {beg, self.it},
			// decrementing the beginning sentinel fails
			case beg  -> none;
			case end  -> {node, self.it},
		};
}