Main Page

Source Files

Class Hierarchy

Alphabetical List

Compound List

Compound Members

File Members

Related Pages

Search for

---

libsrc/ndcuts.cxx

Go to the documentation of this file.

/**********************************************************************
 * Copyright 2002 Jeff Rush <jrush@taupro.com>
 * Original Copyright 1979-2002 Udanax.com
 *
 * This file is part of the Udanax xanalogical storage system.
 *
 * Udanax 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 2 of the License, or
 * (at your option) any later version.
 *
 * Udanax 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 Udanax; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 **********************************************************************/

/* Modification History:
 * $Log: ndcuts.cxx,v $
 * Revision 1.12  2004/09/11 13:59:21  jrush
 * Changed all fprintf's to stderr to use the Nana library L() macro.  Also
 * removed a 2-3 minor compiler warnings.
 *
 * Revision 1.11  2004/09/04 16:02:17  jrush
 * Added Doxygen headers before each and every function definition.
 *
 * Revision 1.10  2002/07/26 04:32:01  jrush
 * Replaced gerror() with assert()
 *
 * Revision 1.9  2002/05/28 04:22:29  jrush
 * Adjusted source files to comply with GPL licensing.
 *
 * Revision 1.8  2002/05/28 02:51:11  jrush
 * Made static any functions and global variables private to this source file
 * and commented out any unused functions.
 *
 * Revision 1.7  2002/04/12 11:56:43  jrush
 * Reorganized include file layout, renamed xanadu.h to udanax.h and
 * typecontext/typecrumcontext to C++ class Context/CrumContext.
 *
 * Revision 1.6  2002/04/09 21:45:46  jrush
 * Renamed class 'tumbler' to 'Tumbler', for consistency with Python sources,
 * and changed typeisa from typedef to a subclass, in preparation for cleaning
 * up the type/class tree.
 *
 * Revision 1.5  2002/04/08 18:55:55  jrush
 * Switched from using global variable 'user' to object 'Session' as a
 * connection for tracking open document descriptors in the bert table.
 *
 * Revision 1.4  2002/04/06 19:51:30  jrush
 * Renamed TRUE/FALSE constant use to the C++ standard of true/false.
 *
 * Revision 1.3  2002/04/06 15:01:17  jrush
 * Changed INT to just 'int'.
 *
 * Revision 1.2  2002/02/14 09:27:43  jrush
 * Cleaned up source:
 *
 * 1. ran thru the indent tool to achieve a standard look,
 * 2. added structured comments at top for use with DOxygen reporting
 *    as well as CVS keywords,
 * 3. fixed compiler warnings re ambiguous assign/compares,
 *    needed casts and unused/uninitialized variables,
 * 4. fixed funcs that didn't specify a return type,
 * 5. centralized prototypes in protos.h, removing incomplete ones,
 * 6. cleaned up use of bool/BOOLEAN type to suit C++ type,
 * 7. fixed initializer nesting in tumbler constants,
 * 8. renamed vars that conflict with C++ keywords (new, this),
 * 9. fixed global/extern confusion re some global vars.
 *
 */

#include <memory.h>
#include "udanax.h"

static void makecutsbackuptohere(typecuc *ptr, typewid *offset, typeknives *knives);

    static bool
crumiscut(
    typecuc    *ptr,
    typewid    *offset,
    typeknives *knives)
{
    int i;
    for (i = 0; i < knives->nblades; ++i) {
        if (whereoncrum((typecorecrum *) ptr, offset, &knives->blades[i], knives->dimension) == THRUME)
            return true;
    }
    return false;
}

    static bool
sonsarecut(
    typecuc    *ptr,
    typewid    *offset,
    typeknives *knives)
{
    typecuc *son;
    typewid grasp;

    prologuend((typecorecrum *) ptr, offset, &grasp, (typedsp *) NULL);
    for (son = (typecuc *) findleftson(ptr); son; son = (typecuc *) findrightbro((typecorecrum *) son)) {
        if (crumiscut(son, &grasp, knives))
            return true;
    }

    return false;
}

    static void
