Տեքստի հավասարեցում ըստ էջի լայնության

«Этюды для программистов» (Чарльз Уэзерелл, ― «Etudes for Programmers», Charles Wetherell) գրքի չորրորդ էտյուդն առաջարկում է գրել տեքստի ֆորմատավորման ծրագիր, որի պահանջներից մեկը տողի բառերի արանքներում բացատներ ավելացնելով տեքստը ըստ էջի լայնության հավասարացնելն է։ Տեքստի ֆորմատավորման այս մասնակի խնդիրն է նկարագրված նաև, օրինակ, «100 задач по программированию» գրքի (հեղինակներ՝ Дагене В. А., Григас Г. К., Аугутис К. Ф.) 78-րդ առաջադրանքում, որ կոչվում է «Տեքստի տեխնիկական խմբագրում»։

Մի կողմից կարող է այս խնդիրը, գործնական տեսակետից, հնացած թվալ, մյուս կողմից էլ, սակայն, ժամանակակից տեքստային խմբագրիչներում և տեքստային պրոցեսորներում նույնպես կիրառվում են տեքստի հավասարեցման գործողություններ։ Օրինակ, LibreOffice Writer ծրագիրը հավասարեցումը կատարում է ոչ թե բացատների քանակն ավելացնելով, այլ դրանց չափերն ավելացնելով։ Կամ, TeX տեքստային պրոցեսորում ընդհանրապես բացակայում է բացատ նիշը, իսկ հավասարեցման համար բառերի արանքները լցվում են «սոսինձ» կոչվող ազատ տարածությամբ։

Խնդրի լուծման ընթացքը կարող է լինել այսպիսին (որ նույնպես կարդացել եմ ինչ-որ գրքում, արդեն չեմ հիշում, թե՝ որ). ա) տրված տեքստը տրոհել առավելագույնը n երկարությամբ տողերի՝ չթույլատրելով բառի տրոհում, բ) եթե արդյունքում տողի երկարությունն ավելի կարճ է ստացվում, քան n թիվը, ապա պատահական բառերի արանքներում ավելացնել այնքան բացատներ, որ տողի երկարությունը դառնա n-ի հավասար։ Հավասարեցման գործողությունը պետք չէ կիրառել վերջին տողի նկատմամբ։

Այս գրառման մեջ ես պատմում եմ, թե ինչպես եմ C լեզվով ծրագրավորել տեքստն ըստ լայնության հավասարեցման գործողությունը։ Ստորև բերված ծրագրում ես դիտարկում եմ տեքստի հետ կապված մի քանի հասկացություններ. բառ, տող և պարագրաֆ։ Տվյալների կառուցվածքների տեսակետից տեքստը պարագրաֆների հաջորդականություն է։ Պարագրաֆը տողերի կապակցված ցուցակ է։ Տողը բառերի կապակցված ցուցակ է։

#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <time.h>

Տեքստի մեկ բառը ներկայացնելու համար նախատեսել եմ word ստրուկտուրան։ Սրա w դաշտը բառի տեքստն է, l դաշտը բառի երկարությունն է, s դաշտը բառին հաջորդող բացատների քանակն է, իսկ n դաշտը հաջորդ բառի ցուցիչն է։

/* տեքստի բառի ներկայացումը */
struct word {
  char* w;        /* պարունակությունը */
  size_t l; /* երկարությունը */
  size_t s; /* հաջորդող բացատների քանակը */
  struct word* n; /* հաջորդ բառի ցուցիչը */
};

Իմ առաջին խնդիրն է const char* text ցուցիչով տրված տողի սկզբից առանձնացնել len երկարությամբ հատված, և կազմել այդ հատվածի բառերի կապակցված ցուցակը։ split_to_words ֆունկցիան ստանում է տողի ցուցիչը, դիտարկվող հատվածի երկարությունը և վերադարձնում է կառուցված ցուցակի առաջին տարրի ցուցիչը։ (Բայց քանի որ տողը բառերի տրոհելու ընթացքում բառերի ցուցակը կառուցվում է գլխիվայր, առաջին բառի ցուցիչը վերադարձնելուց առաջ նախ պետք է շրջել կառուցված ցուցակը։) Բոլոր լրացուցիչ բացատրությունները գրված են ֆունկցիայի մարմնում՝ C լեզվի մեկնաբանությունների տեսքով։

/* Տրոհել տեքստը և կառուցել բառերի կապակցված ցուցակ։ 
   Վերադարձնում է առաջին բառի ցուցիչը։ */
struct word* split_to_words( const char* text, size_t len )
{
  /* բառերի ցուցակը */
  struct word* res = NULL;

