/*

  $Id: isort.h,v 1.6 2008/04/17 17:39:48 karl Exp $

  Copyright (C) 2004, 2005, 2008 Rocky Bernstein <rocky@gnu.org>

  Copyright (C) 1998 Monty xiphmont@mit.edu

  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 _ISORT_H_

#define _ISORT_H_

typedef struct sort_link{

  struct sort_link *next;

} sort_link_t;

typedef struct sort_info {

  int16_t *vector;               /* vector (storage doesn't belong to us) */

  long  *abspos;                 /* pointer for side effects */

  long  size;                    /* vector size */

  long  maxsize;                 /* maximum vector size */

  long sortbegin;                /* range of contiguous sorted area */

  long lo,hi;                    /* current post, overlap range */

  int  val;                      /* ...and val */

  /* sort structs */

  sort_link_t **head;           /* sort buckets (65536) */

  long *bucketusage;          /*  of used buckets (65536) */

  long lastbucket;

  sort_link_t *revindex;

} sort_info_t;

/*! ========================================================================

 * sort_alloc()

 *

 * Allocates and initializes a new, empty sort_info object, which can

 * be used to index up to (size) samples from a vector.

 */

extern sort_info_t *sort_alloc(long int size);

/*! ========================================================================

 * sort_unsortall() (internal)

 *

 * This function resets the index for further use with a different

 * vector or range, without the overhead of an unnecessary free/alloc.

 */

extern void sort_unsortall(sort_info_t *i);

/*! ========================================================================

 * sort_setup()

 *

 * This function initializes a previously allocated sort_info_t.  The

 * sort_info_t is associated with a vector of samples of length

 * (size), whose position begins at (*abspos) within the CD's stream

 * of samples.  Only the range of samples between (sortlo, sorthi)

 * will eventually be indexed for fast searching.  (sortlo, sorthi)

 * are absolute sample positions.

 *

 * ???: Why is abspos a pointer?  Why not just store a copy?

 *

 * Note: size *must* be <= the size given to the preceding sort_alloc(),

 * but no error checking is done here.

 */

extern void sort_setup(sort_info_t *i, int16_t *vector, long int *abspos,

		       long int size, long int sortlo, long int sorthi);

/* =========================================================================

 * sort_free()

 *

 * Releases all memory consumed by a sort_info object.

 */

extern void sort_free(sort_info_t *i);

/*! ========================================================================

 * sort_getmatch()

 *

 * This function returns a sort_link_t pointer which refers to the

 * first sample equal to (value) in the vector.  It only searches for

 * hits within (overlap) samples of (post), where (post) is an offset

 * within the vector.  The caller can determine the position of the

 * matched sample using ipos(sort_info *, sort_link *).

 *

 * This function returns NULL if no matches were found.

 */

extern sort_link_t *sort_getmatch(sort_info_t *i, long post, long overlap,

				  int value);

/*! ========================================================================

 * sort_nextmatch()

 *

 * This function returns a sort_link_t pointer which refers to the

 * next sample matching the criteria previously passed to

 * sort_getmatch().  See sort_getmatch() for details.

 *

 * This function returns NULL if no further matches were found.

 */

extern sort_link_t *sort_nextmatch(sort_info_t *i, sort_link_t *prev);

/* ===========================================================================

 * is()

 *

 * This macro returns the size of the vector indexed by the given sort_info_t.

 */

#define is(i) (i->size)

/* ===========================================================================

 * ib()

 *

 * This macro returns the absolute position of the first sample in the vector

 * indexed by the given sort_info_t.

 */

#define ib(i) (*i->abspos)

/* ===========================================================================

 * ie()

 *

 * This macro returns the absolute position of the sample after the last

 * sample in the vector indexed by the given sort_info_t.

 */

#define ie(i) (i->size+*i->abspos)

/* ===========================================================================

 * iv()

 *

 * This macro returns the vector indexed by the given sort_info_t.

 */

#define iv(i) (i->vector)

/* ===========================================================================

 * ipos()

 *

 * This macro returns the relative position (offset) within the indexed vector

 * at which the given match was found.

 *

 * It uses a little-known and frightening aspect of C pointer arithmetic:

 * subtracting a pointer is not an arithmetic subtraction, but rather the

 * additive inverse.  In other words, since

 *   q     = p + n returns a pointer to the nth object in p,

 *   q - p = p + n - p, and

 *   q - p = n, not the difference of the two addresses.

 */

#define ipos(i,l) (l-i->revindex)

#endif /* _ISORT_H_ */