lzindex/trie.c

   1
   2  // LZ78 trie data structure
   3
   4 #include "trie.h"
   5
   6         // creates trie
   7
   8 trie createTrie (void)
   9
  10    { trie pTrie;
  11      uint i;
  12      pTrie = malloc (sizeof(struct strie));
  13      pTrie->nid = 0;
  14      pTrie->trie.id = pTrie->nid++;
  15      pTrie->trie.nchildren = 0;
  16      pTrie->trie.children = NULL;
  17      pTrie->heaps[0] = createHeap(sizeof(triebody));
  18      for (i=1;i<256;i++)
  19         pTrie->heaps[i] = createHeap(i*sizeof(struct schild));
  20      return pTrie;
  21    }
  22
  23 uint sizeofTrie(triebody *t)
  24  {
  25     uint i, size = 0;
  26     size = sizeof(uint)+sizeof(short)+sizeof(struct schild *);
  27     for (i=0;i<t->nchildren;i++)
  28        size += sizeof(byte)+sizeof(struct striebody *)+sizeofTrie(t->children[i].trie);
  29     return size;
  30  }
  31
  32         // frees the trie
  33
  34 void destroyTrie (trie pTrie)
  35
  36    { uint i;
  37      for (i=0;i<256;i++) destroyHeap (pTrie->heaps[i]);
  38      free (pTrie);
  39    }
  40
  41         // inserts word[0...] into pTrie and returns new text ptr
  42         // insertion proceeds until we get a new trie node
  43
  44 byte *insertTrie (trie pTrie, byte *word)
  45
  46    { triebody *t = &pTrie->trie;
  47      triebody *nt;
  48      struct schild *newc;
  49      int i,j;
  50      int m = 0;
  51         // traverse pTrie with word[0...]
  52      while (true)
  53        { i = 0;
  54          while (i < t->nchildren)
  55             { if (t->children[i].car >= word[m]) break;
  56               i++;
  57             }
  58          if ((i == t->nchildren) || (t->children[i].car > word[m]))
  59             break;  // not found, get out
  60          t = t->children[i].trie;
  61          m++;
  62        }
  63         // at this point we fell off the trie, which is guaranteed to occur
  64         // since the text finishes with the unique character 0
  65      newc = mallocHeap(pTrie->heaps[t->nchildren+1]);
  66      memcpy (newc,t->children,i*sizeof(struct schild));
  67      memcpy (newc+i+1,t->children+i,(t->nchildren-i)*sizeof(struct schild));
  68      freeHeap (pTrie->heaps[t->nchildren],t->children);
  69      t->children = newc;
  70      t->children[i].car = word[m];
  71      nt = mallocHeap (pTrie->heaps[0]);
  72      t->children[i].trie = nt;
  73      t->nchildren++;
  74         // new node created
  75      nt->id = pTrie->nid++;
  76      nt->nchildren = 0;
  77      nt->children = NULL;
  78         // return rest of text
  79      return word+m+1;
  80    }
  81
  82         // inserts word[0..len-1] into pTrie, with id = id
  83         // assumes that no two equal strings are ever inserted
  84
  85 void insertstringTrie (trie pTrie, byte *word, uint len, uint id)
  86
  87    { triebody *t,*nt;
  88      uint i,j,m;
  89      struct schild *newc;
  90         // traverse pTrie with word[0...]
  91      t = &pTrie->trie;
  92      m = 0;
  93      while (m < len)
  94        { i = 0;
  95          while (i < t->nchildren)
  96             { if (t->children[i].car >= word[m]) break;
  97               i++;
  98             }
  99          if ((i == t->nchildren) || (t->children[i].car > word[m]))
 100             break;  // not found, get out
 101          t = t->children[i].trie;
 102          m++;
 103        }
 104         // if we fell off the trie, we create more (unary and empty) nodes
 105      while (m < len)
 106        { newc = mallocHeap(pTrie->heaps[t->nchildren+1]);
 107          memcpy (newc,t->children,i*sizeof(struct schild));
 108          memcpy (newc+i+1,t->children+i,(t->nchildren-i)*sizeof(struct schild));
 109          freeHeap (pTrie->heaps[t->nchildren],t->children);
 110          t->children = newc;
 111          if ((t->id == ~0) && (t->nchildren == 1)) pTrie->nid++; //not mute now
 112          t->children[i].car = word[m];
 113          nt = mallocHeap (pTrie->heaps[0]);
 114          nt->id = ~0; // empty node, at least for now
 115          nt->nchildren = 0;
 116          nt->children = NULL;
 117          t->children[i].trie = nt;
 118          t->nchildren++;
 119          t = nt;
 120          m++; i = 0;
 121        }
 122         // new node created or existing node with id added
 123      t->id = id;
 124      if (t->nchildren <= 1) pTrie->nid++; //not mute now
 125    }
 126
 127         // represents pTrie with parentheses, letters and ids
 128
 129         // also returns the leftmost id
 130 static uint traverse(triebody *t, uint *parent, byte *letters, uint *ids,
 131                      uint *pi, uint *pli)
 132  {
 133     uint i,chid,oldpli,myid;
 134     myid = t->id;
 135     // open parenthesis
 136     bitclean(parent,*pi);
 137     ids[myid] = *pi;
 138     (*pi)++;
 139     oldpli = *pli;
 140     // traverse children
 141     for (i=0; i<t->nchildren; i++) {
 142        (*pli)++;
 143        letters[*pli] = t->children[i].car;
 144        chid = traverse(t->children[i].trie,parent,letters,ids,pi,pli);
 145     }
 146     // close parenthesis
 147     bitset(parent,*pi);
 148     (*pi)++;
 149     // return leftmost id
 150     return myid;
 151  }
 152
 153 void representTrie (trie pTrie, uint *parent, byte *letters, uint *ids)
 154  {
 155     uint pi,pli;
 156     letters[0] = 0; // dummy value
 157     pi = 0; pli = 0;
 158     traverse(&pTrie->trie,parent,letters,ids,&pi,&pli);
 159  }
 160