  /* տրոհել տողը */
  const char* end = text + len; /* դիտարկվող հատվածի վերջը */
  /* քանի դեռ text ցուցիչը չի հասել հատվածի վերջին */
  while( text != end ) {
    /* անցնել բացատների վրայով */
    while( isspace(*text) ) ++text;
    /* text-ը ցույց է տալիս բառի սկիզբը, 
       p ցուցիչը որոնում է բառի վերջը */
    const char* p = text;
    /* քանի դեռ բացատ չէ և տողն ավարտող 0 նիշը չէ,
       առաջ տանել p-ն */
    while( !isspace(*p) && *p != '\0' ) ++p;
    /* բառի ստրուկտուրայի նմուշի համար վերցնել հիշողություն */
    struct word* wo = malloc(sizeof(struct word));
    /* բառի չափը նրա վերջն ու սկիզբը ցույց տվող ցուցիչների 
       դիրքերի տարբերությունն է */
    wo->l = p - text;
    /* հիշղություն վերցնել բառի պարունակության համար */
    wo->w = malloc(1 + wo->l);
    /* պատճենել գտված բառը ստրուկտուրայի մեջ */
    strncpy(wo->w, text, wo->l);
    /* բառի վերջում ավելացնել 0 նիշը */
    wo->w[wo->l] = '\0';
    /* բառին հաջորդում է 1 բացատ */
    wo->s = 1;
    /* նոր ստեղծվող բառը կցել ցուցակի սկզբից */
    wo->n = res;
    /* ցուցակի սկիզբ համարել նոր ավելացրած բառը */
    res = wo;
    /* անցնել հաջորդ բառի որոնմանը */
    text = p;
  }
  /* վերջին բառին հաջորդող բացատների քանակը նշել զրո */
  res->s = 0;

  /* շրջել բառերի միակապ ցուցակը */
  struct word* pp = NULL;
  struct word* nn = res->n;
  while( nn != NULL ) {
    res->n = pp;
    pp = res;
    res = nn;
    nn = nn->n;
  }
  res->n = pp;

  /* վերադարձնել կառուցված ցուցակը */
  return res;
}

Տեքստի մեկ տողը ներկայացնելու համար սահմանել եմ line ստրուկտուրան։ Սրա w դաշտը կապված է տվյալ տողի բառերի ցուցակի առաջին տարրին, c դաշտում պահվում է տողի բառերի քանակը, l դաշտը ցույց է տալիս տողի երկարությունը, իսկ n դաշտը հաջորդ տողի ցուցիչն է։

/* տեքստի տողի ներկայացումը */
struct line {
  struct word* w; /* բառերի ցուցակ */
  size_t c; /* բառերի քանակ */
  size_t l; /* տողի երկարություն */
  struct line* n; /* հաջորդ տողի ցուցիչ */
};

Տեքստի տողը, ինչպես վերն ասացի՝ բառերի կապակցված ցուցակ է, կառուցվում է create_line ֆունկցիայով։ Սա ստանում է տեքստի ցուցիչը և մեկ տողի առավելագույն երկարությունը։

/* Կառուցել տրված երկորությամբ տող */
struct line* create_line( const char* str, size_t len )
{
  /* կառուցել բառերի ցուցակը */
  struct line* res = malloc(sizeof(struct line));
  res->w = split_to_words( str, len );
  /* բառերի քանակն ու տողի երկարությունը դեռ զրո են */
  res->c = 0; res->l = 0;
  /* սկսել առաջին բառից */
  struct word* i = res->w;
  /* քանի դեռ բառերը չեն վերջացել */
  while( i != NULL ) {
    /* ավելացնել բառերի հաշվիչը */
    ++res->c;
    /* հաշվել տողի ընթացիկ երկարությունը */
    res->l += i->l + i->s;
    /* անցնել հաջորդ բառին */
    i = i->n;
  }
  /* հաջորդ տողի ցուցիչը դեռ դատարկ է */
  res->n = NULL;
  /* վերադարձնել կառուցված օբյեկտը */
  return res;
}

Քանի որ տողերի ցուցակի կառուցման համար էլ է օգտագործվում դինամիկ առանձնացված հիշողություն, պետք է նախատեսել նաև այդ հիշողությունը խնամքով ազատելու և համակարգին վերադարձնելու միջոցը։ Դա արվել է destroy_words ֆունկցիայով։

/* քանդել տողերի ցուցակը */
void destroy_words( struct word* l )
{
  /* եթե ցուցակը դատարկ չէ */
  if( l != NULL ) {
    /* ռեկուրսիվ կանչ ցուցակի պոչի համար */
    destroy_words( l->n );
    /* ազատել բառի տեեքստի տեղը */
    free(l->w);
    /* ազատել բառի ստրուկտուրայի տեղը */
    free(l);
  }
}

