lib/ts/Vec.h

/** @file

  Vector and Set templates with qsort.

  @section license License

  Licensed to the Apache Software Foundation (ASF) under one
  or more contributor license agreements.  See the NOTICE file
  distributed with this work for additional information
  regarding copyright ownership.  The ASF licenses this file
  to you under the Apache License, Version 2.0 (the
  "License"); you may not use this file except in compliance
  with the License.  You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the specific language governing permissions and
  limitations under the License.
*/

#ifndef _vec_H_
#define _vec_H_

#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include "defalloc.h"
#include "ink_assert.h"

// Simple Vector class, also supports open hashed sets

#define VEC_INTEGRAL_SHIFT_DEFAULT      2               /* power of 2 (1 << VEC_INTEGRAL_SHIFT)*/
#define VEC_INTEGRAL_SIZE               (1 << (S))
#define VEC_INITIAL_SHIFT               ((S)+1)
#define VEC_INITIAL_SIZE                (1 << VEC_INITIAL_SHIFT)

#define SET_LINEAR_SIZE         4               /* must be <= than VEC_INTEGRAL_SIZE */
#define SET_INITIAL_INDEX       2

template <class C, class A = DefaultAlloc, int S = VEC_INTEGRAL_SHIFT_DEFAULT>  // S must be a power of 2
class Vec {
 public:
  size_t        n;
  size_t        i;      // size index for sets, reserve for vectors
  C             *v;
  C             e[VEC_INTEGRAL_SIZE];
  
  Vec();
  Vec<C,A,S>(const Vec<C,A,S> &vv);
  Vec<C,A,S>(const C c);
  ~Vec();

  C &operator[](int i) const { return v[i]; }

  C get(size_t i);
  void add(C a);  
  void push_back(C a) { add(a); } // std::vector name
  bool add_exclusive(C a);
  C& add();
  C pop();
  void reset();
  void clear();
  void free_and_clear();
  void delete_and_clear();
  void set_clear();
  C *set_add(C a);
  void set_remove(C a); // expensive, use BlockHash for cheaper remove
  C *set_add_internal(C a);
  bool set_union(Vec<C,A,S> &v);
  int set_intersection(Vec<C,A,S> &v);
  int some_intersection(Vec<C,A,S> &v);
  int some_disjunction(Vec<C,A,S> &v);
  int some_difference(Vec<C,A,S> &v);
  void set_intersection(Vec<C,A,S> &v, Vec<C,A,S> &result);
  void set_disjunction(Vec<C,A,S> &v, Vec<C,A,S> &result);
  void set_difference(Vec<C,A,S> &v, Vec<C,A,S> &result);
  size_t set_count() const;
  size_t count() const;
  C *in(C a);
  C *set_in(C a);
  C first_in_set();
  C *set_in_internal(C a);
  void set_expand();
  ssize_t index(C a) const;
  void set_to_vec();
  void vec_to_set();
  void move(Vec<C,A,S> &v);
  void copy(const Vec<C,A,S> &v);
  void fill(size_t n);
  void append(const Vec<C> &v);
  template <typename CountType> void append(const C * src, CountType count);
  void prepend(const Vec<C> &v);
  void remove_index(int index);
  void remove(C a) { int i = index(a); if (i>=0) remove_index(i); }
  C& insert(size_t index);
  void insert(size_t index, Vec<C> &vv);
  void insert(size_t index, C a);
  void push(C a) { insert(0, a); }
  void reverse();
  void reserve(size_t n);
  C* end() const { return v + n; }
  C &first() const { return v[0]; }
  C &last() const { return v[n-1]; }
  Vec<C,A,S>& operator=(Vec<C,A,S> &v) { this->copy(v); return *this; }
  int length () const { return n; }
  // vector::size() intentionally not implemented because it should mean "bytes" not count of elements
  int write(int fd);
  int read(int fd);
  void qsort(bool (*lt)(C,C));
  
private:
  void move_internal(Vec<C,A,S> &v);
  void copy_internal(const Vec<C,A,S> &v);
  void add_internal(C a);
  C& add_internal();
  void addx();
};

