/*
* Characters classes
* Copyright
* (C) 2015 Joseph H. Allen
*
* This file is part of JOE (Joe's Own Editor)
*/
#include "types.h"
/* Sort an array of struct intervals */
static int itest(const void *ia, const void *ib)
{
struct interval *a = (struct interval *)ia;
struct interval *b = (struct interval *)ib;
if (a->first > b->first)
return 1;
else if (a->first < b->first)
return -1;
else
return 0;
}
void interval_sort(struct interval *array, ptrdiff_t num)
{
jsort(array, num, SIZEOF(struct interval), itest);
}
/* Test if character ch is in one of the struct intervals in array using binary search.
* Returns index to interval, or -1 if none found. */
ptrdiff_t interval_test(struct interval *array, ptrdiff_t size, int ch)
{
if (size) {
ptrdiff_t min = 0;
ptrdiff_t mid;
ptrdiff_t max = size - 1;
if (ch < array[min].first || ch > array[max].last)
goto no_match;
while (max >= min) {
mid = (min + max) / 2;
if (ch > array[mid].last)
min = mid + 1;
else if (ch < array[mid].first)
max = mid - 1;
else
return mid;
}
}
no_match:
return -1;
}
/* Return true if character ch is in radix tree r */
int rset_lookup(struct Rset *r, int ch)
{
int a = (TOPMASK & (ch >> TOPSHIFT));
int b = (SECONDMASK & (ch >> SECONDSHIFT));
int c = (THIRDMASK & (ch >> THIRDSHIFT));
int d = (LEAFMASK & (ch >> LEAFSHIFT));
if (a >= TOPSIZE)
return 0;
if (a || b) { /* Full lookup for character >= 512 */
int idx = r->top.entry[a];
if (idx != -1) {
idx = r->second.table.b[idx].entry[b];
if (idx != -1) {
idx = r->third.table.c[idx].entry[c];
return ((1 << d) & idx) != 0;
}
}
} else { /* Quick lookup for character < 512 */
int idx = r->mid.entry[c];
return ((1 << d) & idx) != 0;
}
return 0;
}
/* Same as above, but can be be called before rset_opt() */
int rset_lookup_unopt(struct Rset *r, int ch)
{
int a = (TOPMASK & (ch >> TOPSHIFT));
int b = (SECONDMASK & (ch >> SECONDSHIFT));
int c = (THIRDMASK & (ch >> THIRDSHIFT));
int d = (LEAFMASK & (ch >> LEAFSHIFT));
int idx;
if (a >= TOPSIZE)
return 0;
idx = r->top.entry[a];
if (idx != -1) {
idx = r->second.table.b[idx].entry[b];
if (idx != -1) {
idx = r->third.table.c[idx].entry[c];
return ((1 << d) & idx) != 0;
}
}
return 0;
}
void rset_init(struct Rset *r)
{
int x;
for (x = 0; x != TOPSIZE; ++x)
r->top.entry[x] = -1;
r->second.alloc = 0;
r->second.size = 1;
r->second.table.b = (struct Mid *)joe_malloc(r->second.size * SIZEOF(struct Mid));
r->third.alloc = 0;
r->third.size = 1;
r->third.table.c = (struct Mid *)joe_malloc(r->third.size * SIZEOF(struct Mid));
}
void rset_clr(struct Rset *r)
{
joe_free(r->second.table.b);
joe_free(r->third.table.c);
}
static int rset_alloc(struct Level *l, int levelno)
{
int x;
if (l->alloc == l->size) {
l->size *= 2;
switch (levelno) {
case 1: {
l->table.b = (struct Mid *)joe_realloc(l->table.b, l->size * SIZEOF(struct Mid));
break;
} case 2: {
l->table.c = (struct Mid *)joe_realloc(l->table.c, l->size * SIZEOF(struct Mid));
break;
}
}
}
switch (levelno) {
case 1: {
for (x = 0; x != SECONDSIZE; ++x)
l->table.b[l->alloc].entry[x] = -1;
break;
} case 2: {
for (x = 0; x != THIRDSIZE; ++x)
l->table.c[l->alloc].entry[x] = 0;
break;
}
}
return l->alloc++;
}
void rset_add(struct Rset *r, int ch, int che)
{
int a = (TOPMASK & (ch >> TOPSHIFT));
int b = (THIRDMASK & (ch >> SECONDSHIFT));
int c = (SECONDMASK & (ch >> THIRDSHIFT));
int d = (LEAFMASK & (ch >> LEAFSHIFT));
int ib;
int ic;
while (ch <= che) {
if (a >= TOPSIZE)
return;
ib = r->top.entry[a];
if (ib == -1) {
r->top.entry[a] = ib = rset_alloc(&r->second, 1);
}
while (ch <= che) {
ic = r->second.table.b[ib].entry[b];
if (ic == -1) {
r->second.table.b[ib].entry[b] = ic = rset_alloc(&r->third, 2);
}
while (ch <= che) {
r->third.table.c[ic].entry[c] |= (1 << d);
++ch;
if (++d == LEAFSIZE) {
d = 0;
if (++c == THIRDSIZE) {
c = 0;
break;
}
}
}
if (++b == SECONDSIZE) {
b = 0;
break;
}
}
++a;
}
}
/* Optimize radix tree: setup mid */
void rset_opt(struct Rset *r)
{
int x;
int idx;
/* Set up mid table */
for (x = 0; x != THIRDSIZE; ++x)
r->mid.entry[x] = 0;
idx = r->top.entry[0];
if (idx != -1) {
idx = r->second.table.b[idx].entry[0];
if (idx != -1) {
mcpy(r->mid.entry, r->third.table.c[idx].entry, SIZEOF(r->mid.entry));
}
}
}
void rset_set(struct Rset *r, struct interval *array, ptrdiff_t size)
{
ptrdiff_t y;
for (y = 0; y != size; ++y) {
rset_add(r, array[y].first, array[y].last);
/* int x;
for (x = array[y].first; x <= array[y].last; ++x)
rset_add(r, x); */
}
}
void rset_show(struct Rset *r)
{
int first = -2;
int last = -2;
int a;
for (a = 0; a != TOPSIZE; ++a) {
int ib = r->top.entry[a];
if (ib != -1) {
int b;
for (b = 0; b != SECONDSIZE; ++b) {
int ic = r->second.table.b[ib].entry[b];
if (ic != -1) {
int c;
for (c = 0; c != THIRDSIZE; ++c) {
int id = r->third.table.c[ic].entry[c];
int d;
for (d = 0; d != LEAFSIZE; ++d) {
if (id & (1 << d)) {
int ch = (a << TOPSHIFT) + (b << SECONDSHIFT) + (c << THIRDSHIFT) + d;
if (ch == last + 1) {
last = ch;
} else if (first != -2) {
printf(" { 0x%4.4X, 0x%4.4X },\n", first, last);
first = last = ch;
} else {
first = last = ch;
}
}
}
}
}
}
}
}
if (first != -2)
printf(" { 0x%4.4X, 0x%4.4X },\n", first, last);
}
void cclass_init(struct Cclass *m)
{
m->size = 0;
m->len = 0;
m->intervals = 0;
}
void cclass_clr(struct Cclass *m)
{
if (m->intervals)
joe_free(m->intervals);
m->size = 0;
m->len = 0;
m->intervals = 0;
}
/* Delete range from character class at position x
* x is in range 0 to (m->len - 1), inclusive.
*/
static void cclass_del(struct Cclass *m, int x)
{
mmove(m->intervals + x, m->intervals + x + 1, SIZEOF(struct interval) * (m->len - (x + 1)));
--m->len;
}
/* We are about to insert: expand array if necessary */
static void cclass_grow(struct Cclass *m)
{
if (m->len == m->size) {
if (!m->size) {
m->size = 1;
m->intervals = (struct interval *)joe_malloc(SIZEOF(struct interval) * (m->size));
} else {
m->size *= 2;
m->intervals = (struct interval *)joe_realloc(m->intervals, SIZEOF(struct interval) * (m->size));
}
}
}
/* Insert a range into a character class at position x
* x is in range 0 to m->len inclusive.
*/
static void cclass_ins(struct Cclass *m, int x, int first, int last)
{
cclass_grow(m);
mmove(m->intervals + x + 1, m->intervals + x, SIZEOF(struct interval) * (m->len - x));
++m->len;
m->intervals[x].first = first;
m->intervals[x].last = last;
}
/* Add a single range [first,last] into class m. The resulting m->intervals will
* be sorted and consist of non-overlapping, non-adjacent ranges.
*/
void cclass_add(struct Cclass *m, int first, int last)
{
int x;
/* If it's invalid, ignore */
if (last < first)
return;
for (x = 0; x != m->len; ++x) {
if (first > m->intervals[x].last + 1) {
/* intervals[x] is below new range, skip it. */
} else if (m->intervals[x].first > last + 1) {
/* intervals[x] is fully above new range, so insert new one here */
break;
} else if (m->intervals[x].first <= first) {
if (m->intervals[x].last >= last) { /* && m->intervals[x].first <= first */
/* Existing covers new: we're done. */
return;
} else { /* m->intervals[x].last < last && m->intervals[x].first <= first */
/* Enlarge new, delete existing */
first = m->intervals[x].first;
cclass_del(m, x);
--x;
}
} else { /* m->intervals[x].first > first */
if (m->intervals[x].last <= last) { /* && m->intervals[x].first <= first */
/* New fully covers existing, delete existing */
cclass_del(m, x);
--x;
} else { /* m->intervals[x].last > last && m->intervals[x].first > first */
/* Extend existing */
m->intervals[x].first = first;
return;
}
}
}
cclass_ins(m, x, first, last);
}
/* Merge class n into class m */
void cclass_union(struct Cclass *m, struct Cclass *n)
{
int x;
if (n)
for (x = 0; x != n->len; ++x)
cclass_add(m, n->intervals[x].first, n->intervals[x].last);
}
void cclass_merge(struct Cclass *m, struct interval *array, int len)
{
int x;
for (x = 0; x != len; ++x)
cclass_add(m, array[x].first, array[x].last);
}
/* Subtract a single range [first,last] from class m. The resulting m->array will
* be sorted and consist of non-overlapping, non-adjacent ranges.
*/
void cclass_sub(struct Cclass *m, int first, int last)
{
int x;
/* If it's invalid, ignore */
if (last < first)
return;
for (x = 0; x != m->len; ++x) {
if (first > m->intervals[x].last) {
/* intervals[x] is below range, skip it. */
} else if (m->intervals[x].first > last) {
/* intervals[x] is fully above new range, we're done */
break;
} else if (first <= m->intervals[x].first) {
if (last >= m->intervals[x].last) { /* && first <= m->intervals[x].first */
/* Range fully covers entry, delete it */
cclass_del(m, x);
--x;
} else { /* last < m->intervals[x].last && first <= m->intervals[x].first */
/* Range cuts off bottom of entry */
m->intervals[x].first = last + 1;
}
} else { /* first > m->intervals[x].first */
if (last >= m->intervals[x].last) { /* && first > m->intervals[x].first */
/* Range cuts off top of entry */
m->intervals[x].last = first - 1;
} else { /* last < m->intervals[x].last && first > m->intervals[x].first */
/* Range is in middle of entry, split it */
cclass_ins(m, x, m->intervals[x].first, first - 1);
m->intervals[x + 1].first = last + 1;
++x;
}
}
}
}
/* Remove any parts of m which also appear in n */
void cclass_diff(struct Cclass *m, struct Cclass *n)
{
int x;
if (n)
for (x = 0; x != n->len; ++x)
cclass_sub(m, n->intervals[x].first, n->intervals[x].last);
}
/* Compute inverse of class m */
#define UNICODE_LAST 0x10FFFF
void cclass_inv(struct Cclass *m)
{
// printf("\r\nBefore:\n");
// cclass_show(m);
if (m->len && !m->intervals[0].first) {
/* Starts at 0 */
int x;
int last = m->intervals[0].last;
for (x = 0; x != m->len - 1; ++x) {
m->intervals[x].first = last + 1;
m->intervals[x].last = m->intervals[x + 1].first - 1;
last = m->intervals[x + 1].last;
}
if (last == UNICODE_LAST) {
--m->len; /* Delete last one */
} else {
m->intervals[x].first = last + 1;
m->intervals[x].last = UNICODE_LAST;
}
} else {
/* Does not start at 0 */
int x;
int first = 0;
for (x = 0; x != m->len; ++x) {
int new_first = m->intervals[x].last + 1;
m->intervals[x].last = m->intervals[x].first - 1;
m->intervals[x].first = first;
first = new_first;
}
if (first != UNICODE_LAST) {
cclass_grow(m);
m->intervals[x].first = first;
m->intervals[x].last = UNICODE_LAST;
++m->len;
}
}
// printf("\r\nAfter:\n");
// cclass_show(m);
// sleep(1);
}
int cclass_lookup_unopt(struct Cclass *m, int ch)
{
return interval_test(m->intervals, m->len, ch) != -1;
}
void cclass_opt(struct Cclass *m)
{
rset_init(m->rset);
rset_set(m->rset, m->intervals, m->len);
rset_opt(m->rset);
}
int cclass_lookup(struct Cclass *m, int ch)
{
return rset_lookup(m->rset, ch);
}
void cclass_show(struct Cclass *m)
{
int x;
int first = 0;
for (x = 0; x != m->len; ++x) {
if (!first)
first = 1;
else
printf(" ");
printf("[%x..%x]", (unsigned)m->intervals[x].first, (unsigned)m->intervals[x].last);
}
printf("\n");
}
