Logo Search packages:      
Sourcecode: ted version File versions

docListNumberTree.c

/************************************************************************/
/*                                                    */
/*  Manage the numbers in bulleted and numbered lists.                  */
/*                                                    */
/*  Levels in the tree correspond to the ilvl value of the paragraphs.  */
/*                                                    */
/************************************************************************/

#   include "tedConfig.h"

#   include <stdlib.h>
#   include <string.h>
#   include <stdio.h>

#   include <appDebugon.h>

#   include "docListNumberTree.h"
#   include "docListLevel.h"

/************************************************************************/
/*                                                    */
/*  Initialise a node.                                      */
/*                                                    */
/************************************************************************/

static void docInitListNumberTreeNode(    ListNumberTreeNode *    lntn )
    {
    lntn->lntnParagraphNumber= -1;
    lntn->lntnLeafCount= 0;
    lntn->lntnChildren= (ListNumberTreeNode *)0;
    lntn->lntnChildCount= 0;
    lntn->lntnIsLeaf= 0;

    return;
    }

static void docCleanListNumberTreeNode(   ListNumberTreeNode *    lntn )
    {
    docFreeListNumberNodes( lntn->lntnChildren, lntn->lntnChildCount );

    return;
    }

/************************************************************************/
/*                                                    */
/*  Debugging:                                              */
/*                                                    */
/*  1)  Get rid of 'not used' warning.                            */
/*                                                    */
/************************************************************************/

static void docDebugListNumberTreeNode(   int                     indent,
                              const ListNumberTreeNode *    lntn,
                              int                     before,
                              int                     after )
    {
    int                 i;

    const char *  bb= "";
    const char *  aa= "";

    if  ( before >= 0                     &&
        lntn->lntnParagraphNumber >= 0    &&
        lntn->lntnParagraphNumber <= before     )
      { bb= "#+#"; }
    if  ( after >= 0 && lntn->lntnParagraphNumber >= after )
      { aa= "#-#"; }

    appDebug( "%*sLEAVES= %d PARA= %d%s%s%s\n", 4* indent, "",
                            lntn->lntnLeafCount,
                            lntn->lntnParagraphNumber, bb, aa,
                            lntn->lntnIsLeaf?"*":"" );

    if  ( lntn->lntnParagraphNumber >= 0 )
      { before= lntn->lntnParagraphNumber;      }

    for ( i= 0; i < lntn->lntnChildCount- 1; i++ )
      {
      int         aft;

      aft= lntn->lntnChildren[i+ 1].lntnParagraphNumber;

      docDebugListNumberTreeNode( indent+ 1, &(lntn->lntnChildren[i]),
                                              before, aft );

      if  ( lntn->lntnChildren[i].lntnParagraphNumber >= 0 )
          { before= lntn->lntnChildren[i].lntnParagraphNumber;    }
      }

    if  ( i < lntn->lntnChildCount )
      {
      docDebugListNumberTreeNode( indent+ 1, &(lntn->lntnChildren[i]),
                                              before, after );
      }

    return;
    }

void docLogListNumberTreeNode(            int                     indent,
                              const ListNumberTreeNode *    lntn )
    {
    docDebugListNumberTreeNode( indent, lntn, -1, -1 );
    return;
    }

static void docListNumberTreeLogPath(     ListNumberTreeNode **   path,
                              int *             nums,
                              int               level )
    {
    int           i;

    /*  1  */
    if  ( level < -1 )
      { docListNumberTreeLogPath( path, nums, level+ 1 ); }

    appDebug( "PATH[%d]: ", level );

    for ( i= 0; i <= level; i++ )
      {
      ListNumberTreeNode *    node= path[i];

      if  ( ! node )
          { XDEB(node); return; }
      if  ( nums[i] < 0 )
          { LDEB(nums[i]); return; }

      if  ( nums[i] >= node->lntnChildCount )
          {
          appDebug( "%d[%d]. ",
                      node->lntnParagraphNumber,
                      nums[i] );
          }
      else{
          ListNumberTreeNode *      child;

          child= &(node->lntnChildren[nums[i]]);

          appDebug( "%d[%d]->%d%s ",
                      node->lntnParagraphNumber,
                      nums[i],
                      child->lntnParagraphNumber,
                      child->lntnIsLeaf?"*":"" );
          }
      }

    appDebug( "\n" );
    }

