/* MIT License
 *
 * Copyright (c) 2023 Tyge Løvset
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#include "priv/linkage.h"

#ifndef CPQUE_H_INCLUDED
#include "ccommon.h"
#include <stdlib.h>
#include "forward.h"
#endif

#define _i_prefix cpque_
#define _i_ispque
#include "priv/template.h"
#ifndef i_is_forward
  _cx_DEFTYPES(_c_cpque_types, _cx_Self, i_key);
#endif
typedef i_keyraw _cx_raw;

STC_API void _cx_MEMB(_make_heap)(_cx_Self* self);
STC_API void _cx_MEMB(_erase_at)(_cx_Self* self, intptr_t idx);
STC_API _cx_value* _cx_MEMB(_push)(_cx_Self* self, _cx_value value);

STC_INLINE _cx_Self _cx_MEMB(_init)(void)
    { return c_LITERAL(_cx_Self){NULL}; }

STC_INLINE void _cx_MEMB(_put_n)(_cx_Self* self, const _cx_raw* raw, intptr_t n)
    { while (n--) _cx_MEMB(_push)(self, i_keyfrom(*raw++)); }

STC_INLINE _cx_Self _cx_MEMB(_from_n)(const _cx_raw* raw, intptr_t n)
    { _cx_Self cx = {0}; _cx_MEMB(_put_n)(&cx, raw, n); return cx; }

STC_INLINE bool _cx_MEMB(_reserve)(_cx_Self* self, const intptr_t cap) {
    if (cap != self->_len && cap <= self->_cap) return true;
    _cx_value *d = (_cx_value *)i_realloc(self->data, cap*c_sizeof *d);
    return d ? (self->data = d, self->_cap = cap, true) : false;
}

STC_INLINE void _cx_MEMB(_shrink_to_fit)(_cx_Self* self)
    { _cx_MEMB(_reserve)(self, self->_len); }

STC_INLINE _cx_Self _cx_MEMB(_with_capacity)(const intptr_t cap) {
    _cx_Self out = {NULL}; _cx_MEMB(_reserve)(&out, cap);
    return out;
}

STC_INLINE _cx_Self _cx_MEMB(_with_size)(const intptr_t size, i_key null) {
    _cx_Self out = {NULL}; _cx_MEMB(_reserve)(&out, size);
    while (out._len < size) out.data[out._len++] = null;
    return out;
}

STC_INLINE void _cx_MEMB(_clear)(_cx_Self* self) {
    intptr_t i = self->_len; self->_len = 0;
    while (i--) { i_keydrop((self->data + i)); }
}

STC_INLINE void _cx_MEMB(_drop)(_cx_Self* self)
    { _cx_MEMB(_clear)(self); i_free(self->data); }

STC_INLINE intptr_t _cx_MEMB(_size)(const _cx_Self* q)
    { return q->_len; }

STC_INLINE bool _cx_MEMB(_empty)(const _cx_Self* q)
    { return !q->_len; }

STC_INLINE intptr_t _cx_MEMB(_capacity)(const _cx_Self* q)
    { return q->_cap; }

STC_INLINE const _cx_value* _cx_MEMB(_top)(const _cx_Self* self)
    { return &self->data[0]; }

STC_INLINE void _cx_MEMB(_pop)(_cx_Self* self)
    { c_assert(!_cx_MEMB(_empty)(self)); _cx_MEMB(_erase_at)(self, 0); }

#if !defined i_no_clone
STC_API _cx_Self _cx_MEMB(_clone)(_cx_Self q);

STC_INLINE void _cx_MEMB(_copy)(_cx_Self *self, const _cx_Self* other) {
    if (self->data == other->data) return;
    _cx_MEMB(_drop)(self);
    *self = _cx_MEMB(_clone)(*other);
}
STC_INLINE i_key _cx_MEMB(_value_clone)(_cx_value val)
    { return i_keyclone(val); }
#endif // !i_no_clone

#if !defined i_no_emplace
STC_INLINE void _cx_MEMB(_emplace)(_cx_Self* self, _cx_raw raw)
    { _cx_MEMB(_push)(self, i_keyfrom(raw)); }
#endif // !i_no_emplace

/* -------------------------- IMPLEMENTATION ------------------------- */
#if defined(i_implement) || defined(i_static)

STC_DEF void
_cx_MEMB(_sift_down_)(_cx_Self* self, const intptr_t idx, const intptr_t n) {
    _cx_value t, *arr = self->data - 1;
    for (intptr_t r = idx, c = idx*2; c <= n; c *= 2) {
        c += i_less((&arr[c]), (&arr[c + (c < n)]));
        if (!(i_less((&arr[r]), (&arr[c])))) return;
        t = arr[r], arr[r] = arr[c], arr[r = c] = t;
    }
}

STC_DEF void
_cx_MEMB(_make_heap)(_cx_Self* self) {
    intptr_t n = self->_len;
    for (intptr_t k = n/2; k != 0; --k)
        _cx_MEMB(_sift_down_)(self, k, n);
}

#if !defined i_no_clone
STC_DEF _cx_Self _cx_MEMB(_clone)(_cx_Self q) {
    _cx_Self out = _cx_MEMB(_with_capacity)(q._len);
    for (; out._len < out._cap; ++q.data)
        out.data[out._len++] = i_keyclone((*q.data));
    return out;
}
#endif

STC_DEF void
_cx_MEMB(_erase_at)(_cx_Self* self, const intptr_t idx) {
    i_keydrop((self->data + idx));
    const intptr_t n = --self->_len;
    self->data[idx] = self->data[n];
    _cx_MEMB(_sift_down_)(self, idx + 1, n);
}

STC_DEF _cx_value*
_cx_MEMB(_push)(_cx_Self* self, _cx_value value) {
    if (self->_len == self->_cap)
        _cx_MEMB(_reserve)(self, self->_len*3/2 + 4);
    _cx_value *arr = self->data - 1; /* base 1 */
    intptr_t c = ++self->_len;
    for (; c > 1 && (i_less((&arr[c/2]), (&value))); c /= 2)
        arr[c] = arr[c/2];
    arr[c] = value;
    return arr + c;
}

#endif
#define CPQUE_H_INCLUDED
#include "priv/template2.h"
#undef _i_ispque