lib/tasort.c

   1 /* tasort.c */
   2
   3 /*
   4  * Copyright (C) 2011-2012 by Werner Lemberg.
   5  *
   6  * This file is part of the ttfautohint library, and may only be used,
   7  * modified, and distributed under the terms given in `COPYING'.  By
   8  * continuing to use, modify, or distribute this file you indicate that you
   9  * have read `COPYING' and understand and accept it fully.
  10  *
  11  * The file `COPYING' mentioned in the previous paragraph is distributed
  12  * with the ttfautohint library.
  13  */
  14
  15
  16 /* originally file `afangles.c' (2011-Mar-28) from FreeType */
  17
  18 /* heavily modified 2011 by Werner Lemberg <wl@gnu.org> */
  19
  20 #include "tatypes.h"
  21 #include "tasort.h"
  22
  23
  24 /* two bubble sort routines */
  25
  26 void
  27 ta_sort_pos(FT_UInt count,
  28             FT_Pos* table)
  29 {
  30   FT_UInt i;
  31   FT_UInt j;
  32   FT_Pos swap;
  33
  34
  35   for (i = 1; i < count; i++)
  36   {
  37     for (j = i; j > 0; j--)
  38     {
  39       if (table[j] >= table[j - 1])
  40         break;
  41
  42       swap = table[j];
  43       table[j] = table[j - 1];
  44       table[j - 1] = swap;
  45     }
  46   }
  47 }
  48
  49
  50 void
  51 ta_sort_and_quantize_widths(FT_UInt* count,
  52                             TA_Width table,
  53                             FT_Pos threshold)
  54 {
  55   FT_UInt i;
  56   FT_UInt j;
  57   FT_UInt cur_idx;
  58   FT_Pos cur_val;
  59   FT_Pos sum;
  60   TA_WidthRec swap;
  61
  62
  63   if (*count == 1)
  64     return;
  65
  66   /* sort */
  67   for (i = 1; i < *count; i++)
  68   {
  69     for (j = i; j > 0; j--)
  70     {
  71       if (table[j].org >= table[j - 1].org)
  72         break;
  73
  74       swap = table[j];
  75       table[j] = table[j - 1];
  76       table[j - 1] = swap;
  77     }
  78   }
  79
  80   cur_idx = 0;
  81   cur_val = table[cur_idx].org;
  82
  83   /* compute and use mean values for clusters not larger than `threshold'; */
  84   /* this is very primitive and might not yield the best result, */
  85   /* but normally, using reference character `o', `*count' is 2, */
  86   /* so the code below is fully sufficient */
  87   for (i = 1; i < *count; i++)
  88   {
  89     if (table[i].org - cur_val > threshold
  90         || i == *count - 1)
  91     {
  92       sum = 0;
  93
  94       /* fix loop for end of array */
  95       if (table[i].org - cur_val <= threshold
  96           && i == *count - 1)
  97         i++;
  98
  99       for (j = cur_idx; j < i; j++)
 100       {
 101         sum += table[j].org;
 102         table[j].org = 0;
 103       }
 104       table[cur_idx].org = sum / j;
 105
 106       if (i < *count - 1)
 107       {
 108         cur_idx = i + 1;
 109         cur_val = table[cur_idx].org;
 110       }
 111     }
 112   }
 113
 114   cur_idx = 1;
 115
 116   /* compress array to remove zero values */
 117   for (i = 1; i < *count; i++)
 118   {
 119     if (table[i].org)
 120       table[cur_idx++] = table[i];
 121   }
 122
 123   *count = cur_idx;
 124 }
 125
 126 /* end of tasort.c */