/************************************************************************/
/*                                                    */
/*  Allocate nodes.                                         */
/*                                                    */
/************************************************************************/

int docClaimListNumberTreeNodes(    ListNumberTreeNode **   pLntn,
                              int *             pCount,
                              int               count )
    {
    ListNumberTreeNode *      fresh;
    int                       i;

    fresh= (ListNumberTreeNode *)realloc( *pLntn,
                            count* sizeof( ListNumberTreeNode ) );
    if  ( ! fresh )
      { LXDEB(count,fresh); return -1;    }

    for ( i= *pCount; i < count; i++ )
      { docInitListNumberTreeNode( &(fresh[i]) );     }

    *pLntn= fresh;
    *pCount= count;

    return 0;
    }

/************************************************************************/
/*                                                    */
/*  Clean and free an array of nodes.                             */
/*                                                    */
/************************************************************************/

void docFreeListNumberNodes(  ListNumberTreeNode *    nodes,
                        int               count )
    {
    int                       i;
    ListNumberTreeNode *      lntn= nodes;

    for ( i= 0; i < count; lntn++, i++ )
      { docFreeListNumberNodes( lntn->lntnChildren, lntn->lntnChildCount ); }

    if  ( nodes )
      { free( nodes );  }

    return;
    }

/************************************************************************/
/*                                                    */
/*  Find a paragraph in the number tree.                    */
/*                                                    */
/*  1)  From root to leaves..                               */
/*  2)  Look for a child that is on, or past the paragraph that we look */
/*    for.                                            */
/*  3)  Found?                                              */
/*  4)  Enter the child before, or if there is none, report this as the */
/*    possible insertion point.                             */
/*  5)  Not found.. Report where.                           */
/*                                                    */
/*  path is the series of parent nodes that leads us to the node. */
/*  nums is the series of child node numbers if the corresponding */
/*    positions in 'path'. If the node is found, the value is the */
/*    index of the node. If nothing is found, the value is the index    */
/*    where it would be inserted at that particular level.        */
/*                                                    */
/************************************************************************/

static int docListNumberTreeFindParagraph(
                              int *             pLevel,
                              int *             pAfter,
                              ListNumberTreeNode **   path,
                              int *             nums,
                              ListNumberTreeNode *    root,
                              int               paraNr )
    {
    ListNumberTreeNode *      node= root;
    ListNumberTreeNode *      child= (ListNumberTreeNode *)0;

    int                       after= 0;
    int                       level= 0;
    int                       pos= 0;
    int                       cmp= -1;

    /*  1  */
    while( node->lntnChildCount > 0 )
      {
      path[level]= node;

      /*  2  */
      cmp= 1;
      child= (ListNumberTreeNode *)0;
      for ( pos= 0; pos < node->lntnChildCount; pos++ )
          {
          child= &(node->lntnChildren[pos]);

          cmp= paraNr- child->lntnParagraphNumber;
          if  ( cmp <= 0 )
            { break;    }
          }

      /*  3  */
      if  ( cmp == 0 && child->lntnIsLeaf )
          {
          nums[level]= pos;
          *pAfter= after;
          *pLevel= level;
          return 0;
          }

      /*  4  */
      if  ( pos == 0 )
          { after= 1; break;  }
      pos--;

      nums[level]= pos;
      node= &(node->lntnChildren[pos]);
      level++;
      }

    /*  5  */
    path[level]= node;
    nums[level]= 0;

    *pAfter= after;
    *pLevel= level;
    return 1;
    }

/************************************************************************/
/*                                                    */
/*  1)      Determine the list numbers on the path to a certain paragraph.    */
/*  2)      Determine the list numbers on the path to the predecessor of a    */
/*    certain paragraph.                                    */
/*                                                    */
/************************************************************************/

