template<class T>
struct SLList_elem {    // single-linked list element
  T d;
  SLList_elem<T>* nxt;
  SLList_elem(T& d1):d(d1),nxt(0) { }
  // no destructor
};

template<class T>     // single-linked list
struct SLinkedList {
  SLList_elem<T> *lis;
  SLinkedList() { lis=0; }
  ~SLinkedList() { reset(); }
  void reset() {
    if (!lis) return;
    SLList_elem<T> *p1,*p2;
    for (p1=lis,p2=lis->nxt;;p1=p2,p2=p2->nxt) {
      delete p1;
      if (!p2) break;
    }
    lis=0;
  }
  void insert(T elm) {
    SLList_elem<T> *p;
    if (!lis)
      lis=new SLList_elem<T>(elm);
    else {
      for (p=lis;;p=p->nxt) {
        if (p->d==elm) { p->d=elm; break; } // assignment maybe needed because of definitions of '=' and '=='
        if (!p->nxt) {
          p->nxt=new SLList_elem<T>(elm);
          break;
        }
      }
    }
  }
  SLList_elem<T> *ord_insert(T elm) {  // if incr then increasing
    const bool incr=true; // increasing
    SLList_elem<T> *p,*p1,
                   *ret=0;
    if (!lis)
      lis=ret=new SLList_elem<T>(elm);
    else if (elm==lis->d);
    else if ((incr && (elm<lis->d)) || (!incr && (lis->d<elm))) {
      p1=ret=new SLList_elem<T>(elm);
      p1->nxt=lis; lis=p1;
    }
    else {
      for (p=lis;;p=p->nxt) {
        if (p->d==elm) break;
        if (!p->nxt) {
          p->nxt=ret=new SLList_elem<T>(elm);
          break;
        }
        if ((incr && (elm < p->nxt->d)) || (!incr && (p->nxt->d < elm))) {
          p1=ret=new SLList_elem<T>(elm);
          p1->nxt=p->nxt; p->nxt=p1;
          break;
        }
      }
    }
    return ret;
  }
  SLList_elem<T> *prepend(T elm) {
    SLList_elem<T> *p,
                   *ret;
    if (!lis)
      lis=ret=new SLList_elem<T>(elm);
    else {
      p=ret=new SLList_elem<T>(elm);
      p->nxt=lis; lis=p;
    }
    return ret;
  }
  SLList_elem<T> *find(T elm) {
    SLList_elem<T> *p,*prev;
    if (!lis) return 0;
    if (lis->d==elm) {
      return lis;
    }
    for (prev=lis,p=lis->nxt;p;) {
      if (p->d==elm) {
        return p;
      }
      else { prev=p; p=p->nxt; }
    }
    puts("SLL: find: elm not found");
    return 0;
  }
  SLList_elem<T> *remove(SLList_elem<T> *p) { // returns next element
    SLList_elem<T> *p1,*prev;
    if (!lis) { puts("SLL: lis=0"); return 0; }
    if (lis==p) {
      p1=lis->nxt; lis->nxt=0; delete lis; lis=p1;
      return lis;
    }
    for (prev=lis,p1=lis->nxt;p1;) {
      if (p==p1) {
        prev->nxt=p1->nxt; p1->nxt=0; delete p1;
        return prev->nxt;
      }
      prev=p1; p1=p1->nxt;
    }
    puts("SLL: remove: ptr not found");
    return 0;
  }
};

template <class T,Uint32 dim>
struct Array {
  T buf[dim];
  T& operator[](Uint32 ind) {
    if (ind<dim) return buf[ind];
    alert("Array: index=%d (>=%d)",ind,dim);// if (debug) abort();
    return buf[0];
  }
};

template<class T>
T* re_alloc(T* arr,int& len) {
  T* new_arr=new T[len*2];
  for (int i=0;i<len;++i) new_arr[i]=arr[i];
  delete[] arr;
  len*=2;
  return new_arr;
}
