am_string_array.h

ADaM is a data mining and image processing toolkit

/*
  Logistic Regression using Truncated Iteratively Re-weighted Least Squares
  (includes several programs)
  Copyright (C) 2005  Paul Komarek

  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 2 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, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

  Author: Paul Komarek, [e-mail]
  Alternate contact: Andrew Moore, [e-mail]

*/


/* 	File: am_string_array.h
 * 	Author(s): Andrew Moore
 * 	Date:
 * 	Purpose: This is the new home for most string_array functions.
 *      string_array is a dynamically resizable array of strings. Some
 *      of the functions and the declaration used to live in amiv.h.
 *
 */
#ifndef AM_STRING_ARRAY_H
#define AM_STRING_ARRAY_H

#include "standard.h"
#include "ambs.h"
#include "amiv.h"
#include "am_string.h"

typedef struct string_array_struct
{
  int string_array_code;
  int size;
  int sarr_size;
  char **sarr;
} string_array, *string_array_ptr;

string_array *mk_string_array(int size);
void free_string_array(string_array *sar);
string_array *mk_copy_string_array(const string_array *sa);

/* Warning: The compiler won't catch type errors here. Pass the values
   as integers, or behavior will be undefined (read: bad things will
   probably happen sometime) */
string_array *mk_string_array_x( int size, ...);

char **mk_array_from_string_array( string_array *sa);

/* Sort into lexicographic order */
void sort_string_array(string_array *sa);
string_array *mk_sort_string_array(string_array *sa);
string_array *mk_sort_string_array_remove_duplicates(string_array *sa);
string_array *mk_string_array_from_array(char **sarr,int size);

/*reverse string array order */
string_array *mk_reverse_string_array(string_array *sa);

void fprintf_string_array(FILE *s,
                          const char *m1,
                          const string_array *sar,
                          const char *m2);

void fprintf_string_array_contents(FILE *s,string_array *sar);
void fprintf_string_array_contents_on_one_line(FILE *s,string_array *sar);

int string_array_size(const string_array *sar);

bool string_array_equal(string_array *a,string_array *b);

char *string_array_ref(const string_array *sar, int i);
void string_array_set(string_array *sar,int i,char *value);

/* Extends the length of the string_array by one (efficiently, if
   amortized over time) and adds "string" as the size-1'th entry where
   size is the new size.

   COPIES in string. It's okay if string is NULL.  */
void add_to_string_array(string_array *sa,const char *string);

/* Only for people who really want to save time allocating memory. After 
   calling this, forget about the memory in string without freeing it.
*/
void add_to_string_array_no_copy(string_array *sa, char *string);

/* Following function adds an element at the pos location.  pos can be
   at the end of the array */
void insert_in_string_array(string_array *sa, int pos, char *string);

/* XXX Depreciated synonym for add_to_string_array */
void string_array_add(string_array *sa,char *string);

/* Returns a result of length equal to size of indices.
   result[i] = sa[indices[i]] */
string_array *mk_string_array_subset(string_array *sa,ivec *indices);

/* split/join -- would be cool to support regex at some point.
   note - delimiter is a string, not a set of characters
*/
string_array *mk_split_string(const char *str, const char *delimiter);
char *mk_join_string_array(const string_array *sa, const char *delimiter);


/*
Tokenizes a string_array given a separator:
For Example with the ";" token the string_array on the left becomes
that on the right:
[  0] = something  
[  1] = 1                
[  2] = 2                [  0] something 1 2
[  3] = ;            =>  [  1] 3 4
[  4] = 3                [  2] 5
[  5] = 4                 
[  6] = ;
[  7] = 5

Note: It is not necessary for the last element of the original 
string_array to be a separator
*/

string_array *parse_string_array(string_array *sa, char *sep);
string_array *parse_string_array_endpoints(string_array *sa, char *sep, int start, int end);

