<![CDATA[//datei-name: baum2.C
#include "baum.h"
void Baum::knotDisplay(int i)
{ cout << i << endl; }
void Baum::baumLoc(int k)
// musterrekursion
{ s[k].lc = loc;
if (s[k].t1 == 's') baumLoc(s[k].sl);
if (s[k].t2 == 's') baumLoc(s[k].sr); }
int Baum::vLSatz(int i)
// setzt rSatz
{ int rzi; rzi = w[i].b;
while (rzi)
{ rSatz = r[rzi].zS;
if (s[rSatz].v == '"' && s[rSatz].sl == i && s[rSatz].lc == loc) return rSatz;
rzi = r[rzi].zz; }
rzi = w[i].b;
while (rzi)
{ rSatz = r[rzi].zS;
if (s[rSatz].v == '"' && s[rSatz].sl == i) return rSatz;
rzi = r[rzi].zz; }
return 0; }
char Baum::vLSatz0(int i)
// sucht labelWurzel
{ int rzi; rzi = w[i].b;
while (rzi)
{ rSatz = r[rzi].zS;
if (s[rSatz].v == '"' && s[rSatz].sl == i && s[rSatz].lc == loc)
{ if (! s[rSatz].b) return 0; }
rzi = r[rzi].zz; }
return 1; }
int Baum::vSatz(int i, char t, char v)
// setzt rSatz
{ int rzi;
if (t == 'w') rzi = w[i].b;
else rzi = s[i].b;
while (rzi)
{ rSatz = r[rzi].zS;
if (s[rSatz].v == v) return rSatz;
rzi = r[rzi].zz; }
return 0; }
void Baum::getRSatz(int i)
// setzt rSatz
{ int rzi;
vSatzN(i);
rzi = w[i].b; rrSatz = r[rzi].zS;
while (rzi)
{ rSatz = r[rzi].zS;
if (s[rSatz].v == '"' && s[rSatz].sl == i && s[rSatz].lc == loc)
{ first(rzi); return; }
rzi = r[rzi].zz; }
rSatz = rrSatz; }
void Baum::vSatzN(int i)
{ int rzi, rzr, pre, per, prep;
rzi = w[i].b;
while (rzi)
{ querz = 0;
rSatz = r[rzi].zS; rzr = s[rSatz].b;
while (rzr)
{ ++querz; rzr = r[rzr].zz; }
s[rSatz].s = querz;
rzi = r[rzi].zz; }
rzi = rzr = pre = prep = w[i].b;
while (rzr)
{ per = rzi;
rrSatz = r[rzr].zS; sum = s[rrSatz].s;
while (per != rzr)
{ rSatz = r[per].zS; querz = s[rSatz].s;
if (querz < sum)
{ r[pre].zz = r[rzr].zz; r[rzr].zz = per;
if (per == rzi)
{ w[i].b = rzr; rzi = rzr; }
else r[prep].zz = rzr;
break; }
else
{ if (prep != per) prep = per;
per = r[per].zz; } }
pre = per; rzr = r[pre].zz; }
gW = i; }
void Baum::first(int rzi)
// setzt rSatz voraus. setzt rSatz eventuell neu.
{ int k, rz;
rz = w[first_].b;
loop:
if (rz)
{ k = r[rz].zS;
if (s[k].v == '"')
{ k = s[k].sr; flag = 0;
while (rzi)
{ baumi = r[rzi].zS; firstMember(k); //1
if (flag)
{ rSatz = baumi; return; }
rzi = r[rzi].zz; } }
else
{ rz = r[rz].zz; goto loop; } } }
//1 setzt baumi voraus. setzt flag
void Baum::firstMember(int k)
// setzt baumi und typ voraus. setzt flag
{ if (flag) return;
if (s[k].t1 == 's')
{ if (s[s[k].sl].v == '"')
{ if (s[k].sl == baumi)
{ flag = 1; return; } }
else firstMember(s[k].sl); }
if (s[k].t2 == 's')
{ if (s[s[k].sr].v == '"')
{ if (s[k].sr == baumi)
{ flag = 1; return; } }
else firstMember(s[k].sr); } }
int* Baum::getRzp(int i, char t)
{ if (t == 's') return &(s[i].b);
else if (t == 'w') return &(w[i].b);
else return 0; }
void Baum::rzLabCheck()
// setzt rFlag
{ int k, rzi; rFlag = 0;
if (rTyp == 's' && s[root].v == '"' && s[root].t2 == 's')
{ k = s[root].sl;
rzi = w[k].b; querz = 0;
while(rzi)
{ rSatz = r[rzi].zS;
if (s[rSatz].v == '"') querz++;
rzi = r[rzi].zz; }
if (querz > 1) rFlag = 1;
k = s[root].sr;
rzi = s[k].b; querz = 0;
while(rzi)
{ querz++; rzi = r[rzi].zz; }
if (querz > 1)
{ if (rFlag) rFlag = 3;
else rFlag = 2; } } }
void Baum::modify0(int i)
// setzt i : satz u. *rzp voraus
{ int rzl, vorg;
rzl = *rzp;
rSatz = r[rzl].zS;
if (rSatz == i) return;
do
{ vorg = rzl;
rzl = r[rzl].zz;
rSatz = r[rzl].zS;
if (! rSatz)
{ r[rzl].zz = *rzp; *rzp = 0; return; } } //1
while (rSatz != i);
r[vorg].zz = r[rzl].zz;
r[rzl].zz = *rzp;
*rzp = rzl; }
//1 sonderfall fr shadow
char Baum::modify(int i, char lr)
// setzt i : satz voraus
{ if (lr == 'l') rzp = getRzp(s[i].sl, s[i].t1);
else if (lr == 'r') rzp = getRzp(s[i].sr, s[i].t2);
else return 0;
if (rzp && *rzp)
{ modify0(i); return 1; }
return 0; }
void Baum::clrWurz(int i)
// setzt i : wurzel_satz
{ int rzi;
if (modify(i, 'l'))
{ rzi = *rzp;
*rzp = r[rzi].zz;
r[rzi] = r[ENDRL]; //1
if (rzi && rzl0 > rzi) rzl0 = rzi; } //2
if (modify(i, 'r'))
{ rzi = *rzp;
*rzp = r[rzi].zz;
r[rzi] = r[ENDRL]; //1
if (rzi && rzl0 > rzi) rzl0 = rzi; } //2
s[i] = s[ENDS]; //3
if (satz0 > i) satz0 = i; }
//1: leeres lr kopieren
//2: rzl0 : erstes freies r
//3: leeren satzblock kopieren
//-------------------------------------------------------------------------------------------
void Baum::neuRz(int i)
// setzt rzp voraus
{ int rzi; rzi = *rzp;
while(r[rzl0].zS) rzl0++; //1
*rzp = rzl0; //2
if (rMax < rzl0) rMax = rzl0;
r[rzl0].zS = i;
r[rzl0].zz = rzi; }
//1: rzl0 : n�hster freier Rckzeiger
//2: hier beginnt der tanz der rckzeiger
void Baum::umbau(int is, char rl, int um, char t)
// is: stamm um: neuer ast
{ int rzi; int i; char it;
if (rl == 'l')
{ i = s[is].sl; it = s[is].t1; }
else
{ i = s[is].sr; it = s[is].t2; }
if (it == 's' && i == um)
{ cout << "umbau *" << is << " geht leider nicht" << endl; return; }
ast = is;
if (t == 's')
{ if (satzRek(um))
{ cout << "umbau *" << is << " geht leider nicht" << endl; return; } }
if (t == 's') s[um].h = 0;
if (it == 's') s[i].h = 0;
rzp = getRzp(i, it);
if (!rzp || (rzp && !*rzp))
{ if (rl == 'l')
{ s[is].t1 = t; s[is].sl = um; }
else
{ s[is].t2 = t; s[is].sr = um; }
if (t == 'w' || t == 's')
{ rzp = getRzp(um, t); neuRz(is); } }
else
{ modify0(is); rzi = *rzp; *rzp = r[rzi].zz;
if (! *rzp && it == 's') s[i].lc = OUTLOC;
if (rl == 'l')
{ s[is].t1 = t; s[is].sl = um; }
else
{ s[is].t2 = t; s[is].sr = um; }
rzp = getRzp(um, t);
if (rzp)
{ r[rzi].zz = *rzp; *rzp = rzi; } } }
char Baum::satzRek(int um)
{ if (um == ast) return 1;
if (s[um].t1 == 's')
{ if (satzRek(s[um].sl)) return 1; }
if (s[um].t2 == 's')
{ if (satzRek(s[um].sr)) return 1; }
return 0; }
void Baum::anbauLl(int i, int an, char t, char v)
// setzt satz voraus
{ an = sBau(an, s[i].sl, t, s[i].t1, v);
umbau(i, 'l', an, 's'); }
void Baum::anbauLr(int i, int an, char t, char v)
// setzt satz voraus
{ an = sBau(s[i].sl, an, s[i].t1, t, v);
umbau(i, 'l', an, 's'); }
void Baum::anbauRl(int i, int an, char t, char v)
// setzt satz voraus
{ an = sBau(an, s[i].sr, t, s[i].t2, v);
umbau(i, 'r', an, 's'); }
void Baum::anbauRr(int i, int an, char t, char v)
// setzt satz voraus
{ an = sBau(s[i].sr, an, s[i].t2, t, v);
umbau(i, 'r', an, 's'); }
void Baum::abbauLl(int wrzl)
// wrzl_links wird durch ihren rechten zweig ersetzt
{ int um; char t;
um = s[wrzl].sl;
t = s[um].t2; um = s[um].sr;
umbau(wrzl, 'l', um, t); }
void Baum::abbauLr(int wrzl)
// wrzl_links wird durch ihren linken zweig ersetzt
{ int um; char t;
um = s[wrzl].sl;
t = s[um].t1; um = s[um].sl;
umbau(wrzl, 'l', um, t); }
void Baum::abbauRl(int wrzl)
// wrzl_rechts wird durch ihren rechten zweig ersetzt
{ int um; char t;
um = s[wrzl].sr;
t = s[um].t2; um = s[um].sr;
umbau(wrzl, 'r', um, t); }
void Baum::abbauRr(int wrzl)
// wrzl_rechts wird durch ihren linken zweig ersetzt
{ int um; char t;
um = s[wrzl].sr;
t = s[um].t1; um = s[um].sl;
umbau(wrzl, 'r', um, t); }
int Baum::rootAbbau(int wrzl, char lr)
// called by wscan u. baum1.C/CntrlL
{ int rwrzl, rzi;
rzi = s[wrzl].b;
if (! rzi)
{ rwrzl = wrzl;
if ( lr == 'l')
{ baumi = s[wrzl].sl; typi = s[wrzl].t1;
rwrzl = s[wrzl].sr; rTyp = s[wrzl].t2; clrWurz(wrzl); }
else
{ baumi = s[wrzl].sr; typi = s[wrzl].t2;
rwrzl = s[wrzl].sl; rTyp = s[wrzl].t1; clrWurz(wrzl); }
if (typi == 's' && ! s[baumi].b) s[baumi].lc = OUTLOC; }
else
{ rSatz = r[rzi].zS;
if (wrzl == s[rSatz].sl)
{ if (lr == 'l') abbauLl(rSatz);
else abbauLr(rSatz); }
else
{ if (lr == 'l') abbauRl(rSatz);
else abbauRr(rSatz); }
rwrzl = rSatz; }
return rwrzl; }
//-----------------------------------------------------------------------------------------------
void Baum::neuwort(char *string)
{ wort0++; // leerer w_block
w[wort0].st = asci0; // erh�t string-heap_zeiger
while (*string) *asci0++ = *string++; // einguter hacker ...
*asci0++ = 0; } // stringinhalt wird nachtr�lich dorthin kopiert
int Baum::suchbaum(char *string, int anker)
{ int erg;
do
{ kett1 = w[anker].st;
erg = strcmp(kett1, string);
if (erg > 0) // kett1 > txt0
{ if (w[anker].wl)
{ anker = w[anker].wl;
continue; } // links weiter
else
{ neuwort(string); // war nix neu anlegen
w[anker].wl = wort0;
anker = wort0;
break; } }
else
{ if (erg < 0) // kett1 < txt0
{ if (w[anker].wr)
{ anker = w[anker].wr;
continue; } // rechts weiter
else
{ neuwort(string); // war nix neu anlegen
w[anker].wr = wort0;
anker = wort0;
break; } } } }
while (erg); // while txt0 != asci1 play it again sam.
return anker; } // na endlich.
int Baum::wortI(char* string)
{ unsigned char c; int anker, index;
c = *string;
if (*(string + 1))
{ anker = w[c].wl;
if (anker) index = suchbaum(string, anker); // suchbaum hat anker
else
{ neuwort(string); index = wort0; w[c].wl = index; } } // wort als neuer suchbaum.
else index = c;
return index; }
char Baum::istsatz()
// setzt rzp voraus
{ int rzi; rzi = *rzp; // sowohl bei wort als auch bei satz
while (rzi) // rckzeigerliste durchgehen
{ rSatz = r[rzi].zS; // ob satz vorhanden.
if (s0.sl == s[rSatz].sl)
if (s0.sr == s[rSatz].sr)
if (s0.v == s[rSatz].v)
if (s0.t1 == s[rSatz].t1)
if (s0.t2 == s[rSatz].t2)
if (s0.lc == s[rSatz].lc) return 1;
rzi = r[rzi].zz; }
return 0; }
int Baum::makesatz()
// setzt s0 voraus
{ s0.lc = loc; s0.b = 0; s0.h = 0; s0.s = 0;
if (! s0.t1 || ! s0.t2) return 0;
if ((s0.t1 == 'w' && ! s0.sl) || (s0.t2 == 'w' && ! s0.sr)) return 0;
if (s0.t1 == 's') s[s0.sl].h = 0;
if (s0.t2 == 's') s[s0.sr].h = 0;
rzp = getRzp(s0.sl, s0.t1);
if (rzp)
{ if (istsatz()) return rSatz;
while(s[satz0].v) satz0++; // neuer satz: satz0: neuer s_block: leer
if (satz0 > sMax) sMax = satz0;
s[satz0] = s0; // sieben auf einen streich
neuRz(satz0);
rzp = getRzp(s0.sr, s0.t2);
if (rzp) neuRz(satz0);
return satz0; }
rzp = getRzp(s0.sr, s0.t2);
if (rzp)
{ if (istsatz()) return rSatz;
while(s[satz0].v) satz0++; // neuer satz: satz0: neuer s_block: leer
if (satz0 > sMax) sMax = satz0;
s[satz0] = s0; // sieben auf einen streich
neuRz(satz0);
return satz0; }
while(s[satz0].v) satz0++; // neuer satz: satz0: neuer s_block: leer
s[satz0] = s0; // sieben auf einen streich
if (satz0 > sMax) sMax = satz0;
return satz0; }
int Baum::sBau(int sl, int sr, char t1, char t2, char v)
{ s0.v = v;
s0.t1 = t1; s0.sl = sl;
s0.t2 = t2; s0.sr = sr;
return makesatz(); }
int Baum::strToVal(char* txt)
// gibt int n zurck
{ char c; int n = 0;
c = *txt++;
if (!c) return 0;
if (c == '\'') return *txt; // '_'-zeichen
if (c == '0' && *txt == 'x') // hexadezimalzahl ermitteln
{ txt++;
while ((c = *txt++))
{ if (c >= '0' && c <= '9') c -= '0';
else if (c >= 'A' && c <= 'F') c = c - 'A' + 10;
else if (c >= 'a' && c <= 'f') c = c - 'a' + 10;
n *= 16; n += c; }
return n; }
--txt; return(atoi(txt)); }
int Baum::holzI(char* txt)
// called by wscan satzbau s3scan freeScan
{ char c, d, e; int ast; char* txt1;
txt1 = txt; typ = 'w';
while (*txt1)
{ if (*txt1 == '`') *txt1 = ' '; txt1++; } // internes einsetzen von blanks
c = *txt; d = *(txt + 1); ast = 0;
switch (c)
{ case '!':
if (! *(txt + 2))
{ typ = '!'; return (unsigned char) d; }
++txt;
break;
case '.': //1
if (d)
{ txt++; ast = wortI(txt);
getRSatz(ast); typ = 's'; return rSatz; }
break;
case ':': //2
if (d)
{ ast = wortI(txt + 1); rSatz = 0;
if (vSatz(ast, 'w', 'l'))
{ typ = s[rSatz].t2; return s[rSatz].sr; }
return ast; }
break;
case '/': //3
if (d == '/') return labPath(txt + 2);
break;
case '*': //4
if ((d >= '0') && (d <= '9'))
{ ++txt; typ = 's'; ast = atoi(txt); return ast; }
break;
case '#': //5
if (! d)
{ if (! clip[0]) ast = '#';
else
{ ast = clip[0]; typ = clipTyp[0]; }
return ast; }
if (d >= '1' && d <= '8') { d -= '1'; ast = clip[int(d)]; typ = clipTyp[int(d)]; return ast; }
e = *(txt + 2);
if (d == '#') //6
{ if (! e)
{ ast = clap[0]; typ = clapTyp[0]; return ast; }
if (e >= '1' && e <= '8')
{ e -= '1'; ast = clap[int(e)]; typ = clapTyp[int(e)]; return ast; } } }
ast = wortI(txt); return ast; }
// 1 punktlabel .label
// 2 nach labelpfad suchen
// 3 alias :name
// 4 satznummer mit * z.B. *1234
// 5 clipboard #1 - #8
// 6 clapboard ##1 - ##8
void Baum::tlz(int alt, int neu, char tAlt, char tNeu)
{ int rzA, rzA_, rzB, rzB_;
rzp = getRzp(alt, tAlt);
if (rzp)
{ if (tNeu == 's')
{ if (tAlt == 's')
{ s[neu].h = s[alt].h; s[alt].h = 0; }
else s[neu].h = histor; }
else
{ if (tAlt == 's')
{ histor = s[alt].h; s[alt].h = 0; } }
rzAB(rzA, rzA_, rzB, rzB_); *rzp = rzB;
if (rzA)
{ if (tNeu == 's') rzATest(rzA, rzB_, neu);
rzi = rzA;
while (rzi)
{ rSatz = r[rzi].zS;
if (alt == s[rSatz].sl)
{ s[rSatz].t1 = tNeu; s[rSatz].sl = neu; }
else
{ s[rSatz].t2 = tNeu; s[rSatz].sr = neu; }
rzi = r[rzi].zz; }
rzp = getRzp(neu, tNeu);
if (rzp)
{ rzi = *rzp;
if (rzi)
{ if (rzA)
{ *rzp = rzA; r[rzA_].zz = rzi; } }
else *rzp = rzA; }
else
{ while (rzA)
{ if (rzl0 > rzA) rzl0 = rzA;
rzi = r[rzA].zz;
r[rzA] = r[ENDRL]; //1
rzA = rzi; } } } //2
if (! rzB)
{ if (tAlt == 's') s[alt].lc = OUTLOC;
if (root == alt)
{ root = neu; rTyp = tNeu; } } } }
//1: leeres lr kopieren
//2: rzl0 : erstes freies r
void Baum::rzAB(int& rzA, int& rzA_, int& rzB, int& rzB_)
// zerlegt die kette rzi in zwei teilketten rzA u. rzB
{ rzA = rzB = 0;
rzi = *rzp; rSatz = r[rzi].zS;
if (loc == s[rSatz].lc)
{ rzA = rzi;
while (r[rzi].zz)
{ rzi = r[rzi].zz; rSatz = r[rzi].zS;
if (loc != s[rSatz].lc)
{ rzB = rzi; break; } } }
else
{ rzB = rzi;
while (r[rzi].zz)
{ rzi = r[rzi].zz; rSatz = r[rzi].zS;
if (loc == s[rSatz].lc)
{ rzA = rzi; break; } } }
rzi = *rzp; rzA_ = rzA; rzB_ = rzB;
while (r[rzi].zz)
{ rzi = r[rzi].zz; rSatz = r[rzi].zS;
if (loc == s[rSatz].lc)
{ if (rzi != rzA)
{ r[rzA_].zz = rzi; rzA_ = rzi; } }
else
{ if (rzi != rzB)
{ r[rzB_].zz = rzi; rzB_ = rzi; } } }
r[rzA_].zz = 0; r[rzB_].zz = 0;
*rzp = rzB; }
void Baum::rzATest(int& rzA, int rzB_, int neu)
// nimmt r[rzi].zS = neu aus der A_kette und h�gt es an die B_kette
{ int rzV, rzN; rzV = rzi = rzA;
while (rzi)
{ rzN = r[rzi].zz;
rSatz = r[rzi].zS;
if (rSatz == neu)
{ r[rzB_].zz = rzi; r[rzi].zz = 0;
if (rzA == rzi) rzA = rzi = rzN; //1
else r[rzV].zz = rzN; }
rzV = rzi; rzi = rzN; } }
//1: wenn es sich um den 1. knoten in der A_kette handelt dann ist vorsicht geboten
/*****************************************************************************/
void Baum::comboload()
{ int i, i1; char* wStr;
for (i = i1 = 0; i1 < 16; ++i, ++i1)
{ if (combo[i1] == root && comboTyp[i1] == rTyp) ++i1;
if (comboTyp[i1] == 's' && (s[combo[i1]].v != '"' || s[combo[i1]].t1 != 'w' || s[combo[i1]].lc == OUTLOC)) ++i1;
if (i1 > i)
{ combo[i] = combo[i1]; comboTyp[i] = comboTyp[i1]; } }
if (i < 16)
{ combo[i - 1] = 0; comboTyp[i - 1] = 0; }
for (i = 15; i; --i)
{ combo[i] = combo[i - 1]; comboTyp[i] = comboTyp[i - 1]; }
combo[0] = root; comboTyp[0] = rTyp;
comboRBox->clear(); i = 0;
while (combo[i] && i < 16)
{ if (comboTyp[i] == 'w') wStr = w[combo[i]].st;
else wStr = w[s[combo[i]].sl].st;
comboRBox->insertItem((QString) wStr, -1); i++; } }
int Baum::labPath(char* txt)
// labelpfad suchen z.B. //label1/label2/label3
{ char string[100]; char* str; int k;
labI = 0;
loop:
str = string;
while (*txt && *txt != '/') *str++ = *txt++;
*str = 0;
worti = wortI(string);
if (! *txt)
{ if (! labI)
{ k = vLSatz(worti);
if (k)
{ typ = 's'; return k; }
typ = 'w'; return worti; }
ast = 0; lab = worti;
labIScan(labI); k = ast;
if (k)
{ typ = 's'; return k; }
typ = 'w'; return worti; }
if (! labI)
{ k = vLSatz(worti);
if (k) labI = k;
++txt; goto loop; }
ast = 0; lab = worti;
labIScan(labI); k = ast;
if (k)
{ ++txt; labI = k; goto loop; }
typ = 'w'; return worti; }
void Baum::labIScan(int wrzl)
{ int sl, sr; char t1, t2, v;
sl = s[wrzl].sl; sr = s[wrzl].sr; t1 = s[wrzl].t1; t2 = s[wrzl].t2; v = s[wrzl].v;
if (! lab) return;
if (v == '"' && sl == lab)
{ ast = wrzl; lab = 0; return; }
if (t1 == 's') labIScan(sl);
if (t2 == 's') labIScan(sr); }
//************************************************************
void Baum::locLoesch(char c)
{ int i; i = sMax;
while (i)
{ if (! s[i].b)
{ if(s[i].lc == c) loeschen(i, 's'); }
--i; } }
void Baum::loeschen(int i, char t)
{ if (i != root) loeschRek(i, t); }
void Baum::loeschRek(int i, char t)
{ if (t != 's') return;
s[i].h = 0;
if (s[i].b || ! s[i].v) return;
*stck0++ = s[i].sr; *cstck0++ = s[i].t2;
*stck0++ = s[i].sl; *cstck0++ = s[i].t1;
clrWurz(i);
i = *--stck0; t = *--cstck0; loeschRek(i, t);
i = *--stck0; t = *--cstck0; loeschRek(i, t); }]]>
back to
baumC