#pragma once

#include "base.h"

#include <iterator>

namespace immutable {

struct ArrayImp;

template <typename T> struct TransientArray;

static constexpr uint32 END = 0xffffffff;

// Persistent array (aka vector aka random-access list)

template <typename T>

struct Array : RefCounted {

using ValueT = Value<T>;

using TransientArrayT = TransientArray<T>;

struct Iterator;

// The empty array

static ref<Array> empty();

// Create an array with values from initializer list

template <typename Y> static ref<Array> create(std::initializer_list<Y>&&);

// Create an array with values from iterable

template <typename Iterable> static ref<Array> create(Iterable&&);

template <typename Iterable> static ref<Array> create(const Iterable&);

static ref<Array> create(Iterator&& begin, const Iterator& end);

static ref<Array> create(Iterator& begin, const Iterator& end);

template <typename It> static ref<Array> create(It& begin, const It& end);

template <typename It> static ref<Array> create(It&& begin, const It& end);

// Number of values in this array

uint32 size() const { return _end - _start; }

// Append value to the end. Form 2 constructs a value T in-place.

ref<Array> push(ValueT*) const; // 1

template <typename Arg> ref<Array> push(Arg&&) const; // 2

// Append values from iterator to end.

// The value type of the iterator must be either Value<T> or some value that T can

// be constructed from (like T itself or an argument accepted by T's constructor)

ref<Array> push(Iterator&& begin, const Iterator& end) const;

ref<Array> push(Iterator& begin, const Iterator& end) const;

template <typename It> ref<Array> push(It&& begin, const It& end) const;

template <typename It> ref<Array> push(It& begin, const It& end) const;

// Prepend value to the beginning. Form 2 constructs a value T in-place.

ref<Array> cons(ValueT*) const; // 1

template <typename Arg> ref<Array> cons(Arg&&) const; // 2

// Set value at index i, where i must be less than size().

// Returns nullptr if i is out-of bounds. Form 1 constructs a value T in-place.

template <typename Arg> ref<Array> set(uint32 i, Arg&&) const; // 1

ref<Array> set(uint32 i, ValueT*) const; // 2

// Access value at index. If i >= size() the behavior is undefined.

const T& get(uint32 i) const;

// Find value at index. Returns the end iterator if index is out-of bounds.

Iterator find(uint32 i) const;

// Find value at index. Returns nullptr if index is out-of bounds.

const ref<ValueT> findValue(uint32 i) const;

// Access value at index. If i >= size() the behavior is undefined.

const ref<ValueT> getValue(uint32 i) const;

// Access first and last value

const T& first() const;

const T& last() const;

const ref<ValueT> firstValue() const;

const ref<ValueT> lastValue() const;

// Remove the last item

ref<Array> pop() const;

// Returns an array with all items but the first. Equiv to slice(1)

// Called "pop_front" or "shift" in some mutative implementation.

ref<Array> rest() const;

// Returns a version of this array with other array added to the end

ref<Array> concat(ref<Array>) const;

// Returns a slice of this array, from start up until (but not including) end.

// Returns null if start and/or end is out-of bounds.

ref<Array> slice(uint32 start, uint32 end=END) const;

// Replaces values within the range [start, end) with values from iterator it.

template <typename It>

ref<Array> splice(uint32 start, uint32 end, It&& it, const It& endit) const;

ref<Array> splice(uint32 start, uint32 end, Iterator&& it) const;

ref<Array> splice(uint32 start, uint32 end, Iterator& it) const;

// Replaces values within the range [start, end) with values from another array.

ref<Array> splice(uint32 start, uint32 end, ref<Array>) const;

// Removes values within the range [start, end). Returns null if i is out-of bounds.

ref<Array> without(uint32 start, uint32 end=END) const;

// return a new TransientArray contaning the same values as this array

ref<TransientArrayT> asTransient() const;

// apply modification with a transient.

// F should return either Array<T> or TransientArray<T>, e.g.

// auto a = Array<int>::create({1,2,3});

// a = a->modify([] (ref<TransientArray<int>> t) { // param can be `auto` in C++14

// t->set(0, 10)->set(1, 20)->set(2, 30);

// });

// assert(a->get(1, 20));

//

template <typename F> ref<Array> modify(F&& fn) const;

// True if this array has the same values as the other array.

// Compares values using std::less<T>.

int compare(const ref<Array>& other) const;

// True if the other array refers to the same underlying data.

bool operator==(const ref<Array>& rhs) const;

bool operator!=(const ref<Array>& rhs) const { return !(*this == rhs); }

// Iteration

Iterator begin(uint32 start=0, uint32 end=END) const;

const Iterator& end() const;

// forward iterator

struct Iterator {

};

// lower-case name for STL compatibility

typedef Iterator iterator;

// copyable and movable

Array(const Array&) = default;

Array(Array&&) = default;

Array& operator=(const Array&) = default;

Array& operator=(Array&&) = default;

protected:

friend struct ArrayImp;

uint32 _start; // index offset used when this array is a slice of another array

uint32 _end; // _end - _offs = number of values in the list

uint32 _shift; // BITS times (the depth of this trie minus one)

ref<Object> _root; // trie root

ref<Object> _tail; // holds the last few entries for efficieny reasons

Array() = delete; // use Array::empty() instead

Array(uint32 start, uint32 end, uint32 shift, ref<Object> root, ref<Object> tail);

Array(ref<Object> root, ref<Object> tail);

void dealloc() { delete this; }

IMMUTABLE_REFCOUNTED_IMPL(Array)

};

// Transient version of Array to be used for efficient batch modifications.

// Supports only a subset of the operations provided by Array.

// If there's an operation provided in Array that isn't provided here, it means

// that using the operation on Array is as efficient as it would be if implemented

// for a transient.

template <typename T> struct TransientArray : RefCounted {

} // namespace