#pragma once

#include <stdlib.h>
#include <string.h>
#include <functional>
#include "typedef.h"

template <typename T>
struct LIST_ITERATOR {
  T* ptr;

  LIST_ITERATOR( T* ptr ) : ptr( ptr ) {}
  T& operator*() { return *ptr; }
  T* operator->() { return ptr; }
  LIST_ITERATOR& operator++() { ptr++; return *this; }
  LIST_ITERATOR operator+=( U8 n ) { ptr += n; return *this; }
  bool operator==( const LIST_ITERATOR& other ) { return ptr == other.ptr; }
  bool operator!=( const LIST_ITERATOR& other ) { return ptr != other.ptr; }
};

template <typename T>
using QSORT_FN = std::function< U8( T*, T* ) >;

template <typename T>
static U8 qsort_basic_sort( T* t1, T* t2 ) {
  return (*t1 > *t2);
}

// sort fn should return 0 if t1 < t2, else 1
template < typename T >
static void _qsort( T* arr, I32 low, I32 high, QSORT_FN<T> sortfn = qsort_basic_sort<T> ) {
  if( low > high )
    return;

  T pivot = arr[high];
  I32 i = ( low - 1 );

  for( I32 j = low; j <= high - 1; j++ ) {
    if( sortfn( &arr[j], &pivot ) ) {
      i++;
      T temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
  T temp = arr[i + 1];
  arr[i + 1] = arr[high];
  arr[high] = temp;
  I32 pi = i + 1;

  _qsort( arr, low, pi - 1, sortfn );
  _qsort( arr, pi + 1, high, sortfn );
}

template < typename T >
struct LIST {
  T* data;
  U32 capacity;
  U32 size;

  using ON_EACH_FN = std::function< void(T*) >;
  using ON_SEARCH_FN = std::function< bool(T*) >;

  LIST() {
    data = (T*)malloc( sizeof( T ) );
    memset( data, 0, sizeof( T ) );
    capacity = 1;
    size = 0;
  }

  LIST( U32 _size ) {
    if( !_size ) _size = 1;
    data = (T*)malloc( sizeof( T ) * _size );
    memset( data, 0, _size * sizeof( T ) );
    capacity = _size;
    size = 0;
  }

  LIST( U32 _size, const T* data ) {
    data = (T*)malloc( sizeof( T ) * _size );
    memcpy( data, data, _size * sizeof( T ) );
    size     = _size;
    capacity = _size;
  }

  LIST( const LIST<T>& other ) {
    if( this == &other ) return;

    if( !other.capacity || !other.size ) {
      capacity = 1;
      size     = 0;
      data     = (T*)malloc( sizeof( T ) );
      memset( data, 0, sizeof( T ) );
      return;
    }

    data     = (T*)malloc( sizeof( T ) * other.capacity );
    size     = other.size;
    capacity = other.capacity;
    if constexpr( __is_trivially_copyable(T) )
      memcpy( data, other.data, other.size * sizeof(T) );
    else {
      memset( data, 0, other.capacity * sizeof(T) );
      for( U32 i = 0; i < other.size; i++ )
        data[i] = other.data[i];
    }
  }

  LIST<T>& operator=( const LIST<T>& other ) {
    if( this == &other )
      return *this;

    if( data && data != other.data ) {
      if constexpr( !__is_trivially_destructible(T) ) {
        for( U32 i = 0; i < size; i++ )
          data[i].~T();
      }
      free( data );
    }

    data = 0;

    if( !other.capacity || !other.size || !other.data ) {
      capacity = 1;
      size     = 0;
      data     = (T*)malloc( sizeof( T ) );
      memset( data, 0, sizeof( T ) );
      return *this;
    }

    data     = (T*)malloc( other.capacity * sizeof( T ) );
    size     = other.size;
    capacity = other.capacity;
    if constexpr( __is_trivially_copyable(T) )
      memcpy( data, other.data, other.size * sizeof(T) );
    else {
      memset( data, 0, other.capacity * sizeof(T) );
      for( U32 i = 0; i < other.size; i++ )
        data[i] = other.data[i];
    }

    return *this;
  }

  ~LIST() {
    if constexpr( !__is_trivially_destructible(T) ) {
      for( U32 i = 0; i < size; i++ )
        data[i].~T();
    }
    if( data )
      free( data );
    size = 0;
    data = 0;
  }

  T at( U32 index ) {
    return data[index];
  }

  void reserve( U32 count ) {
    if( capacity >= count )
      return;

    T* newblock = (T*)malloc( count * sizeof( T ) );
    memset( newblock, 0, count * sizeof( T ) );
    if( data ) {
      memcpy( newblock, data, size * sizeof( T ) );
      free( data );
    }
    data = newblock;
    capacity = count;
  }

  void grow() {
    capacity = 2 * capacity;
    T* newblock = (T*)malloc( capacity * sizeof( T ) );
    memset( newblock, 0, capacity * sizeof( T ) );
    if( data ) {
      memcpy( newblock, data, size * sizeof( T ) );
      free( data );
    }
    data = newblock;
  }

  void shrink() {
    if( capacity == 0 )
      return;

    capacity /= 2;
    T* newblock = (T*)malloc( capacity * sizeof( T ) );
    if( data ) {
      memcpy( newblock, data, capacity * sizeof( T ) );
      free( data );
    }
    data = newblock;
  }

  // does not call copy funcs or constructors
  T* emplace( const T& item ) {
    if( capacity == size )
      grow();
    memcpy( &data[size++], &item, sizeof( T ) );

    return &data[size - 1];
  }

  T* push( const T& item ) {
    if( capacity == size )
      grow();
    data[size++] = item;

    return &data[size - 1];
  }

  void resize( U32 size ) {
    if( size > capacity )
      reserve( size * 2 );

    if( size < capacity / 4 )
      shrink();

    if( this->size < size ) {
      memset( &data[this->size], 0, sizeof(T) * (size - this->size) );
      for( U32 i = this->size; i < size; ++i )
        data[i] = T();
    }

    this->size = size;
  }

  // does not call copy constructors, raw memcpy
  void emplace_list( const LIST<T>& list ) {
    if( !list.size )
      return;
    capacity += list.size;
    T* newblock = (T*)malloc( capacity * sizeof(T) );
    memset( newblock, 0, sizeof(T) * capacity );
    if( data ) {
      memcpy( newblock, data, sizeof(T) * size );
      free( data );
    }

    memcpy( &newblock[size], list.data, sizeof(T) * list.size );
    data = newblock;
    size += list.size;
  }

  // slow - pushes every item individually, calls copy constructors
  void push_list( LIST<T>& list ) {
    if constexpr( __is_trivially_copyable(T) ) {
      emplace_list( list );
    } else {
      reserve( list.capacity );
      list.each( fn( T* item ) {
        push( *item );
      } );
    }
  }

  T pop() {
    if( size == 0 ) {
      dlog( "LIST::pop_front() : called on empty list\n" );
      abort();
      return {};
    }

    T ret = data[--size];
    if( size < capacity / 4 )
      shrink();

    return ret;
  }

  T pop_front() {
    if( size == 0  ) {
      dlog( "LIST::pop_front() : called on empty list\n" );
      abort();
      return {};
    }

    T ret = data[0];
    erase( 0 );
    return ret;
  }

  void erase( U32 idx ) {
    if( idx >= size )
      return;

    if constexpr( !__is_trivially_destructible(T) ) {
      data[idx].~T();
      memset( &data[idx], 0, sizeof(T) );
    }

    for( U32 i = idx; i < size - 1; i++ )
      data[i] = data[i + 1];

    if( --size < capacity / 4 )
      shrink();
  }

  T& operator[]( U32 idx ) {
    return data[idx];
  }

  void clear() {
    if constexpr( !__is_trivially_destructible(T) ) {
      for( U32 i = 0; i < size; ++i )
        data[i].~T();
    }

    size = 0;
    free( data );
    data = (T*)malloc( sizeof( T ) );
    memset( data, 0, sizeof( T ) );
    capacity = 1;
  }

  void each( ON_EACH_FN func ) {
    for( U32 i = 0; i < size; ++i ) {
      func( &data[i] );
    }
  }

  I32 idx_of( const T& what ) {
    for( U32 i = 0; i < size; ++i ) {
      if( data[i] == what ) {
        return i;
      }
    }

    return -1;
  }

  I32 idx_of( const T* what ) {
    for( U32 i = 0; i < size; ++i ) {
      if( &data[i] == what ) {
        return i;
      }
    }

    return -1;
  }

  I32 idx_where( ON_SEARCH_FN what ) {
    for( U32 i = 0; i < size; ++i ) {
      if( what( &data[i] ) ) {
        return i;
      }
    }

    return -1;
  }

  T* find( const T& what ) {
    for( U32 i = 0; i < size; ++i ) {
      if( data[i] == what ) {
        return &data[i];
      }
    }
    return 0;
  }

  T* where( ON_SEARCH_FN what ) {
    for( U32 i = 0; i < size; ++i ) {
      if( what( &data[i] ) ) {
        return &data[i];
      }
    }
    return 0;
  }

  // does not copy, sorts in place
  //
  // sort fn should return 0 if t1 < t2, else 1
  LIST<T>& sort( QSORT_FN<T> fn = qsort_basic_sort<T> ) {
    _qsort<T>( data, 0, size - 1, fn );
    return *this;
  }

  // creates a sorted copy
  //
  // sort fn should return 0 if t1 < t2, else 1
  LIST<T> sorted( QSORT_FN<T> fn = qsort_basic_sort<T> ) {
    LIST<T> ret = LIST<T>( *this );
    ret.sort( fn );
    return ret;
  }

  LIST_ITERATOR<T> begin() {
    return LIST_ITERATOR<T>( data );
  }

  LIST_ITERATOR<T> end() {
    return LIST_ITERATOR<T>( data + size );
  }
};