/* Stop characters are any whitespace character, or any
   character in the seppers string.

   If seppers is NULL it's ignored.

   Any stop character is removed and used as a separator breaking string
   into smaller chunks.
   Each word (chunk) is placed as a separate entry into the string array.

   If string is NULL or "" or has only sepper characters, a string_array of
   length 0 is returned.

   Modified 1-23-96 JS: A single string may include whitespace including
   a newline character if delimited by single or double quotes.  Note the
   delimiting characters are still left in the string, as are all backslashes
   used to produce the characters '"\ in the string.
   Modified 1-31-96 JS: The single quote is no longer considered a delimiter
*/
string_array *mk_broken_string_using_seppers(const char *string, const char *seppers);

/* Here stop characters are only those in seppers (not whitespace!) */
string_array *mk_broken_string_using_seppers_only(char *string,char *seppers);

/* whitespace is removed, and each word is placed as a separate entry
   int the string array.
   If string is NULL or "" or has only whitespace, a string_array of
   length 0 is returned.  */
string_array *mk_broken_string(const char *string);

/*  As in mk_broken_string except removes all double quote marks before doing the splitting. */
string_array *mk_broken_quoteless_string(char *string);

char *string_before_col(string_array *seps, int col);
char *rightmost_string(string_array *seps);

/* If n == 0 returns "",
   else returns rightmost "n" entries in sa, concatenated with...

     'sep' char between them (if use_sep TRUE)
     nothing    between them (if use_sep FALSE)

   PRE: n <= size */
char *mk_string_from_last_n_with_separator(string_array *sa,int n,
					   bool use_sep,char sep);

/* In the functions below, entries are separated by whitespace. If n == 0 returns "",
   else returns rightmost "n" entries in sa, concatenated with ' '
   between them.

   PRE: n <= size */
char *mk_string_from_last_n(string_array *sa,int n);

/* If n == 0 returns "",
   else returns all the entries in sa, concatenated with sep char between
   them. */
char *mk_string_from_string_array_with_separator(string_array *sa,char sep);

/* In below, entries are separated by whitespace. If sa has
   no entries returns "", else all entries in sa, concatenated with ' '
   between them. */
char *mk_string_from_string_array(string_array *sa);

/* In below, entries are separated by nothing. If sa has
   no entries returns "", else all entries in sa, concatenated directly,
   eg { "Andrew" , "Moore" } --> "AndrewMoore" */
char *mk_string_from_string_array_no_gaps(string_array *sa);


/* Reads to the end of line, or end of file, skipping white space
   and adding each new word into the string array. If nothing on
   the line, returns a string_array of size zero. If nothing
   on line and file ends immediately returns NULL */
string_array *mk_string_array_from_line(FILE *s);

void string_array_malloc_report(void);

/* Finds lowest index in sa with value string, or returns -1 if not found. */
int find_index_in_string_array(const string_array *sa, const char* string);
/* case-insensitive version of find_index_in_string_array */
int caseless_find_index_in_string_array(string_array *sa,char *string);
/* True if the value of string is a string in string_array */
bool string_array_member(string_array *sa,char *string);


/**** Removal functions on string_arrays ****/

/* Reduces the size of sa by one.
   string_array_ref(sa,index) disappears.
   Everything to the right of string_array_ref(sa,index) is copied one to the left.

   Formally: Let saold be the string_array value beore calling this function
             Let sanew be the string_array value after calling this function.

PRE: string_array_size(saold) > 0
     0 <= index < string_array_size(saold)

POST: string_array_size(sanew) = string_array_size(saold)-1
      for j = 0 , 1, 2 ... index-1  : 
         string_array_ref(sanew,j) == string_array_ref(saold,j)

      for j = index , index+1 , ... string_array_size(sanew)-1:
         string_array_ref(sanew,j) == string_array_ref(saold,j+1) */

void string_array_remove(string_array *sa,int idx); 
                                   /* Reduces size by 1, removes index'th 
                                      element. All elements to right of
                                      delete point copied one to left.
                                      See comments in amdm.c more details */

