Ontwerp van een Formule Editor
download tree exerciser program download tree exerciser Delphi project

Inleiding

Mijn wiskunde editor (in aanbouw) heeft de volgende onderdelen:
    - tekst met formules (wortels, breuken, machten, haakjes...)
    - tekeningen (punten,lijnen, cirkels,ellipsen)
    - meetkundige constructies (hoogtelijn, deellijn, loodlijn, in- en omgeschreven cirkels...)
    - grafieken
In dit artikel wordt het ontwerp beschreven van de tekst editor.

Tekst met formules

    wat we niet willenwat we wel willen
    x^(2x-1)
    x/(2x-1)
    sqrt(2x-1)

Automatische aanpassingen

De volgende eisen worden gesteld aan de automatische aanpassingen:
    - horizontaal centreren van teller en noemer in een breuk
    - wortelteken en breukstreep groeien mee met de breedte van de tekst
    - haakjes groeien mee met de hoogte van de tekst
    - teller en noemer van een breuk passen hun vertikale positie aan de hoogte aan

Aanpak

1. Ga uit van een vel papier van A4 formaat
2. Plaats hierop elementen. Een element is een rechthoek met een bepaalde inhoud

Elementen zijn bijvoorbeeld:
    - characters
    - regels tekst (lijnen)
    - haakjes, machten, indices, breuken, wortels, matrices, tabellen
    - symbolen als : S ,Õ , ò
De elementen hebben eigenschappen en procedures:
    elementeneigenschappenprocedures
    algemeenpositie (x,y)editing
    breedte,hoogte: dx,dy
    relatie andere elementen
    specifiekcodecreate
    fontpaint
    lijndikte,kleurencalculate{dx,dy..}

Hieronder staat een pagina met een regel tekst met daarin een wortel.
De afmetingen van het wortelteken moeten zich aanpassen aan de breedte en de hoogte van de lijn onder het wortelteken.

Probleem

Hoe geven we relaties tussen elementen aan?
    - hoe "ziet" een lijn of wortelteken dat hij moet krimpen of verlengen?
    - hoe "weet" een lijn dat de characters opnieuw uitgelijnd moeten worden?
We gaan te rade bij de Grafentheorie
Een Graaf is een tekening met punten.
Die punten kunnen (wel/niet) met lijnen zijn verbonden.

Grafentheorie wordt toegepast bij:
    - wegenkaarten en plattegronden
    - chemische formules
    - industriële planning
    - ICT
      - computerspelletjes
      - file systemen
      - editing

Een speciaal soort Grafen is de Boom
Eigenschappen van een Boom (Tree) zijn:
    - geen losse punten
    - geen rondwegen: als 1 verbinding wegvalt, dan ontstaat een losse tak
    - de heenweg van A naar B = de terugweg van B naar A
Hieronder staat een voorbeeld van een boom:
De punten zijn hier de elementen, een lijn geeft een relatie aan: het ene element is afhankelijk van het andere.

Soorten relaties

een regel (lijn) bevat 3 tekens.
Die tekens zijn onderdeel van de regel.
De regel noemen we ouder (parent) , de tekens zijn onderdeel van de regel en die noemen we de kinderen (children).
De breedte en hoogte van de regel is afhankelijk van de totale breedte van de letters en van de hoogste letter.

Probleem

Een parent kan veel children hebben.
Het is onhandig om per element een array te reserveren om alle eventuele kinderen in op te slaan.

Oplossing

    - Een parent kan naar 1 child verwijzen
    - Een child kan weer naar een volgend child verwijzen, enzovoorts
Een element ziet er dan zo uit:
Vier variabelen verwijzen naar de parent, child of het volgende child van de parent next.
Previous verwijst naar het vorige kind van de parent.

Parent en previous zijn niet strikt noodzakelijk om de relaties aan te geven, maar ze vergemakkelijken
het navigeren door een boom omdat de terugweg niet onthouden hoeft te worden.

Als een element geen children heeft, dan is het veld children = 0 .
Voor het eerste kind geldt: previous = 0, voor het laatste geldt next = 0.

Voor ICT toepassingen is een andere notatie van een boomstructuur handiger

Definitie van een element

type Telementtype = elfree,elDoc,elPage,elStrip,elFrame,
                    elBG,elImage,elTable,elCoord,elLine,
                    elText,elChar);

     TElement = record
                 elType  : TelementType;
                 elCode  : byte;
                 p1      : byte;
                 p2      : byte;
                 p3      : word;
                 p4      : word;
                 x1      : word;
                 y1      : word;
                 dx      : word;
                 dy      : word;
                 parent  : dword;
                 child   : dword;
                 next    : dword;
                 previous: dword;
                end;
Elementen staan in een array[1... ] dus hebben meteen een nummer ( > 0 )

const maxElement = 500000; 
....
....
var element : array[1..maxelement] of TElement
Een element heeft twee soorten eigenschappen:
    voor elk element gelijk x, y : positie relatief tov parent. Parent berekent x, y
    dx, dy : breedte en hoogte, element berekent dit zelf
    type : het type element
    parent, child, next, previous : verbinding met andere elementen
    element specifiekcode : nadere omschrijving van de inhoud
    p1 .. p4 : eigenschappen of verwijzing naar tabellen met eigenschappen
    (lijndikte, kleur, font.....)

