fsmTree.c

Go to the documentation of this file.

/* Copyright 2013 Jorge Merlino

   This file is part of Context.

   Context is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   Context is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with Context.  If not, see <http://www.gnu.org/licenses/>.
*/
 
#include <assert.h>
#include "fsmTree.h"
#include "alpha.h"
#include "text.h"
#include "spacedef.h"
#include "debug.h"
#include "arithmetic/coder.h"
#include "arithmetic/bitio.h"

#define ROOT -1

#define obstack_chunk_alloc malloc
#define obstack_chunk_free free

static short pos;

static Ushort internalNodes; 

static Uint totalNodes;

static void fastCanonize(fsmTree_t tree, Uint xLeft, Uint xRight, fsmTree_t *r, Uint *uLeft, Uint *uRight, Uint *vLeft, Uint *vRight) {
  BOOL end;
  fsmTree_t child = NULL;

  *vLeft = 1;
  *vRight = 0; /* v is empty */
  
  if (tree->left != ROOT) {
    xLeft += tree->length + tree->right - tree->left + 1;
  }
  end = xLeft > xRight;
  
  while (!end) {
    child = tree->children[GETINDEX(xLeft)];
    if ((child->right - child->left) <= (xRight - xLeft)) {
      xLeft += child->right - child->left + 1;
      tree = child;
      end = xLeft > xRight;
    }
    else {
      end = True;
    }
  }

  *r = tree;
  if (xLeft <= xRight) {
    *uLeft = child->left;
    *uRight = child->left + xRight - xLeft;
  }
  else {
    *uLeft = 1;
    *uRight = 0; /* u is empty */
  }
}


static void canonize(fsmTree_t tree, Uint xLeft, Uint xRight, fsmTree_t *r, Uint *uLeft, Uint *uRight, Uint *vLeft, Uint *vRight) {
  BOOL end = False;
  Uint i;
  fsmTree_t child;

  if (xLeft > xRight) {
    *uLeft = 1;
    *uRight = 0; /* u is empty */
    end = True;
  }
  else if (tree->left != ROOT) {
    xLeft += tree->length + tree->right - tree->left + 1;
  }

  while (!end) {
    child = tree->children[GETINDEX(xLeft)]; 
    if (child) { /* there is an edge in the direction of xLeft */
      for (i=child->left; (i<=child->right) && (xLeft<=xRight) && (text[i]==text[xLeft]); i++, xLeft++); 
      if (i > child->right) { /* all the edge is in x */
    tree = child;
    if (xLeft > xRight) {
      end = True;
      *uLeft = 1;
      *uRight = 0; /* u is empty */
    }
      }
      else {
    end = True;
    *uLeft = child->left;
    *uRight = i-1;
      }
    }
    else {
      end = True;
      *uLeft = 1;
      *uRight = 0; /* u is empty */
    }
  }

  *r = tree;
  *vLeft = xLeft;
  *vRight = xRight;
}


static fsmTree_t insert (fsmTree_t r, Uint uLeft, Uint uRight, Uint vLeft, Uint vRight) {
  fsmTree_t new  = initFsmTree(), newLeaf, ret;

  if (uLeft > uRight) {
    /* add */
    new->left = vLeft;
    new->right = vRight;
    if (r->left != ROOT) {
      new->length = r->length + r->right - r->left + 1;
    }
    new->parent = r; 
    r->children[GETINDEX(vLeft)] = new;

    new->origin = r->origin;
    ret = new;
  }
  else {
    /* split */
    new->left = uLeft;
    new->right = uRight;
    new->length = r->children[GETINDEX(uLeft)]->length;
    new->children[GETINDEX(uRight+1)] = r->children[GETINDEX(uLeft)]; 
    new->children[GETINDEX(uRight+1)]->left = uRight+1;
    new->children[GETINDEX(uRight+1)]->length = new->length + uRight - uLeft + 1;
    new->children[GETINDEX(uRight+1)]->parent = new; 
    new->parent = r; 
    r->children[GETINDEX(uLeft)] = new;

    new->origin = r->origin;
    new->traversed[GETINDEX(uRight+1)] = r->traversed[GETINDEX(uLeft)];

    if (vLeft <= vRight) {
      newLeaf = initFsmTree();
      /* add */
      newLeaf->left = vLeft;
      newLeaf->right = vRight;
      newLeaf->length = new->length + new->right - new->left + 1;
      newLeaf->parent = new; 
      new->children[GETINDEX(vLeft)] = newLeaf;

      newLeaf->origin = new->origin;
      ret = newLeaf;
    }
    else {
      ret = new;
    }
  }
  return ret; 
}


