#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

typedef unsigned Character;
typedef double Double;
typedef int Float;
typedef FILE *In_Stream;
typedef int Integer;
typedef int Logical;
typedef FILE *Out_Stream;
typedef union string__Union *String;
typedef unsigned int Unsigned;

struct string__Literal {
    unsigned char size;
    unsigned char data[3];
};

struct string__Header {
  unsigned char size;
  unsigned char data[3];
  unsigned char *buffer;
  unsigned limit;
  unsigned front_size;
  unsigned total_size;
};

union string__Union {
  struct string__Literal literal;
  struct string__Header header;
  char *unix_string;
};

extern unsigned char *string__unix_string(String string);
extern String string__unix_create(unsigned char *str);

static void string__realloc(String, Unsigned);


extern void string__external__initialize(void);

extern String string___initial;
extern String string__allocate(void);
extern void string__Erase(String string);
extern Unsigned string__address_get(String string);
extern void string__buffer_append(String string, String buffer);
extern void string__character_append(String string, Character character);
extern void string__character_delete(String string, Unsigned offset);
extern void string__character_insert(String string, Unsigned offset, Character character);
extern void string__character_gap_insert(String string, Character character);
extern void string__character_prepend(String string, Character character);
extern Integer string__compare(String string1, String string2);
extern Logical string__equal(String string1, String string2);
extern Character string__fetch1(String string, Unsigned index);
extern void string__flush(String buffer, Out_Stream out_stream);
extern int string__float_convert(String text);
extern void string__format(String text, String buffer);
extern Unsigned string__format_begin(String buffer);
extern void string__format_end(String buffer, Unsigned anchor);
extern void string__format_prepare(String buffer, String format);
extern Unsigned string__front_size_get(String string);
extern void string__gap_set(String string, Unsigned gap);
extern Logical string__is_buffered(String string);
extern Logical string__is_buffered(String string);
extern Unsigned string__limit_get(String string);
extern Character string__lop(String string);
extern void string__put(String string, Out_Stream out_stream);
extern Integer string__range_compare(String string1, Unsigned offset1, Unsigned count1, String string2, Unsigned offset2, Unsigned count2);
extern void string__range_append(String to_string, String from_string, Unsigned from_offset, Unsigned count);
extern void string__range_copy(String to_string, Unsigned to_offset, String from_string, Unsigned from_offset, Unsigned count);
extern void string__range_delete(String string, Unsigned offset, Unsigned count);
extern void string__range_insert(String to_string, Unsigned to_offset, String from_string, Unsigned from_offset, Unsigned count);
extern void string__range_nulls_insert(String string, Unsigned offset, Unsigned count);
extern String string__read_only_copy(String string);
extern Unsigned string__stream_read(String string, Unsigned offset, Unsigned amount, In_Stream in_stream);
extern Unsigned string__size_get(String string);
extern void string__store1(String string, Unsigned index, Character character);
extern void string__string_append(String to_string, String from_string);
extern void string__string_insert(String to_string, Unsigned offset, String from_string);
extern void string__string_gap_insert(String to_string, String from_string);
extern void string__string_prepend(String to_string, String from_string);
extern void string__trim(String string, Unsigned new_size);

/* {String} stuff: */

union string__Union string__Initial;

String string___initial = (String)&string__Initial;

void string__Initialize(void)
{
    /* Do Nothing */
}

static void string__fail(void)
{
    assert(0);
}

void string__Erase(
  String string)
{
    Unsigned size;

    size = string->literal.size;
    if (size == 255) {
	/* Buffered string: */
	string->header.total_size = 0;
	string->header.front_size = 0;
    }
}

unsigned string__address_get(
  String string)
{
    return (unsigned)string;
}

String string__allocate(void)
{
    String string;
    unsigned char *buffer;

    string = (String)malloc(sizeof *string);
    assert (string != (String)0);
    buffer = (unsigned char *)malloc(4);
    assert (buffer != (unsigned char *)0);

    string->header.size = 255;
    string->header.limit = 4;
    string->header.total_size = 0;
    string->header.front_size = 0;
    string->header.buffer = buffer;
    return string;
}

