/*
 * lftp - file transfer program
 *
 * Copyright (c) 1996-2017 by Alexander V. Lukyanov (lav@yars.free.net)
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef XARRAY_H
#define XARRAY_H 1

#include <sys/types.h>
#include "xmalloc.h"
#include "Ref.h"

class xarray0
{
protected:
   void *buf;
   int len;
private:
   size_t size;
   const unsigned short element_size;
   const short keep_extra;

   void init() { buf=0; size=len=0; }

   xarray0& operator=(const xarray0&); // make assignment fail
   xarray0(const xarray0&);	       // disable cloning

protected:
   void *get_ptr(int n) const { return static_cast<char*>(buf)+n*element_size; }

public:
   xarray0(size_t e,int k=0) : element_size(e),keep_extra(k) { init(); }
   ~xarray0() { xfree(buf); }

   // allocates s slots, with preferred granularity g, may shrink
   void get_space_do(size_t s,size_t g=32);
   void get_space(size_t s,size_t g=32) {
      if(size<s+keep_extra || size/2>=s+keep_extra)
	 get_space_do(s,g);
   }
   // only grows, not shrinks
   void grow_space(size_t s,size_t g=32) {
      if(size<s+keep_extra)
	 get_space_do(s,g);
   }

   size_t get_element_size() const { return element_size; }

   int length() const { return len; }
   int count()  const { return len; }

   void _set_length(size_t n) { len=n; }
   void _nset(const void *s,int len);
   void _unset() { _nset(0,0); }
   void *_insert(int before);
   void *_append() { grow_space(len+1); return get_ptr(len++); }
   void _remove(int i,int j);
   void _remove(int i) { _remove(i,i+1); }
   void _chop() { len--; }
   void *_last() { return get_ptr(len-1); }
   void *_borrow();
   void move_here(xarray0& o);

   operator bool() const { return buf!=0; }

   typedef int (*qsort_cmp_t)(const void*,const void*);
   void qsort(qsort_cmp_t cmp) {
      if(len>0)
	 ::qsort(buf,len,element_size,cmp);
   }
   bool _bsearch(const void*,qsort_cmp_t,int *);
   void *_insert_ordered(const void*,qsort_cmp_t);
};

template<typename T>
class xarray : public xarray0
{
   xarray& operator=(const xarray&); // make assignment fail
   xarray(const xarray&);	       // disable cloning
public:
   xarray() : xarray0(sizeof(T)) {}
   T *get_non_const() { return static_cast<T*>(buf); }
   const T *get() const { return static_cast<const T*>(buf); }
   T& operator[](int i) { return get_non_const()[i]; }
   const T& operator[](int i) const { return get()[i]; }
   size_t get_element_size() const { return sizeof(T); }
/*   operator const T*() const { return get(); }*/
   void nset(const T *s,int len) { _nset(s,len); }
   void set(const xarray<T> &a) { nset(a.get(),a.count()); }
   void set_length(size_t n) { _set_length(n); }
   void unset() { _unset(); }
   void truncate() { set_length(0); }
   void insert(const T& n,int before) { *static_cast<T*>(_insert(before))=n; }
   void append(const T& n) { *static_cast<T*>(_append())=n; }
   void remove(int i) { _remove(i); }
   void remove(int i,int j) { _remove(i,j); }
   void chop() { _chop(); }
   T& last() { return (*this)[len-1]; }
   T *borrow() { return static_cast<T*>(_borrow()); }
   typedef int (*cmp_t)(const T*,const T*);
   void qsort(cmp_t cmp) {
      xarray0::qsort((qsort_cmp_t)cmp);
   }
   void insert_ordered(const T& n,cmp_t cmp) {
      *static_cast<T*>(_insert_ordered(&n,(qsort_cmp_t)cmp))=n;
   }
   int search(const T &x) const {
      for(int i=0; i<len; i++)
      {
	 if(get()[i]==x)
	    return i;
      }
      return -1;
   }
   bool bsearch(const T &x,cmp_t cmp,int *pos) {
      return _bsearch(&x,(qsort_cmp_t)cmp,pos);
   }
   int bsearch(const T &x,cmp_t cmp) {
      int pos;
      return bsearch(x,cmp,&pos) ? pos : -1;
   }
   void allocate(int c,const T& fill) {
      while(c-->0) {
	 append(fill);
      }
   }
};