Handig : Edit procedures zijn voor alle typen elementen gelijk! (maar het effect niet)

Hieronder staat een regel tekst met daaronder de boomstructuur


Opmerking:
    - horizontale lijnen geven een parent-child relatie aan
    - vertikale lijnen geven een next-previous relatie aan, dus zijn children

Navigeren door een boom

function ParentEl(var nel : dword) : boolean;
function ChildEl(var nel : dword) : boolean;
function NextEl(var nel : dword) : boolean;
function previousEl(var nel : dword) : boolean;
Als element nel een parent( child, next, previous) heeft, dan wordt nel hierdoor vervangen
en het result van de functie is true. 
function ParentEl(var nel : dword) : boolean;
var e : dword;
begin
 e := element[nel].parent;
 if e > 0 then
  begin
   nel := e;
   result := true;
  end else result := false;
end;

function NextEl(var nel : dword) : boolean;
var e : dword;
begin
 e := element[nel].next;
 if e > 0 then
  begin
   nel := e;
   result := true;
  end else result := false;
end;

function ScanElement(var elmnt : dword; lt : TLinkType)
                    : TLinktype;
Deze functie stapt systemetisch door een boom, van voor naar achter en weer terug.
Element elmnt wordt vervangen door het volgende element van de boom.
Een nieuwe stap is afhankelijk van de vorige.
Het TLinktype functieresultaat geeft de laatste stap aan. 
type TLinkType = ltNone, ltParent, ltChild,ltNext, 
                 ltPrevious);
...............
function ScanElement(var elmnt : dword; lt : TLinktype)
                     : TLinktype;
//walk thru tree, children first then next (down)
//replace elmnt by next element
begin
 result := ltNone;
 if (lt = ltChild) or (lt = ltNext) then
  begin
   if childEl(elmnt) then result := ltChild
    else
     if nextEl(elmnt) then result := ltNext
      else
       if previousEl(elmnt) then result:=ltPrevious
        else
         if parentEl(elmnt) then result := ltParent;
  end;
 if result <> ltNone then exit;

 if lt = ltPrevious then
  begin
   if previousEl(elmnt) then result := ltPrevious
    else if parentEl(elmnt) then result := ltParent;
  end;
 if result <> ltNone then exit;

 if lt = ltParent then
  begin
   if nextEl(elmnt) then result := ltNext
    else if previousEl(elmnt) then result := ltPrevious
     else if parentEl(elmnt) then result:= ltParent;
  end;
end;

Toepassing van scanline(...) functie

    - tijdens weg ....parent ---> child.... afmetingen van children berekenen
    - tijdens terugweg ....child ---> parent... afmetingen van parent en posities van children berekenen.
    - element verwijderen inclusief children
    - de boomstructuur tekenen

Elementen editen

1. Element plaatsen na een ander element 
procedure PlaceELA(del,sel : dword);
2. Element plaatsen vóór een ander element
procedure PlaceELB(del,sel : dword);
opmerking:
- del = destination element (hieronder A of B)
- sel = selected element (hieronder X)

plaats X na A (of plaats X voor B):

    A.next was B, wordt X
    B.previous was A, wordt X
    X.parent = A.parent
    X.previous = A
    X.next = B
3. Element plaatsen als laatste kind van een ander element (place child after)

procedure PlaceChildA(del,sel : dword);
(sel wordt het laatste kind van element del)

4. Element plaatsen als eerste kind van een ander element (place child before)
procedure PlaceChildB(del,sel : dword);
(sel wordt het eerste kind van element del)

(hierboven is sel = X en del = A)

Opmerking:
als element del geen children heeft dan is er geen verschil tussen procedures 3. en 4.

5. Een element door een ander element vervangen
procedure ReplaceEL(del,sel : dword);
Element del wordt vervangen door sel.

Opmerkingen:
    - bij place... procedures kan het geselecteerde element deel van de boom zijn.
    In dat geval wordt sel eerst losgemaakt.
    - bij replace mag sel geen deel van de boom uitmaken, het moet een ongebruikt element zijn.
...place... zijn eigenlijk verplaats operaties

6. Een element verwijderen 
procedure deleteEL(del : dword);
(verwijdert element del, maar de informatie blijft behouden)

Voor het losmaken van een element uit de boom ("plukken") wordt gebruikt: 
function pickEL(pel : dword) : TEditAction;
//extract element pel from tree
//save link info
var par,nxt,prv : dword;
begin
 with result do
  begin
   linkEL := getELlink(linktype,pel);
   if linkType <> ltNone then
    begin
     with element[pel] do
      begin
       par := parent;
       nxt := next;
       prv := previous;
      end;
     if prv > 0 then element[prv].next := nxt
      else if par > 0 then element[par].child := nxt;
     if nxt > 0 then element[nxt].previous := prv;
    end;//if link
  end;//with result