/*  1  */
int docListNumberTreeGetNumberPath( int *             nums,
                              ListNumberTreeNode *    root,
                              int               ilvl,
                              int               paraNr )
    {
    ListNumberTreeNode *      path[DLmaxLEVELS+1];
    int                       level= 0;
    int                       after= 0;

    if  ( ilvl < 0 || ilvl >= DLmaxLEVELS )
      { LLDEB(ilvl,DLmaxLEVELS); return -1;     }

    /* LLDEB(ilvl,paraNr);docLogListNumberTreeNode(0,root); */

    if  ( docListNumberTreeFindParagraph( &level, &after,
                                    path, nums, root, paraNr ) )
      {
      LDEB(paraNr); docLogListNumberTreeNode(0,root);
      return -1;
      }

    if  ( level != ilvl )
      { LLDEB(level,ilvl);    }

    return 0;
    }

/*  2  */
static int docListNumberTreePrevPath(     int *             nums,
                              int *             pLevel,
                              ListNumberTreeNode **   path,
                              int               level )
    {
    int                       ilvl= level;
    ListNumberTreeNode *      node;

    while( ilvl >= 0 && nums[ilvl] == 0 )
      {
      if  ( path[ilvl]->lntnParagraphNumber >= 0 )
          {
          *pLevel= ilvl- 1;
          return 0;
          }

      ilvl--;
      }

    if  ( ilvl < 0 )
      { return 1; }

    node= path[ilvl];
    nums[ilvl]--;
    node= &(node->lntnChildren[nums[ilvl]]);
    ilvl++;
    while( node->lntnChildCount > 0 )
      {
      nums[ilvl]= node->lntnChildCount- 1;
      node= &(node->lntnChildren[nums[ilvl]]);
      ilvl++;
      }

    *pLevel= ilvl- 1;
    return 0;
    }

/*  2  */
int docListNumberTreeGetPrevPath(   int *             nums,
                              int *             pLevel,
                              ListNumberTreeNode *    root,
                              int               paraNr )
    {
    ListNumberTreeNode *      path[DLmaxLEVELS+1];
    int                       level= 0;
    int                       after= 0;

    /* SLDEB("PREV",paraNr);docLogListNumberTreeNode(0,root); */

    if  ( docListNumberTreeFindParagraph( &level, &after,
                                    path, nums, root, paraNr ) )
      { LDEB(paraNr); return -1;    }

    return docListNumberTreePrevPath( nums, pLevel, path, level );
    }

/************************************************************************/
/*                                                    */
/*  Move node from one parent to another.                   */
/*                                                    */
/*  1)  Allocate memory.                                    */
/*  2)  Open hole.                                          */
/*  3)  Move nodes.                                         */
/*  4)  Close hole.                                         */
/*  5)  Fix counts.                                         */
/*                                                    */
/************************************************************************/

static int docListNumberTreeMoveChildren( ListNumberTreeNode *    to,
                                    int               topos,
                                    ListNumberTreeNode *    fr,
                                    int               frpos,
                                    int               cnt )
    {
    int           leavesMoved= 0;
    int           i;

    /*
    appDebug( "MOVE %d CHILDREN FROM %d[%d] TO %d[%d]\n", cnt,
                      fr->lntnParagraphNumber,
                      fr->lntnChildCount,
                      to->lntnParagraphNumber,
                      to->lntnChildCount );
    */

    /*  1  */
    if  ( docClaimListNumberTreeNodes( &(to->lntnChildren),
                               &(to->lntnChildCount),
                               to->lntnChildCount+ cnt ) )
      { LDEB(cnt); return -1; }

    /*  2  */
    for ( i= to->lntnChildCount- 1; i >= topos+ cnt; i-- )
      {
      to->lntnChildren[i]= to->lntnChildren[i- cnt];
      }

    /*  3  */
    for ( i= 0; i < cnt; i++ )
      {
      /*
      appDebug( "    MOVE %d FROM %d[%d] TO %d[%d]\n",
                  fr->lntnChildren[frpos+ i].lntnParagraphNumber,
                  fr->lntnParagraphNumber, frpos+ i,
                  to->lntnParagraphNumber, topos+ i );
      */

      to->lntnChildren[topos+ i]= fr->lntnChildren[frpos+ i];
      leavesMoved += to->lntnChildren[topos+ i].lntnLeafCount;
      }

    /*  4  */
    if  ( fr->lntnChildCount > frpos+ cnt )
      {
      for ( i= 0; i < cnt; i++ )
          { fr->lntnChildren[frpos+ i]= fr->lntnChildren[frpos+ i+ cnt]; }
      }

    /*  5  */
    fr->lntnChildCount -= cnt;
    to->lntnLeafCount += leavesMoved;
    fr->lntnLeafCount -= leavesMoved;

    return 0;
    }