makecutsdownnd(
    typecuc    *fullcrumptr,
    typewid    *offset,
    typeknives *knives)
{
    typecuc *ptr;
    typecorecrum *sonptr, *son;
    int n;

    ptr = fullcrumptr;
    for (; (knives->nblades > 1) && false && ptr->height;) {
        for (n = 0, son = findleftson(ptr); son; son = findrightbro(son)) {
            if (crumiscut((typecuc *) son, offset, knives)) {
                n++;
                sonptr = son;
            }
        }

        if (n == 1) {
            prologuend((typecorecrum *) ptr, offset, offset, (typedsp *) NULL);
            ptr = (typecuc *) sonptr;
        } else
            break;
    }                                  /* now we're at intersection */

    makecutsbackuptohere(ptr, offset, knives);
    if (toomanysons(ptr)) {
        /* L("found toomany sons in makecutsdownnd\n"); */
        if (isfullcrum((typecorecrum *) ptr)) {
            /* L("and was fullcrum\n"); */
            /* return; */

            levelpush(ptr);
            makecutsnd(fullcrumptr, knives);
            /* L("returningfrom makecutsnd\n"); */
        } else
            makecutsnd(fullcrumptr, knives);
    }
}

    static void
cutsons(
    typecuc    *ptr,
    typewid    *offset,
    typeknives *knives)
{
    typewid grasp;
    typecorecrum *son, *nextson;

    while (sonsarecut(ptr, offset, knives)) {
          setwispupwards(ptr, 1);
          for (son = findleftson(ptr); son; son = nextson) {
            nextson = findrightbro(son);
            prologuend((typecorecrum *) ptr, offset, &grasp, (typedsp *) NULL);
            for (; crumiscut((typecuc *) son, &grasp, knives);
                 prologuend((typecorecrum *) ptr, offset, &grasp, (typedsp *) NULL)) {
                makecutsbackuptohere((typecuc *) son, &grasp, knives);
            }
        }
    }
}

    static bool
crumleftofithcut(
    typecorecrum *ptr,
    typewid      *offset,
    typeknives   *knives,
    int           i)
{
    if (whereoncrum(ptr, offset, &knives->blades[i], knives->dimension) > THRUME)
        return false;
    else
        return true;
}

    static void
newpeelcrumoffnd(
    typecorecrum *ptr,
    typecorecrum *newuncle)
{
    typedsp temp;
    typecuc *father;
    typedsp grasp;
    typewid origin;
    typedsp offset;

    if (!roomformoresons((typecuc *) newuncle))
        assert(0); // noroomfor more  sons for newuncle

    if (isfullcrum(ptr))
        assert(0); // peeloffcurmnd called with fullcrum

    ivemodified(ptr);                  /* to set father->modified */
    father = findfather(ptr);
    clear(&offset, sizeof(offset));
    dspadd(&father->cdsp, &ptr->cdsp, &origin, (int) father->cenftype);
/* 1 ptr->cdsp */
/* 
 * L("in newpeelcrumoffnd 1 \n"); dumpwid(&father->cdsp);
 * dumpwid(&ptr->cdsp); dumpwid(&origin); */
    (void)tumblercheckptr((Tumbler *) & origin, (int *) ptr);

    makeroomonleftnd((typecuc *) newuncle, &offset, &origin, &grasp);
    disown(ptr);
    adopt(ptr, LEFTMOSTSON, newuncle);
/* dspsub(&father->cdsp,&newuncle->cdsp,&temp,ptr->cenftype); */
/* 2 &temp <- father->cdsp - newuncle->cdsp check this father temp stuff4/6/85 */
    dspadd(&father->cdsp, &ptr->cdsp, &temp, (int) ptr->cenftype);
/* 
 * dumpwid(&newuncle->cdsp); L("in newpeelcrumoffnd 2 \n");
 * dumpwid(&temp); */
    (void)tumblercheckptr((Tumbler *) & temp, (int *) ptr);

/* dspadd(&ptr->cdsp,&temp,&ptr->cdsp, ptr->cenftype); */
    dspsub(&temp, &newuncle->cdsp, &ptr->cdsp, (int) ptr->cenftype);
/* 3 ptr->cdsp <- temp + ptr->cdsp */
/* 
 * L("in newpeelcrumoffnd 3 \n"); dumpwid(&ptr->cdsp);
 * dump(ptr); */
    (void)tumblercheckptr((Tumbler *) & ptr->cdsp, (int *) ptr);

    ivemodified(ptr);
    ivemodified(newuncle);
/* setwispsofsons(newuncle);// to fix makeroomonleftnd// */
    setwispupwards((typecuc *) ptr, 0);
    setwispupwards((typecuc *) newuncle, 0);
    setwispupwards(father, 1);

    if (toomanysons((typecuc *) newuncle))
        assert(0); // toomany sons for newuncle

    /* L("calling fixincoresubtreewids\n"); */
    /* fixincoresubtreewids(findfullcrum(ptr)); */
}

    static void