static void verify(const fsmTree_t root, fsmTree_t node, BOOL fast) {
  Uint xLeft, uLeft, uRight, vLeft, vRight, i, cidx;
  fsmTree_t r, x;
 
  if (node->left != ROOT) {
    cidx = GETINDEX(node->left - node->length);
    xLeft = node->left - node->length + 1;

    if (fast) {
      fastCanonize(root, xLeft, node->right, &r, &uLeft, &uRight, &vLeft, &vRight);
    } 
    else {
      canonize(root, xLeft, node->right, &r, &uLeft, &uRight, &vLeft, &vRight);
    }

    if ((uLeft <= uRight) || (vLeft <= vRight)) {
      x = insert(r, uLeft, uRight, vLeft, vRight);
      if (uLeft <= uRight) {
    if (r->traversed[GETINDEX(uLeft)]) {
      verify((r->left == ROOT ? r : r->tail), r->children[GETINDEX(uLeft)], True);
    }
      }
      else if (r->traversed[GETINDEX(vLeft)]) {
    verify((r->left == ROOT ? r : r->tail), r->children[GETINDEX(vLeft)], False);
      }
    }
    else { /* the node already exists */
      x = r;
    }
    node->tail = x;
    x->transitions[cidx] = node;
  } 
  for (i=0; i<alphasize; i++) {
    if (!node->traversed[i]) {
      node->traversed[i] = True;
      if (node->children[i]) {
    verify((node->left == ROOT ? node : node->tail), node->children[i], False);
      }
    }
  }  
}


static void propagateTransitions(fsmTree_t *transitions, fsmTree_t tree) {
  Uint i;

  for (i=0; i<alphasize; i++) {
    if (!tree->transitions[i]) {
      tree->transitions[i] = transitions[i];
    }
  }

  for (i=0; i<alphasize; i++) {
    if (tree->children[i]) {
      propagateTransitions(tree->transitions, tree->children[i]);
    }
  }
}

static BOOL writeEncoder(BOOL internal, FILE *file) {
  SYMBOL s;
  Uint shift = 0, totalN = totalNodes, internalN = internalNodes;

  while ((totalN & 0xFFFFC000) != 0) { /* some of the most significative 18 bits on */
    totalN >>= 1;
    shift++;
  }

  if (shift > 0) {
    internalN >>= shift;
    totalN = (internalN * alphasize) + 1;
  }

  s.scale = totalN;
  if (internal) {
    s.low_count = 0;
    s.high_count = internalN;
    internalNodes--;
  }
  else {
    s.low_count = internalN;
    s.high_count = totalN;
  }
  totalNodes--;
  encode_symbol(file, &s);

  return ((totalNodes == internalNodes) || internalNodes == 0);
}


static BOOL writeFsmTreeRec(const fsmTree_t tree, Uint offset, FILE *file) {
  Uint i;
  BOOL leaf = True, stop;

  if (tree->left + offset == tree->right) {
    for (i=0; i<alphasize && leaf; i++) {
      leaf = !tree->children[i];
    }
    if (leaf) {
      return writeEncoder(0, file);
    }
    else {
      stop = writeEncoder(1, file);
      if (stop) return True;
      for (i=0; i<alphasize; i++) {
    if (tree->children[i]) {
      stop = writeFsmTreeRec(tree->children[i], 0, file);
      if (stop) return True;
    }
    else {
      stop = writeEncoder(0, file);
      if (stop) return True;
    }
      }
    }
  }
  else {
    stop = writeEncoder(1, file);
    if (stop) return True;
    for (i=0; i<alphasize; i++) {
      if (GETINDEX(tree->left + offset + 1) == i) {
    stop = writeFsmTreeRec(tree, offset+1, file);
    if (stop) return True;
      }
      else {
    stop = writeEncoder(0, file);
    if (stop) return True;
      }
    }
  }
  return False;
}


static Ushort getInternalNodeCount (const fsmTree_t tree, const Uint offset) {
  Uint i, count = 0;
  BOOL leaf = True;

  if (tree->left + offset == tree->right) {
    for (i=0; i<alphasize; i++) {
      if (tree->children[i]) {
    count += getInternalNodeCount(tree->children[i], 0);
    leaf = False;
      }
    }
    if (!leaf) count ++;
  }
  else {
    count = getInternalNodeCount(tree, offset+1) + 1;
  }
  return count;
}