/************************************************************************/
/*                                                    */
/*  Insert a child in a parent node.                              */
/*                                                    */
/*  1)  Allocate memory.                                    */
/*  2)  Open hole.                                          */
/*  3)  Initialize fresh child.                                   */
/*                                                    */
/************************************************************************/

static ListNumberTreeNode * docListNumberTreeInsertChild(
                              ListNumberTreeNode *    node,
                              int               pos )
    {
    int           i;

    /*  1  */
    if  ( docClaimListNumberTreeNodes( &(node->lntnChildren),
               &(node->lntnChildCount), node->lntnChildCount+ 1 ) )
      { LDEB(node->lntnChildCount); return (ListNumberTreeNode *)0;     }

    /*  2  */
    for ( i= node->lntnChildCount- 1; i > pos; i-- )
      { node->lntnChildren[i]= node->lntnChildren[i-1];     }

    /*  3  */
    docInitListNumberTreeNode( &(node->lntnChildren[pos]) );

    return &(node->lntnChildren[pos]);
    }

/************************************************************************/
/*                                                    */
/*  Insert a paragraph in a list number tree.                     */
/*                                                    */
/*  1)  Find a path to the insertion point.                       */
/*  2)  If it does not go up do the desired level, extend the tree upto */
/*    the desired level.                                    */
/*  3)  Insert the new leaf at the correct position.              */
/*  4)  Split deeper levels if necessary.                   */
/*                                                    */
/************************************************************************/

