src/ptra.c
l_int32
ptraInsert(L_PTRA  *pa,
           l_int32  index,
           void    *item,
           l_int32  shiftflag)
{
l_int32    i, ihole, imax;
l_float32  nexpected;

    PROCNAME("ptraInsert");

    if (!pa)
        return ERROR_INT("pa not defined", procName, 1);
    if (index < 0 || index > pa->nalloc)
        return ERROR_INT("index not in [0 ... nalloc]", procName, 1);
    if (shiftflag != L_AUTO_DOWNSHIFT && shiftflag != L_MIN_DOWNSHIFT &&
        shiftflag != L_FULL_DOWNSHIFT)
        return ERROR_INT("invalid shiftflag", procName, 1);

    if (item) pa->nactual++;
    if (index == pa->nalloc) {  /* can happen when index == n */
        if (ptraExtendArray(pa))
            return ERROR_INT("extension failure", procName, 1);
    }

        /* We are inserting into a hole or adding to the end of the array.
         * No existing items are moved. */
    ptraGetMaxIndex(pa, &imax);
    if (pa->array[index] == NULL) {
        pa->array[index] = item;
        if (item && index > imax)  /* new item put beyond max so far */
            pa->imax = index;
        return 0;
    }

        /* We are inserting at the location of an existing item,
         * forcing the existing item and those below to shift down.
         * First, extend the array automatically if the last element
         * (nalloc - 1) is occupied (imax).  This may not be necessary
         * in every situation, but only an anomalous sequence of insertions
         * into the array would cause extra ptr allocation.  */
    if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
        return ERROR_INT("extension failure", procName, 1);

        /* If there are no holes, do a full downshift.
         * Otherwise, if L_AUTO_DOWNSHIFT, use the expected number
         * of holes between index and n to determine the shift mode */
    if (imax + 1 == pa->nactual)
        shiftflag = L_FULL_DOWNSHIFT;
    else if (shiftflag == L_AUTO_DOWNSHIFT) {
        if (imax < 10)
            shiftflag = L_FULL_DOWNSHIFT;  /* no big deal */
        else {
            nexpected = (l_float32)(imax - pa->nactual) *
                         (l_float32)((imax - index) / imax);
            shiftflag = (nexpected > 2.0) ? L_MIN_DOWNSHIFT : L_FULL_DOWNSHIFT;
        }
    }

    if (shiftflag == L_MIN_DOWNSHIFT) {  /* run down looking for a hole */
        for (ihole = index + 1; ihole <= imax; ihole++) {
             if (pa->array[ihole] == NULL)
                 break;
        }
    }
    else   /* L_FULL_DOWNSHIFT */
        ihole = imax + 1;

    for (i = ihole; i > index; i--)
        pa->array[i] = pa->array[i - 1];
    pa->array[index] = (void *)item;
    if (ihole == imax + 1)  /* the last item was shifted down */
        pa->imax++;

    return 0;
}
/*!
 *  ptraInsert()
 *
 *      Input:  ptra 
 *              index (location in ptra to insert new value)
 *              item  (generic ptr to a struct; can be null)
 *              shiftflag (L_AUTO_DOWNSHIFT, L_MIN_DOWNSHIFT, L_FULL_DOWNSHIFT)
 *      Return: 0 if OK, 1 on error
 *
 *  Notes:
 *      (1) This checks first to see if the location is valid, and
 *          then if there is presently an item there.  If there is not,
 *          it is simply inserted into that location.
 *      (2) If there is an item at the insert location, items must be
 *          moved down to make room for the insert.  In the downward
 *          shift there are three options, given by @shiftflag.
 *            - If @shiftflag == L_AUTO_DOWNSHIFT, a decision is made
 *              whether, in a cascade of items, to downshift a minimum
 *              amount or for all items above @index.  The decision is
 *              based on the expectation of finding holes (null ptrs)
 *              between @index and the bottom of the array.
 *              Assuming the holes are distributed uniformly, if 2 or more
 *              holes are expected, we do a minimum shift.
 *            - If @shiftflag == L_MIN_DOWNSHIFT, the downward shifting
 *              cascade of items progresses a minimum amount, until
 *              the first empty slot is reached.  This mode requires
 *              some computation before the actual shifting is done.
 *            - If @shiftflag == L_FULL_DOWNSHIFT, a shifting cascade is
 *              performed where pa[i] --> pa[i + 1] for all i >= index.
 *              Then, the item is inserted at pa[index].
 *      (3) If you are not using L_AUTO_DOWNSHIFT, the rule of thumb is
 *          to use L_FULL_DOWNSHIFT if the array is compacted (each
 *          element points to an item), and to use L_MIN_DOWNSHIFT
 *          if there are a significant number of null pointers.
 *          There is no penalty to using L_MIN_DOWNSHIFT for a
 *          compacted array, however, because the full shift is required
 *          and we don't do the O(n) computation to look for holes.
 *      (4) This should not be used repeatedly on large arrays,
 *          because the function is generally O(n).
 *      (5) However, it can be used repeatedly if we start with an empty
 *          ptr array and insert only once at each location.  For example,
 *          you can support an array of Numa, where at each ptr location
 *          you store either 0 or 1 Numa, and the Numa can be added
 *          randomly to the ptr array.
 */
