/* Self-bounded vectors (one-dimensional arrays) of things. */
/* Last edited on 2005-01-16 15:01:37 by stolfi */
/* Copyright © 2005 Jorge Stolfi, UNICAMP. See note at end of file. */

/* This module defines tools for handling generic vectors
  (unidimensional arrays) of things, where, unlike standard C vectors,
  the number of elements is stored as part of the representation.
  Thus, when passing a {vec_t} to a procedure, there is no need to
  pass its size as as a separate parameter.
  
  This module also defines efficient and convenient procedures for
  extending and trimming vectors as needed. Expansion doubles the size
  of the vector, so the total cost of the expansion is small and
  proportional to the final size of the vector.
  
  In many contexts, these vectors can replace linked lists, with
  advantages. A typical example would be
  
    double_vec_t x = double_vec_new(initsize);
    { int nx = 0;
      for ...
        { ...
          double_vec_expand(&x, nx);
          x.el[nx] = ...; nx++;
        }
      double_vec_trim(&x, nx);
    }
    for (i = 0; i < x.nel; i++) { print(x.el[i]); }

  */

#ifndef vec_H
#define vec_H

#include <stdlib.h>
#include <js.h>

/* VECTOR DESCRIPTORS */

typedef struct vec_t /* General vector descriptor. */
  { nat nel;   /* Number of elements. */
    void *el;  /* Pointer to element zero. */
  } vec_t;
  /* A {vec_t} {v} describes a uni-dimensional array of {v.nel} elements
    of the same size and type, stored in consecutive memory locations,
    starting at address {v.el}.
    
    The element size is not part of the structure, and must be
    provided separately. Usually, {vec_t}s are used to implement
    vectors of a specific type, such as {int} or {nat}, where the size
    can be provided by macros. See the examples of {int_vec_t} and
    {char_vec_t} below. */

vec_t vec_new(int nel, size_t elsz);
  /* Allocates a new vector with {nel} elements of size {elsz}.
    Bombs out if there is no space for the request. 
    If {nel == 0}, the result has {el == NULL}. */

void vec_expand(vec_t *v, nat index, size_t elsz);
  /* Makes sure that element {v->el[index]} exists, reallocating and
    copying the array {*v->el} if {index >= v->nel}. If that happens,
    the new {v->nel} will be about twice as big as the old one. */

void vec_trim(vec_t *v, nat nel, size_t elsz);
  /* Makes sure that {v.nel == nel}, reallocating and copying 
    the  array {*v->el} if {v.nel != nel}. If {nel == 0}, the 
    result will have {el == NULL}. */

vec_t *vec_cast_ref(void *v);
  /* Casts the argument as an address to a {vec_t}. Can be used to
    apply vec_expand or vec_trim to vectors of specific types. 
    We define it as a function in order to trigger type warnings 
    when {v} is not an address (a common mistake). */

/* SUB-VECTOR DESCRIPTORS */

typedef struct vec_sub_t /* Regular sub-sequence of a {vec_t}. */
  { nat nel;   /* Number of elements in sub-vector. */
    void *el;  /* Pointer to element zero of sub-vector. */
    int step;  /* Increment between consecutive elements (in elements). */
  } vec_sub_t;

vec_sub_t vec_as_sub(vec_t *v);
  /* Returns a sub-vector descriptor for the entire vector
    {v} (with {step == 1}). */
    
vec_sub_t vec_sub(vec_sub_t *vs, nat start, int step, nat nel, size_t elsz);
  /* Returns a descriptor {r} for the specified subsequence of elements
    of {vs}, namely {r[i] = vs[start + i*step]}, for {i = 0..r.nel-1}.
    The {step} cannot be zero.
    
    The result size {r.nel} is the largest integer in {0..nel} such
    that all those elements exist. In particular, if {start} is not in
    {0..vs.nel-1}, then {m} is zero. */
    
/* SOME USEFUL TYPED VECTORS */

/* Vectors of {int}: */

typedef struct int_vec_t { nat nel; int *el; } int_vec_t;

int_vec_t int_vec_new(nat nel);
#define int_vec_expand(nv,index) \
  vec_expand(vec_cast_ref(nv), index, sizeof(int))
#define int_vec_trim(nv,nel) \
  vec_trim(vec_cast_ref(nv), nel, sizeof(int))

/* Vectors of unsigned integers ({nat}): */

typedef struct nat_vec_t { nat nel; nat *el; } nat_vec_t;

nat_vec_t nat_vec_new(nat nel);
#define nat_vec_expand(nv,index) \
  vec_expand(vec_cast_ref(nv), index, sizeof(nat))
#define nat_vec_trim(nv,nel) \
  vec_trim(vec_cast_ref(nv), nel, sizeof(nat))

/* Vectors of {double}: */

typedef struct double_vec_t { nat nel; double *el; } double_vec_t;

double_vec_t double_vec_new(nat nel);
#define double_vec_expand(nv,index) \
  vec_expand(vec_cast_ref(nv), index, sizeof(double))
#define double_vec_trim(nv,nel) \
  vec_trim(vec_cast_ref(nv), nel, sizeof(double))

/* Vectors of {bool}: */

typedef struct bool_vec_t { nat nel; bool *el; } bool_vec_t;

bool_vec_t bool_vec_new(nat nel);
#define bool_vec_expand(nv,index) \
  vec_expand(vec_cast_ref(nv), index, sizeof(bool))
#define bool_vec_trim(nv,nel) \
  vec_trim(vec_cast_ref(nv), nel, sizeof(bool))

/* Vectors of {char}: */

typedef struct char_vec_t { nat nel; char *el; } char_vec_t;

char_vec_t char_vec_new(nat nel);
#define char_vec_expand(nv,index) \
  vec_expand(vec_cast_ref(nv), index, sizeof(char))
#define char_vec_trim(nv,nel) \
  vec_trim(vec_cast_ref(nv), nel, sizeof(char))

/* Vectors of strings ({char*}): */

typedef struct string_vec_t { nat nel; char **el; } string_vec_t;

string_vec_t string_vec_new(nat nel);
#define string_vec_expand(nv,index) \
  vec_expand(vec_cast_ref(nv), index, sizeof(char *))
#define string_vec_trim(nv,nel) \
  vec_trim(vec_cast_ref(nv), nel, sizeof(char *))

#endif
/* COPYRIGHT AND AUTHORSHIP NOTICE

  Copyright © 2005 Jorge Stolfi, Universidade Estadual de Campinas (UNICAMP).
  Created by Jorge Stolfi in 1992--2005.
  
  This source file can be freely distributed, used, and modified,
  provided that this copyright and authorship notice is preserved in
  all copies, and that any modified versions of this file are clearly
  marked as such.
  
  This software has NO WARRANTY of correctness or applicability for
  any purpose. Neither the author nor his employers shall be held
  responsible for any losses or damages that may result from its use.

  END OF NOTICE */