/*
 * string__unix_str(text, buffer)
 *	This procedure will copy "text" into "buffer" such that it
 *	is a short read_only string.  "buffer" must be at least 128
 *	bytes in length.  A pointer to buffer cast to a String is
 *	returned.
 */
String
string__unix_str(
	unsigned char	*text,
	unsigned char	*buffer)
{
	unsigned	length;

	length = strlen(text);
	assert(length < 127);
	buffer[0] = (char)length;
	(void)strcpy(buffer + 1, text);
	return (String)buffer;

}

unsigned char *string__unix_string(
  String string)
{
    /* This rouitne returns a pointer to Unix style null-terminated string. */

    Unsigned total_size;
    Unsigned limit;
    unsigned char *result;

    if (string->literal.size == 255) {
	/* Buffered string: */
	total_size = string->header.total_size;
	limit = string->header.limit;
	if (total_size >= limit) {
	    /* Bummer; there is no room for the terminating null: */
	    string__realloc(string, total_size + 4);
	    limit = string->header.limit;
	    assert (total_size < limit);
	}
	string__gap_set(string, total_size);
	result = string->header.buffer;
	result[total_size] = '\0';
    } else {
	/* Literal string: */
	result = &string->literal.data[0];
    }
    return result;
}

void string__gap_set(
  String string,
  Unsigned gap)
{
    Unsigned total_size;
    Unsigned front_size;
    Unsigned back_size;
    unsigned char *buffer;
    Unsigned delta;
    Unsigned limit;

    assert (string->literal.size == 255);
    total_size = string->header.total_size;
    assert (gap <= total_size);
    front_size = string->header.front_size;
    assert (front_size <= total_size);
    back_size = total_size - front_size;
    limit = string->header.limit;
    assert (total_size <= limit);    
    buffer = string->header.buffer;
    if (gap < front_size) {
	delta = front_size - gap;
	(void)memmove(buffer + limit - back_size - delta, buffer + gap, delta);
    } else if (gap > front_size) {
	delta = gap - front_size;
	(void)memmove(buffer + front_size, buffer + limit - back_size, delta);
    }
    string->header.front_size = gap;
}

static void string__realloc(
  String string,
  Unsigned new_limit)
{
    unsigned size;

    size = string->literal.size;
    if (size == 255) {
	/* Buffered string: */
	Unsigned total_size;

	total_size = string->header.total_size;
	if (total_size < new_limit) {
	    /* Everything will fit in the new buffer; */
	    unsigned char *buffer;
	    Unsigned limit;
	    Unsigned total_size;
	    Unsigned front_size;
	    Unsigned back_size;

	    total_size = string->header.total_size;
	    front_size = string->header.front_size;
	    back_size = total_size - front_size;
	    buffer = string->header.buffer;
	    limit = string->header.limit;
	    if (new_limit < limit) {
		/* Buffer is getting smaller: */
		/* Move the back string forward; then reallocate: */
		(void)memmove(buffer + new_limit - back_size,
		  buffer + limit - back_size, back_size);
		buffer = (unsigned char *)realloc((void *)buffer, new_limit);
		assert (buffer != (unsigned char *)0);
		string->header.buffer = buffer;
		string->header.limit = new_limit;
	    } else if (new_limit > limit) {
		/* Buffer is getting larger: */
		/* Realloacate; then move the back string backward: */
		buffer = (unsigned char *)realloc((void *)buffer, new_limit);
		assert (buffer != (unsigned char *)0);
		string->header.buffer = buffer;
		(void)memmove(buffer + new_limit - back_size,
		  buffer + limit - back_size, back_size);
		string->header.limit = new_limit;
	    }
	} else {
	    string__fail();
	}
    } else {
	/* Literal string */
	string__fail();
    }
}