int docListNumberTreeInsertParagraph(     ListNumberTreeNode *    root,
                              int               ilvl,
                              int               paraNr )
    {
    ListNumberTreeNode *      path[DLmaxLEVELS+1];
    int                       nums[DLmaxLEVELS+1];

    ListNumberTreeNode *      node= root;
    ListNumberTreeNode *      fresh= root;
    int                       level= 0;
    int                       after= 0;

    int                       pos;
    int                       res;

    /* SLLDEB("ADD",ilvl,paraNr);docLogListNumberTreeNode(0,root); */

    if  ( ilvl < 0 || ilvl >= DLmaxLEVELS )
      { LLDEB(ilvl,DLmaxLEVELS); return -1;     }

    /*  1  */
    res= docListNumberTreeFindParagraph( &level, &after,
                                    path, nums, root, paraNr );
    if  ( res <= 0 )
      { LLDEB(paraNr,res); return -1;     }

    if  ( level < 0 )
      { LDEB(level); return -1;     }

    /* SDEB("@@"); docListNumberTreeLogPath( path, nums, level ); */

    /*  2  */
    if  ( level < ilvl )
      {
      node= path[level];
      pos= nums[level];

      while( level < ilvl )
          {
          fresh= docListNumberTreeInsertChild( node, pos );
          if  ( ! fresh )
            { XDEB(fresh); return -1;     }

          fresh->lntnParagraphNumber= -1;
          fresh->lntnLeafCount= 0; /* ++ below */
          fresh->lntnIsLeaf= 0;

          level++;

          path[level]= node= fresh;
          nums[level]= pos= 0;
          }
      }

    node= path[ilvl];
    pos= nums[ilvl];

    if  ( pos == 0                                    &&
        after                                         &&
        node->lntnChildren[pos].lntnParagraphNumber == -1   )
      {
      node->lntnChildren[pos].lntnParagraphNumber= paraNr;
      node->lntnChildren[pos].lntnLeafCount++;
      node->lntnChildren[pos].lntnIsLeaf= 1;
      }
    else{
      if  ( level > ilvl )
          { pos++;      }

      /*  3  */
      fresh= docListNumberTreeInsertChild( node, pos );
      if  ( ! fresh )
          { XDEB(fresh); return -1; }

      fresh->lntnParagraphNumber= paraNr;
      fresh->lntnLeafCount= 1;
      fresh->lntnIsLeaf= 1;
      }

    /*  4  */
    if  ( pos > 0 )
      {
      int               lev= ilvl+ 1;

      ListNumberTreeNode *    this= &(node->lntnChildren[pos   ]);

      while( lev <= level )
          {
          ListNumberTreeNode *      prev= &(node->lntnChildren[pos- 1]);
          const int                 topos= 0;

          pos= nums[lev]+ 1;
          if  ( after )
            { pos--;    }

          if  ( pos >= prev->lntnChildCount )
            { break;    }

          if  ( docListNumberTreeMoveChildren( this, topos,
                            prev, pos, prev->lntnChildCount- pos ) )
            { LDEB(pos); return -1; }

          if  ( lev < level- 1 )
            {
            fresh= docListNumberTreeInsertChild( this, 0 );
            if  ( ! fresh )
                { XDEB(fresh); return -1; }

            fresh->lntnParagraphNumber= -1;
            fresh->lntnLeafCount= 0; /* ++ below */
            fresh->lntnIsLeaf= 0;
            }

          this= &(this->lntnChildren[0]);
          node= prev;

          lev++;
          after= 0;
          }
      }

    /* SLLDEB("ADDDED",ilvl,paraNr);docLogListNumberTreeNode(0,root); */
    return 0;
    }


/************************************************************************/
/*                                                    */
/*  Delete a paragraph from the number tree.                      */
/*                                                    */
/*  1)  Look for the node.                                  */
/*  2)  Demote the node to an internal node.                      */
/*  3)  Try to merge children into predeceding nodes.             */
/*  4)  Look for the top level of the merge.                      */
/*  5)  Recursively merge all children into predecessor nodes.          */
/*  6)  If no children are left, remove the node from the tree.         */
/*  7)  Remove empty parents (unless a leaf!)                     */
/*                                                    */
/************************************************************************/

