Binary strings

Binary strings
You are encouraged to solve this task according to the task description, using any language you may know.

Many languages have powerful and useful (binary safe) strings manipulation functions, while others haven't, making it harder for these languages to accomplish some kind of tasks. This task is about creating functions to handle (binary) strings (strings made of arbitrary bytes, i.e. byte strings) for those languages that haven't a builtin support for them. If your language of choice is not among these, show a possible alternative implementation for the functions or abilities already provided by the language. In particular the functions you need to create are:

• String creation and destruction (when needed and if there's no garbage collection or similar mechanisms)
• String assignment (there's no need to pretend the syntax of common types assignments)
• String comparison
• String cloning and copying
• Check if a string is empty
• Append a byte to a string
• Extract a substring from a string
• Replace every occurrences of a byte (or a string) in a string with another string
• Join strings

Possible contexts of use: compression algorithms (like LZW compression), L-systems (manipulation of symbols), many more.

C

estrings.h <lang c>#ifndef ESTRINGS_H_

1. define ESTRINGS_H_

1. include <string.h>
2. include <stdlib.h>
3. include <stdbool.h>

1. define BYTES_PER_BLOCK 128

struct StringStruct {

 char *bstring;
 size_t length;
 size_t blocks;

}; typedef struct StringStruct *String;

String newString(); String setString(String s, char *p, size_t len); String appendChar(String s, char c); int compareStrings(String s1, String s2); void destroyString(String s); String copyString(String to, String from); String cloneString(String s); bool stringIsEmpty(String s); String subString(String s, size_t from, size_t to); String replaceWith(String str, String ch, String repl); String joinStrings(String s1, String s2);

1. endif</lang>

estrings.c <lang c>#include "estrings.h"

1. include <stdio.h>
2. define NOT_IMPLEMENTED_YET fprintf(stderr, "not implemented yet\n")</lang>

<lang c>String newString() {

 String t;
 t = malloc(sizeof(struct StringStruct));
 if ( t == NULL ) return NULL;
 t->length = 0;
 t->blocks = 1;
 t->bstring = malloc(BYTES_PER_BLOCK * t->blocks);
 if ( t->bstring == NULL ) { free(t); return NULL; }
 return t;

}</lang>

<lang c>static bool _fitString(String s, size_t len) {

 s->blocks = len/BYTES_PER_BLOCK + 1;
 s->bstring = realloc(s->bstring, s->blocks * BYTES_PER_BLOCK);
 if ( s->bstring != NULL ) return true;
 return false;

}</lang>

<lang c>String setString(String s, char *p, size_t len) {

  if ( s != NULL )
  {
     if ( p == NULL ) { s->length = 0; return s; }
     _fitString(s, len);
     if ( s->bstring != NULL )
     {
       memcpy(s->bstring, p, len);
       s->length = len;
     }
  }
  return s;

}</lang>

<lang c>String appendChar(String s, char c) {

  if ( s == NULL ) return NULL;
  _fitString(s, s->length + 1);
  s->length++;
  if ( s->bstring != NULL )
  {
     s->bstring[s->length-1] = c;
  }
  return s;

}</lang>

<lang c>int compareStrings(String s1, String s2) {

  if ( s1->length < s2->length ) return -1;
  if ( s1->length > s2->length ) return 1;
  return memcmp(s1->bstring, s2->bstring, s1->length);

}</lang>

<lang c>void destroyString(String s) {

  if ( s != NULL )
  {
     if ( s->bstring != NULL ) free(s->bstring);
     free(s);
  }

}</lang>

<lang c>String copyString(String to, String from) {

  if ( (to->bstring != NULL) && (from->bstring != NULL) )
  {
     to->blocks = from->blocks;
     to->length = from->length;
     to->bstring = realloc(to->bstring, to->blocks * BYTES_PER_BLOCK);
     memcpy(to->bstring, from->bstring, to->length);
  }
  return to;

}</lang>

<lang c>String cloneString(String s) {

  String ps = malloc(sizeof(struct StringStruct));
  if ( ps != NULL )
  {
     ps->length = s->length;
     ps->blocks = s->blocks;
     ps->bstring = malloc(s->blocks * BYTES_PER_BLOCK);
     if ( ps->bstring != NULL )
     {
        memcpy(ps->bstring, s->bstring, s->length);
     } else {
        free(ps); return NULL;
     }
  }
  return ps;

}</lang>

<lang c>bool stringIsEmpty(String s) {

 if ( s == NULL ) return true;
 if ( s->length == 0 ) return true;
 return false;

}</lang>

<lang c>String subString(String s, size_t from, size_t to) {

 String ss;

 if ( stringIsEmpty(s) || (to < from) || ( from >= s->length )) return newString();
 if ( (from == 0) && (to >= (s->length - 1) ) ) return cloneString(s);
 ss = newString();
 if ( ss == NULL ) return NULL;
 if ( _fitString(ss, to - from) ) {
   ss->length = to - from;
   memcpy(ss->bstring, s->bstring+from, ss->length);
 }
 return ss;

}</lang>

<lang c>String replaceWith(String str, String ch, String repl) {

 String d = NULL;
 int occ = 0, i, j;

 if ( stringIsEmpty(str) ) return NULL;
 if ( stringIsEmpty(ch) ) return cloneString(str);
 if ( ch->length > 1 ) {
   NOT_IMPLEMENTED_YET;
   return str;
 }
 for(i=0; i < str->length; i++) {
   if ( str->bstring[i] == ch->bstring[0] ) occ++;
 }
 if ( occ == 0 ) return cloneString(str);
 d = newString();
 if ( _fitString(d, str->length + occ * (repl->length - 1)) ) {
   d->length = str->length + occ * (repl->length - 1);
   for(i=0, j=0; i < str->length; i++) {
     if ( str->bstring[i] != ch->bstring[0] ) {

d->bstring[j] = str->bstring[i]; j++;

     } else {

memcpy(d->bstring + j, repl->bstring, repl->length); j += repl->length;

     }
   }
 }
 return d;

}</lang>

<lang c>String joinStrings(String s1, String s2) {

 String d;
 
 if ( stringIsEmpty(s1) ) return cloneString(s2);
 if ( stringIsEmpty(s2) ) return cloneString(s1);
 d = newString();
 if ( _fitString(d, s1->length + s2->length) ) {
   memcpy(d->bstring, s1->bstring, s1->length);
   memcpy(d->bstring + s1->length, s2->bstring, s2->length);
   d->length = s1->length + s2->length;
 }
 return d;

}</lang>

<lang c>#undef NOT_IMPLEMENTED_YET</lang>

Tcl

Tcl strings are binary safe. <lang tcl># string creation set x "hello world"

1. string destruction

unset x

1. string assignment with a null byte

set x a\0b string length $x ;# ==> 3

1. string comparison

if {$x eq "hello"} {puts equal} else {puts "not equal"} set y bc if {$x < $y} {puts "$x is lexicographically less than $y"}

1. string copying

set xx $x

1. check if empty

if {$x eq ""} {puts "is empty"} if {[string length $x] == 0} {puts "is empty"}

1. append a byte

append x \07

1. substring

set xx [string range $x 0 end-1]

1. replace bytes

set y [string map {l L} "hello world"]

1. join strings

set a "hel" set b "lo w" set c "orld" set d $a$b$c</lang>