unsigned string__fetch1(
  String string,
  unsigned index)
{
    Unsigned size;
    Unsigned character;

    size = string->literal.size;
    if (size == 255) {
	/* Buffered string */
	Unsigned total_size;

	total_size = string->header.total_size;
	if (index < string->header.total_size) {
	    Unsigned front_size;
	    unsigned char *buffer;

	    buffer = string->header.buffer;
	    front_size = string->header.front_size; 
	    if (index < front_size) {
		character = buffer[index];
	    } else {
		character = buffer[string->header.limit - total_size + index];
	    }
	} else {
	    string__fail();
	}
    } else {
	/* String Literal */
	if (index < size) {
	    character = string->literal.data[index];
	} else {
	    string__fail();
	}
    }
    return character & 0xff;
}

int string__float_convert(
  String string)
{
    float result;

    result = (float)atof(string__unix_string(string));
    return *((int *)&result);
}

Unsigned string__limit_get(
  String string)
{
    Unsigned size;

    size = string->literal.size;
    if (size == 255) {
	size = string->header.limit;
    }
    return size;
}

Unsigned string__front_size_get(
  String string)
{
    Unsigned size;

    size = string->literal.size;
    if (size == 255) {
	size = string->header.front_size;
    }
    return size;
}

Logical string__is_buffered(
  String string)
{
    return string->literal.size == 255;
}

Logical string__is_literal(
  String string)
{
    return string->literal.size != 255;
}

#ifdef UNFINISHED
void string__range_copy(
  String to_string,
  Unsigned to_offset,
  String from_string,
  Unsigned from_offset,
  Unsigned count)
{
    Unsigned from_size;
    Unsigned from_front_size;
    Unsigned to_size;
    Unsigned to_front_size;
    unsigned char *to_buffer;

    assert (to_string->literal.size == 255);
    to_size = to_string->header.total_size;
    assert (to_offset + count < to_size);
    to_front_size = to_string->header.front_size;
    to_buffer = to_string->header.buffer;

    from_size = from_string->literal.size;
    if (from_size  == 255) {
	/* {from_string} is buffered: */
	from_size = from_string->header.total_size;
	from_front_size = from_string->header.front_size;
    } else {
	/* {from_string} is a literal: */
	Unsigned front_count;
	Unsigned back_count;

	assert (from_offset + count < from_size);
	if (to_offset < to_front_size) {
	    /* At least one byte will land in front: */
	    if (to_offset + count <= to_front_size) {
		/* Everything fits into the front: */
		front_count = count;
	    } else {
		/* Both front and back are spanned: */
		front_count = to_front_size - to_offset;
	    }
	} else {
	    /* Everything fits into the back: */
	    front_count = 0;
	}
	back_count = count - front_count;

	if (front_count != 0) {
	    (void)memmove(to_buffer + to_offset,
	      from_string->literal.data + from_offset, front_count);
	}
	if (back_count != 0) {
	    assert (0);
	    (void)memmove(to_buffer, from_string->literal.data + from_offset + front_count, back_count);
	}
    }
}  
#endif /* UNFINISHED */

void string__range_delete(
  String string,
  Unsigned offset,
  Unsigned count)
{
    Unsigned size;

    size = string->literal.size;
    if (size == 255) {
	/* Buffered string: */
	size = string->header.total_size;
	assert (offset + count <= size);
	string__gap_set(string, offset);
	string->header.total_size = size - count;
    } else {
	/* Literal string: */
	string__fail();
    }
}  

void string__range_nulls_insert(
  String string,
  Unsigned offset,
  Unsigned count)
{
    Unsigned size;
    Unsigned back_size;
    Unsigned front_size;
    unsigned char *buffer;
    Unsigned limit;
    Unsigned total_size;
    Unsigned new_limit;

    size = string->literal.size;
    if (size == 255) {
	/* Buffered string: */
	total_size = string->header.total_size;
	assert (offset <= total_size);
	string__gap_set(string, offset);
	front_size = string->header.front_size;
	assert (front_size <= total_size);
	back_size = total_size - front_size;
	limit = string->header.limit;
	buffer = string->header.buffer;
	assert (total_size <= limit);

	new_limit = limit;
	while (total_size + count > new_limit) {
	    new_limit <<= 1;
	}
	if (limit != new_limit) {
	    string__realloc(string, new_limit);
	    limit = string->header.limit;
	    buffer = string->header.buffer;
	}
	(void)memset(buffer + front_size, 0, count);
	string->header.front_size = front_size + count;
	string->header.total_size = total_size + count;
    } else {
	/* Literal string: */
	string__fail();
    }
}  