static void copyStatisticsRec (const fsmTree_t orig, const int offsetOrig, fsmTree_t dest, const int offsetDest, const Uchar * text2) {
  int i, posDest, posOrig;
  BOOL end;
 
  posDest = dest->left + offsetDest;
  posOrig = orig->left + offsetOrig;
  end = False;
  while (posOrig <= orig->right && posDest <= dest->right && !end) {
    if (text2[posOrig] == text[posDest]) {
      posOrig++;
      posDest++;
    }
    else {
      end = True;
    }
  }

  if (!end) {
    if (posDest > dest->right) { /* reached a node in dest */
      dest->origin->totalSyms = orig->origin->totalSyms;
      dest->origin->totalCount = orig->origin->totalCount;
      for (i=0; i<alphasize; i++) {
    dest->origin->symbols[i] = orig->origin->symbols[i];
    dest->origin->count[i] = orig->origin->count[i];
      }

      if (posOrig > orig->right) { /* reached a node in orig also */
    for (i=0; i<alphasize; i++) {
      if (orig->children[i] && dest->children[i]) {
        copyStatisticsRec(orig->children[i], 0, dest->children[i], 0, text2);
      }
    }
      }
      else {
    if (dest->children[GETINDEX3(posOrig)]) {
      copyStatisticsRec(orig, posOrig, dest->children[GETINDEX3(posOrig)], 0, text2);
    }
      }
    
    }
    else { /* reached a node in orig */
      if (orig->children[GETINDEX(posDest)]) 
    copyStatisticsRec(orig->children[GETINDEX(posDest)], 0, dest, posDest, text2);
    }
  }
}

#ifdef DEBUG

static void printRec(const fsmTree_t tree, int level) {
  int i;

  if (level > 0) {
    for (i=1; i<=level; i++) {
      printf("-");
    }

    assert (tree->right < textlen);
    assert (tree->left < textlen);
    printf("%ld - %ld (%p) parent: %p orig: %p\n", tree->left, tree->right, (void*)tree, (void*)tree->parent, (void*)tree->origin); 
    for (i=tree->left; i< tree->right; i++) {
      printf("%d-", *(text + i));
    }
    if (tree->right == textlen) {
      printf("$\n");
    }
    else {
      printf("%d\n", *(text + tree->right));
    }
  }
  else {
    printf("(root)\n");
  }
  
  level++;
  for (i=0; i<alphasize; i++) {
    if (tree->children[i]) {
      printf ("hijo %d ", i);
      printRec(tree->children[i], level);
    }
  }
}

#endif

fsmTree_t initFsmTree() {
  fsmTree_t ret;

  CALLOC(ret, struct fsmTree, 1);
  memset(ret, 0, sizeof(struct fsmTree));

#ifndef WIN32
  obstack_init (&(ret->nodeStack));
  if (obstack_chunk_size (&(ret->nodeStack)) < 16384) {
    obstack_chunk_size (&(ret->nodeStack)) = 16384;
  }
  
  ret->children = (fsmTree_t *)obstack_alloc(&(ret->nodeStack), sizeof(struct fsmTree *) * alphasize);
  memset(ret->children, 0, sizeof(struct fsmTree *) * alphasize);
  
  ret->transitions = (fsmTree_t *)obstack_alloc(&(ret->nodeStack), sizeof(struct fsmTree *) * alphasize);
  memset(ret->transitions, 0, sizeof(struct fsmTree *) * alphasize);
  
  ret->traversed = (BOOL *)obstack_alloc(&(ret->nodeStack), sizeof(BOOL) * alphasize);
  memset(ret->traversed, 0, sizeof(BOOL) * alphasize);
  
  ret->count = (Uint *)obstack_alloc(&(ret->nodeStack), sizeof(Uint) * alphasize);
  ret->symbols = (Uchar *)obstack_alloc(&(ret->nodeStack), sizeof(Uchar) * alphasize);
#else
  CALLOC(ret, struct fsmTree, 1);
  CALLOC(ret->children, struct fsmTree *, alphasize);
  CALLOC(ret->transitions, struct fsmTree *, alphasize);
  CALLOC(ret->traversed, BOOL, alphasize);
  MALLOC(ret->count, Uint, alphasize); 
  MALLOC(ret->symbols, Uchar, alphasize); 
#endif

  /* not always true but makes sense as init */
  ret->left = ret->right = ROOT;
  ret->origin = ret;
  ret->used = False;
  return ret;
}