Տողերի ցուցակ կազմելու համար պետք է append_line ֆունկցիայով տրված տողի n ցուցիչին կապել ևս մի տող։ Սա մի հասարակ ռեկուրսիվ ֆունկցիա է։

/* տողերի ցուցակի պոչից կցել ևս մի տող */
void append_line( struct line** dest, struct line* src )
{
  if( *dest == NULL )
    *dest = src;
  else
    append_line( &((*dest)->n), src );
}

Պարագրաֆը տողերի ցուցակ է (տողն էլ իր հերթին՝ բառերի ցուցակ է)։ create_paragraph ֆունկցիան ստանում է նախնական տողի ցուցիչը և ֆորմատավորվող տեքստի նպատակային լայնությունը։ Ինչպես վերևում՝ լրացուցիչ բացատրությունները ծրագրի տեքստում են։

/* տրված տեքստից կառուցել տրված երկարությունը չգերազանցող տողերի ցուցակ */
struct line* create_paragraph( const char* text, size_t width )
{
  /* արդյունքի ցուցիչը */
  struct line* res = NULL;
  /* դիտարկվողղ տողի սկիզբն ու վերջը ցույց տվող ինդեքսներ */
  size_t begin = 0, end = strlen(text);
  /* քանի դեռ տեքստի վերջը չէ */
  while( begin < end ) {
    /* հաշվել հերթական հատվածի վերջը */
    size_t pos = begin + width;
    /* ճշտվում է վերջին հատվածի եզրը */
    if( pos > end ) pos = end;
    /* հատվածի աջ եզրից հետ գալ՝ կիսատ բառը չվերցնելու համար */
    while( !isspace(text[pos]) && text[pos] != '\0' ) --pos;
    /* կառուցել նոր տող և կցել տողերի ցուցակի պոչից */
    append_line( &res, create_line( text + begin, pos - begin ) );
    /* անցնել տեքստի հաջորդ հատվածին */
    begin = pos;
  }
  /* վերադարձնել պարագրաֆների ցուցակը */
  return res;
}

Պարագրաֆի համար առանձնացված հիշողության դինամիկ տիրույթը համակարգին է վերադարձվում destroy_lines ֆունկցիայի օգնությամբ։

/* ազատել պարագրաֆի զբաղեցրած հիշողությունը */
void destroy_lines( struct line* p )
{
  /* եթե տողերի ցուցակը դատարկ չէ */
  if( p != NULL ) {
    /* ռեկուրսիվ կանչ պոչի համար */
    destroy_lines(p->n);
    /* քանդել բառերի ցուցակը */
    destroy_words(p->w);
    /* ազատել տողի ստրուկտուրայի տեղը */
    free(p);
  }
}

Պարագրաֆի տողերը արտածման ստանդարտ հոսքին են դուրս բերվում print_lines ֆունկցիայով։ Այն նախ տպում է բառը, իսկ հետո՝ դրան հաջորդող բացատաները՝ հարկավոր քանակով։ Արտածվելիք բացատների քանակը պահվում է word ստրուկտուրայի s դաշտում։ print_lines ֆունկցիայում սահմանված spaces ստատիկ հաստատունը պարունակում է բառից հետո արտածվող բացատների ենթադրվող առավելագույն երկարությամբ տողը, իսկ scount փոփոխականը՝ այդ տողի երկարությունը։ k->w բառն արտածելուց հետո պարզապես պետք է արտածել նաև spaces տողի վերջին k->s հատվածը։

/* արտածել տողերը */
void print_lines( struct line* lines )
{
  /* բացատների տող, և բացատների քանակ */
  static const char* spaces = "                   ";
  static const size_t scount = 20;

  /* քանի դեռ ցուցակի վերջը չէ */
  while( lines != NULL ) {
    /* k-ն ցուցակի աչաջին բառն է */
    struct word* k = lines->w;
    /* քանի դեռ k-ն չի հասել բառերի ցուցակի վերջին */
    while( k != NULL ) {
      /* արտածել բառը դրան հաջորդող բացատները */
      printf( "%s%s", k->w, spaces + scount - k->s );
      /* անցնել հաջորդ բառին */
      k = k->n;
    }
    /* արտածել նոր տողին անցնելու նիշը */
    putchar('\n');
    /* անցնել պարագրաֆի հաջորդ տողին */
    lines = lines->n;
  }
}

Տողի հավասարեցման մարտավարությունը հետևյալն է․ քանի դեռ հացասարեցվող տողի երկարությունը, որը ցույց է տալիս line ստրուկտուրայի l դաշտը, փոքր է պահաջվածից, տողում ընտրել պատահական մի բառ (բացի վերջինից) և դրան հաջորդող բացատների քանակն ավելացնել մեկով։