peelsoncorrectly(
    typecorecrum *ptr,
    typewid      *offset,
    typecorecrum *son,
    typewid      *grasp,
    typeknives   *knives,
    int           i)
{                                      /* put son in leftest uncle with room that is less than cut */
    typecuc *uncle;

    uncle = (typecuc *) findleftmostbro(ptr);
    for (; uncle; uncle = (typecuc *) findrightbro((typecorecrum *) uncle)) {
        if (uncle == (typecuc *) ptr) {
            continue;
        }
        if (roomformoresons(uncle)) {
            if (crumleftofithcut((typecorecrum *) uncle, offset, knives, i)) {
                newpeelcrumoffnd((typecorecrum *) son, (typecorecrum *) uncle);
                return;
            }
        }
    }
    uncle = (typecuc *) createcrum((int) ptr->height, (int) ptr->cenftype);
    adopt((typecorecrum *) uncle, RIGHTBRO, findrightmostbro(ptr));
    movewisp(&ptr->cdsp, &uncle->cdsp);
    newpeelcrumoffnd((typecorecrum *) son, (typecorecrum *) uncle);
}

    static bool
crumiscutbyithknife(
    typecuc    *ptr,
    typewid    *offset,
    typeknives *knives,
    int         i)
{
    if (whereoncrum((typecorecrum *) ptr, offset, &knives->blades[i], knives->dimension) == THRUME)
        return true;

    return false;
}

    static void
makeithcutonson(
    typecorecrum *ptr,
    typewid      *offset,
    typecorecrum *son,
    typewid      *grasp,
    typeknives   *knives,
    int           i)
{
    int temp;

    if (!crumiscutbyithknife((typecuc *) ptr, offset, knives, i)) {
#ifndef DISTRIBUTION
        L("foo return in makeithcutonson\n");
#endif
        return;
    }
    if ((temp = whereoncrum(son, grasp, &knives->blades[i], knives->dimension)) < THRUME) {
        peelsoncorrectly(ptr, offset, son, grasp, knives, i);
          setwispupwards((typecuc *) ptr, 1);
          if (!crumiscutbyithknife((typecuc *) ptr, offset, knives, i)) {
              setwispupwards((typecuc *) ptr, 1);
             
/* prologuend(ptr,offset,grasp,NULL); */
                    if (((typecuc *) ptr)->numberofsons == 0) {
#ifndef DISTRIBUTION
                displaycutspm(knives);
                dumpwid(offset, ptr->cenftype);
                L("sons went away\n");
/* dump(ptr); *//*dumpwholetree(ptr); */
                check((typecuc *) ptr);
#endif
                return;
            }
            return;
        }
        (void)findleftson((typecuc *) ptr);     /* make sure its in core */
        if (((typecuc *) ptr)->numberofsons == 0) {
#ifndef DISTRIBUTION
            displaycutspm(knives);
            dumpwid(offset, ptr->cenftype);
            L("____sons went away\n");
            dump(ptr);
            check((typecuc *) ptr);
            assert(0); // sons went away
#else
            assert(0);
#endif
        }
    } else if (temp == THRUME)
        assert(0); // makecutsbackuptohere crum not cut
}

    static bool