String string__read_only_copy(
  String string)
{
    String result;
    Unsigned total_size;

    if (string->literal.size == 255) {
	/* Buffered String: */
	total_size = string->header.total_size;     
	if (total_size < 255) {
	    /* {string} is small enough to represent as a literal string: */
	    string__gap_set(string, total_size);
	    result = (String)malloc(total_size + 2);
	    (void)memcpy((void *)&result->literal.data[0],
	      (void *)(string->header.buffer), total_size);
	    result->literal.size = total_size;
	    result->literal.data[total_size] = '\0';
	} else {
	    /* We'll just make a copy: */
	    result = string__allocate();
	    string__string_append(result, string);
	}
    } else {
	/* Literal String: */
	result = string;
    }    
    return result;
}


Unsigned string__stream_read(
  String string,
  Unsigned offset,
  Unsigned amount,
  In_Stream in_stream)
{
    Unsigned total_size;
    Unsigned result;

    if (string->literal.size = 255) {
	/* Buffered String: */
	total_size = string->header.total_size;
	if (offset + amount <= total_size) {
	    string__gap_set(string, total_size);
	    result = fread(string->header.buffer + offset,
	      1, amount, in_stream);
	} else {
	    string__fail();
	}
    } else {
	/* Literal String: */
	string__fail();
    }
    return result;
}

Unsigned string__size_get(
  String string)
{
    Unsigned size;

    size = string->literal.size;
    if (size == 255) {
	/* Buffered string: */
	size = string->header.total_size;
    } else {
	/* Literal string: */
    }
    return size;
}

void string__store1(
  String string,
  Unsigned index,
  Unsigned character)
{
    Unsigned size;

    size = string->literal.size;
    if (size == 255) {
	/* Buffered string: */
	Unsigned total_size;

	total_size = string->header.total_size;
	if (index < total_size) {
	    Unsigned front_size;
	    unsigned char *buffer;

	    buffer = string->header.buffer;
	    front_size = string->header.front_size; 
	    if (index < front_size) {
		buffer[index] = character;
	    } else {
		buffer[string->header.limit - total_size + index] = character;
	    }
	} else {
	    string__fail();
	}
    } else {
	/* Literal string: */
	if (index < size) {
	    string->literal.data[index] = character;
	} else {
	    string__fail();
	}
    }
}

void string__external__initialize(void)
{
}

String
string__unix_create(
	unsigned char	*str)
{
	unsigned	index;
	unsigned	size;
	String		string;

	string = string__allocate();
	size = strlen(str);
	index = 0;
	while (index < size) {
		string__character_append(string, str[index]);
		index = index + 1;
	}
	return string;
}


/*
 * string__unix_load(string, str)
 *	This routine will copy the contents of {str} into {string}.
 *	1 is returned if {string} is read-only and 0 otherwise.
 */
int
string__unix_load(
	String		string,
	unsigned char	*str)
{
	unsigned	index;
	unsigned	size;

	assert (string->literal.size == 255);
	string__trim(string, 0);
	size = strlen(str);
	index = 0;
	while (index < size) {
		string__character_append(string, str[index]);
		index += 1;
	}
	return 0;
}


/*
 * string__unix_append(string, str)
 *	This routine will copy the contents of {str} into {string}.
 *	1 is returned if {string} is read-only and 0 otherwise.
 */
int
string__unix_append(
	String		string,
	unsigned char	*str)
{
	unsigned	index;
	unsigned	size;

	assert (string->literal.size == 255);
	size = strlen(str);
	index = 0;
	while (index < size) {
		string__character_append(string, str[index]);
		index += 1;
	}
	return 0;
}