Տողի n-րդ բառի ցուցիչը վերցնելու համար է նախատեսված nth ֆունկցիան։ Եթե տողում բառերի քանակը ավելի քիչ է, քան տրված n թիվը, ապա, բնականաբար, վերադարձվում է NULL։

/* Վերադարձնում է բառերի ցուցակի n-րդ տարրը։ */
struct word* nth( struct word* list, size_t n )
{
  struct word* res = list;
  while( n-- > 0 ) {
    res = res->n;
    if( res == NULL )
      return NULL;
  }
  return res;
}

Վերջապես ամեն ինչ պատրաստ է՝ պարագրաֆը տրված լայնությամբ հավասարեցնելու համար։ justify_paragraph ֆունկցիան ստանում է տողերի ցուցակն ու տողի հարկավոր width լայնությունը։ Այնուհետև, անցնելով ցուցակի բոլոր տարրերով, բառերի արանքներում բացատներ է ավելացնում այնքան ժամանակ, քանի դեռ տողի երկարությունը չի հասել width թվին։

/* տողերը հավասարեցնել՝ բառերի արանքներում
   ներմուծելով լրացուցիչ բացատներ */
void justify_paragraph( struct line* par, size_t width )
{
  /* քանի դեռ ցուցակի նախավերջին տողը չէ */
  while( par->n != NULL ) {
    /* քանի դեռ տողի երկարությունը փոքր է width-ից */
    while( par->l < width ) {
      /* ընտրել պատահական ինդեքս */
      int po = rand() % (par->c - 1);
      /* վերցնել տողի՝ այդ ինդեքսով բառը */
      struct word* wd = nth( par->w, po );
      /* 1-ով ավելացնել բառի բացատների քանակը */
      ++wd->s;
      /* 1-ով ավելացնել տողի ընդհանուր երկարությունը */
      ++par->l;
    }
    /* անցնել հաջորդ տողին */
    par = par->n;
  }
}

Ահա այսքանը։ Մնում է միայն կազմակերպել ծրագրի մուտքի կետը՝ main ֆունկցիան, որպեսզի հնարավոր լինի ծրագիրն օգտագործել իր նշանակությամբ։ Նախատեսված է, որ ծրագիրը տեքստը կարդում է ներմուծման ստանդարտ հոսքից, իսկ ֆորմատավորված արդյունքը դուրս է բերում արտածման ստանդարտ հոսքին։

int main( int argc, char** argv )
{
  /* ծրագիրը որպես պարամետր սպասում է միայն
     տեքստի լայնությունը */
  if( argc != 1 && argc != 3 )
    return 1;

  /* եթե լայնությունը տրված չէ՝ այն համարել 40 */
  size_t length = 40;
  /* հրամանային տողից կարդալ length-ի նոր արժեքը */
  if( argc == 3 )
    if( argv[1][0] == '-' && argv[1][1] == 'w' )
      sscanf(argv[2], "%d", &length);

  /* արժեքավորել պատահական թվերի գեներատորը */
  srand(time(0));

  /* նախնական տեքստի բուֆերի չափը */
  const size_t bsize = 4096;
  /* դինամիկ բուֆեր՝ տեքստի համար */
  char* text = calloc(bsize, sizeof(char));
  /* քանի դեռ stdin-ի վրա կարդալու բան կա,
     կարդալ այն text բուֆերի մեջ */
  while( fgets(text, bsize, stdin ) != NULL ) {
    /* կարդացած տեքստից կառուցել տողերի ցուցակ */
    struct line* u = create_paragraph( text, length );
    /* հավասարեցնել պարագրաֆը տրված լայնությամբ */
    justify_paragraph( u, length );
    /* արտածել պարագրաֆի տողերը */
    print_lines( u );
    /* ազատել պարագրաֆի զբաղեցրած հիշողությունը */
    destroy_lines( u );
  }
  /* ազատել բուֆերի զբաղեցրած հիշողությունը */
  free(text);

  return 0;
}

Ծրագիրը կոմպիլյացնելու համար կարելի է օտագործել gcc կամ clang կոմպիլյատորները․

$ gcc -std=c11 -o splitext splitext.c

Իսկ test1.txt ֆայլում պարունակվող տեքստը, օրինակ, 30 նիշ լայնությամբ տողերով ֆորմատավորելու համար պետք է գրել։

$ ./splittext -w 30 < text1.txt

Նույն արդյունքը կարելի է ստանալ նաև հետևյալ հրամանով․

$ cat test1.txt | ./splittext -w 30