peeloffcorrectson(
    typecorecrum *ptr,
    typeknives   *knives)
{
    typecorecrum *bro, *uncle;

    if (toomanysons((typecuc *) ptr)) {
        for (bro = findrightbro(ptr); bro; ptr = findrightbro(ptr)) {
            if (roomformoresons /* !toomanysons */ ((typecuc *) bro)) {
                newpeelcrumoffnd(findleftson((typecuc *) ptr), bro);
                return true;
            }
        }
        uncle = createcrum((int) ptr->height, (int) ptr->cenftype);
        adopt(uncle, RIGHTBRO, ptr);
        movewisp(&ptr->cdsp, &uncle->cdsp);
        newpeelcrumoffnd(findleftson((typecuc *) ptr), uncle);
    }
    return true;
}

    static void
slicecbcpm(
    typecorecrum *ptr,
    typewid      *offset,
    typecorecrum *newcc,
    Tumbler      *cut,
    int           index)
{
    typedsp grasp /* , reach */ ;
    Tumbler localcut;
    typewid newwid;
    int i;

/* L("entering slicecbcpm \n"); */
    int enftype = ptr->cenftype;

    prologuend(ptr, offset, &grasp, /* &reach */ (typedsp *) NULL);
    if (whereoncrum(ptr, offset, cut, index) != THRUME)
        assert(0); // Why are you trying to slice me?

    if (!lockis1story(ptr->cwid.dsas, (unsigned)widsize(enftype)))
        assert(0); // Not one story in POOM wid

    tumblersub(cut, &grasp.dsas[index], &localcut);

    if (localcut.exp != ptr->cwid.dsas[index].exp) {
#ifndef DISTRIBUTION
        dump(ptr);
        dump(newcc);
        dumptumbler(cut);
        dumptumbler(&localcut);
        dumpwholetree(ptr);
        assert(0); // Oh well, I thought I understood this1
#else
        assert(0);
#endif
    }
    if (!is1story(&localcut)) {
#ifndef DISTRIBUTION
        L("\nin slicecbcpm  ptr \n");
        dump(ptr);
        L("\nin slicecbcpm newcc  \n");
        dump(newcc);
        L("\nin slicecbcpm  offset \n");
        dumpwid(offset, ptr->cenftype);
        L("\nin slicecbcpm  grasp \n");
        dumpwid(&grasp, ptr->cenftype);
        L("\nin slicecbcpm  cut \n");
        dumptumbler(cut);
        L("\nin slicecbcpm  localcut \n");
        dumptumbler(&localcut);
        L("\nin slicecbcpm wholedamn tree  \n");
        dumpwholetree(ptr);
        assert(0); // Oh well, I thought I understood this2
#else
        assert(0);
#endif
    }

    if (tumblerlength(cut) != tumblerlength(&ptr->cwid.dsas[index]))
        assert(0); // level mismatch

    movewisp(&ptr->cwid, &newwid);
    for (i = 0; i < widsize(enftype); i++) {    /* I really don't understand this loop */
        newwid.dsas[i].mantissa[0] = localcut.mantissa[0];
        tumblerjustify(&newwid.dsas[i]);
    }

/* locksubtract (&ptr->cwid, &newwid, &newcc->cwid, widsize (enftype)); */
    locksubtract((Tumbler *) & ptr->cwid, (Tumbler *) & newwid, (Tumbler *) & newcc->cwid, (unsigned)widsize(enftype));

    movewisp(&newwid, &ptr->cwid);
    dspadd(&ptr->cdsp, &ptr->cwid, &newcc->cdsp, enftype);
    move2dinfo(&((type2dcbc *) ptr)->c2dinfo, &((type2dcbc *) newcc)->c2dinfo);
    adopt(newcc, RIGHTBRO, ptr);
/* L("leaving slicecpcpm \n"); */
}

    void