template<typename T,typename RefT>
class _RefArray : public xarray0
{
   void dispose(int i) { get_non_const()[i].unset(); }
   void dispose(int i,int j) { while(i<j) dispose(i++); }
   void clear(int i) { get_non_const()[i]._clear(); }
   void clear(int i,int j) { while(i<j) clear(i++); }
public:
   _RefArray() : xarray0(sizeof(RefT)) {}
   ~_RefArray() { dispose(0,len); }
   RefT *get_non_const() { return static_cast<RefT*>(buf); }
   const RefT *get() const { return static_cast<const RefT*>(buf); }
   RefT& operator[](int i) { return get_non_const()[i]; }
   const RefT& operator[](int i) const { return get()[i]; }
   size_t get_element_size() const { return sizeof(RefT); }
   void set_length(size_t n) { dispose(n,len); _set_length(n); }
   void unset() { dispose(0,len); _unset(); }
   void truncate() { set_length(0); }
   void insert(T *n,int before) { static_cast<RefT*>(_insert(before))->_set(n); }
   void append(T *n) { static_cast<RefT*>(_append())->_set(n); }
   void remove(int i) { dispose(i); _remove(i); }
   void remove(int i,int j) { dispose(i,j); _remove(i,j); }
   void chop() { dispose(len-1); _chop(); }
   RefT& last() { return (*this)[len-1]; }
   RefT *borrow() { return static_cast<RefT*>(_borrow()); }
   void allocate(int c) { while(c-->0) append((T*)0); }
   typedef int (*cmp_t)(const RefT*,const RefT*);
   void qsort(cmp_t cmp) {
      xarray0::qsort((qsort_cmp_t)cmp);
   }
};

template<typename T>
class RefArray : public _RefArray< T,Ref<T> > {
   RefArray& operator=(const RefArray&); // make assignment fail
   RefArray(const RefArray&);	       // disable cloning
public:
   RefArray() : _RefArray< T,Ref<T> >() {}
};

template<typename T>
class xarray_s : public _RefArray<const char,T> {
   xarray_s& operator=(const xarray_s&); // make assignment fail
   xarray_s(const xarray_s&);	       // disable cloning
public:
   xarray_s() : _RefArray<const char,T>() {}
};

// array of new'ed pointers
template<typename T>
class xarray_p : public xarray0
{
   xarray_p& operator=(const xarray_p&); // make assignment fail
   xarray_p(const xarray_p&);	       // disable cloning

   virtual void dispose(T *p) { delete p; }
   void dispose(int i) { dispose(get_non_const()[i]); }
   void dispose(int i,int j) { while(i<j) dispose(i++); }
   void clear(int i) { get_non_const()[i]=0; }
   void clear(int i,int j) { while(i<j) clear(i++); }
   void z() { clear(len); }
public:
   xarray_p() : xarray0(sizeof(T*),1) {}
   virtual ~xarray_p() { dispose(0,len); }
   T **get_non_const() { return static_cast<T**>(buf); }
   T *const* get() const { return static_cast<T*const*>(buf); }
   T *&operator[](int i) { return get_non_const()[i]; }
   T *operator[](int i) const { return get()[i]; }
   size_t get_element_size() const { return sizeof(T*); }
   void nset(T *const*s,int s_len) { dispose(0,len); _nset(s,s_len); if(buf) z(); }
   void set(const xarray_p<T> &a) { nset(a.get(),a.count()); }
   void set_length(size_t n) { dispose(n,len); _set_length(n); if(buf) z(); }
   void unset() { dispose(0,len); _unset(); }
   void truncate() { set_length(0); }
   void insert(T *n,int before) { *static_cast<T**>(_insert(before))=n; z(); }
   void append(T *n) { *static_cast<T**>(_append())=n; z(); }
   void remove(int i) { dispose(i); _remove(i); z(); }
   void remove(int i,int j) { dispose(i,j); _remove(i,j); z(); }
   void chop() { dispose(len-1); _chop(); }
   T *last() { return (*this)[len-1]; }
   T **borrow() { return static_cast<T**>(_borrow()); }
   typedef int (*cmp_t)(const T**,const T**);
   void qsort(cmp_t cmp) {
      xarray0::qsort((qsort_cmp_t)cmp);
   }
};

// array of malloc'ed pointers
template<typename T>
class xarray_m : public xarray_p<T>
{
   void dispose(T *p) { xfree(p); }
public:
   ~xarray_m() { xarray_p<T>::truncate(); }
};


template<typename T,class A,typename P> class _xqueue
{
protected:
   A q;
   int ptr;
public:
   _xqueue() : ptr(0) {}
   int count() const { return q.count()-ptr; }
   void empty() { q.truncate(); ptr=0; }
   void push(P n) {
      if(ptr>count()) {
	 q.remove(0,ptr);
	 ptr=0;
      }
      q.append(n);
   }
   void remove(int i) {
      if(i==0)
	 ptr++;
      else
	 q.remove(ptr+i);
   }
   // returned pointer valid till the next push
   T& next() { return q[ptr++]; }
   T& operator[](int i) { return q[ptr+i]; }
   const T& operator[](int i) const { return q[ptr+i]; }
   void move_here(_xqueue& o) { q.move_here(o.q); ptr=o.ptr; o.ptr=0; }
};

template<typename T,class A> class xqueue : public _xqueue<T,A,const T&> {};
template<typename T> class xqueue_p : public _xqueue<T*,xarray_p<T>,T*> {};
template<typename T> class xqueue_m : public _xqueue<T*,xarray_m<T>,T*> {};
template<typename T> class RefQueue : public _xqueue<Ref<T>,RefArray<T>,T*> {};

#endif // XARRAY_H