ptraInsert()
Input:  ptra
index (location in ptra to insert new value)
item  (generic ptr to a struct; can be null)
shiftflag (L_AUTO_DOWNSHIFT, L_MIN_DOWNSHIFT, L_FULL_DOWNSHIFT)
Return: 0 if OK, 1 on error

(1) This checks first to see if the location is valid, and
then if there is presently an item there.  If there is not,
it is simply inserted into that location.
(2) If there is an item at the insert location, items must be
moved down to make room for the insert.  In the downward
shift there are three options, given by @shiftflag.
- If @shiftflag == L_AUTO_DOWNSHIFT, a decision is made
whether, in a cascade of items, to downshift a minimum
amount or for all items above @index.  The decision is
based on the expectation of finding holes (null ptrs)
between @index and the bottom of the array.
Assuming the holes are distributed uniformly, if 2 or more
holes are expected, we do a minimum shift.
- If @shiftflag == L_MIN_DOWNSHIFT, the downward shifting
cascade of items progresses a minimum amount, until
the first empty slot is reached.  This mode requires
some computation before the actual shifting is done.
- If @shiftflag == L_FULL_DOWNSHIFT, a shifting cascade is
performed where pa[i] --> pa[i + 1] for all i >= index.
Then, the item is inserted at pa[index].
(3) If you are not using L_AUTO_DOWNSHIFT, the rule of thumb is
to use L_FULL_DOWNSHIFT if the array is compacted (each
element points to an item), and to use L_MIN_DOWNSHIFT
if there are a significant number of null pointers.
There is no penalty to using L_MIN_DOWNSHIFT for a
compacted array, however, because the full shift is required
and we don't do the O(n) computation to look for holes.
(4) This should not be used repeatedly on large arrays,
because the function is generally O(n).
(5) However, it can be used repeatedly if we start with an empty
ptr array and insert only once at each location.  For example,
you can support an array of Numa, where at each ptr location
you store either 0 or 1 Numa, and the Numa can be added
randomly to the ptr array.
ptraInsert () Input : ptra index ( location in ptra to insert new value ) item ( generic ptr to a struct ; can be null ) shiftflag ( L_AUTO_DOWNSHIFT L_MIN_DOWNSHIFT L_FULL_DOWNSHIFT ) Return : 0 if OK 1 on error ( 1 ) This checks first to see if the location is valid and then if there is presently an item there . If there is not it is simply inserted into that location . ( 2 ) If there is an item at the insert location items must be moved down to make room for the insert . In the downward shift there are three options given by @shiftflag . - If @shiftflag == L_AUTO_DOWNSHIFT a decision is made whether in a cascade of items to downshift a minimum amount or for all items above @index . The decision is based on the expectation of finding holes ( null ptrs ) between @index and the bottom of the array . Assuming the holes are distributed uniformly if 2 or more holes are expected we do a minimum shift . - If @shiftflag == L_MIN_DOWNSHIFT the downward shifting cascade of items progresses a minimum amount until the first empty slot is reached . This mode requires some computation before the actual shifting is done . - If @shiftflag == L_FULL_DOWNSHIFT a shifting cascade is performed where pa [ i ] -- > pa [ i + 1 ] for all i > = index . Then the item is inserted at pa [ index ] . ( 3 ) If you are not using L_AUTO_DOWNSHIFT the rule of thumb is to use L_FULL_DOWNSHIFT if the array is compacted ( each element points to an item ) and to use L_MIN_DOWNSHIFT if there are a significant number of null pointers . There is no penalty to using L_MIN_DOWNSHIFT for a compacted array however because the full shift is required and we don ' t do the O ( n ) computation to look for holes . ( 4 ) This should not be used repeatedly on large arrays because the function is generally O ( n ) . ( 5 ) However it can be used repeatedly if we start with an empty ptr array and insert only once at each location . For example you can support an array of Numa where at each ptr location you store either 0 or 1 Numa and the Numa can be added randomly to the ptr array .
l_int32
ptraInsert(L_PTRA  *pa,
           l_int32  index,
           void    *item,
           l_int32  shiftflag)
{
l_int32    i, ihole, imax;
l_float32  nexpected;
    PROCNAME("ptraInsert");
    if (!pa)
        return ERROR_INT("pa not defined", procName, 1);
    if (index < 0 || index > pa->nalloc)
        return ERROR_INT("index not in [0 ... nalloc]", procName, 1);
    if (shiftflag != L_AUTO_DOWNSHIFT && shiftflag != L_MIN_DOWNSHIFT &&
        shiftflag != L_FULL_DOWNSHIFT)
        return ERROR_INT("invalid shiftflag", procName, 1);
    if (item) pa->nactual++;
    if (index == pa->nalloc) {  
        if (ptraExtendArray(pa))
            return ERROR_INT("extension failure", procName, 1);
    }
    ptraGetMaxIndex(pa, &imax);
    if (pa->array[index] == NULL) {
        pa->array[index] = item;
        if (item && index > imax)  
            pa->imax = index;
        return 0;
    }
    if (imax >= pa->nalloc - 1 && ptraExtendArray(pa))
        return ERROR_INT("extension failure", procName, 1);
    if (imax + 1 == pa->nactual)
        shiftflag = L_FULL_DOWNSHIFT;
    else if (shiftflag == L_AUTO_DOWNSHIFT) {
        if (imax < 10)
            shiftflag = L_FULL_DOWNSHIFT;  
        else {
            nexpected = (l_float32)(imax - pa->nactual) *
                         (l_float32)((imax - index) / imax);
            shiftflag = (nexpected > 2.0) ? L_MIN_DOWNSHIFT : L_FULL_DOWNSHIFT;
        }
    }
    if (shiftflag == L_MIN_DOWNSHIFT) {  
        for (ihole = index + 1; ihole <= imax; ihole++) {
             if (pa->array[ihole] == NULL)
                 break;
        }
    }
    else   
        ihole = imax + 1;
    for (i = ihole; i > index; i--)
        pa->array[i] = pa->array[i - 1];
    pa->array[index] = (void *)item;
    if (ihole == imax + 1)  
        pa->imax++;
    return 0;
}
l_int32 ptraInsert ( L_PTRA * pa , l_int32 index , void * item , l_int32 shiftflag ) { l_int32 i , ihole , imax ; l_float32 nexpected ; PROCNAME ( " " ) ; if ( ! pa ) return ERROR_INT ( " " , procName , 1 ) ; if ( index < 0 || index > pa -> nalloc ) return ERROR_INT ( " " , procName , 1 ) ; if ( shiftflag != L_AUTO_DOWNSHIFT && shiftflag != L_MIN_DOWNSHIFT && shiftflag != L_FULL_DOWNSHIFT ) return ERROR_INT ( " " , procName , 1 ) ; if ( item ) pa -> nactual ++ ; if ( index == pa -> nalloc ) { if ( ptraExtendArray ( pa ) ) return ERROR_INT ( " " , procName , 1 ) ; } ptraGetMaxIndex ( pa , & imax ) ; if ( pa -> array [ index ] == NULL ) { pa -> array [ index ] = item ; if ( item && index > imax ) pa -> imax = index ; return 0 ; } if ( imax >= pa -> nalloc - 1 && ptraExtendArray ( pa ) ) return ERROR_INT ( " " , procName , 1 ) ; if ( imax + 1 == pa -> nactual ) shiftflag = L_FULL_DOWNSHIFT ; else if ( shiftflag == L_AUTO_DOWNSHIFT ) { if ( imax < 10 ) shiftflag = L_FULL_DOWNSHIFT ; else { nexpected = ( l_float32 ) ( imax - pa -> nactual ) * ( l_float32 ) ( ( imax - index ) / imax ) ; shiftflag = ( nexpected > 2.0 ) ? L_MIN_DOWNSHIFT : L_FULL_DOWNSHIFT ; } } if ( shiftflag == L_MIN_DOWNSHIFT ) { for ( ihole = index + 1 ; ihole <= imax ; ihole ++ ) { if ( pa -> array [ ihole ] == NULL ) break ; } } else ihole = imax + 1 ; for ( i = ihole ; i > index ; i -- ) pa -> array [ i ] = pa -> array [ i - 1 ] ; pa -> array [ index ] = ( void * ) item ; if ( ihole == imax + 1 ) pa -> imax ++ ; return 0 ; }
ptraInsert()
      Input:  ptra
              index (location in ptra to insert new value)
              item  (generic ptr to a struct; can be null)
              shiftflag (L_AUTO_DOWNSHIFT, L_MIN_DOWNSHIFT, L_FULL_DOWNSHIFT)
      Return: 0 if OK, 1 on error
ptraInsert () Input : ptra index ( location in ptra to insert new value ) item ( generic ptr to a struct ; can be null ) shiftflag ( L_AUTO_DOWNSHIFT L_MIN_DOWNSHIFT L_FULL_DOWNSHIFT ) Return : 0 if OK 1 on error
/* can happen when index == n */ /* We are inserting into a hole or adding to the end of the array.
         * No existing items are moved. */ /* new item put beyond max so far */ /* We are inserting at the location of an existing item,
         * forcing the existing item and those below to shift down.
         * First, extend the array automatically if the last element
         * (nalloc - 1) is occupied (imax).  This may not be necessary
         * in every situation, but only an anomalous sequence of insertions
         * into the array would cause extra ptr allocation.  */ /* If there are no holes, do a full downshift.
         * Otherwise, if L_AUTO_DOWNSHIFT, use the expected number
         * of holes between index and n to determine the shift mode */ /* no big deal */ /* run down looking for a hole */ /* L_FULL_DOWNSHIFT */ /* the last item was shifted down */