diff options
Diffstat (limited to 'app/baisy/2.2.1-schulis/src/systembaum')
-rw-r--r-- | app/baisy/2.2.1-schulis/src/systembaum | 299 |
1 files changed, 299 insertions, 0 deletions
diff --git a/app/baisy/2.2.1-schulis/src/systembaum b/app/baisy/2.2.1-schulis/src/systembaum new file mode 100644 index 0000000..2497398 --- /dev/null +++ b/app/baisy/2.2.1-schulis/src/systembaum @@ -0,0 +1,299 @@ +PACKET systembaumDEFINES sohnvon,reorganisieren,gibbaumtabelle,KNOTEN ,=, +neuerknoten,nilknoten,markierungsknoten,erster,naechster,gueltig,suche, +existiert,read,write,inknotenmenge,ausknotenmenge,knotenloeschen,move, +KNOTENMENGE ,:=,zahlderelemente,leereknotenmenge,knotenmengeloeschen,exporte, +importe,system,listederteilbaeume,startesystembaum,kopieresystembaum, +ueberschreibesystembaum,setzesystembaumzurueck:BOOL PROC sohnvon(KNOTEN +CONST vater,sohn):pos(kmknoten,CONCR (sohn))>0.kmknoten:IF CONCR (vater)<= +maxknTHEN systembaum.tabzeile(CONCR (vater)).knotenELSE verwaltung.tabzeile( +CONCR (vater)-maxkn).knotenFI .ENDPROC sohnvon;LET maxkn=2190,niltext="",null +=0,knindex=1;LET kn1=2191,kn2=2192,kn3=2193;LET systembaumname="BAISY-0", +systembaumkopie="SBKOP",verwaltungsname="BAISY-1",verwaltungskopie="VWKOP"; +LET maxhoehe=100,bottom=1,refkz="1",erreichtkz="2";LET reorgincr=7000;TYPE +TUPEL =STRUCT (KNOTEN kn,INT index,BOOL markiert);TYPE STACK =STRUCT (ROW +maxhoeheTUPEL st,INT top);TYPE KNOTENMENGE =INT ;TYPE KNOTEN =INT ;TYPE +EINTRAG =STRUCT (TEXT attribute,KNOTEN vater,LONGROW knotenmengenLONGROW +knoten);TYPE SYSTAB =STRUCT (INT maxeintrag,ersterfreier,ROW maxknEINTRAG +tabzeile);KNOTEN CONST nilknoten:=KNOTEN :(null);KNOTEN CONST +markierungsknoten:=KNOTEN :(4711);BOUND SYSTAB VAR systembaum;BOUND SYSTAB +VAR verwaltung;BOUND SYSTAB VAR reorg;KNOTENMENGE VAR exp,imp,sys;PROC +gibbaumtabelle(TEXT CONST startknotenname,DATASPACE VAR ds):CONCR (systembaum +.tabzeile(systembaum.ersterfreier).vater):=zeilennr(startknotenname);ds:=old( +systembaumname)END PROC gibbaumtabelle;INT PROC zeilennr(TEXT CONST +startknotenname):KNOTEN VAR k;IF existiert(exporte,k,startknotenname)THEN +KNOTENMENGE VAR soehne;read(k,soehne);CONCR (erster(soehne))ELSE nullFI END +PROC zeilennr;OP :=(KNOTEN VAR k,KNOTEN CONST l):CONCR (k):=CONCR (l)END OP +:=;BOOL OP =(KNOTEN CONST k,KNOTEN CONST l):CONCR (k)=CONCR (l)END OP =; +KNOTEN PROC neuerknoten(KNOTENMENGE CONST m):KNOTEN VAR k;CONCR (k):= +neuereintrag(CONCR (m)<>CONCR (sys),true);inknotenmenge(m,k);kEND PROC +neuerknoten;KNOTEN PROC neuerknoten(KNOTENMENGE CONST m,TEXT CONST schluessel +):KNOTEN VAR k;IF existiert(m,k,schluessel)THEN LEAVE neuerknotenWITH kFI ; +KNOTEN VAR l;CONCR (l):=neuereintrag(CONCR (m)<>CONCR (sys),true);write(l, +schluessel);inknotenmenge(m,l,k);lEND PROC neuerknoten;BOOL PROC existiert( +KNOTENMENGE CONST a,KNOTEN VAR r,TEXT CONST muster):BOOL VAR gefunden;suche(a +,muster,r,gefunden);gefundenEND PROC existiert;PROC read(KNOTEN CONST k, +KNOTEN VAR vater):vater:=kvater.kvater:IF CONCR (k)<=maxknTHEN systembaum. +tabzeile(CONCR (k)).vaterELSE verwaltung.tabzeile(CONCR (k)-maxkn).vaterFI . +END PROC read;PROC read(KNOTEN CONST k,KNOTENMENGE VAR soehne):CONCR (soehne) +:=CONCR (k)END PROC read;PROC read(KNOTEN CONST k,TEXT VAR attribute): +attribute:=kattribute.kattribute:IF CONCR (k)<=maxknTHEN systembaum.tabzeile( +CONCR (k)).attributeELSE verwaltung.tabzeile(CONCR (k)-maxkn).attributeFI . +END PROC read;PROC read(KNOTEN CONST k,EINTRAG VAR attribute):attribute:= +keintrag.keintrag:IF CONCR (k)<=maxknTHEN systembaum.tabzeile(CONCR (k))ELSE +verwaltung.tabzeile(CONCR (k)-maxkn)FI .END PROC read;PROC write(KNOTEN +CONST k,KNOTEN CONST vater):kvater:=vater.kvater:IF CONCR (k)<=maxknTHEN +systembaum.tabzeile(CONCR (k)).vaterELSE verwaltung.tabzeile(CONCR (k)-maxkn) +.vaterFI .END PROC write;PROC write(KNOTEN CONST k,KNOTENMENGE CONST soehne): +kknoten:=sohnknoten.kknoten:IF CONCR (k)<=maxknTHEN systembaum.tabzeile( +CONCR (k)).knotenELSE verwaltung.tabzeile(CONCR (k)-maxkn).knotenFI . +sohnknoten:IF CONCR (soehne)<=maxknTHEN systembaum.tabzeile(CONCR (soehne)). +knotenELSE verwaltung.tabzeile(CONCR (soehne)-maxkn).knotenFI .END PROC write +;PROC write(KNOTEN CONST k,TEXT CONST attribute):kattribute:=attribute. +kattribute:IF CONCR (k)<=maxknTHEN systembaum.tabzeile(CONCR (k)).attribute +ELSE verwaltung.tabzeile(CONCR (k)-maxkn).attributeFI .END PROC write;PROC +write(KNOTEN CONST k,EINTRAG CONST attribute):keintrag:=attribute.keintrag: +IF CONCR (k)<=maxknTHEN systembaum.tabzeile(CONCR (k))ELSE verwaltung. +tabzeile(CONCR (k)-maxkn)FI .END PROC write;PROC inknotenmenge(KNOTENMENGE +CONST km,KNOTEN CONST k):kmknotenCAT kindex;kknotenmengenCAT kmindex.kmknoten +:IF CONCR (km)<=maxknTHEN systembaum.tabzeile(CONCR (km)).knotenELSE +verwaltung.tabzeile(CONCR (km)-maxkn).knotenFI .kknotenmengen:IF CONCR (k)<= +maxknTHEN systembaum.tabzeile(CONCR (k)).knotenmengenELSE verwaltung.tabzeile +(CONCR (k)-maxkn).knotenmengenFI .kindex:CONCR (k).kmindex:CONCR (km).END +PROC inknotenmenge;PROC inknotenmenge(KNOTENMENGE CONST km,KNOTEN CONST k,l): +IF l=nilknotenTHEN inknotenmenge(km,k)ELSE insert(kmknoten,posl,kindex); +kknotenmengenCAT kmindexFI .posl:pos(kmknoten,lindex).kmknoten:IF CONCR (km) +<=maxknTHEN systembaum.tabzeile(CONCR (km)).knotenELSE verwaltung.tabzeile( +CONCR (km)-maxkn).knotenFI .kknotenmengen:IF CONCR (k)<=maxknTHEN systembaum. +tabzeile(CONCR (k)).knotenmengenELSE verwaltung.tabzeile(CONCR (k)-maxkn). +knotenmengenFI .kindex:CONCR (k).lindex:CONCR (l).kmindex:CONCR (km).END +PROC inknotenmenge;PROC ausknotenmenge(KNOTENMENGE CONST km,KNOTEN VAR k): +KNOTEN VAR l:=k;naechster(l,km);delete(kmknoten,kindex);delete(kknotenmengen, +kmindex);k:=l.kmknoten:IF CONCR (km)<=maxknTHEN systembaum.tabzeile(CONCR (km +)).knotenELSE verwaltung.tabzeile(CONCR (km)-maxkn).knotenFI .kknotenmengen: +IF CONCR (k)<=maxknTHEN systembaum.tabzeile(CONCR (k)).knotenmengenELSE +verwaltung.tabzeile(CONCR (k)-maxkn).knotenmengenFI .kindex:pos(kmknoten, +CONCR (k)).kmindex:pos(kknotenmengen,CONCR (km)).END PROC ausknotenmenge; +PROC knotenloeschen(KNOTENMENGE CONST km,KNOTEN VAR k):IF +knotenundknotenmengeexistierenTHEN ausallenmengen;sohnknotenmengeloeschen; +ungueltigmachen(CONCR (l))FI .knotenundknotenmengeexistieren:(CONCR (km)<>0) +CAND (CONCR (k)<>0).ausallenmengen:KNOTEN VAR nachf:=k;KNOTEN CONST l:=k; +LONGROW VAR mengen:=kknotenmengen;INT VAR i,mindex;KNOTENMENGE VAR m;FOR i +FROM 1UPTO length(mengen)REP mindex:=mengen_i;CONCR (m):=mindex; +ausknotenmenge(m,k);IF mindex=CONCR (km)THEN nachf:=kFI ;k:=lPER ;k:=nachf. +sohnknotenmengeloeschen:KNOTENMENGE VAR soehne;CONCR (soehne):=CONCR (l); +knotenmengeloeschen(soehne).kknotenmengen:IF CONCR (k)<=maxknTHEN systembaum. +tabzeile(CONCR (k)).knotenmengenELSE verwaltung.tabzeile(CONCR (k)-maxkn). +knotenmengenFI .END PROC knotenloeschen;PROC move(KNOTEN CONST k,KNOTEN +CONST l):eigenschaftenuebertragen;pointerpflegen.eigenschaftenuebertragen: +systembaum.tabzeile(CONCR (l)).knoten:=systembaum.tabzeile(CONCR (k)).knoten; +systembaum.tabzeile(CONCR (l)).attribute:=systembaum.tabzeile(CONCR (k)). +attribute.pointerpflegen:soehnevonkumsetzen;vaetervonkumsetzen. +soehnevonkumsetzen:soehneumsetzen(systembaum.tabzeile(CONCR (k)).knoten,k,l). +vaetervonkumsetzen:vaeterumsetzen(systembaum.tabzeile(CONCR (k)).knotenmengen +,k,l).END PROC move;PROC soehneumsetzen(LONGROW CONST soehne,KNOTEN CONST von +,nach):INT VAR i;FOR iFROM 1UPTO length(soehne)REP INT VAR sohni:=soehne_i; +replace(beisohni,posvon,CONCR (nach))PER .beisohni:systembaum.tabzeile(sohni) +.knotenmengen.posvon:pos(beisohni,CONCR (von)).END PROC soehneumsetzen;PROC +vaeterumsetzen(LONGROW CONST vaeter,KNOTEN CONST von,nach):INT VAR i,refindex +;refindex:=CONCR (systembaum.tabzeile(CONCR (von)).vater);FOR iFROM 1UPTO +length(vaeter)REP INT VAR vateri:=vaeter_i;vaterumsetzen(vateri,refindex,nach +)PER END PROC vaeterumsetzen;PROC vaterumsetzen(INT CONST vaterindex,refindex +,KNOTEN CONST nach):IF (vaterindex<>CONCR (system))CAND (vaterindex<>refindex +)THEN KNOTENMENGE VAR vater;CONCR (vater):=vaterindex;inknotenmenge(vater, +nach)FI END PROC vaterumsetzen;KNOTEN PROC erster(KNOTENMENGE CONST m): +LONGROW CONST ordnung:=mknoten;ersternach(null,ordnung).mknoten:IF CONCR (m) +<=maxknTHEN systembaum.tabzeile(CONCR (m)).knotenELSE verwaltung.tabzeile( +CONCR (m)-maxkn).knotenFI .END PROC erster;PROC naechster(KNOTEN VAR k, +KNOTENMENGE CONST m):LONGROW CONST ordnung:=mknoten;k:=ersternach(indexvonk, +ordnung).indexvonk:pos(ordnung,CONCR (k)).mknoten:IF CONCR (m)<=maxknTHEN +systembaum.tabzeile(CONCR (m)).knotenELSE verwaltung.tabzeile(CONCR (m)-maxkn +).knotenFI .END PROC naechster;BOOL PROC gueltig(KNOTEN CONST k):CONCR (k)<> +nullEND PROC gueltig;PROC suche(KNOTENMENGE CONST m,TEXT CONST muster,KNOTEN +VAR k,BOOL VAR gefunden):LONGROW CONST ordnung:=mknoten;INT CONST l:=length( +ordnung);IF l=nullTHEN gefunden:=false;k:=nilknotenELSE INT VAR ordnungsindex +;binsearch(ordnung,muster,BOOL PROC (TEXT CONST ,INT CONST )kleiner, +ordnungsindex);IF ordnungsindex>lTHEN gefunden:=false;k:=nilknotenELSE CONCR +(k):=ordnung_ordnungsindex;TEXT VAR gefundenesmuster;read(k,gefundenesmuster) +;gefunden:=(muster=gefundenesmuster)FI FI .mknoten:IF CONCR (m)<=maxknTHEN +systembaum.tabzeile(CONCR (m)).knotenELSE verwaltung.tabzeile(CONCR (m)-maxkn +).knotenFI .END PROC suche;OP :=(KNOTENMENGE VAR k,KNOTENMENGE CONST l): +CONCR (k):=CONCR (l)END OP :=;INT PROC zahlderelemente(KNOTENMENGE CONST km): +length(kmknoten).kmknoten:IF CONCR (km)<=maxknTHEN systembaum.tabzeile(CONCR +(km)).knotenELSE verwaltung.tabzeile(CONCR (km)-maxkn).knotenFI .END PROC +zahlderelemente;KNOTENMENGE PROC leereknotenmenge:KNOTENMENGE VAR k;CONCR (k) +:=neuereintrag(true,false);kEND PROC leereknotenmenge;PROC +knotenmengeloeschen(KNOTENMENGE VAR km):IF knotenmengeexistiertTHEN +allezeigerloeschen;alsungueltigkennzeichnenFI .knotenmengeexistiert:CONCR (km +)<>0.allezeigerloeschen:INT CONST kmind:=CONCR (km);LONGROW VAR knoten:= +kmindknoten;INT VAR i,kindex;LONGROW VAR row;FOR iFROM 1UPTO length(knoten) +REP kindex:=knoten_i;row:=kindexknotenmengen;delete(kindexknotenmengen,pos( +row,kmind))PER ;.kmindknoten:IF kmind<=maxknTHEN systembaum.tabzeile(kmind). +knotenELSE verwaltung.tabzeile(kmind-maxkn).knotenFI .kindexknotenmengen:IF +kindex<=maxknTHEN systembaum.tabzeile(kindex).knotenmengenELSE verwaltung. +tabzeile(kindex-maxkn).knotenmengenFI .alsungueltigkennzeichnen:IF +nichtinknotenTHEN ungueltigmachen(kmind);ELSE kmindknoten:=newrowFI ;CONCR ( +km):=null.nichtinknoten:KNOTEN VAR vglknoten,kmknoten;CONCR (kmknoten):=kmind +;read(kmknoten,vglknoten);CONCR (vglknoten)=knindex.END PROC +knotenmengeloeschen;KNOTENMENGE PROC exporte:expEND PROC exporte;KNOTENMENGE +PROC importe:impEND PROC importe;KNOTENMENGE PROC system:sysEND PROC system; +PROC startesystembaum:IF verwaltungdaTHEN nurankoppelnELSE +ankoppelnundpermanenteknotenmengenerzeugenFI ;systembaumbehandeln. +verwaltungda:exists(verwaltungsname).nurankoppeln:verwaltung:=old( +verwaltungsname);CONCR (exp):=kn1;CONCR (imp):=kn2;CONCR (sys):=kn3. +ankoppelnundpermanenteknotenmengenerzeugen:verwaltung:=new(verwaltungsname); +verwaltung.maxeintrag:=0;verwaltung.ersterfreier:=1;exp:=leereknotenmenge;imp +:=leereknotenmenge;sys:=leereknotenmenge.systembaumbehandeln:IF exists( +systembaumname)THEN systembaum:=old(systembaumname)ELSE systembaum:=new( +systembaumname);systembaum.maxeintrag:=0;systembaum.ersterfreier:=1;FI .END +PROC startesystembaum;PROC listederteilbaeume(TEXT CONST dateiname):LONGROW +VAR refinements;FILE VAR f:=sequentialfile(output,dateiname);refinements:= +verwaltung.tabzeile(CONCR (exporte)-maxkn).knoten;INT VAR i;FOR iFROM 1UPTO +length(refinements)REP put(f,verwaltung.tabzeile((refinements_i)-maxkn). +attribute);line(f)PER ;close(f)END PROC listederteilbaeume;PROC +kopieresystembaum:copy(systembaumname,systembaumkopie);systembaum:=old( +systembaumkopie);copy(verwaltungsname,verwaltungskopie);verwaltung:=old( +verwaltungskopie)END PROC kopieresystembaum;PROC ueberschreibesystembaum: +forget(systembaumname,quiet);rename(systembaumkopie,systembaumname);forget( +verwaltungsname,quiet);rename(verwaltungskopie,verwaltungsname)END PROC +ueberschreibesystembaum;PROC setzesystembaumzurueck:systembaum:=old( +systembaumname);forget(systembaumkopie,quiet);verwaltung:=old(verwaltungsname +);forget(verwaltungskopie,quiet)END PROC setzesystembaumzurueck;INT PROC +neuereintrag(BOOL CONST istverwaltung,istknoten):EINTRAG VAR e;e.attribute:= +niltext;IF istknotenTHEN CONCR (e.vater):=null;ELSE CONCR (e.vater):=knindex +FI ;e.knotenmengen:=newrow;e.knoten:=newrow;INT VAR eintragsnr; +naechstenfreiensuchen(istverwaltung,eintragsnr);KNOTEN VAR k;CONCR (k):= +eintragsnr;write(k,e);eintragsnrEND PROC neuereintrag;OP :=(EINTRAG VAR e, +EINTRAG CONST f):CONCR (e):=CONCR (f)END OP :=;PROC naechstenfreiensuchen( +BOOL CONST istverwaltung,INT VAR eintragsnr):IF istverwaltungTHEN +naechstenfreieninverwaltungsuchen(eintragsnr)ELSE +naechstenfreieninsystembaumsuchen(eintragsnr)FI END PROC +naechstenfreiensuchen;PROC naechstenfreieninsystembaumsuchen(INT VAR +eintragsnr):eintragsnr:=systembaum.ersterfreier;IF systembaum.ersterfreier> +systembaum.maxeintragTHEN systembaum.maxeintrag:=systembaum.ersterfreier; +systembaum.ersterfreierINCR 1ELSE INT VAR i;FOR iFROM systembaum.ersterfreier ++1UPTO systembaum.maxeintragREP IF NOT istgueltigTHEN systembaum.ersterfreier +:=i;LEAVE naechstenfreieninsystembaumsuchenFI PER ;systembaum.ersterfreier:= +systembaum.maxeintrag+1FI .istgueltig:CONCR (systembaum.tabzeile(i).vater)>= +null.END PROC naechstenfreieninsystembaumsuchen;PROC +naechstenfreieninverwaltungsuchen(INT VAR eintragsnr):eintragsnr:=verwaltung. +ersterfreier+maxkn;IF verwaltung.ersterfreier>verwaltung.maxeintragTHEN +verwaltung.maxeintrag:=verwaltung.ersterfreier;verwaltung.ersterfreierINCR 1 +ELSE INT VAR i;FOR iFROM verwaltung.ersterfreier+1UPTO verwaltung.maxeintrag +REP IF NOT istgueltigTHEN verwaltung.ersterfreier:=i;LEAVE +naechstenfreieninverwaltungsuchenFI PER ;verwaltung.ersterfreier:=verwaltung. +maxeintrag+1FI .istgueltig:CONCR (verwaltung.tabzeile(i).vater)>=null.END +PROC naechstenfreieninverwaltungsuchen;KNOTEN PROC ersternach(INT CONST +knindex,LONGROW CONST ordnung):KNOTEN VAR k:=nilknoten;INT CONST l:=length( +ordnung);IF (l>0)CAND (knindex<l)THEN CONCR (k):=ordnung_(knindex+1)FI ;kEND +PROC ersternach;BOOL PROC kleiner(TEXT CONST muster,INT CONST i):KNOTEN VAR k +;TEXT VAR vglmuster;CONCR (k):=i;read(k,vglmuster);muster<=vglmusterEND PROC +kleiner;PROC ungueltigmachen(INT CONST nr):EINTRAG VAR e;e.attribute:=niltext +;CONCR (e.vater):=-1;e.knotenmengen:=newrow;e.knoten:=newrow;KNOTEN VAR k; +CONCR (k):=nr;write(k,e);ersterfreier(nr)END PROC ungueltigmachen;PROC +ersterfreier(INT CONST nr):IF nr<=maxknTHEN ersterfreier(systembaum. +ersterfreier,nr)ELSE ersterfreier(verwaltung.ersterfreier,nr-maxkn)FI END +PROC ersterfreier;PROC ersterfreier(INT VAR ef,INT CONST nr):IF nr<efTHEN ef +:=nrFI END PROC ersterfreier;PROC reorganisieren:meldestartderreorganisation; +reorganisieresystem;reorganisiereverwaltung.meldestartderreorganisation:out( +"��");put("Der Systembaum wird reorganisiert").END PROC reorganisieren;PROC +reorganisieresystem:vorbereitung;ausfuehrung;abschluss.ausfuehrung: +sammlealleunbenutztenrefinements;reorganisierediese. +sammlealleunbenutztenrefinements:LONGROW VAR refinements;refinements:= +verwaltung.tabzeile(CONCR (exporte)-maxkn).knoten;LONGROW VAR unbenutzte:= +newrow,startknoten:=newrow;INT VAR i;EINTRAG VAR e;FOR iFROM 1UPTO length( +refinements)REP INT VAR knnummer:=refinements_i;INT VAR relnummer:=knnummer- +maxkn;e:=verwaltung.tabzeile(relnummer);IF NOT ((e.vater)=markierungsknoten) +THEN unbenutzteCAT knnummer;startknotenCAT (e.knoten_1)FI PER . +reorganisierediese:reorganisiere(unbenutzte,startknoten).vorbereitung: +DATASPACE VAR ds:=nilspace;reorg:=ds;reorg.maxeintrag:=0;reorg.ersterfreier:= +1.abschluss:forget(systembaumname,quiet);copy(ds,systembaumname);forget(ds). +END PROC reorganisieresystem;PROC reorganisiereverwaltung:vorbereitung; +ausfuehrung;abschluss.ausfuehrung:line;put( +"Die Verwaltungsstruktur wird reorganisiert");INT VAR i;FOR iFROM 1UPTO reorg +.maxeintragREP IF gueltigTHEN uebertrageELSE markiereFI PER .gueltig:cout(i); +CONCR (verwaltung.tabzeile(i).vater)>=0.uebertrage:EINTRAG VAR e;e.attribute +:=verwaltung.tabzeile(i).attribute;e.knotenmengen:=verwaltung.tabzeile(i). +knotenmengen;e.vater:=verwaltung.tabzeile(i).vater;e.knoten:=decr(verwaltung. +tabzeile(i).knoten);reorg.tabzeile(i):=e.markiere:CONCR (reorg.tabzeile(i). +vater):=-1.vorbereitung:DATASPACE VAR ds:=nilspace;reorg:=ds;reorg.maxeintrag +:=verwaltung.maxeintrag;reorg.ersterfreier:=verwaltung.ersterfreier.abschluss +:forget(verwaltungsname,quiet);copy(ds,verwaltungsname);forget(ds); +startesystembaum.END PROC reorganisiereverwaltung;PROC reorganisiere(LONGROW +CONST unbenutzte,startknoten):INT VAR i;FOR iFROM 1UPTO length(unbenutzte) +REP reorganisiere(knoten,name)PER .knoten:KNOTEN :(startknoten_i).name:TEXT +VAR na;read(KNOTEN :(unbenutzte_i),na);na.END PROC reorganisiere;PROC +reorganisiere(KNOTEN CONST k,TEXT CONST teilbaumname):line;put("Teilbaum "+ +teilbaumname+" wird reorganisiert");reorganisiere(k)END PROC reorganisiere; +PROC reorganisiere(KNOTEN CONST k):vorbereitung;erstenaufstack;REP +stackbearbeitungUNTIL stackleerPER .stackbearbeitung:nimmoberstenvomstack;IF +(NOT oberstermarkiert)CAND hatsoehneTHEN markiertzurueck; +allesoehneaufdenstackELSE oberstenuebertragenFI .vorbereitung:STACK VAR s:= +leererstack.erstenaufstack:TUPEL VAR tup;IF schonmalerreicht(k)THEN LEAVE +reorganisiereELSE tup.kn:=k;tup.index:=naechsterindex;tup.markiert:=false; +alserreichtkennzeichnen(k);vater.kn:=systembaum.tabzeile(CONCR (k)).vater; +vater.index:=CONCR (vater.kn);hauptindexaendern(tup,vater);push(s,tup)FI . +stackleer:leer(s).nimmoberstenvomstack:TUPEL VAR vater;pop(s,vater). +oberstermarkiert:vater.markiert.markiertzurueck:vater.markiert:=true;push(s, +vater).hatsoehne:KNOTENMENGE VAR soehne;read(vater.kn,soehne);INT VAR +sohnzahl:=zahlderelemente(soehne);sohnzahl>0.oberstenuebertragen:uebertrage( +vater).allesoehneaufdenstack:INT VAR i;LONGROW VAR sohnverzeichnis:= +systembaum.tabzeile(CONCR (soehne)).knoten;tup.markiert:=false;FOR iFROM 1 +UPTO sohnzahlREP holesohn;IF NOT (schonmalerreicht(sohn))THEN +itersohnaufstackELSE indexaendern(s,vater,sohn)FI PER .holesohn:KNOTEN VAR +sohn;CONCR (sohn):=sohnverzeichnis_i.itersohnaufstack:tup.kn:=sohn;tup.index +:=naechsterindex;IF isrefinement(sohn)THEN alserreichtkennzeichnen(sohn)FI ; +hauptindexaendern(tup,vater);push(s,tup).END PROC reorganisiere;BOOL PROC +schonmalerreicht(KNOTEN CONST k):is(k,erreichtkz)END PROC schonmalerreicht; +BOOL PROC isrefinement(KNOTEN CONST k):is(k,refkz)END PROC isrefinement;BOOL +PROC is(KNOTEN CONST k,TEXT CONST muster):is(attribute(k),muster)END PROC is; +BOOL PROC is(TEXT CONST k,TEXT CONST muster):(subtext(k,1,1)=muster)END PROC +is;PROC alserreichtkennzeichnen(KNOTEN CONST k):replace(systembaum.tabzeile( +CONCR (k)).attribute,1,erreichtkz)END PROC alserreichtkennzeichnen;TEXT PROC +attribute(KNOTEN CONST k):systembaum.tabzeile(CONCR (k)).attributeEND PROC +attribute;INT PROC naechsterindex:reorg.maxeintragINCR 1;reorg.ersterfreier +INCR 1;cout(reorg.maxeintrag);reorg.maxeintragEND PROC naechsterindex;PROC +uebertrage(TUPEL CONST tup):EINTRAG VAR e;INT VAR knummer:=CONCR (tup.kn);e. +attribute:=systembaum.tabzeile(knummer).attribute;e.vater:=systembaum. +tabzeile(knummer).vater;e.knotenmengen:=decr(systembaum.tabzeile(knummer). +knotenmengen);e.knoten:=decr(systembaum.tabzeile(knummer).knoten);IF +schonmalerreichtTHEN replace(e.attribute,1,refkz)FI ;reorg.tabzeile(tup.index +):=e;CONCR (systembaum.tabzeile(knummer).vater):=tup.index.schonmalerreicht: +is(e.attribute,erreichtkz).END PROC uebertrage;PROC hauptindexaendern(TUPEL +CONST tup,TUPEL CONST vater):INT VAR knummer:=CONCR (tup.kn);LONGROW VAR +knotenmengen:=systembaum.tabzeile(knummer).knotenmengen;INT VAR i;FOR iFROM 1 +UPTO length(knotenmengen)REP IF verwaltungodervaterTHEN indexaendern(knummer, +tup.index,iteknotenmenge,vater.index)FI PER .verwaltungodervater:INT VAR +iteknotenmenge:=knotenmengen_i;(iteknotenmenge>maxkn)COR (iteknotenmenge= +CONCR (vater.kn)).END PROC hauptindexaendern;PROC indexaendern(STACK CONST s, +TUPEL CONST vater,KNOTEN CONST sohn):INT VAR neuersohnindex:=CONCR ( +systembaum.tabzeile(CONCR (sohn)).vater);IF nochaufstackTHEN +sucheneuensohnindexFI ;indexaendern(CONCR (sohn),neuersohnindex,CONCR (vater. +kn),vater.index);reorg.tabzeile(neuersohnindex).knotenmengen:=decr(systembaum +.tabzeile(CONCR (sohn)).knotenmengen).nochaufstack:(neuersohnindex>maxkn). +sucheneuensohnindex:search(s,CONCR (sohn),neuersohnindex);.END PROC +indexaendern;PROC indexaendern(INT CONST alterindex,nind,knalt,kneu):INT VAR +neuerindex:=nind+reorgincr,knneu:=kneu+reorgincr;IF knalt<=maxknTHEN +possystemELSE errechneposition;posverwaltung;FI .possystem:INT VAR ps:=pos( +systemknoten,alterindex);replace(systemknoten,ps,neuerindex);replace( +systemknotenmengen,knpos,knneu).systemknoten:systembaum.tabzeile(knalt). +knoten.systemknotenmengen:systembaum.tabzeile(alterindex).knotenmengen.knpos: +pos(systemknotenmengen,knalt).errechneposition:INT CONST position:=knalt- +maxkn.posverwaltung:INT VAR pv:=pos(verwaltungsknoten,alterindex);replace( +verwaltungsknoten,pv,neuerindex).verwaltungsknoten:verwaltung.tabzeile( +position).knoten.END PROC indexaendern;LONGROW PROC decr(LONGROW CONST l): +LONGROW VAR row:=newrow;INT VAR i;FOR iFROM 1UPTO length(l)REP rowCAT ((l_i) +MOD reorgincr)PER ;rowEND PROC decr;STACK PROC leererstack:STACK VAR s;s.top +:=bottom;sEND PROC leererstack;OP :=(TUPEL VAR ziel,TUPEL CONST quelle): +CONCR (ziel):=CONCR (quelle)END OP :=;OP :=(STACK VAR ziel,STACK CONST quelle +):CONCR (ziel):=CONCR (quelle)END OP :=;PROC push(STACK VAR s,TUPEL CONST k): +IF NOT (s.top=maxhoehe)THEN s.st(s.top):=k;s.topINCR 1ELSE errorstop( +"Stacküberlauf")FI END PROC push;PROC pop(STACK VAR s,TUPEL VAR k):IF NOT (s. +top=bottom)THEN s.topDECR 1;k:=s.st(s.top)ELSE errorstop("Stackunterlauf")FI +END PROC pop;PROC search(STACK CONST s,INT CONST index,INT VAR neuersohnindex +):INT VAR i:=0;REP iINCR 1;IF i>s.topTHEN errorstop("Rekursionsauflösung: "+ +text(index)+" nicht auf stack")FI UNTIL CONCR (s.st(i).kn)=indexPER ; +neuersohnindex:=s.st(i).indexEND PROC search;INT PROC hoehe(STACK CONST s):s. +top-1END PROC hoehe;BOOL PROC voll(STACK CONST s):s.top=maxhoeheEND PROC voll +;BOOL PROC leer(STACK CONST s):s.top=bottomEND PROC leer;END PACKET +systembaum; + |