/* Shrinks sa by one element by removing the rightmost element. 
   Example:

  Before: sa == ( "I" "hate" "to" "see" "you" "leave" )
    string_array_remove_last_element(sa)
  Before: sa == ( "I" "hate" "to" "see" "you" ) */
void string_array_remove_last_element(string_array *sa); 

/* PRE: 0 <= start_index <= end_index <= size
   Returns a new string array of size end_index - start_index
   consisting of 
     { sa[start_index] , sa[start_index+1] ... sa[end_index-1] } */
string_array *mk_string_array_segment(string_array *sa,
                                      int start_index,int end_index);

string_array *mk_string_array_from_ivec(ivec *iv);

/* Returns a string array in which the i'th element is "<prefix><i>",
   eg mk_int_string_array("plop",3) would return

   { "plop0" , "plop1" , "plop2" } */
string_array *mk_int_string_array(char *prefix,int size);


/* *************************************************** */
/* Operations on Sorted String Arrays */
/* A sorted string array is an ordinary string array where
   the following property holds:
   FIXME: Insert description here

  You can tell if a string array is sorted by calling FIXME: do the obvious
  If you call sorted operations on a nonsorted string_array, undefined behavior will result */

/* SUGGESTION: If you're thinking of using sorted string arrays for
   sets of strings, let me recommend extra/namer.h instead -- ?? */

int find_index_in_sorted_string_array(string_array *sa,char *s);
/* Finds lowest index in sa with value >= string, between 0 and
   string_array_size(sa), inclusive.  NOTE that string_array_size(sa)
   is the index one past the end of the string_array! */
int find_closest_index_in_sorted_string_array(string_array *sa, char* string);
/* place s into string array whether or not a duplicate already exists */
void insert_in_sorted_string_array(string_array *sa,char *s);
/* place s into string array only if it does not already exist there */
void maybe_insert_in_sorted_string_array(string_array *sa,char *s);


/* If n == 0 returns "",
   else returns all the entries in sa, concatenated with...

     'sep' char between them (if use_sep TRUE)
     nothing    between them (if use_sep FALSE)

   PRE: n <= size */
char *mk_string_from_string_array_basic(string_array *sa,bool use_sep,char sep);

void check_string_array_access(const string_array *sar, int i, const char *name);
void assert_string_array_shape(string_array *sar,int size,char *name);
void swap_string_array(string_array *sa, int i, int j);
void qsort_string_array(string_array *sa, int left, int right);

/* Input is a string which may optionally have curly braces
   and commas in it. All square and curly braces and commas are turned into
   spaces and then a string_array is made from the remaining unique
   space-separated tokens */
string_array *mk_string_array_from_set_notation(char *setnot);

/* I wasn't able to find good documentation for this function. For now, read the
   source. Sorry. --Pat */
string_array *mk_string_array_from_parse(char *s,char separator);

/* Searches for key on the command line. If it doesn't find key returns
   a string_array of length zero.

   If it does find it then looks at the next token. If it's a single
   simple token, simply returns a string_array of length 1, containing
   that token.

   If this token begins and ends with "" or if it contains
   whitespace, then breaks it up by removing all whitespace and commas
   and returns a string_array with the remaining elements

   If this token begins with [, searches for the next token (including
   the start one) that ends with ] and uses all the items inside,
   again separating with whitespace and commas.

   EXAMPLES:
    Each of the command-lines would cause a string array of size three
    to be created with elements "william" "chye" and "lee-moore" if the
    caller had set key be "names".

      ./program names [william chye lee-moore]
      ./program names [ william chye lee-moore ]
      ./program names [william,chye,lee-moore]
      ./program names william,chye,lee-moore
      ./program names "william,chye,lee-moore"
      ./program names "william chye lee-moore"

    But this command line would result in an array of length 1 with only
    "william" in the string array:

      ./program names william chye lee-moore