int docListNumberTreeDeleteParagraph(     ListNumberTreeNode *    root,
                              int               paraNr )
    {
    ListNumberTreeNode *      path[DLmaxLEVELS+1];
    int                       nums[DLmaxLEVELS+1];

    ListNumberTreeNode *      node;
    ListNumberTreeNode *      this;

    int                       level;
    int                       after;
    int                       pos;

    int                       i;

    /* SLDEB("DEL",paraNr);docLogListNumberTreeNode(0,root); */

    /*  1  */
    if  ( docListNumberTreeFindParagraph( &level, &after,
                                    path, nums, root, paraNr ) )
      { LDEB(paraNr); return -1;    }

    /* SDEB("@@"); docListNumberTreeLogPath( path, nums, level ); */

    node= path[level];
    pos= nums[level];
    this= &(node->lntnChildren[pos]);

    node->lntnLeafCount--;

    /*  2  */
    this->lntnParagraphNumber= -1;
    this->lntnIsLeaf= 0;

    /*  3  */
    if  ( this->lntnChildCount > 0 && pos > 0 )
      {
      int               top= level+ 1;
      ListNumberTreeNode *    prev;
      ListNumberTreeNode *    here;

      ListNumberTreeNode *    ppth[DLmaxLEVELS+1];
      int               pnms[DLmaxLEVELS+1];

      for ( i= 0; i < top; i++ )
          {
          ppth[i]= path[i];
          pnms[i]= nums[i];
          }

      prev= &(node->lntnChildren[pos- 1]);
      here= this;

      ppth[top]= node;
      pnms[top]= pos- 1;

      /*  4  */
      while( prev && here->lntnParagraphNumber == -1 )
          {
          if  ( here->lntnChildCount == 0 )
            { break;    }

          path[top]= here;
          nums[top]= 0;

          ppth[top]= prev;
          if  ( prev->lntnChildCount == 0 )
            { pnms[top]= 0;               }
          else{ pnms[top]= prev->lntnChildCount- 1;   }

          here= &(here->lntnChildren[0]);
          prev= &(prev->lntnChildren[prev->lntnChildCount- 1]);

          top++;
          }

      /*  5  */
      top--;
      while( top > level )
          {
          ListNumberTreeNode *      p= ppth[top];
          ListNumberTreeNode *      h= path[top];
          int                       skip= 0;

          /*
          SLDEB("PATH",top); docListNumberTreeLogPath( path, nums, top );
          docLogListNumberTreeNode(top,path[top]);
          SLDEB("PPTH",top); docListNumberTreeLogPath( ppth, pnms, top );
          docLogListNumberTreeNode(top,ppth[top]);
          */

          if  ( h->lntnChildCount > 0                       &&
              h->lntnChildren[0].lntnParagraphNumber < 0    )
            { skip= 1;  }

          if  ( docListNumberTreeMoveChildren( p, p->lntnChildCount,
                            h, 0+ skip, h->lntnChildCount- skip ) )
            { LDEB(pos); return -1; }

          if  ( skip )
            {
            docCleanListNumberTreeNode( &(h->lntnChildren[0]) );
            h->lntnChildCount--;
            }

          top--;
          }
      }

    /*  6  */
    if  ( this->lntnChildCount == 0 )
      {
      docCleanListNumberTreeNode( this );

      node->lntnChildCount--;
      for ( i= pos; i < node->lntnChildCount; i++ )
          { node->lntnChildren[i]= node->lntnChildren[i+ 1]; }

      /*  7  */
      while( level > 0 && node->lntnChildCount == 0 )
          {
          level--;

          node= path[level];
          pos= nums[level];
          this= &(node->lntnChildren[pos]);

          if  ( this->lntnChildCount != 0 )
            { LDEB(this->lntnChildCount); }

          if  ( this->lntnParagraphNumber < 0   )
            {
            docCleanListNumberTreeNode( this );

            node->lntnChildCount--;
            for ( i= pos; i < node->lntnChildCount; i++ )
                { node->lntnChildren[i]= node->lntnChildren[i+ 1]; }
            }
          }
      }

    /* SLDEB("DELETED",paraNr);docLogListNumberTreeNode(0,root); */
    return 0;
    }

/************************************************************************/
/*                                                    */
/*  Adapt references from bullets to the text because the number of     */
/*  paragraphs changed in the document.                           */
/*                                                    */
/*  1)  Loop: To use less recursion.. handle the last child of a node   */
/*    in a loop.                                      */
/*  2)  Handle the other children in a recursive call.                  */
/*  3)  Skip children before the first paragraph.                 */
/*                                                    */
/************************************************************************/

void docShiftBulletReferences(            ListNumberTreeNode *    root,
                              int               paraFrom,
                              int               paraShift )
    {
    ListNumberTreeNode *      node= root;

    /*  1  */
    for (;;)
      {
      int         pos;

      if  ( node->lntnParagraphNumber >= paraFrom )
          { node->lntnParagraphNumber += paraShift;   }

      if  ( node->lntnChildCount == 0 )
          { break;      }

      /*  2  */
      for ( pos= 0; pos < node->lntnChildCount- 1; pos++ )
          {
          /*  3  */
          if  ( node->lntnChildren[pos+ 1].lntnParagraphNumber <= paraFrom )
            { continue; }

          docShiftBulletReferences( &(node->lntnChildren[pos]),
                                          paraFrom, paraShift );
          }

      node= &(node->lntnChildren[node->lntnChildCount- 1]);
      }

    return;
    }


Generated by  Doxygen 1.6.0   Back to index