makecutsnd(
    typecuc    *fullcrumptr,
    typeknives *knives)
{
    typewid offset;

    //FIX: needs access to Session from higher-level code     logbertmodifiedforcrum(sess, fullcrumptr);
/* (L("\nmakecutsnd knives = \n"); displaycutspm(knives); */
    clear(&offset, sizeof(offset));
    makecutsdownnd(fullcrumptr, &offset, knives);
    clear(&offset, sizeof(offset));    /* clears ARE redundant */
    for (fullcrumptr = findfullcrum((typecorecrum *) fullcrumptr); sonsarecut(fullcrumptr, &offset, knives);
         fullcrumptr = findfullcrum((typecorecrum *) fullcrumptr)) {
        clear(&offset, sizeof(offset));
        makecutsdownnd(fullcrumptr, &offset, knives);
    }
#ifndef DISTRIBUTION
    asserttreeisok((typecorecrum *) fullcrumptr);
#endif
}

    static void
makecutsbackuptohere(
    typecuc    *ptr,
    typewid    *offset,
    typeknives *knives)
{
    typewid grasp;
    int i;
    typecuc *son, *newcc, *nextson;

    if (ptr->height == 0) {
        for (i = 0; i < knives->nblades; i++) {
            if (whereoncrum((typecorecrum *) ptr, offset, &knives->blades[i], knives->dimension) == THRUME) {
                newcc = (typecuc *) createcrum((int) ptr->height, (int) ptr->cenftype);
                if (ptr->cenftype == GRAN) {
                    ((typecbc *) newcc)->cinfo.infotype = ((typecbc *) ptr)->cinfo.infotype;
                }
                slicecbcpm((typecorecrum *) ptr, offset, (typecorecrum *) newcc, &knives->blades[i], knives->dimension);
                ivemodified((typecorecrum *) ptr);
                ivemodified((typecorecrum *) newcc);
                  setwisp((typecorecrum *) ptr);
                 
/* asserttreeisok(ptr); */
            }
        }
        return;
    } else {
        for (i = 0; i < knives->nblades; ++i) {
            cutsons(ptr, offset, knives);

            if (!isfullcrum((typecorecrum *) ptr)) {
                  setwispupwards(ptr, 0);
                  if (crumiscutbyithknife(ptr, offset, knives, i)) {
                    for (son = (typecuc *) findleftson(ptr); son; son = nextson) {
                        nextson = (typecuc *) findrightbro((typecorecrum *)
                                                           son);
                        prologuend((typecorecrum *) ptr, offset, &grasp, (typedsp *) NULL);

                        makeithcutonson((typecorecrum *) ptr, offset, (typecorecrum *) son, &grasp, knives, i);
                        if (!crumiscutbyithknife(ptr, offset, knives, i)) {
                            if (ptr->numberofsons == 0) {
                                return;
                            }
                            break;
                        }
                    }
                }
                 setwispupwards(ptr, 0);
             }
/* asserttreeisok(ptr); */
        }
    }
    if (!isfullcrum((typecorecrum *) ptr)) {
        if (toomanysons(ptr)) {
            while (toomanysons(ptr)) {
#ifndef DISTRIBUTION
                L("setwispupwards 4\n" /*BUG: too many args, 1*/);
#endif
                  setwispupwards(ptr, 0);
                 
#ifndef DISTRIBUTION
                        L("toomanysons peel\n");
#endif
                peeloffcorrectson((typecorecrum *) ptr, knives);
            }
#ifndef DISTRIBUTION
            L("calling makecutsbackuptohere\n");
#endif
            makecutsbackuptohere(ptr, offset, knives);
        }
    } else if (toomanysons(ptr)) {
#ifndef DISTRIBUTION
        L("________________toomanysons in fullcrum\n");
#endif
    }
     setwispupwards(ptr, 1);
 
}

---