// c -- class, p -- pointer to elements of v, v -- vector
#define forv_Vec(_c, _p, _v) if ((_v).n) for (_c *qq__##_p = (_c*)0, *_p = (_v).v[0]; \
                    ((intptr_t)(qq__##_p) < (_v).length()) && ((_p = (_v).v[(intptr_t)qq__##_p]) || 1); qq__##_p = (_c*)(((intptr_t)qq__##_p) + 1))
#define for_Vec(_c, _p, _v) if ((_v).n) for (_c *qq__##_p = (_c*)0, _p = (_v).v[0]; \
                    ((intptr_t)(qq__##_p) < (_v).length()) && ((_p = (_v).v[(intptr_t)qq__##_p]) || 1); qq__##_p = (_c*)(((intptr_t)qq__##_p) + 1))
#define forvp_Vec(_c, _p, _v) if ((_v).n) for (_c *qq__##_p = (_c*)0, *_p = &(_v).v[0]; \
                    ((intptr_t)(qq__##_p) < (_v).length()) && ((_p = &(_v).v[(intptr_t)qq__##_p]) || 1); qq__##_p = (_c*)(((intptr_t)qq__##_p) + 1))

template <class C, class A = DefaultAlloc, int S = VEC_INTEGRAL_SHIFT_DEFAULT> class Accum { public:
  Vec<C,A,S> asset;
  Vec<C,A,S> asvec;
  void add(C c) { if (asset.set_add(c)) asvec.add(c); }
  void add(Vec<C,A,S> v) { for (int i = 0; i < v.n; i++) if (v.v[i]) add(v.v[i]); }
  void clear() { asset.clear(); asvec.clear(); }
};

// Intervals store sets in interval format (e.g. [1..10][12..12]).
// Inclusion test is by binary search on intervals.
// Deletion is not supported
class Intervals : public Vec<int> {
 public:
  void insert(int n);
  bool in(int n) const;
};

// UnionFind supports fast unify and finding of
// 'representitive elements'.
// Elements are numbered from 0 to N-1.
class UnionFind : public Vec<int> {
 public:
  // set number of elements, initialized to singletons, may be called repeatedly to increase size
  void size(int n); 
  // return representitive element
  int find(int n);
  // unify the sets containing the two elements
  void unify(int n, int m);
};

extern const uintptr_t prime2[];
extern const uintptr_t open_hash_primes[256];

/* IMPLEMENTATION */

template <class C, class A, int S> inline
Vec<C,A,S>::Vec() : n(0), i(0), v(0) {
  memset(&e[0], 0, sizeof(e));
}

template <class C, class A, int S> inline
Vec<C,A,S>::Vec(const Vec<C,A,S> &vv) {
  copy(vv);
}

template <class C, class A, int S> inline
Vec<C,A,S>::Vec(C c) {
  n = 1;
  i = 0;
  v = &e[0];
  e[0] = c;
}

template <class C, class A, int S> inline C
Vec<C,A,S>::get(size_t i) {
  if (i < n && i >= 0)
    return v[i];
  else
    return C();
}

template <class C, class A, int S> inline void 
Vec<C,A,S>::add(C a) {
  if (n & (VEC_INTEGRAL_SIZE-1))
    v[n++] = a;
  else if (!v)
    (v = e)[n++] = a;
  else
    add_internal(a);
}

template <class C, class A, int S> inline C&
Vec<C,A,S>::add() {
  C *ret;
  if (n & (VEC_INTEGRAL_SIZE-1))
    ret = &v[n++];
  else if (!v)
    ret = &(v = e)[n++];
  else
    ret = &add_internal();
  return *ret;
}

template <class C, class A, int S> inline C
Vec<C,A,S>::pop() {
  if (!n)
    return 0;
  n--;
  C ret = v[n];
  if (!n)
    clear();
  return ret;
}

template <class C, class A, int S> inline void
Vec<C,A,S>::set_clear() {
  memset(v, 0, n * sizeof(C));
}

template <class C, class A, int S> inline C *
Vec<C,A,S>::set_add(C a) {
  if (n < SET_LINEAR_SIZE) {
    for (C *c = v; c < v + n; c++)
      if (*c == a)
        return 0;
    add(a);
    return &v[n-1];
  }
  if (n == SET_LINEAR_SIZE) {
    Vec<C,A,S> vv(*this);
    clear();
    for (C *c = vv.v; c < vv.v + vv.n; c++) {
      set_add_internal(*c);
    }
  }
  return set_add_internal(a);
}

template <class C, class A, int S> void
Vec<C,A,S>::set_remove(C a) {
  Vec<C,A,S> tmp;
  tmp.move(*this);
  for (C *c = tmp.v; c < tmp.v + tmp.n; c++)
    if (*c != a)
      set_add(a);
}

template <class C, class A, int S> inline size_t
Vec<C,A,S>::count() const {
  int x = 0;
  for (C *c = v; c < v + n; c++)
    if (*c)
      x++;
  return x;
}

template <class C, class A, int S> inline C*
Vec<C,A,S>::in(C a) {
  for (C *c = v; c < v + n; c++)
    if (*c == a)
      return c;
  return NULL;
}

template <class C, class A, int S> inline bool
Vec<C,A,S>::add_exclusive(C a) {
  if (!in(a)) {
    add(a);
    return true;
  } else 
    return false;
}

template <class C, class A, int S> inline C *
Vec<C,A,S>::set_in(C a) {
  if (n <= SET_LINEAR_SIZE)
    return in(a);
  return set_in_internal(a);
}

template <class C, class A, int S> inline C
Vec<C,A,S>::first_in_set() {
  for (C *c = v; c < v + n; c++)
    if (*c)
      return *c;
  return 0;
}

template <class C, class A, int S> inline ssize_t
Vec<C,A,S>::index(C a) const {
  for (C *c = v; c < v + n; c++) {
    if (*c == a) {
      return c - v;
    }
  }
  return -1;
}

template <class C, class A, int S> inline void 
Vec<C,A,S>::move_internal(Vec<C,A,S> &vv)  {
  n = vv.n;
  i = vv.i;
  if (vv.v == &vv.e[0]) { 
    memcpy(e, &vv.e[0], sizeof(e));
    v = e;
  } else
    v = vv.v;
}

template <class C, class A, int S> inline void 
Vec<C,A,S>::move(Vec<C,A,S> &vv)  {
  move_internal(vv); 
  vv.v = 0;
  vv.clear();
}

template <class C, class A, int S> inline void 
Vec<C,A,S>::copy(const Vec<C,A,S> &vv)  {
  n = vv.n;
  i = vv.i;
  if (vv.v == &vv.e[0]) { 
    memcpy(e, &vv.e[0], sizeof(e));
    v = e;
  } else {
    if (vv.v) 
      copy_internal(vv);
    else
      v = 0;
  }
}

template <class C, class A, int S> inline void 
Vec<C,A,S>::fill(size_t nn)  {
  for (size_t i = n; i < nn; i++)
    add() = 0;
}

template <class C, class A, int S> inline void
Vec<C,A,S>::append(const Vec<C> &vv)  {
  for (C *c = vv.v; c < vv.v + vv.n; c++)
    if (*c != 0)
      add(*c);
}

template <class C, class A, int S>
template <typename CountType>
inline void
Vec<C,A,S>::append(const C * src, CountType count)  {
  reserve(length() + count);
  for (CountType c = 0; c < count; ++c) {
    add(src[c]);
  }
}

template <class C, class A, int S> inline void
Vec<C,A,S>::prepend(const Vec<C> &vv)  {
  if (vv.n) {
    int oldn = n;
    fill(n + vv.n);
    if (oldn)
      memmove(&v[vv.n], &v[0], oldn * sizeof(v[0]));
    memcpy(&v[0], vv.v, vv.n * sizeof(v[0]));
  }
}

template <class C, class A, int S> void 
Vec<C,A,S>::add_internal(C a) {
  addx();
  v[n++] = a;
}

template <class C, class A, int S> C&
Vec<C,A,S>::add_internal() {
  addx();
  return v[n++];
}

template <class C, class A, int S> C *
Vec<C,A,S>::set_add_internal(C c) {
  size_t j, k;
  if (n) {
    uintptr_t h = (uintptr_t)c;
    h = h % n;
    for (k = h, j = 0; j < i + 3; j++) {
      if (!v[k]) {
        v[k] = c;
        return &v[k];
      } else if (v[k] == c) {
        return 0;
      }
      k = (k + open_hash_primes[j]) % n;
    }
  }
  Vec<C,A,S> vv;
  vv.move_internal(*this);
  set_expand();
  if (vv.v) {
    set_union(vv);
  }
  return set_add(c);
}

template <class C, class A, int S> C *
Vec<C,A,S>::set_in_internal(C c) {
  size_t j, k;
  if (n) {
    uintptr_t h = (uintptr_t)c;
    h = h % n;
    for (k = h, j = 0; j < i + 3; j++) {
      if (!v[k])
        return 0;
      else if (v[k] == c)
        return &v[k];
      k = (k + open_hash_primes[j]) % n;
    }
  }
  return 0;
}

template <class C, class A, int S> bool
Vec<C,A,S>::set_union(Vec<C,A,S> &vv) {
  bool changed = false;
  for (size_t i = 0; i < vv.n; i++) {
    if (vv.v[i]) {
      changed = set_add(vv.v[i]) || changed;
    }
  }
  return changed;
} 

template <class C, class A, int S> int
Vec<C,A,S>::set_intersection(Vec<C,A,S> &vv) {
  Vec<C,A,S> tv;
  tv.move(*this);
  int changed = 0;
  for (int i = 0; i < tv.n; i++)
    if (tv.v[i]) {
      if (vv.set_in(tv.v[i]))
        set_add(tv.v[i]);
      else
        changed = 1;
    }
  return changed;
} 

template <class C, class A, int S> int
Vec<C,A,S>::some_intersection(Vec<C,A,S> &vv) {
  for (int i = 0; i < n; i++)
    if (v[i])
      if (vv.set_in(v[i]))
        return 1;
  return 0;
} 

template <class C, class A, int S> int
Vec<C,A,S>::some_disjunction(Vec<C,A,S> &vv) {
  for (int i = 0; i < n; i++)
    if (v[i])
      if (!vv.set_in(v[i]))
        return 1;
  for (int i = 0; i < vv.n; i++)
    if (vv.v[i])
      if (!set_in(vv.v[i]))
        return 1;
  return 0;
} 

template <class C, class A, int S> void
Vec<C,A,S>::set_intersection(Vec<C,A,S> &vv, Vec<C,A,S> &result) {
  for (int i = 0; i < n; i++)
    if (v[i])
      if (vv.set_in(v[i]))
        result.set_add(v[i]);
} 

template <class C, class A, int S> void
Vec<C,A,S>::set_disjunction(Vec<C,A,S> &vv, Vec<C,A,S> &result) {
  for (int i = 0; i < n; i++)
    if (v[i])
      if (!vv.set_in(v[i]))
        result.set_add(v[i]);
  for (int i = 0; i < vv.n; i++)
    if (vv.v[i])
      if (!set_in(vv.v[i]))
        result.set_add(vv.v[i]);
} 

template <class C, class A, int S> void
Vec<C,A,S>::set_difference(Vec<C,A,S> &vv, Vec<C,A,S> &result) {
  for (int i = 0; i < n; i++)
    if (v[i])
      if (!vv.set_in(v[i]))
        result.set_add(v[i]);
} 

template <class C, class A, int S> int
Vec<C,A,S>::some_difference(Vec<C,A,S> &vv) {
  for (int i = 0; i < n; i++)
    if (v[i])
      if (!vv.set_in(v[i]))
        return 1;
  return 0;
} 

template <class C, class A, int S> size_t
Vec<C,A,S>::set_count() const {
  size_t x = 0;
  for (size_t i = 0; i < n; i++) {
    if (v[i]) {
      x++;
    }
  }
  return x;
} 

template <class C, class A, int S> void
Vec<C,A,S>::set_to_vec() {
  C *x = &v[0], *y = x;
  for (; y < v + n; y++) {
    if (*y) {
      if (x != y)
         *x = *y;
       x++;
    }
  }
  if (i) {
    i = prime2[i];  // convert set allocation to reserve
    if (i - n > 0)
      memset(&v[n], 0, (i - n) * (sizeof(C)));
  } else {
    i = 0;
    if (v == &e[0] && VEC_INTEGRAL_SIZE - n > 0)
      memset(&v[n], 0, (VEC_INTEGRAL_SIZE - n) * (sizeof(C)));
  }
}

template <class C, class A, int S> void
Vec<C,A,S>::vec_to_set() {
  Vec<C,A,S> vv;
  vv.move(*this);
  for (C *c = vv.v; c < vv.v + vv.n; c++)
    set_add(*c);
}

template <class C, class A, int S> void 
Vec<C,A,S>::remove_index(int index) {
  if (n > 1)
    memmove(&v[index], &v[index+1], (n - 1 - index) * sizeof(v[0]));
  n--;
  if (n <= 0)
    v = e;
}

template <class C, class A, int S> void
Vec<C,A,S>::insert(size_t index, C a) {
  add();
  memmove(&v[index+1], &v[index], (n - index - 1) * sizeof(C));
  v[index] = a;
}

template <class C, class A, int S> void
Vec<C,A,S>::insert(size_t index, Vec<C> &vv) {
  fill(n + vv.n);
  memmove(&v[index+vv.n], &v[index], (n - index - 1) * sizeof(C));
  for (int x = 0; x < vv.n; x++)
    v[index + x] = vv[x];
}

template <class C, class A, int S>  C &
Vec<C,A,S>::insert(size_t index) {
  add();
  memmove(&v[index+1], &v[index], (n - index - 1) * sizeof(C));
  memset(&v[index], 0, sizeof(C));
  return v[index];
}

template <class C, class A, int S> void 
Vec<C,A,S>::reverse() {
  for (int i = 0; i < n/2; i++) {
    C *s = &v[i], *e = &v[n - 1 - i];
    C t;
    memcpy(&t, s, sizeof(t));
    memcpy(s, e, sizeof(t));
    memcpy(e, &t, sizeof(t));
  }
}

template <class C, class A, int S> void
Vec<C,A,S>::copy_internal(const Vec<C,A,S> &vv) {
  int l = n, nl = (1 + VEC_INITIAL_SHIFT);
  l = l >> VEC_INITIAL_SHIFT;
  while (l) { l = l >> 1; nl++; }
  nl = 1 << nl;
  v = (C*)A::alloc(nl * sizeof(C));
  memcpy(v, vv.v, n * sizeof(C));
  memset(v + n, 0, (nl - n) * sizeof(C)); 
  if (i > n)  // reset reserve
    i = 0;
}

template <class C, class A, int S> void
Vec<C,A,S>::set_expand() {
  if (!n)
    i = SET_INITIAL_INDEX;
  else
    i = i + 1;
  n = prime2[i];
  v = (C*)A::alloc(n * sizeof(C));
  memset(v, 0, n * sizeof(C));
}

template <class C, class A, int S> inline void 
Vec<C,A,S>::reserve(size_t x) {
  if (x <= n)
    return;
  unsigned xx = 1 << VEC_INITIAL_SHIFT;
  while (xx < x) xx *= 2;
  i = xx;
  void *vv = (void*)v;
  v = (C*)A::alloc(i * sizeof(C));
  if (vv && n)
    memcpy(v, vv, n * sizeof(C));
  memset(&v[n], 0, (i-n) * sizeof(C));
  if (vv && vv != e)
    A::free(vv);
}

template <class C, class A, int S> inline void 
Vec<C,A,S>::addx() {
  if (!v) {
    v = e;
    return;
  }
  if (v == e) {
    v = (C*)A::alloc(VEC_INITIAL_SIZE * sizeof(C));
    memcpy(v, &e[0], n * sizeof(C));
    ink_assert(n < VEC_INITIAL_SIZE);
    memset(&v[n], 0, (VEC_INITIAL_SIZE - n) * sizeof(C));
  } else {
    if ((n & (n-1)) == 0) {
      size_t nl = n * 2;
      if (nl <= i) {
        return;
      } else {
        i = 0;
      }
      void *vv = (void*)v;
      v = (C*)A::alloc(nl * sizeof(C));
      memcpy(v, vv, n * sizeof(C));
      memset(&v[n], 0, n * sizeof(C));
      A::free(vv);
    }
  }
}

template <class C, class A, int S> inline void
Vec<C,A,S>::reset() {
  v = NULL;
  n = 0;
  i = 0;
}

template <class C, class A, int S> inline void
Vec<C,A,S>::clear() {
  if (v && v != e) A::free(v);
  reset();
}

template <class C, class A, int S> inline void
Vec<C,A,S>::free_and_clear() {
  for (int x = 0; x < n; x++)
    if (v[x])
      A::free(v[x]);
  clear();
}

template <class C, class A, int S> inline void
Vec<C,A,S>::delete_and_clear() {
  for (size_t x = 0; x < n; x++) {
    if (v[x]) {
      delete v[x];
    }
  }
  clear();
}

template <class C, class A, int S> 
inline Vec<C,A,S>::~Vec() { 
  if (v && v != e) A::free(v); 
}

template <class C, class A, int S> 
inline int marshal_size(Vec<C,A,S> &v) {
  int l = sizeof(int) * 2;
  for (int x = 0; x < v.n; x++)
    l += ::marshal_size(v.v[x]);
  return l;
}

template <class C, class A, int S> 
inline int marshal(Vec<C,A,S> &v, char *buf) {
  char *x = buf;
  *(int*)x = v.n; x += sizeof(int);
  *(int*)x = v.i; x += sizeof(int);
  for (int i = 0; i < v.n; i++)
    x += ::marshal(v.v[i], x);
  return x - buf;
}

template <class C, class A, int S> 
inline int unmarshal(Vec<C,A,S> &v, char *buf) {
  char *x = buf;
  v.n = *(int*)x; x += sizeof(int);
  v.i = *(int*)x; x += sizeof(int);
  if (v.n) {
    v.v = (C*)A::alloc(sizeof(C) * v.n);
    memset(v.v, 0, sizeof(C) * v.n);
  } else
    v.v = v.e;
  for (int i = 0; i < v.n; i++)
    x += ::unmarshal(v.v[i], x);
  return x - buf;
}

template <class C, class A, int S> 
inline int Vec<C,A,S>::write(int fd) {
  int r = 0, t = 0;
  if ((r = ::write(fd, this, sizeof(*this))) < 0) return r; t += r;
  if ((r = ::write(fd, v, n * sizeof(C))) < 0) return r; t += r;
  return t;
}

template <class C, class A, int S> 
inline int Vec<C,A,S>::read(int fd) {
  int r = 0, t = 0;
  if ((r = ::read(fd, this, sizeof(*this))) < 0) return r; t += r;
  v = (C*)A::alloc(sizeof(C) * n);
  memset(v, 0, sizeof(C) * n);
  if ((r = ::read(fd, v, n * sizeof(C))) < 0) return r; t += r;
  return t;
}

template <class C> 
inline void qsort_Vec(C *left, C *right, bool (*lt)(C,C)) {
 Lagain:
  if (right - left < 5) {
    for (C *y = right - 1; y > left; y--) {
      for (C *x = left; x < y; x++) {
        if (lt(x[1],x[0])) {
          C t = x[0];
          x[0] = x[1];
          x[1] = t;
        }
      }
    }
  } else {
    C  *i = left + 1, *j = right - 1;
    C x = *left;
    for (;;) {
      while (lt(x,*j)) j--;
      while (i < j && lt(*i,x)) i++;
      if (i >= j) break;
      C t = *i;
      *i = *j;
      *j = t;
      i++; j--;
    }
    if (j == right - 1) {
      *left = *(right - 1);
      *(right - 1) = x;
      right--;
      goto Lagain;
    }
    if (left < j) qsort_Vec<C>(left, j + 1, lt);
    if (j + 2 < right) qsort_Vec<C>(j + 1, right, lt);
  }
}

template <class C> 
inline void qsort_VecRef(C *left, C *right, bool (*lt)(C&,C&)) {
 Lagain:
  if (right - left < 5) {
    for (C *y = right - 1; y > left; y--) {
      for (C *x = left; x < y; x++) {
        if (lt(x[1],x[0])) {
          C t = x[0];
          x[0] = x[1];
          x[1] = t;
        }
      }
    }
  } else {
    C  *i = left + 1, *j = right - 1;
    C x = *left;
    for (;;) {
      while (lt(x,*j)) j--;
      while (i < j && lt(*i,x)) i++;
      if (i >= j) break;
      C t = *i;
      *i = *j;
      *j = t;
      i++; j--;
    }
    if (j == right - 1) {
      *left = *(right - 1);
      *(right - 1) = x;
      right--;
      goto Lagain;
    }
    if (left < j) qsort_VecRef<C>(left, j + 1, lt);
    if (j + 2 < right) qsort_VecRef<C>(j + 1, right, lt);
  }
}

template <class C, class A, int S> 
inline void Vec<C,A,S>::qsort(bool (*lt)(C,C)) {
  if (n)
    qsort_Vec<C>(&v[0], end(), lt);
}

void test_vec();

#endif