void freeFsmTree(fsmTree_t tree) {
#ifndef WIN32
  obstack_free(&(tree->nodeStack), NULL);
#else
  FREE(tree->children);
  FREE(tree->transitions);
  FREE(tree->traversed);
  FREE(tree->count);
  FREE(tree->symbols);
  FREE(tree);
#endif
} 

void addSymbol(fsmTree_t tree, const Uchar sym) {
  tree->symbols[tree->totalSyms] = sym;
  tree->count[tree->totalSyms] = 1;
  tree->totalSyms++;
  tree->totalCount++;
}

void makeFsm(fsmTree_t tree) {
  fsmTree_t *transitions;
  Uint i;

  CALLOC(transitions, fsmTree_t, alphasize);
  tree->used = True;
  verify(tree, tree, False);
  for (i=0; i<alphasize; i++) {
    transitions[i] = tree; /* ROOT */
  }
  propagateTransitions (transitions, tree);
  FREE(transitions);
}


void writeFsmTree(const fsmTree_t tree, FILE *file) {
  Uint total, internal;
  SYMBOL s;
  long cost;

  pos = 0;
  
  internalNodes = internal = getInternalNodeCount(tree, 0);
  totalNodes = total = (internalNodes * alphasize) + 1;

  cost = bit_ftell_output(file);

  assert(internalNodes < 16383);
  s.scale = 16383;
  s.low_count = internalNodes;
  s.high_count = internalNodes + 1;
  encode_symbol(file, &s);
  
  if (internalNodes > 0) {
    writeFsmTreeRec(tree, 0, file);
  }
  printf("Representantion cost: %ld (internal: %ld, total: %ld)\n", 
     bit_ftell_output(file) - cost, internal, total);
}


BOOL isRootFsmTree(const fsmTree_t tree) {
  return tree->left == ROOT;
}

Uint getHeight (const fsmTree_t tree) {
  Uint i, max = 0, h;

  for (i=0; i<alphasize; i++) {
    if (tree->children[i]) {
      h = getHeight(tree->children[i]);
      if (h > max) max = h;
    }
  }

  return max + tree->right - tree->left + 1;
}

void printContext (fsmTree_t tree) {
  int i;
  
  while (tree->left != ROOT) {
    for (i=tree->left; i< tree->right; i++) {
      printf("%c", *(text + i));
    }
    if (tree->right == textlen) {
      printf("$\n");
    }
    else {
      printf("%c\n", *(text + tree->right));
    }
    tree = tree->parent;
  }
  printf("root\n");
}

static int compareTreesRec (const fsmTree_t treeA, const fsmTree_t treeB, int level) {
  int i, minLevel, actLevel;

  if ((treeA == NULL && treeB != NULL) || (treeA != NULL && treeB == NULL)) {
    return level;
  }
  else if (treeA == NULL && treeB == NULL) {
    return -1;
  }
  else {
    minLevel = compareTreesRec(treeA->children[0], treeB->children[0], level+1);
    for (i=1; (i<alphasize) && (minLevel != level+1); i++) {
      actLevel = compareTreesRec(treeA->children[i], treeB->children[i], level+1);
      if ((actLevel > 0) && (minLevel > actLevel)) {
    minLevel = actLevel;
      }
    }

    return minLevel;
  }
}

void compareTrees (const fsmTree_t treeA, const fsmTree_t treeB) {
  int level = compareTreesRec(treeA, treeB, 0);
  printf("First different level = %d\n", level);
}

void copyStatistics (const fsmTree_t orig, fsmTree_t dest, const Uchar * text2) {
  int i;

  dest->totalSyms = orig->totalSyms;
  dest->totalCount = orig->totalCount;
  for (i=0; i<alphasize; i++) {
    dest->symbols[i] = orig->symbols[i];
    dest->count[i] = orig->count[i];
  }
  
  for (i=0; i<alphasize; i++) {
    if (orig->children[i] && dest->children[i]) {
      copyStatisticsRec(orig->children[i], 0, dest->children[i], 0, text2);
    }
  }
}

#ifdef DEBUG

void printFsmTree(const fsmTree_t tree) {
  printRec(tree, 0);
}

#endif