end;
Opmerking:
Funtie getELlink levert het element waaraan het verwijderde element gelinkt was, met het type link.
Voorkeur hierbij heeft next, daarna previous, daarna parent.

Het UNDO systeem

Edit-acties ...place...placeChild...replace...delete moeten ongedaan gemaakt kunnen worden.
Methode:
    - per editstap wordt informatie in een array UndoList[ ] opgeslagen. 
type TELaction = (eaPlaceA, eaPlaceB, eaPlaceChildA, 
                  eaPlaceChildB,eaReplace, eaDelete, 
                  eaUndo,eaNone);

     TEditAction=record
                  action  : TELaction;
                  elmnt   : dword;//element
                  linkEL  : dword;//old element link
                  linkType: Tlinktype;//type of link
                  bwlink  : boolean;//backward link
                 end;

const maxundo = 25;//undo actions
.......
var undolist : array[1..maxundo] of TEditAction;
maxundo is het maximale aantal undo stappen.
Als een element wordt verplaatst, dan is linkEL het element waarmee het verplaatste was verbonden in de boom.
Linktype is dan het soort link.

Gelinkte UNDO akties (meerdere elementen)

Eén edit-aktie kan meerdere elementen omvatten. (bijvoorbeeld 3 elementen verwijderen)
Door een vlag te zetten (bwlink) worden UNDO opdrachten gelinkt, ze vormen dan samen één opdracht.
Hieronder staat een afbeelding van het undo array met editakties:

Na maxundo edit stappen is het undo-stack vol.
Bij de volgende editstap wordt het stack 1 positie naar boven geshift, zodat de laatste entry vrijkomt.
De shift overschrijft undolist[1] , deze edit-aktie kan dus niet meer ongedaan worden gemaakt.
Als undolist[1] een delete of replace operatie was, dan wordt het betreffende element vrijgemaakt voor hergebruik door: 
procedure destroyEL(del : dword);
destroy wist alle informatie van het element en zijn children, zodat ze opnieuw gebruikt kunnen worden.

De tree-exerciser

Om de tree operations te testen is een exerciser programma geschreven.
Dit Delphi-7 project omvat:
    - unit1
      - knoppen voor de edit akties
      - bitmap bm en paintbox treebox voor de afbeelding van de tree
      - paintbox actionbox voor display van het UNDO stack
      - statictext componenten voor weergave van element eigenschappen
    - tree_unit
      - data definities en procedures voor tree bewerkingen
Hieronder staat een afbeelding van de tree-exerciser:

Plaats de muiswijzer over een element, druk de muisknop in en houd ingedrukt.
Sleep het element naar een ander element om de geselecteerde aktie uit te voeren.

Voor deze exerciser is als element specifieke eigenschap ingevoerd:
- marked (kleurt het element geel, display eigenschappen)

X en Y zijn de plaats van het element op de paintbox en niet de positie relatief tov de parent.

type TElement = record
                 eltype : TElementType;
                 marked : boolean;
                 x,y    : word;
                 parent : dword;
                 child  : dword;
                 next   : dword;
                 previous : dword
                end;

Exerciser knoppen

    placeA,Bsleep element naar ander om het ervoor (erachter) te plaatsen
    placeChildA,Bsleep element naar ander om het als child (vooraan, achteraan) te plaatsen
    replacesleep vrij element naar te vervangen element
    markmarkeer een element met een muisklik
    deletedelete een element met een muisklik
    initmaak nieuwe boom met alleen element 1
    verwijder de undo list
    linksmeedt volgende editakties aaneen tot één aktie
    scanmarkeert het volgende element
    undomaak laatste bewerking ongedaan
    purgemaak alle akties in de undolist ongedaan, wist het undo stack
    elementgeeft overzicht van alle elementen
    zwart: ingebruik
    rood: deleted
    groen: vrij

Tekenen van de boom

procedure paintTree;
//calculate element x,y & paint
var elmnt : dword;
    mcode : TLinktype;//movecode 
    posX,posY : byte;
    pnt : boolean;  //paint flag
begin
 clearbm;
 elmnt := 1;  //eerste element
 posX := 1;   //positie (1,1)
 posY := 1;
 mcode := ltChild;//start zoekrichting
 pnt := true;
 repeat
  if pnt then paintElementNr(elmnt);
  mcode := ScanElement(elmnt,mcode);
  case mcode of
   ltParent : dec(posX);
   ltChild  : inc(posX);
   ltNext   : inc(posY);//Y wordt alleen verhoogd
  end;
  pnt := (mcode = ltChild) or (mcode = ltNext);
  if pnt then
   with element[elmnt] do
    begin
     x := posX;//geef element zijn plaats
     y := posY;
    end;
 until mcode = ltNone;
 paintFreeElements;
 form1.treebox.Canvas.Draw(0,0,bm);
end;
Voor verdere details verwijs ik naar de source code van het project.

Zie top van de pagina om de .exe van de exerciser of het gehele Delphi-7 project te downloaden.

Opmerking:
het project gebruikt de davArrayButton component.
Dit component staat op deze website beschreven.
Maar arraybuttons kunnen ook door speedbuttons worden vervangen.