Eindverslag. Versiebeheer Repository Invantive Producer. Versie 1.0 Wouter Vos Project: C412 Proces: t20879 Laatst bewerkt:

Eindverslag

Versiebeheer Repository IP

Eindverslag Versiebeheer Repository Invantive Producer Versie 1.0

Wouter Vos

Project: C412

Proces: t20879

Laatst bewerkt: 01-03-2012

Wouter Vos

1/53

Eindverslag


Voorwoord Ik studeer Technische Informatica en werk graag aan technische software oplossingen. Ter afronding van mijn studie heb ik mijn afstudeeropdracht uitgevoerd bij Invantive in Harderwijk. De producten die deze afstudeerperiode heeft voortgebracht zullen binnen Invantive gebruikt worden bij het beheren van specificaties op basis waarvan software gemaakt wordt. Gegenereerde software wordt steeds belangrijker. Ik ben dan ook erg blij om bij Invantive aan een dergelijk technisch en relevant project gewerkt te hebben. Als programmeur sta je bij Invantive midden in een dynamisch en professioneel bedrijf en werk je in een informele en constructieve werkomgeving. Mijn dank gaat uit naar Patrick Hofman voor goede begeleiding en hulp bij technisch moeilijke stukken. Guido Leenders heeft veel nuttige feedback gegeven. Johan de Zwaan verzorgde fijne woonruimte in de buurt van Invantive en heeft mij uitgelegd hoe Invantive Producer en Invantive Studio werken. Leoni Heijman en Paul Lindhout hebben een aantal keer geholpen met grammatica en zinsopbouw.

Wouter Vos

2 / 53

Eindverslag


Samenvatting Invantive is een softwarebedrijf dat projectmanagement software voor bedrijven maakt. Daarvoor hebben ze Invantive Producer. Het genereert op basis van specificaties een softwarepakket. Die staan opgeslagen staan in een repository. De afstudeeropdracht is het ontwikkelen van een versiebeheersysteem voor die specificaties dat volledig in Invantive Producer geïntegreerd is. Invantive moet regelmatig wijzigingen aanbrengen in de specificaties op basis waarvan software wordt gegenereerd. Via de huidige werkwijze zijn er nogal wat beperkingen aan het maken van die wijzigingen. Voor het beheren van wijzigingen aan specificaties zullen toevoegingen gemaakt moeten worden op Invantive Studio; een nieuwe applicatie voor het werken met Invantive Producer. Als gereedschap heeft de afstudeerder vooral gebruik gemaakt van Microsoft-technologie. De uitvoering van deze opdracht begon met een onderzoek naar versiebeheer. Het prototype dat daarop volgde bleek niet op Invantive Producer aan te sluiten. Daarom is in overleg besloten niet in een keer een prototype te ontwikkelen, maar stap voor stap functionaliteit toe te voegen aan het bestaande systeem. Om dit te bereiken zijn we overgestapt op een iteratief ontwikkelmodel. Hierdoor konden we het bereik beter beheersen en steeds als een deelproduct af was gaf de opdrachtgever feedback. Programmeurs die direct op de database van Invantive werken hebben nu een functie om het verschil tussen twee teksten te berekenen. Gebruikers van Invantive Studio kunnen een venster oproepen dat in detail de verschillen tussen de onderdelen van twee versies van een specificatie visualiseert. Daarnaast kunnen ze in detail de verschillen tussen de eigenschappen van specificaties of hun onderdelen zien. Het resultaat is dat de gebruiker precies kan ontdekken wat de verschillen zijn tussen specificaties. Invantive is zeer tevreden met het resultaat, gebruikt het bij de ontwikkeling van hun specificaties en zal het in de toekomst uitbreiden tot een volledig versiebeheeersysteem.

Wouter Vos

3 / 53

Eindverslag


Inhoudsopgave

Voorwoord ......................................................................................................................... 2 Samenvatting...................................................................................................................... 3 Inhoudsopgave ................................................................................................................... 4 1

Inleiding ...................................................................................................................... 6

2

Invantive ..................................................................................................................... 7 2.1 2.2

3

Probleemanalyse ......................................................................................................... 9 3.1 3.2 3.3

4

Organisatie ..................................................................................................................... 7 Werkomgeving............................................................................................................... 8 Probleemsituatie ........................................................................................................... 9 Werkwijze ...................................................................................................................... 9 Probleemstelling ............................................................................................................ 9

Bereik ........................................................................................................................ 10 4.1 4.2 4.3

Prototype ..................................................................................................................... 10 Verschilfunctie ............................................................................................................. 10 Invantive Studio ........................................................................................................... 10

5

Planning .................................................................................................................... 11

6

Methoden en Technieken .......................................................................................... 12 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10 6.11 6.12

7

Inleiding ....................................................................................................................... 12 Interview ...................................................................................................................... 12 Waterval ontwikkelen.................................................................................................. 12 Iteratief ontwikkelen ................................................................................................... 12 Model View ViewModel .............................................................................................. 12 Mockup ........................................................................................................................ 13 C# ................................................................................................................................. 13 .NET Framework .......................................................................................................... 13 PL/SQL .......................................................................................................................... 14 WPF ............................................................................................................................. 14 Infragistics ................................................................................................................... 14 Gereedschappen ......................................................................................................... 14

Vooronderzoek .......................................................................................................... 16 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8

Inleiding ....................................................................................................................... 16 Waarom versiebeheer? ............................................................................................... 16 Centraal versiebeheer ................................................................................................. 16 Gedistribueerd versiebeheer ....................................................................................... 17 Voordelen van elk type ................................................................................................ 17 Toestanden van een werkkopie................................................................................... 18 Op een database werkt het anders ............................................................................. 18 Functies en kwaliteiten ................................................................................................ 19

Wouter Vos

4 / 53

Eindverslag 8

Uitvoering ................................................................................................................. 20 8.1 8.2 8.3 8.4 8.5 8.6 8.7

9


Inleiding ....................................................................................................................... 20 Waarom verschillen berekenen................................................................................... 20 Verschil algoritme ........................................................................................................ 20 Snel algoritme .............................................................................................................. 22 Welke eigenschappen zijn verschillend ....................................................................... 23 Visualiseer verschillen tussen eigenschappen............................................................. 24 Visualiseer verschillen tussen de specificaties ............................................................ 24

Resultaten ................................................................................................................. 26 9.1 9.2 9.3 9.4 9.5 9.6 9.7

Inleiding ....................................................................................................................... 26 Verschilberekening ...................................................................................................... 26 Snelle Verschilberekening............................................................................................ 26 Welke eigenschappen zijn verschillend? ..................................................................... 26 Verschillen tussen eigenschappen............................................................................... 27 Verschillen tussen inhoud specificaties ....................................................................... 30 Prestaties berekening verschil tussen specificaties .................................................... 32

10 Conclusie ................................................................................................................... 33 10.1 10.2 10.3 10.4

Verschillen zijn duidelijk zichtbaar ........................................................................... 33 Persoonlijk ................................................................................................................ 33 Advies voor de opvolger .......................................................................................... 33 Advies voor leidinggevende bij Invantive ................................................................ 33

11 Woordenlijst ............................................................................................................. 35 12 Bibliografie ................................................................................................................ 36 13 Bijlagen ..................................................................................................................... 37 13.1 13.2 13.3 13.4 13.5 13.6

Oorspronkelijke tijdsindeling afstudeerperiode ...................................................... 37 Gerealiseerde tijdsindeling afstudeerperiode ......................................................... 37 Prestaties van algoritmen die verschillen berekenen.............................................. 38 PL/SQL verschilberekening....................................................................................... 39 C# snelle verschil berekening................................................................................... 41 PL/SQL snelle verschil berekening ........................................................................... 44

Wouter Vos

5 / 53

Eindverslag

1


Inleiding

Als onderdeel van zijn afstudeerstage heeft Wouter Vos, vanaf nu de ‘afstudeerder’ deze scriptie geschreven. In het kader van zijn opleiding HBO Technische Informatica bij Avans hogeschool in Breda heeft de afstudeerder het project Versiebeheer Repository Invantive Producer uitgevoerd. Opdrachtgever voor dit project is Guido Leenders, eigenaar en directeur van Invantive. Invantive is een klein softwarebedrijf. Het werkproces voor de ontwikkeling van hun automatisch gegenereerde software mist de volledige ondersteuning van een versiebeheersysteem. Daarom heeft de afstudeerder een literatuurstudie uitgevoerd om een beeld te krijgen van hoe de belangrijkste versiebeheersystemen werken. Dit gecombineerd met bestaande kennis over databases heeft geleid tot inzicht over hoe versiebeheer op een database zal werken. Daarna is die kennis toegepast door het systeem bij Invantive uit te breiden. De resultaten kunt u verder in dit verslag lezen.

Wouter Vos

6 / 53

Eindverslag

2


Invantive

2.1

Organisatie

Invantive maakt projectmanagement software voor bedrijven [1]. De organisatie heeft een platte structuur. Het werk verloopt altijd gezellig en informeel. De afstudeerder kent het personeel dat op het kantoor in Harderwijk werkt persoonlijk. Zij zijn HBO of universitair opgeleid [2] en vervullen meerdere rollen: -

Guido Leenders,

-

Patrick Hofman,

-

Bastiaan Hup,

-

Joshua Hazelaar, Juan Bijzeit, Johan de Zwaan, Hans Busschers, Wouter Vos,

vervult o.a. de rollen van directeur-eigenaar, programmeur, verkoper support medewerker en kantoorinrichter; vervult o.a. de rollen van programmeur, verkoper, leidinggevende, support en bezoekt klanten; vervult o.a. de rollen van administratief medewerker, business analist en receptionist; werkt met een iMac aan de grafische kant van de software. doet de marketing voor Invantive; werkt aan de software en doet support als niemand anders het doet; activeert zijn omgeving. Werkt aan de software; studeert Technische Informatica. Werkt voor zijn afstudeerstage aan het project Versiebeheer Repository Invantive Producer

In figuur 1 zijn de onderlinge relaties weergegeven.

Figuur 1: Medewerkers bij Invantive, pijlen geven autoriteit weer

Wouter Vos

7 / 53

Eindverslag

2.2


Werkomgeving

Invantive is gevestigd in Harderwijk in pand waar in een ruimte voor elke medewerker een werkplek aanwezig is. Hierdoor kunnen werknemers gemakkelijk met elkaar communiceren en samenwerken. De server verzorgt voor iedere werknemer een virtuele desktop omgeving die op elke werkplek kan worden aangeroepen. Tijdens de afstudeerperiode is er regelmatig overleg tussen de afstudeerder en de bedrijfsbegeleider Patrick Hofman. Dan worden de voortgang en wat er de komende periode nog moet gebeuren besproken. Bij problemen die tussentijds de kop op steken zijn hij en Johan de Zwaan de vraagbaak waarbij de afstudeerder terecht kan. Op grond van deze intensieve contacten beoordeelt hij het werk van de afstudeerder. Hij doet dit in samenspraak met de opdrachtgever Guido Leenders. Naast opdrachtgever treedt hij ook op in de rol van eindgebruiker. Invantive heeft als uitgangspunt dat ze hun eigen software ook zelf gebruiken, dat geldt ook voor dit project. In eerste instantie zullen de medewerkers van Invantive gebruik maken van de producten die dit project oplevert.

Wouter Vos

8 / 53

Eindverslag

3 3.1


Probleemanalyse Probleemsituatie

Invantive maakt een standaard softwarepakket dat bij meerdere klanten in gebruik is. De software wordt per klant naar wens aangepast waardoor klanten het ervaren als op maat gemaakte software. Invantive verzorgt ook de ondersteuning voor deze software en dus moeten regelmatig aanpassingen worden uitgevoerd. Invantive Producer ‘(IP)’ is het belangrijkste softwarepakket van Invantive; het genereert projectmanagement software op basis van een ontwerp. IP is zo krachtig dat het ook gebruikt wordt om zichzelf te genereren. Invantive werkt continu aan de doorontwikkeling van IP en dus ook aan de gebruikte specificaties. Die ontwikkeling is echter lastiger dan de ontwikkeling van andere software. Omdat er geen adequaat versiebeheersysteem bestaat voor het opgeslagen ontwerp. Hierdoor kunnen ontwikkelaars niet gelijktijdig aan een specificatie voor IP werken. Een voorbeeld van een probleem is dat een fout soms wel binnen de interne ontwikkelversie van Invantive opgelost is, maar nog niet in de versie bij de klant. Het is dan gebruikelijk dat de versie die bij de klant geïnstalleerd staat ook aangepast wordt. Alleen het lastig te zien hoe de aanpassing bij de klant gerealiseerd kan worden. Soms is de klantsituatie zodanig verouderd dat de huidige oplossing niet meer van toepassing is. Mede hiervoor wordt bij wijzingen in het ontwerp ook de oude versie bewaard. Wanneer een programmeur een wijziging uitvoert wordt deze de daaropvolgende nacht getest en binnen het bedrijf uitgerold. Het programma IP verandert daardoor intern voortdurend, maar dat geldt niet automatisch voor de versies die bij klanten geïnstalleerd zijn.

3.2

Werkwijze

De afstudeerder kreeg een introductie in het programma Invantive Producer ofwel IP. Hierbij werd uitgelegd hoe Invantive Producer werkt en de specificatie aangepast kan worden. Ook stelde de afstudeerder regelmatig vragen over IP en voerde gesprekken met collega’s over IP. Door al die bronnen te combineren kreeg de afstudeerder een duidelijk beeld van de werking van IP. Gemiddeld wordt er eens in de maand bedrijfsoverleg gevoerd, dan bespreekt de eigenaar met alle medewerkers de bedrijfsvoering. Door hieraan deel te nemen heeft de afstudeerder veel kennis opgedaan over het interne werkproces en de situaties bij klanten.

3.3

Probleemstelling

De specificaties voor IP worden momenteel bewerkt vanuit een Excel bestand dat via een traditioneel versiebeheersysteem opgeslagen wordt. Dat systeem kan alleen verschillen berekenen tussen tekstbestanden. Hierdoor is er onvoldoende ondersteuning van de werkprocessen die bij software ontwikkeling heel gebruikelijk zijn. Invantive wenst daarom een versiebeheersysteem dat aansluit bij de structuur van IP.

Wouter Vos

9 / 53

Eindverslag

4 4.1


Bereik Prototype

De eerste stap bij de uitvoering van deze afstudeerstage zou een prototype voor versiebeheer op een database opleveren. Daarna zou dat uitgebreid worden met meer functionaliteit. Tijdens de uitvoering van het project bleek dat het bouwen van een volledig systeem in één keer te moeilijk was en te weinig zou aansluiten op IP. Daarom werd in overleg met de opdrachtgever en bedrijfsbegeleider besloten om over te gaan op een iteratieve ontwikkelmethode. Hierbij wordt in eerste instantie een onderdeel volledig ontwikkeld. Pas wanneer de opdrachtgever daar tevreden over is begint de uitvoerder met het volgende onderdeel.

4.2

Verschilfunctie

In week 12 van het project (19 november) bleek het bouwen van een volledig systeem voor de afstudeerder toch te moeilijk en werd in overleg met de afstudeerdocent besloten de focus te richten op de verschilfunctie. Dit gereedschap heeft tot doel inzichtelijk te maken welke rijen in de database van elkaar verschillen. Diezelfde functionaliteit dient ook van toepassing te zijn op bedrijfsobjecten, die soms verspreid over meerdere tabellen staan opgeslagen. Het verschil wordt alleen berekend tussen teksten. Andere datasoorten kunnen immers niet deels gewijzigd worden. Een getal bijvoorbeeld kan je niet een beetje veranderen; als het ook maar met 1 verhoogd wordt is het een volledig nieuw getal. In figuur 2 staan twee voorbeeld van teksten die aanzienlijk veranderd zijn:

Figuur 2: Twee Eigenschappen die behoorlijk veranderd zijn.

4.3

Invantive Studio

Invantive Studio is een nieuwe applicatie van Invantive, het wordt gebruikt om de specificaties voor IP te beheren. Aan het begin van de afstudeerperiode werd dat met Excel gedaan, dat is steeds meer overgenomen door Invantive Studio. De functionaliteit met een visuele interface is aan de applicatie ‘Invantive Studio’ toegevoegd. Het is de bedoeling dat Invantive Studio uitgebreid word om de volledige functionaliteit van een versiebeheer systeem te bieden.

Wouter Vos

10 / 53

Eindverslag

5

Planning

Startdatum: 20 augustus 2012 Einddatum:

25 januari 2013

Vakantie:

De weken van 10 en 17 augustus 2012

Totale duur: 21 weken In overleg met de opdrachtgever en bedrijfsbegeleider is er aan het begin van de afstudeerperiode een planning gemaakt. Die is te zien in bijlage 13.1. De vakantieperiode is afgesproken omdat de bedrijfsbegeleider toen met vakantie was. Gedurende de afstudeerperiode bleek echter dat de planning anders gestructureerd moest worden. Ook bleek het niet praktisch direct na de afstudeerperiode de afstudeerpresentatie te houden. Die werd twee maanden later ingepland. Gedurende die twee maanden heeft Invantive een werkplek voor de afstudeerder beschikbaar gehouden. De afstudeerder heeft daar gebruik van gemaakt en vooral gewerkt aan het verslag, de poster en zijn afstudeerpresentatie. Maar kon ook enkele verbeteringen aan het eindproduct realiseren. De gerealiseerde planning is te zien in bijlage 13.2 en heeft een totale duur van 30 weken.

Wouter Vos

Eindverslag

6 6.1


Methoden en Technieken Inleiding

In dit hoofdstuk komen de belangrijkste methoden en technieken aan bod die tijdens deze afstudeerperiode zijn gebruikt. Tevens worden de gebruikte gereedschappen besproken.

6.2

Interview

Tijdens de eerste weken van zijn stage kreeg de afstudeerder een introductie in het ontwikkelen van software met Invantive Producer. Hierbij werd aandacht besteed aan de werking van het programma met ruimte voor vragen.

6.3

Waterval ontwikkelen

Om een goed overzicht te krijgen in hoe een versiebeheersysteem geïmplementeerd moet worden, begon de afstudeerder via een waterval model met de ontwikkeling van een prototype.

6.4

Iteratief ontwikkelen

Bij deze ontwikkelmethode bouwt de ontwikkelaar steeds een zo klein mogelijk onderdeel van de uiteindelijke applicatie. Daarna wordt dit voorgelegd aan de opdrachtgever, klant en eindgebruiker die dan feedback geven over het ontwikkelde onderdeel. Het doel hiervan is de ontwikkelaar zo snel mogelijk bij te sturen als het ontwikkelproces de verkeerde kant op gaat.

6.5

Model View ViewModel

Een techniek met als doel om alles wat met het uiterlijk van het venster te maken heeft op één plek declaratief te definiëren. Om dit te realiseren is er apart ruimte gereserveerd voor het opslaan van gegevens en ruimte voor alle overige zaken. Die overige zaken bestaan meestal uit het berekenen van resultaten en toepassen van relevante logica. Declaratief betekent dat de ontwikkelaar aangeeft wat het resultaat moet zijn. Dit is het tegenovergestelde van procedureel. Waarbij de programmeur een aantal precieze opdrachten geeft die de computer uitvoer waarna een resultaat bereikt wordt. Het model bevat informatie die weergegeven wordt en die de gebruiker kan wijzigen. Dit verbetert uitbreidmogelijkheden en hergebruik van code. De view is zoveel mogelijk beschreven in een declaratieve taal. Dit maakt het mogelijk voor niet-technische ontwikkelaars een grote bijdrage te leveren aan het uiterlijk van het venster. Het ViewModel verzorgt de communicatie tussen deze twee onderdelen. Hier kan ook alle overige functionaliteit toegevoegd worden.

Wouter Vos

12 / 53

Eindverslag

6.6


Mockup

Voordat ontwikkelaars beginnen met het schrijven van code voor een nieuw venster is het goed om het ontwerp voor het venster vast te stellen. Hierin is te zien hoe het venster er ongeveer uit komt te zien en welke functies de gebruiker kan oproepen. Een mockup is in korte tijd samen te stellen en laat duidelijk zien welke functionaliteit waar kom te zitten. Hierop kan de klant meteen feedback geven en kan het ontwerp zonder tijdverspilling bijgesteld worden. Bij het ontwikkelen van de functionaliteit “Welke eigenschappen zijn verschillend” heeft het maken van een mockup de afstudeerder veel werk bespaard. Na feedback van de klant moest het ontwerp twee keer volledig omgegooid worden.

Figuur 3: Een mockup in Balsamiq geeft een idee weer

6.7

C#

Een moderne programmeertaal gebaseerd op C++, Java en Visual Basic. Modern betekent dat het geheugengebruik automatisch beheerd wordt. Dit voorkomt fouten en versnelt het ontwikkelproces. Een nadeel is dat sommige optimalisatietechnieken niet meer mogelijk zijn en de programmeur minder direct toegang heeft tot de hardware. Echter het automatisch geheugenbeheer is zo goed dat de meeste programma’s in C# beter presteren dan wanneer ze in C++ geschreven zouden zijn. Verder werkt C# vanuit het door Microsoft ontwikkelde .NET Framework.

6.8

.NET Framework

Wouter Vos

13 / 53

Eindverslag


Een flexibel platform, ondersteunt meerdere talen, technieken en mogelijkheden om deze met elkaar te integreren. Ook biedt het .NET Framework een uitgebreide set hulpmiddelen die het ontwikkelen van software makkelijker maken. Verder zijn er bedrijven die pakketten functionaliteit speciaal voor het .NET Framework ontwikkelen.

6.9

PL/SQL

Deze taal van Oracle is gebaseerd op Ada en maakt het mogelijk op een goed gestructureerde manier programmeren. De taal maakt gebruik van Oracle technologie en is speciaal gemaakt om binnen Oracle database omgevingen uitgevoerd te worden. Hierdoor werken programma’s zeer dicht op de gegevens die opgeslagen staan in de database en kunnen ze optimaal presteren. Daarbij kan de programmeur gebruik maken van de uitgebreide functionaliteit die in elke Oracle database omgeving aanwezig is.

6.10

WPF

Windows Presentation Foundation [3] is een onderdeel van het .NET Framework speciaal voor het maken van de vensters in een applicatie. Microsoft vind dat het bepalen hoe een venster eruit ziet heel ander werk is dan bepalen hoe het technisch werkt. Daarom gaat WPF er vanuit dat het uiterlijk van het venster op een aparte plek en in een andere taal gedefinieerd word. Om dit te bereiken ondersteund WPF het Model View ViewModel ontwerp principe.

6.11

Infragistics

Infragistics levert sets visuele componenten, de nieuwste gebaseerd op WPF. Hun componenten zijn standaard veel mooier en bieden veel extra mogelijkheden. Bijvoorbeeld bij hun tabel, die biedt gebruikers standaard de mogelijkheid kolommen te verplaatsen.

6.12

Gereedschappen

‘Invantive Estate’ wordt door Invantive zelf gemaakt en gebruikt om de eigen projecten te beheren. Als werknemer bij Invantive heeft de afstudeerder deze software elke dag gebruikt, voornamelijk voor het bijhouden van de gewerkte uren. Maar ook organisatorische zaken worden vaak via de agenda van Invantive Estate geregeld. ‘Visual Studio’ is een krachtige ontwikkel omgeving voor het ontwikkelen van complexe software. Het is gemaakt door Microsoft en is dan ook bedoeld om .NET applicaties mee te maken. Het is op bijna elke denkbare manier uitbreiden, waardoor het bijvoorbeeld ook mogelijk is Java projecten te ontwikkelen. De afstudeerder heeft Visual Studio gebruikt om de aanpassingen in het programma Invantive Studio te maken. ‘Toad for Oracle’ is een programma om Oracle databases te beheren. Maar ook om PL/SQL code op die database uit te voeren. Dit was handig voor het testen van de algoritmen om verschillen te berekenen. ‘Notepad++’ is een tekst verwerker maar dan met wat functionaliteit voor programmeurs. Het standaard lettertype bevat letters die allemaal even groot zijn, waardoor code

Wouter Vos

14 / 53

Eindverslag


makkelijker te analyseren is. En het herkent de meeste programmeertalen waarbij het de sleutelwoorden herkenbaarder maakt door ze een kleur te geven. De afstudeerder heeft Nodepad++ gebruikt voor het schrijven van PL/SQL code. ‘Balsamiq’ is een tool om mockups mee te maken. De plaatjes die je ermee maakt zullen er nooit gepolijst uit zien. Dit voorkomt dat de ontwikkelaar tijd besteed om alles er netjes uit te laten zien. Daarbij is het voor iedereen duidelijk dat het om een idee gaat, zodat er geen tijd besteed wordt aan allerlei details die in de ontwerpfase niet van belang zijn. ‘Invantive Studio’ is een applicatie die door Invantive is ontwikkeld voor het beheer van de specificaties die door IP gebruikt worden. Het geeft een boomstructuur weer die te vergelijken is met de bestandstructuur op je eigen computer. Alleen bevat de structuur van Invantive Studio specificaties die bestaan uit bedrijfsobjecten in plaats van mappen en bestanden.

Wouter Vos

15 / 53

Eindverslag

7


Vooronderzoek

7.1

Inleiding

Dit hoofdstuk legt uit wat een versiebeheersysteem is [4] en bekijkt een aantal manieren waarop Versiebeheer Repository Invantive Producer zou kunnen werken. Tegenwoordig maakt ieder software project gebruik van versiebeheer en buiten de software wordt versiebeheer zeer weinig toegepast, daarom zullen gebruikte voorbeelden uit de software wereld komen.

7.2

Waarom versiebeheer?

Traditioneel zijn er meestal 5 tot 20 ontwikkelaars betrokken bij de ontwikkeling van een software project. Zij willen allemaal hun bijdrage leveren en daarvoor moeten ze vaak aan dezelfde bestanden werken. Echter wanneer zij hun werk willen samenvoegen levert dat vaak problemen op. Bijvoorbeeld: -

twee gebruikers hebben beiden hetzelfde stuk code aangepast; iemand heeft een functie aangepast of verwijderd die een anders juist ging gebruiken; een wijziging zorgt ervoor dat het programma vastloopt.

Een traditioneel versiebeheersysteem [5] maakt werkprocessen mogelijk waardoor deze problemen worden voorkomen of opgelost. Wanneer een gebruiker wijzigingen maakt kunnen andere gebruikers die aan hun eigen versie toevoegen. Als nieuwe functionaliteit problemen veroorzaakt kan gekeken worden hoe de software sinds de vorige versie veranderd is. Invantive wil deze werkprocessen ook toepassen bij de ontwikkeling van specificaties voor Invantive Producer.

7.3

Centraal versiebeheer

De meeste versiebeheersystemen worden centraal op een server geïnstalleerd waar de huidige versie van het project en alle wijzigingen tot nu toe worden bewaard. Iedere gebruiker download de meest recente versie van het project, dat heet een ‘werkkopie’. De gebruiker werkt aan de code in zijn werkkopie en controleert of het programma naar tevredenheid werkt. Wanneer de functie naar tevredenheid is geïmplementeerd geeft de gebruiker het versiebeheer de opdracht ‘commit’. Het versiebeheersysteem vergelijkt de toestand van de werkkopie en berekent welke veranderingen zijn gemaakt ten opzichte van de meest recente versie. Met de resultaten van die berekening maakt hij een ‘patch’ die alle gemaakte wijzigingen bevat. Dan wordt het meest recente versienummer verhoogd met 1. Vervolgens hebben alle andere gebruikers een verouderde versie omdat hun versienummer lager is. Iedere gebruiker kan dan opdracht geven tot een ‘update’, het systeem berekent dan welke wijzigingen die gebruiker nodig heeft. Die wijzigingen worden samengevoegd tot een patch en uitgevoerd op zijn werkkopie. Waardoor die alle wijzigingen bevat en overeen komt met de meest recente versie.

Wouter Vos

16 / 53

Eindverslag


Een belangrijke eigenschap hieraan is dat alleen de gemaakte wijzigingen uitgevoerd worden. Wanneer een ontwikkelaar bij een update een nieuwe kopie van de meest recente versie zou krijgen zouden al zijn gemaakte wijzigingen verloren gaan. In plaats daarvan worden de wijzigingen van andere ontwikkelaars op zijn werkkopie uitgevoerd en waarna hij weer verder kan werken. Verder is het mogelijk een aparte ontwikkeltak of ‘branch’ aan te vragen, bijvoorbeeld voor de ontwikkeling van een speciale functie. Het versiebeheersysteem maakt dan een apart project met een eigen geschiedenis en zonder dat andere branches aangepast worden wanneer de ontwikkelaar een commit doet. Vaak wordt de meest recente versie van de hoofdtak of ‘trunk’ gebruikt als basis waarop de ontwikkelaar dan verder kan werken zonder zich zorgen te maken over het veroorzaken van fouten of, of de wijzigingen van andere ontwikkelaars in de weg zullen zitten. Het is meestal de bedoeling dat die functie uiteindelijk samen gevoegd wordt met de trunk. Daarom kunnen wijzigingen op de trunk nog wel op de onafhankelijke tak worden uitgevoerd, zodat het samenvoegen zo eenvoudig mogelijk is.

7.4

Gedistribueerd versiebeheer

Een recente ontwikkeling is versiebeheer dat bij iedere gebruiker geïnstalleerd staat; hierdoor heeft iedere gebruiker de hele geschiedenis van het project [4] [6]. Een commit maakt geen verbinding meer met een centraal systeem in plaats daarvan wordt het werk meteen lokaal opgeslagen. Wanneer de gebruiker een stukje gewerkt heeft kan hij meteen een commit uitvoeren om het werk op te slaan. Pas wanneer een functie klaar is voor gebruik en de gebruiker beschikking heeft over een internetverbinding geeft hij opdracht tot een ‘push’. Dan worden alle wijzigingen samengevoegd in een patch en aan collega’s beschikbaar gemaakt. Die collega’s kunnen vervolgens zelf beslissen of ze de wijzigingen willen hebben en geven dan opdracht tot een ‘pull’. Een voordeel hiervan is dat de gebruiker geen verbinding met andere gebruikers of het internet nodig heeft om zijn werk op te slaan. Hierdoor worden opdrachten aan het versiebeheer meestal veel sneller uitgevoerd. Ook heeft iedere gebruiker bij calamiteiten een reservekopie van het systeem, inclusief geschiedenis. Een nadeel is dat de volgorde waarop gebruikers updates binnen krijgen niet vastligt. Bij een centraal systeem kun je aan de versienummers altijd zien in welke volgorde ze gemaakt zijn. Een gedistribueerd systeem weet niet welke versienummers bij collega’s in gebruik zijn. Dit wordt opgelost door een lange willekeurige code te genereren; die bijna altijd uniek is.

7.5

Voordelen van elk type

Gedistribueerd: 1. Elke ontwikkelaar kan eenvoudig zijn wijzigingen vastleggen, zonder internetverbinding. Ze hoeven zich ook geen zorgen te maken of iedereen ze zou moeten zien; 2. Goede prestaties omdat de wijzigingen lokaal opgeslagen worden, bij de overige gegevens die allemaal lokaal aanwezig zijn; Wouter Vos

17 / 53

Eindverslag


3. Goede ondersteuning voor vertakkingen en samenvoegen; 4. Nieuwe ontwikkelaars kunnen gemakkelijk bijdragen aan het project. Gecentraliseerd: 1. Centraal geregelde authenticatie en autorisatie leiden tot betere beveiliging; 2. Een duidelijke lineair verloop van wijzingen door de geschiedenis; 3. Efficiënter gebruik van opslagruimte doordat de geschiedenis maar een keer opgeslagen wordt.

7.6

Toestanden van een werkkopie

De toestand van een werkkopie is in beide systemen op vergelijkbare manier te beschrijven. Dit plaatje geeft aan welke acties er in welke toestand mogelijk zijn.

Figuur 4: Toestanden en transities binnen de werkkopie van een gebruiker

7.7

Op een database werkt het anders

Bestaande versiebeheersystemen werken op tekstbestanden in een mappenstructuur, terwijl Versiebeheer Repository Invantive Producer op een database zal werken. Die database wordt door een server toegankelijk gemaakt, dus is het logisch om het versiebeheer ook door die server uit te laten voeren. Verder heeft iedere gebruiker bij Invantive een eigen installatie van de database, die kan als werkkopie functioneren. Met Wouter Vos

18 / 53

Eindverslag


een commit zal de gebruiker zijn werk opslaan, het werk naar collega’s beschikbaar maken zal een aparte functie worden. Om het versiebeheer te ondersteunen komt er een extra database die de geschiedenis van alle werkkopieën bijhoud. Hier staat elke gemaakte verandering in. Een gebruiker kan met een commit natuurlijk veel veranderingen maken, dus commits staan er apart in en kunnen meerdere veranderingen bevatten. Hierdoor kan een verandering door verschillende commits toegepast worden.

7.8

Functies en kwaliteiten

Doordat het versiebeheer op een database zal werken is het relatief eenvoudig zijn om het systeem bewust te laten zijn van de interne structuur. Binnen de database is namelijk expliciet opgeslagen hoe verschillende soorten data met elkaar verbonden zijn. Bijvoorbeeld: Een bedrijf heeft een aantal medewerkers en veranderingen in het bedrijf kunnen invloed hebben op de medewerkers. Dit staat opgeslagen in bedrijfsobjecten en database regels. Bij software zijn er ook afhankelijkheden, maar die moeten impliciet worden afgeleid. Dat zou de werking van een dergelijk programma zeer gecompliceerd maken. Er is bij de afstudeerder geen versiebeheersysteem bekend wat hier rekening mee houdt [7]. Een aantal eigenschappen die een versiebeheersysteem op een database zal hebben: 1. Het versiebeheersysteem houdt rekening met de interne structuur in de database; 2. Elke ontwikkelaar kan committen zonder zich zorgen te maken over de rest van het project; 3. Doordat alle databases op dezelfde server beheerd worden, hoeft het versiebeheer bij opdrachten niet over net netwerk te communiceren en zullen opdrachten snel uitgevoerd worden; 4. Het systeem maakt gebruik van de structuur in de database en de specificaties waarop het versiebeheer toegepast wordt. Het zal deze kennis gebruiken om verschillende versies op een goede manier samen te voegen; 5. Goede branch functionaliteit, die neerkomt op het aanmaken van een nieuwe database; 6. Goede centrale beveiliging; 7. Een duidelijke lineaire geschiedenis; 8. Iedere database omgeving is effectief een werkkopie en een branch; 9. Het systeem bevat beveiliging die ervoor zorgt dat samenvoegen, update of commit operaties alleen volledig of helemaal niet uitgevoerd worden. Nooit gedeeltelijk.

Wouter Vos

19 / 53

Eindverslag

8


Uitvoering

8.1

Inleiding

Dit hoofdstuk gaat over de fase na het onderzoek. Het onderzoek had een ontwerp opgeleverd voor een versiebeheersysteem dat op elke database zou kunnen werken. Echter Invantive wil een versiebeheersysteem specifiek ontworpen voor IP. Dit kost minder om te ontwikkelen en onderhouden dan een systeem dat overal rekening moet houden. Ook kan het gebruik maken van de specifieke structuur van IP om extra functionaliteit te bieden. Daarbij is IP erg complex en zou het niet lukken om een volledig prototype te ontwikkelen dat wel die volledige aansluiting zou hebben met IP. Daarom hebben we in overleg besloten de planning aan te passen en over te stappen op een iteratief ontwikkelmodel. Hierdoor zou de afstudeerder steeds een enkele maar volledige functionaliteit te ontwikkelen. De eerste te ontwikkelen functionaliteit is de verschilfunctie. Die berekent verschillen tussen specificaties. Deze gegevens moeten vervolgens ook op een begrijpelijke manier aan de gebruiker getoond worden.

8.2

Waarom verschillen berekenen

Bij het werken met een versiebeheersysteem hebben gebruikers regelmatig wijzigingen gemaakt waarvan ze niet willen dat iedereen ze heeft. Een aantal voorbeelden is: -

Een bestand toegevoegd om even wat notities te maken; Iets wat specifiek voor hun systeem een beetje anders moet werken; Even een functie uitproberen (zonder gelijk een branch te maken); Het uitvoeren van een update, middenin de ontwikkeling van een functie.

Wanneer verschillen niet berekend zouden worden zouden alle gewijzigde bestanden volledig gekopieerd moeten worden. Als een gebruiker dan een update wil uitvoeren moeten alle gewijzigde bestanden volledig vervangen worden door de nieuwe versie. Hierdoor zou er effectief maar één persoon tegelijk aan een bestand kunnen werken. De berekening van verschillen zorgt ook voor een verbetering van de prestaties. In de meeste gevallen hoeven er maar enkele regels gewijzigd te worden. De meeste software projecten hebben bestanden van duizenden regels. Als die bij elke kleine wijziging allemaal over het netwerk verstuurd moeten worden wordt het systeem erg langzaam. In plaats daarvan stuur je alleen de regels die veranderen. Doordat het systeem weet wat de verschillen zijn kun je zien hoe het bestand in de loop der tijd veranderd is. Dit is erg nuttig bij het repareren van fouten waarbij je weet dat die door een recente wijziging veroorzaakt zijn.

8.3

Verschil algoritme

Als eerste stap voor de verschilfunctie was er een algoritme nodig dat verschillen zou uitrekenen. De docent geavanceerde programmeertechnieken heeft een dergelijk algoritme al een keer besproken. Dat algoritme heeft de afstudeerder omgezet naar

Wouter Vos

20 / 53

Eindverslag


PL/SQL, zodat het op de database zou werken. Dit bleek een goede oefening om PL/SQL te leren programmeren. Om snel en nauwkeurig vast te stellen of het algoritme goed werkte gebruikte de afstudeerder een aantal testcases. Deze werden bij elke test allemaal uitgevoerd en iedere keer was meteen te zien of de huidige uitvoering het goede resultaat opleverde en hoe snel dat ging. Dit eerste algoritme is vrij eenvoudig, het werkt echter anders dan bij traditionele versiebeheersystemen. Zij vergelijken bestanden op regelbasis en werken dus met twee groepen regels. Een database heeft echter tabellen met rijen. Die kunnen niet als geheel met elkaar vergeleken worden, omdat de betekenis van gegevens afhankelijk is van de cel waar ze instaan. Bijvoorbeeld: In een scenario met een tabel persoon, met daarin voor elke persoon een voornaam en achternaam. Als een persoon ‘Jensen’ als voornaam heeft en een andere ‘Jensen’ als achternaam, zijn die teksten helemaal hetzelfde. Ze hebben echter een andere betekenis. Daarom zal de gekozen oplossing steeds de inhoud van individuele cellen vergelijken. De inhoud van die cellen bestaat uit teksten die op letterbasis met elkaar vergeleken worden. Eerst wordt er een rooster gemaakt waar ruimte is voor elke letter van beide teksten en er wordt een extra regel gemaakt om het algoritme van start te laten gaan. Het vergelijken van twee teksten werkt door steeds één letter van de ene tekst met één letter van de andere tekst te vergelijken. Dan wordt in een rooster opgeslagen hoeveel wijzigingen nodig zouden zijn om de eerste tekst op dat punt in de tweede tekst te veranderen. Wanneer de letters hetzelfde zijn hoeft er in het resultaat niets te veranderen en zijn er geen kosten. Dat noemen we een ‘copy’. De kosten zijn hetzelfde als de kosten die voor de voorgangers van beide letters berekend zijn. Wanneer ze verschillen, probeert het algoritme de letter in de eerste tekst te vervangen voor de letter in de tweede. Dat noemen we een ‘replace’. De kosten worden berekend door 1 op te tellen bij de kosten die al eerder zijn berekend, voor de voorgangers van beide letters. Soms is het echter beter de letter uit de eerste groep te verwijderen. Dat noemen we een ‘delete’. Deze kosten worden berekend door 1 op te tellen bij de kosten voor de vergelijking tussen de voorganger van de eerste tekst letters (de huidige letter van die tekst vervalt) en de letter van de tweede tekst. Of het is beter een letter die in de eerste tekst niet aanwezig was uit de tweede tekst te laten staan. Dat noemen we een ‘insert’. Deze kosten bereken je door 1 op te tellen bij de kosten voor de vergelijking tussen de letter van de eerste tekst letters en de voorganger van de tweede tekst letters (de huidige letter van die tekst wordt toegevoegd). Zie Figuur 5 voor een visuele weergave van de vergelijking tussen sporten (eerste tekst) en storend (tweede tekst).

Wouter Vos

21 / 53

Eindverslag


Figuur 5: sporten vergeleken met storend, c = copy, r = replace, d = delete, i = insert

De letter s wordt gekopieerd. De letter p wordt vervangen voor de letter t. De letter o wordt gekopieerd. De letter r wordt gekopieerd. De letter t wordt verwijderd. De letter e wordt gekopieerd. De letter n wordt gekopieerd. De letter d wordt toegevoegd. Er zijn 3 operaties nodig om ‘sporten’ in ‘storend’ te veranderen. Deze uiteindelijke kosten zijn te vinden als het resultaat van de vergelijking tussen de laatste twee letters. Het verander pad bepaald hoe de ene tekst in de andere veranderd kan worden. Dit kan gevonden worden door vanaf de laatste twee letters terug te lopen en steeds de beste optie te nemen. Het algoritme bekijkt alle mogelijke verander paden en zal daardoor altijd het beste pad vinden. De berekentijd en benodigde opslagruimte voor dit algoritme zijn: lengte eerste tekst vermenigvuldigd met lengte tweede tekst. In dit voorbeeld zijn de berkenkosten 7x7 = 49 vergelijkingen. Stel dat je twee teksten heb van duizend tekens dan zijn de berekenkosten 1.000x1.000 = 1.000.000 vergelijkingen. Dat noemen we een kwadratisch algoritme.

8.4

Snel algoritme

Er zijn twee problemen met het eenvoudige algoritme. Ten eerste bevat de database regelmatig teksten die tot 4000 tekens lang kunnen zijn, wat een berekening van meerdere seconden oplevert. Ten tweede is de berekentijd afhankelijk van het aantal tekens. Het aantal wijzigingen maakt geen verschil, terwijl er meestal zeer weinig wijzigingen zijn. Hierdoor is veel winst te behalen is met een algoritme dat sneller is bij weinig wijzigingen. Daarbij berekenen traditionele versiebeheersystemen ook de verschillen tussen grote bestanden heel snel. Om vergelijkbaar resultaat te bereiken heeft de afstudeerder de volgende variaties geprobeerd: -

Alleen vergelijkingen maken wanneer het algoritme verschil in de tekst tegen komt;

Wouter Vos

22 / 53

Eindverslag -


Bij gelijke tekens kopiëren en niet andere mogelijkheden bekijken; Het algoritme uit een bron toepassen [8].

Deze bleken allemaal geen verbetering op te leveren. Het algoritme uit de bron implementeren lukte niet omdat de bron in academisch wiskundige taal geschreven was, die de afstudeerder niet voldoende begreep. Het doel om een snel algoritme te vinden was bijna opgegeven, toen de afstudeerder een project vond dat het algoritme [9] uit de bron had geïmplementeerd. De structuur van de snelle uitvoering is vanaf het begin opnieuw ontworpen om het snelle algoritme uit te voeren. Het werkt door vanaf de eerste letter van beide teksten en de laatste letter een verander pad richting het midden te berekenen. Dit resulteert in twee verander paden. Wanneer die elkaar raken, worden ze aan elkaar geknoopt tot het uiteindelijke verander pad. Verder zal het algoritme letters altijd kopiëren waar mogelijk, zonder te kijken naar andere mogelijkheden. Hierdoor wordt het beste verander pad niet altijd gevonden. Er zijn nog een aantal redenen waarom het algoritme zo snel is. Die komen in [8] en [9] uitgebreid aan bod. Het belangrijkste voordeel van dit algoritme is dat de berekentijd afhankelijk is van het aantal verschillen. Hierdoor zal het algoritme in scenario’s met weinig verschillen altijd een zeer korte berekentijd hebben.

8.5

Welke eigenschappen zijn verschillend

In het programma Studio kan de gebruiker specificaties selecteren en hun eigenschappen bekijken. Iedere specificatie bestaat uit bedrijfsobjecten die ieder voor een stukje functionaliteit zorgen, zoals Lego blokjes samen een geheel vormen. Wanneer meerdere bedrijfsobjecten geselecteerd zijn, worden de eigenschappen van het laatst geselecteerde element getoond. De afstudeerde heeft deze functionaliteit gewijzigd door de eigenschappen te vergelijken. Wanneer er verschil is tussen de eigenschappen word een standaard tekst weer gegeven, in plaats van de eigenlijke waarde. Hierdoor kan de gebruiker snel zien of er verschil zit in de eigenschappen van de geselecteerde bedrijfsobjecten. Om dit te kunnen doen heeft de afstudeerder eerst uitgezocht hoe Studio werkt, onder andere door vragen te stellen aan de programmeur die Studio gemaakt heeft: Johan. Daarna maakte de afstudeerde een mockup gemaakt om zo snel mogelijk een idee te krijgen hoe het er visueel uit kwam te zien. Het plan was om de manier waarop de tekst gewijzigd was direct in het venster weer te geven. Dit bleek niet gewenst. In Studio moest de gebruiker alleen kunnen zien of de bedrijfsobjecten verschil hadden. De gedetailleerde vergelijking kwam in een apart venster. Zonder de mockup zou de afstudeerder veel werk voor niets hebben gedaan hebben om de gekleurde tekst in het venster te krijgen. Dit is te zien in Figuur 9: Precieze weergave van verschillen tussen eigenschappen. Nadat dit werkte heeft de afstudeerder nog een hoop verbeteringen gemaakt om te zorgen dat het programma zich naar verwachting gedraagt. Verschillende type objecten hebben verschillende eigenschappen die niet met elkaar vergeleken kunnen worden. Daarom controleert het programma of alle geselecteerde objecten van hetzelfde type zijn en begint daarna pas met vergelijken. De gebruiker kan op allerlei verschillende manieren objecten

Wouter Vos

23 / 53

Eindverslag


selecteren of de-selecteren. Dus het programma moet goed opletten en wanneer dat mogelijk is zoveel mogelijk informatie weergeven.

8.6

Visualiseer verschillen tussen eigenschappen

Het venster “Compare Properties” toont de gebruiker hoe de eigenschappen van alle geselecteerde bedrijfsobjecten verschillen. Ook bij dit venster is gebruik gemaakt van een mockup, aangezien het een nieuw venster is en de kleuring duidelijk moet maken waar verschillen zitten. Zie Figuur 8 en Figuur 9. Dit nieuwe venster maakt gebruik van WPF vanwege de verbeterde opties voor het opbouwen van visuele elementen. Onder andere voor het weergeven van tekst waar de opmaak per letter anders is. Bij dit venster moet eerst berekent worden welke gegevens getoond worden en hoe. Afhankelijk van alle waarden die verschillende bedrijfsobjecten voor een eigenschap hebben, wordt de achtergrondkleur aangepast. Dit zijn zeer visuele onderdelen. Daardoor is het niet gelukt MVVM (zie 6.5) volledig toe te passen. In de uiteindelijke oplossing maakt de View een aantal visuele hulpstukken die door het ViewModel gebruikt worden om het Model op te bouwen. Dan zit er al veel visuele informatie in het Model. Die informatie wordt dan bij de View aangeleverd zodat die alles direct kan weergeven.

8.7

Visualiseer verschillen tussen de specificaties

Om ook verschillen tussen de inhoud van specificaties te visualiseren heeft de afstudeerder het venster “Compare Contents” gemaakt. Zie Figuur 10 en Figuur 11. Voor dit venster moeten alle aspecten van een bedrijfsobject moeten met die van een ander bedrijfsobject vergeleken worden. Verder moeten alle bedrijfsobjecten in dezelfde boomstructuur weergegeven worden als die waarin ze in Studio te zien zijn. Als eerste wordt de naam vergeleken. Als die anders is, wordt bij het resulterende bedrijfsobject weergegeven hoe dat veranderd is. Dan de eigenschappen. Als daar verschil in zit, maakt het programma een knop die een “Compare Properties” venster laat zien waar alle eigenschappen in detail vergeleken worden. Dan heeft ieder bedrijfsobject nul of meer groepen andere bedrijfsobjecten. Dat zijn per type bedrijfsobject altijd dezelfde groepen. Het vergelijken van twee willekeurige boomstructuren is erg complex [10]. Maar twee beperkingen zorgen ervoor dat het maximaal aantal vergelijkingen altijd het totaal aantal bedrijfsobjecten in beide groepen is. De bedrijfsobjecten staan op een bekende volgorde en er mogen geen dubbele voorkomen. Het algoritme werkt door van beide groepen een bedrijfsobject te nemen en die te vergelijken. De vergelijking geeft aan hoe de bedrijfsobjecten verschillen. Aan de hand van dit resultaat weet het algoritme hoe een of beide bedrijfsobjecten in de transformatie van de eerste groep naar de tweede verwerkt moet worden. Als een bedrijfsobject verwerkt is gaat het algoritme verder met het volgende bedrijfsobject uit die groep. In het voorbeeld is de bekende volgorde getallen van klein naar groot.

Wouter Vos

24 / 53

Eindverslag


Bijvoorbeeld: Neem twee groepen getallen die van klein naar groot zijn  3 gesorteerd en waar geen dubbele in voorkomen. Het algoritme begint in 4 beide groepen bij het eerste getal en vergelijkt die. De pijl geeft aan 6 welke bedrijfsobjecten worden bekeken. 7 1 is kleiner dan 3 en zit in de tweede groep. Dus die wordt toegevoegd.  3 In de tweede groep hebben we nu een bedrijfsobject verwerkt, dus kijkt 4 het algoritme in die groep naar het volgende bedrijfsobject. 6 7 3 is kleiner dan 4 en zit in de eerste groep. Dus die wordt verwijderd. In 3 de eerste groep is nu een bedrijfsobject verwerkt, dus kijken we in die  4 groep naar het volgende bedrijfsobject. 6 7 4 en 4 zijn gelijk, bij een kopie hoeft verder niets te veranderen. In het 3 algoritme betekent dit dat de identiteiten gelijk zijn, dan gaat een ander 4 deel van het algoritme die bedrijfsobjecten verder vergelijken. In beide  6 groepen kijkt het algoritme naar het volgende bedrijfsobject. 7 6 is kleiner dan 7 en zit in de eerste groep. Dus die wordt verwijderd. In 3 de eerste groep is nu een bedrijfsobject verwerkt, dus kijkt het algoritme 4 in die groep naar het volgende bedrijfsobject. 6  7 7 en 7 zijn gelijk dus is in beide groepen een bedrijfsobject verwerkt en 3 kijkt het algoritme in beide groepen naar het volgende bedrijfsobject. In 4 de eerste groep zijn er geen bedrijfsobjecten meer, dus kunnen we de 6 overgebleven bedrijfsobjecten uit de tweede groep kunnen allemaal 7 toevoegen. 

 1 4 7 9 1  4 7 9 1  4 7 9 1 4  7 9 1 4  7 9 1 4 7  9

De resultaten van dit algoritme worden in een boomstructuur weergegeven, die overeenkomt met de boomstructuur waarin de bedrijfsobjecten in Studio te zien zijn. Echter dan staat er per bedrijfsobject aangegeven of het bij de transformatie van de eerste naar de tweede groep, gekopieerd, gewijzigd, verwijderd of toegevoegd moet worden. Bij dit venster zijn er vergelijkbare problemen met MVVM (zie 6.5 Model View ViewModel) als met het vorige venster en de oplossing lijkt dan ook erg op de oplossing hierboven van het vorige venster. Het verschil is dat de visualisering van het verschil tussen de specificaties in de technische code uitgevoerd wordt in plaats van in de declaratieve taal van WPF.

Wouter Vos

25 / 53

Eindverslag

9 9.1


Resultaten Inleiding

In dit hoofdstuk komen alle producten/functies aan bod die deze afstudeerstage opgeleverd heeft.

9.2

Verschilberekening

Voor een versiebeheersysteem is het belangrijk dat verschillen tussen de gegevens die beheerd, berekend kunnen worden. Dit is besproken in 8.2 Waarom verschillen berekenen. De werking van het algoritme staat beschreven in 8.3 Verschil algoritme. Deze functie berekent welke operaties uitgevoerd moeten worden om een gegeven tekst in een andere gegeven tekst te veranderen. Hij is in PL/SQL geschreven en aan het functie pakket op de database toegevoegd. Iemand die direct met de database werkt (bijvoorbeeld via Toad) hoeft de teksten dus niet eerst uit de database op te halen en kan ze direct vergelijken. De code voor deze functie in PL/SQL is te vinden in bijlage 13.4. Testresultaten van de prestaties zijn te vinden in bijlage 13.3.

9.3

Snelle Verschilberekening

Omdat ontwikkelen in C# voor de afstudeerder bekend terrein is en het snelle algoritme ook daar nodig is, is er eerst een C# versie gemaakt. Die is te vinden in bijlage 13.5. Vervolgens heeft de afstudeerder die omgezet naar PL/SQL. Die versie is te vinden in bijlage 13.6. Testresultaten van de prestaties zijn te vinden in bijlage 13.3. Het algoritme is ontworpen vanuit de praktijk dat een ontwikkelaar meestal een paar wijzigingen maakt. Het maakt een aantal offers om ervoor te zorgen dat de berekentijd bij weinig wijzigingen veel beter wordt, zie 8.4.

9.4

Welke eigenschappen zijn verschillend?

Deze functie is beschreven in 8.5.

Figuur 6: Mockup welke eigenschappen hebben verschillen?

Wouter Vos

26 / 53

Eindverslag


Dit scherm is een aanpassing op het huidige scherm in Studio. Daarom zie je screenshots van bestaande knoppen: (boven) groeperen, sorteren, property pages, (onder) Business Objects, Audit, Refresh, Help. De knop “Compare Details” is toegevoegd. Verder zie je een lijst met de eigenschappen van het geselecteerde object en de waarde die er bij hoort. De weergave van het scherm is zo aangepast dat het anders reageert wanneer de gebruiker meerdere objecten selecteert. Er wordt dan een vergelijking gemaakt tussen de eigenschappen van die objecten en waar de objecten een andere waarde hebben voor dezelfde eigenschap wordt er “” weergegeven. In Figuur 7 is te zien hoe het onderdeel er uiteindelijk uit is komen te zien.

Figuur 7: Eigenschappen venster

De uiteindelijke uitvoering is dicht bij het idee gebleven. Zie Figuur 6: Mockup welke eigenschappen hebben verschillen? Alleen de knop “Compare Details” is iets verschoven en bevat nu de tekst “Compare”. Wanneer de gebruiker op de compare knop klikt, verschijnt er een venster waarin precies de verschillen tussen eigenschappen te zien zijn.

9.5

Verschillen tussen eigenschappen

De functie van dit venster is beschreven in 8.6. In Figuur 8 is het ontwerp van dit venster te zien.

Wouter Vos

27 / 53

Eindverslag


Figuur 8: Mockup gedetailleerde vergelijking tussen eigenschappen

Dit is een nieuw venster dat geopend wordt wanneer de gebruiker in het eigenschappen venster op “Compare” klikt. Je ziet een tabel met alle eigenschappen en per geselecteerd object de waarde voor die eigenschap. Waar die waarde anders is dan de waarde bij het eerste object is aangegeven hoe die veranderd is. Verwijderde tekst elementen zijn rood gekleurd, toegevoegde groen en gekopieerde tekst zwart. Daarbij hebben regels waar een verschil is een andere achtergrond kleur. Op regel 4 is te zien dat de eigenschap “Definitie” eerst geen waarde had en later wel. Het toegevoegde deel is groen gekleurd. Op regel 5 zie je dat er één letter is verwijderd en een letter is toegevoegd. Op regel 6 zie je dat de waarde is verwijderd. Op regel 8 zie je dat er een letter is toegevoegd. Bovenin is er een knop om alleen de rijen die een verschil hebben weer te geven. Als er veel eigenschappen zijn kan de gebruiker hiermee snel eigenschappen zonder verschillen laten verdwijnen. Daarnaast is er een knop dat de verschillen tussen de inhoud van de geselecteerde objecten zal visualiseren.

Wouter Vos

28 / 53

Eindverslag


In de uiteindelijke uitvoering zijn er een aantal wijzigingen en is te zien in Figuur 9.

Figuur 9: Precieze weergave van verschillen tussen eigenschappen

Verwijderde letters zijn behalve rood ook doorgestreept en toegevoegde letters zijn behalve groen ook dikgedrukt. Daarbij kan de gebruiker de eigenlijke waarde van de eigenschap te zien krijgen door er met zijn/haar muis boven te hangen. Soms worden de groene en rode letters moeilijk leesbaar, door deze weergave kan de gebruiker toch gemakkelijk zien wat de eigenlijke tekst is. Verder is de knop ‘Compare Business Content’ vervangen voor de knop ‘Size To Fit’. Het venster Compare Content kan alleen twee objecten met elkaar vergelijken, waar dit venster alle geselecteerde objecten vergelijkt. Dus kan die functie niet op een logische manier toegepast worden. Met de knop ‘Size To Fit’ wordt de breedte van kolommen aangepast naar hun inhoud.

Wouter Vos

29 / 53

Eindverslag

9.6


Verschillen tussen inhoud specificaties

Voor deze functie is in Studio een nieuwe knop ‘Compare Contents’ gemaakt. De functie van dit venster wordt beschreven in 9.6. Er is een knop aan Studio toegevoegd om dit venster op te roepen.

Figuur 10: Mockup verschil tussen bedrijfsobjecten

Voor de gegevens in dit venster worden twee door de gebruiker geselecteerde bedrijfsobjecten met elkaar vergeleken. Ieder bedrijfsobject kan zelf ook weer een aantal bedrijfsobjecten bevatten. Die noemen we zijn ‘kinderen’. De kinderen van beide bedrijfsobjecten worden met elkaar vergeleken. Het resultaat is een lijst waar per bedrijfsobject is aangegeven of het bedrijfsobject is gewijzigd. Dat wordt hier weergegeven. Op regel 4 is het bedrijfsobject ‘Data Objects’ weergegeven. Daarbij bestond de eerste groep uit 216 bedrijfsobjecten en de tweede uit 46. Bij het eerste kind is er een bedrijfsobject met een deel van de naam rood en een deel groen. Daarbij is alleen de naam veranderd. Bij het tweede kind is er een bedrijfsobject met het eerste deel van de naam groen gekleurd. Dat is uit de tweede groep toegevoegd. Bij het derde kind is er een bedrijfsobject met het eerste deel van de naam rood gekleurd. Dat is uit de eerste groep verwijderd. Het vierde kind is gekopieerd. Bij het vijfde kind is er een verschil in de kinderen. Die kan de gebruiker bekijken door het open te klappen. Boven de rij resultaten staat welke twee bedrijfsobjecten vergeleken worden. Meestal is de gebruiker alleen geïnteresseerd in de verschillen, daarom is er een knop ‘Only Show Differences’. Hiermee worden alle bedrijfsobjecten die niet gewijzigd zijn weggelaten. De

Wouter Vos

30 / 53

Eindverslag


knop ‘Compare Properties’ opent een venster waarin alle eigenschappen van de geselecteerde bedrijfsobjecten vergeleken wordt. In de uiteindelijke uitvoering is er veel veranderd:

Figuur 11: Verschillen tussen bedrijfsobjecten

Na de titel staat er een telling van het aantal bedrijfsobjecten dat vergeleken is en de tijd die het gekost heeft om dit venster te berekenen. De knop ‘Compare Properties’ is verplaatst naar de bedrijfsobjecten waar de eigenschappen een verschil hebben. Die kan gebruikt worden om precies de eigenschappen van die bedrijfsobjecten te vergelijken. Verder wordt er nu met een icoontje aangegeven wat er met het bedrijfsobject gebeurd is. De tekst is het verschil tussen de naam van het ene bedrijfsobject naar het andere bedrijfsobject. Behalve bij bedrijfsobjecten die een verzameling bedrijfsobjecten zijn. Die zijn aangegeven met een mapje en daarover een klein icoontje om het type bedrijfsobjecten aan te geven die de verzameling bevat. In het kader van het algoritme dat besproken is in 8.7, staan de wijzigingen tussen de kinderen van de twee vergeleken bedrijfsobjecten genoemd: -

Het aantal gekopieerde bedrijfsobjecten in het zwart. Het aantal gewijzigde bedrijfsobjecten in het blauw en onderstreept. Het aantal verwijderde bedrijfsobjecten rood en doorgestreept. Het aantal toegevoegde bedrijfsobjecten groen en vetgedrukt.

Wouter Vos

31 / 53

Eindverslag

9.7


Prestaties berekening verschil tussen specificaties

De meest voorkomende situatie waarin dit venster gebruikt zal worden is het vergelijken van twee versies van een specificatie, waar weinig verschillen tussen zitten. Dit scenario is ook het meeste werk. De eerste keer dat de uitvoering voor dit venster getest werd op een realistisch scenario kon een schatting gemaakt worden dat de volledige berekening ongeveer 10 uur zou duren. Die berekentijd is natuurlijk veel te lang en werd veroorzaakt door een fout. Hierdoor deed het algoritme zeer veel extra werk en leverde het ook verkeerde resultaten. Nadat de fout gerepareerd was duurde de berekening nog ongeveer een half uur. Om het venster voor gebruikers in de toekomst bruikbaarder te maken is het de bedoeling dat de berekentijd naar 10 seconden teruggebracht wordt. Het plan om dit te realiseren is het beter organiseren van communicatie met de database. Tot de afstudeerpresentatie is er een periode waarin de afstudeerder nog voor Invantive blijft werken om dit te realiseren.

Wouter Vos

32 / 53

Eindverslag


10 Conclusie 10.1

Verschillen zijn duidelijk zichtbaar

Met Invantive Studio kunnen softwareontwikkelaars de verschillen zien tussen de specificaties en bedrijfsobjecten die door Invantive Producer worden gebruikt.

10.2

Persoonlijk

De afstudeerder heeft geleerd zich professioneler te presenteren, actiever met collega’s om te gaan, professioneel onderhandelingen te voeren om een beter resultaat te bereiken en op tijd komen. Op technisch gebied heeft de afstudeerder leren omgaan met de database programmeertaal PL/SQL en hoe goede applicaties te ontwikkelen in WPF. De afstudeerder is blij met de opgeleverde producten. Die worden nu al binnen Invantive gebruikt.

10.3

Advies voor de opvolger

De volgende stap is de commit functie. Er is al een mogelijkheid om wijzigingen in een specificatie op te slaan, maar communicatie over en weer met de gebruiker hierover ontbreekt. Daarnaast moet het systeem moet bij het opslaan van de wijzigingen rekening houden met de structuur van Invantive Studio. Nu worden alle wijzigingen simpelweg opgeslagen. De gebruiker moet kunnen zien wat er gewijzigd is en controle hebben over welke wijzigingen worden opgeslagen. Daarna komt de functie voor samenvoegen, als onderdeel van de update functie. Gebruikers moeten wijzigingen van anderen in hun specificatie kunnen krijgen. Bij het samenvoegen moet het systeem rekening houden met de huidige versie die de gebruiker heeft. Hiervoor moet het systeem een set wijzigingen samenstellen die een specificatie van een beginversie naar een doelversie brengt. Als samenvoegen goed werkt kan die functie worden uitgebreid, met ondersteuning voor verschillende branches. Die kunnen wel gemaakt worden, maar gebruikers kunnen wijzigingen op een branch niet automatisch op een andere branch uitvoeren.

10.4

Advies voor leidinggevende bij Invantive

Met Invantive Studio kunnen ontwikkelaars applicaties ontwikkelen. Een applicatie wordt automatisch samengesteld op basis van specificaties in de vorm van bedrijfsregels. Hierdoor kunnen ontwikkelaars continu de software die ze gebruiken verbeteren en evolueren. Ten opzichte van andere ontwikkelomgevingen, mist Invantive Studio echter de functionaliteit die ontwikkelaars traditioneel met een versiebeheer systeem krijgen. Studio zou stap voor stap uitgebreid kunnen worden met de functies die een versiebeheersysteem biedt. Dan kan men steeds per onderdeel kijken wat de noodzaak en het nut van een nieuwe functionaliteit is.

Wouter Vos

33 / 53

Eindverslag In de toekomst zou versiebeheersysteem.

Wouter Vos

Versiebeheer Repository IP Studio

uitgebreid

moeten

worden

met

een

volledig

34 / 53

Eindverslag


11 Woordenlijst Woord

Verklaring

Database

Programma om permanent gestructureerd op te slaan

IP

Invantive Producer. Software dat op basis van een specificatie projectmanagement software genereerd.

Repository

Database voor specificaties waarmee software gegenereerd word.

Studio

Ontwikkeld door Invantive voor het beheer van de specificaties die door IP gebruikt worden.

Oracle

Internationaal Software bedrijf dat zich primair bezig houdt met het ontwikkelen van zijn database software.

PL/SQL

Programmeer taal om programma’s te schrijven die direct op een Oracle database werken.

Mockup

Eenvoudig opgesteld voorbeeld wat weergeeft hoe een applicatie er ongeveer uit komt te zien.

Server

Computer speciaal voor het uitvoeren van een specifieke taak. Is meestal verbonden met het internet waardoor meerdere gebruikers ermee kunnen communiceren en taken uit kunnen laten voeren.

werkkopie

Versie van een project dat wordt beheerd door een versiebeheersysteem en bedoeld is voor een gebruiker om wijzigingen in te maken.

commit

Opdracht aan het versiebeheersysteem om gemaakte wijzigingen uit de werkkopie op te nemen.

update

Opdracht aan het versiebeheersysteem om alle wijzigingen in de meest recente versie uit te voeren op de werkkopie.

patch

Pakket met wijzigingen.

branch

Onafhankelijke tak in het versiebeheersysteem.

Declaratief

De ontwikkelaar geeft aan wat het resultaat moet zijn. Het onderliggende systeem bedenkt zelf hoe dat bereikt wordt. Het tegenovergestelde van procedureel.

Procedureel

De ontwikkelaar geeft aan welke stappen het onderliggende systeem moet uitvoeren. Zo zorgt de ontwikkelaar ervoor dat het gewenste resultaat bereikt wordt. Het tegenovergestelde van declaratief.

Wouter Vos

grote

hoeveelheden

gegevens

35 / 53

Eindverslag


12 Bibliografie

[1] P. Hofman, Interviewee, [Interview]. 2012. [2] G. Leenders, Interviewee, [Interview]. 2012. [3] C. Anderson, Essential Windows Presentation Fundation, Boston: Pearson Education, Inc, 2007. [4] B. Petr, „Current Concepts in Version Control Systems,” Department of Applied Mathematics, Prague, Charles University, 2008. [5] B. Collins-Sussman, B. W. Fitzpatrick en C. M. Pilato, Version Control with Subversion, ISBN: 9780596510336, Creative Commons, 2002-2011. [6] S. Otte, „Version Control Systems,” Institue of Computer Science, Freie Universität Berlin. [7] D. L. Hicks, J. J. Legget en L. J. Schnase, „Version Control in Hypertext Systems,” Hypermedia Research Lab, Tampere University of Technology, 1991. [8] E. Myers, „An O(ND) Difference Algorithm and Its Variations,” Algorithmica, p. 15, 1986. [9] mmanela, „Diffplex,” 22 Mei 2011. [Online]. Available: http://diffplex.codeplex.com/releases/view/66796. [10] H. G.-M. Sudarshan S. Chawathe, „An Expressive Model for Comparing Tree-Structured Data,” Computer Science Department, Stanford, California, 1997. [11] A. Rossini, A. Rutle, Y. Lamo en U. Wolter, „A formalisation of the copy-modify-merge approach to version control in MDE,” The Journal of Logic and Algebraic Programming, nr. 79, pp. 636658, 2010.

Wouter Vos

36 / 53

Eindverslag


13 Bijlagen 13.1

Oorspronkelijke tijdsindeling afstudeerperiode

13.2

Gerealiseerde tijdsindeling afstudeerperiode

Wouter Vos

37/53

Eindverslag

13.3


Prestaties van algoritmen die verschillen berekenen

Voor deze afstudeerstage is een eenvoudig algoritme (beschreven in 8.3 Verschil algoritme) en een snel algoritme (beschreven in 8.4 Snel algoritme) geïmplementeerd om verschillen te berekenen. Het aantal gevonden wijzigingen is een indicatie van de kwaliteit. Het eenvoudige algoritme vindt altijd de beste oplossing of laagst aantal wijzigingen waarmee de ene tekst in de andere te veranderen is. Beide zijn met dezelfde teksten getest en hier staan de resultaten. Tabel 1: Testresultaten van het vergelijken van steeds complexere teksten

Tekens 0x0 7x7 3x4 8x6 12x12 87x101 576x491 2.099x2.639 13.110x13.110 13.112x13.025

Eenvoudig algoritme Snel algoritme Wijzigingen Tijd (sec) Wijzigingen Tijd (sec) 0 0,001 0 0 1 0 1 0,001 2 0 3 0 4 0 4 0,001 3 0 6 0 28 0,001 40 0 404 0,043 561 0,017 1.890 0,68 2.728 0,34 0 22,5 0 0,001 113 22,6 113 0,003

Aan de eerste zes regels is te zien dat beide algoritme bij kleine teksten zeer goed presteren. Ook al vind het snelle algoritme soms een slechter resultaat, afhankelijk van de tekst. Bij teksten met veel wijzigingen (regel 576x491) zie je dat de snelle vergelijking een veel slechter resultaat vindt, 561 wijzigingen tegenover 404 wijzigingen. Het is nog steeds een correcte manier om de ene tekst in de andere te veranderen. Maar als bekend is dat de teksten zeer verschillend zijn zou het eenvoudige algoritme kunnen worden. Aangezien het verschil bij veel wijzigingen ook niet zo groot meer is; 0,017 sec tegenover 0,043 sec. De laatste meting is gestructureerd om de situatie zoals die meestal in het echt is te simuleren. Een groot bestand met enkele groepjes wijzigingen. Je ziet hier dat het aantal en de structuur van de wijzigingen essentieel is voor het snelle algoritme. Doordat de structuur eenvoudig was boette het snelle algoritme niets in aan kwaliteit. En ook al zijn de teksten in de laatste regel 25x groter dan die van regel 576x491, de berekentijd was slechts 0,003 sec.

Wouter Vos

38/53

Eindverslag

13.4


PL/SQL verschilberekening

--- Finds the cheapest way to change p_left into p_right. --- Parameters: -- * p_left: old text, created after reverting the new. -- * p_right: new text, created after converting the old. -- * p_cost: the number of operations needed to complete the change. -- * p_changes: a letter for each operation needed to complete the change. --- * C = Copy, cost 0 -- * R = Replace, cost 1 -- * D = Delete, cost 1 -- * I = Insert, cost 1 -procedure diff ( p_left in varchar2 , p_right in varchar2 , p_cost out number , p_changes out varchar2 ) is --- Row with edit costs. -type t_editcosts_row is table of integer; --- two-dimensinal array with edit costs. -type t_editcosts_matrix is table of t_editcosts_row; -cost_matrix t_editcosts_matrix := t_editcosts_matrix(null); -l_left_length pls_integer; l_right_length pls_integer; l_min pls_integer; l_col pls_integer; l_row pls_integer; l_change char(1 byte); begin l_left_length := coalesce(length(p_left), 0); l_right_length := coalesce(length(p_right), 0); -if p_left is null and p_right is null then p_cost := 0; p_changes := ''; --- Check if given strings are the same. -elsif itgen_utilities.values_equal(p_left, p_right) then -- Use padding to return a string of c's. p_cost := 0; p_changes := 'C'; p_changes := rpad(p_changes, l_left_length, 'C'); --- Check if the arguments actually contain values. -elsif p_left is null then -- Use padding to return a string of i's. p_cost := l_right_length; p_changes := 'I'; p_changes := rpad(p_changes, l_right_length, 'I'); elsif p_right is null then -- Use padding to return a string of d's. p_cost := l_left_length; p_changes := 'D';

Wouter Vos

39 / 53

Eindverslag


p_changes := rpad(p_changes, l_left_length, 'D'); else --- Both strings have values and are different. --- Start of the actual algorithm. -- Left mapped left of the first column and right is mapped above the first row. -- Example: origineel to rigad. -o r i g i n e e l -0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | -- r 1 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | -- i 2 | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | -- g 3 | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 | 6 | -- a 4 | 4 | 4 | 3 | 2 | 2 | 3 | 4 | 5 | 6 | -- d 5 | 5 | 5 | 4 | 3 | 3 | 3 | 4 | 5 | 6 | --- Initialze columns. -cost_matrix.extend(l_right_length + 1); for col_ctr in 1..l_right_length + 1 loop -- Initialize rows. cost_matrix(col_ctr) := t_editcosts_row(null); -- Make sure the row has the right number of columns. cost_matrix(col_ctr).extend(l_left_length + 1); -- Performing this change would be a number of deletes. cost_matrix(col_ctr)(1) := col_ctr - 1; end loop; --- Initialize first row to 0. -for row_ctr in 2..l_left_length + 1 loop -- Performing this change would be a number of inserts. cost_matrix(1)(row_ctr) := row_ctr - 1; end loop; -for col_ctr in 1..l_right_length loop for row_ctr in 1..l_left_length loop -- Compare a letter from each string. if substr(p_left, row_ctr, 1) = substr(p_right, col_ctr, 1) then -- Copy so no cost. l_min := cost_matrix(col_ctr)(row_ctr); -- Replace cost 1. else l_min := cost_matrix(col_ctr)(row_ctr) + 1; end if; if (cost_matrix(col_ctr)(row_ctr + 1) + 1) < l_min then -- Insert cost 1. l_min := cost_matrix(col_ctr)(row_ctr + 1) + 1; end if; if (cost_matrix(col_ctr + 1)(row_ctr) + 1) < l_min then -- Delete cost 1. l_min := cost_matrix(col_ctr + 1)(row_ctr) + 1; end if; --- Store the best option. -cost_matrix(col_ctr + 1)(row_ctr + 1) := l_min; end loop; end loop; --- Both string are fully considered, total cost is found in last element. -p_cost := cost_matrix(l_right_length + 1)(l_left_length + 1); --- Start at the last cell and move back through the matrix. -l_col := l_right_length; l_row := l_left_length; --- Keep moving until all changes have been registered and arrived at the opposite corner.

Wouter Vos

40 / 53

Eindverslag


while l_col > 0 or l_row > 0 loop l_min := cost_matrix(l_col + 1)(l_row + 1); -- Check if we can still move diagonally. if l_col > 0 and l_row > 0 then l_min := cost_matrix(l_col)(l_row); if substr(p_left, l_row, 1) = substr(p_right, l_col, 1) then l_change := 'C'; else l_change := 'R'; end if; end if; --- Consider copy and replace are first, otherwise replace would be ignored often. -if l_col > 0 and l_min > cost_matrix(l_col)(l_row + 1) then -- Move horizontally, only p_left is considered. l_min := cost_matrix(l_col)(l_row + 1); l_change := 'I'; end if; if l_row > 0 and l_min > cost_matrix(l_col + 1)(l_row) then -- Move vertically, only p_right is considered. l_min := cost_matrix(l_col + 1)(l_row); l_change := 'D'; end if; --- Move to the next cell after all options have been viewed. -- Cannot move on choosing the option because it may be overwritten. -if l_change = 'I' then l_col := l_col - 1; elsif l_change = 'D' then l_row := l_row - 1; else -- Move diagonally when copy or modify, both strings are considered. l_col := l_col - 1; l_row := l_row - 1; end if; --- Store the edit that needs to be made in the string with changes. -p_changes := l_change || p_changes; dbms_output.put_line(''); end loop; end if; end;

13.5

C# snelle verschil berekening

/// <summary> /// Calculate which letters must be change on each side. /// <para>Specifies the paft of each tex that must be inspected. /// <para>Forward and reverse diagonals store the quality of each path. /// private void BuildModificationData( string left, bool[] modifiedLeft, int startLeft, int endLeft, string right, bool[] modifiedRight, int startRight, int endRight, int[] forward, int[] reverse) { // Skip elements that can be copied at start. while (startLeft < endLeft && startRight < endRight && left[startLeft].Equals(right[startRight])) { startLeft++; startRight++; } // Skip elements that can be copied at end. while (startLeft < endLeft && startRight < endRight

Wouter Vos

41 / 53

Eindverslag


&& left[endLeft - 1].Equals(right[endRight - 1])) { endLeft--; endRight--; } int remainingLeft = endLeft - startLeft; int remainingRight = endRight - startRight; if (remainingLeft > 0 && remainingRight > 0) { // Calculate where paths overlap in this edit block of the texts. EditLengthResult result = CalculateEditLength( left, startLeft, endLeft, right, startRight, endRight, forward, reverse); if (result.EditLength <= 0) return; if (result.LastEdit == Edit.DeleteRight && result.StartLeft - 1 > startLeft) modifiedLeft[--result.StartLeft] = true; else if (result.LastEdit == Edit.InsertDown && result.StartRight - 1 > startRight) modifiedRight[--result.StartRight] = true; else if (result.LastEdit == Edit.DeleteLeft && result.EndLeft < endLeft) modifiedLeft[result.EndLeft++] = true; else if (result.LastEdit == Edit.InsertUp && result.EndRight < endRight) modifiedRight[result.EndRight++] = true; // I would expect the following recursion to make the algorithm very slow, // but it remains fast, also at higher volumes. // Calculate first half of both collections again. BuildModificationData( left, modifiedLeft, startLeft, result.StartLeft, right, modifiedRight, startRight, result.StartRight, forward, reverse); // Calculate last half of both collections again. BuildModificationData( left, modifiedLeft, result.EndLeft, endLeft, right, modifiedRight, result.EndRight, endRight, forward, reverse); } // If the left text has some letters remaining, mark them for deletion. else if (remainingLeft > 0) { for (int i = startLeft; i < endLeft; i++) modifiedLeft[i] = true; } // If the right text has some letters remaining, mark them for deletion. else if (remainingRight > 0) { for (int i = startRight; i < endRight; i++) modifiedRight[i] = true; } } /// <summary> /// Calculate a forward path from the upper-right corner /// <para>of the imaginary edit matrix and a reverse path /// <para>from the lower-left corner from the imaginary edit matrix. /// <para>Specifies the paft of each tex that must be inspected. /// <para>Forward and reverse diagonals store the quality of each path. /// Section where both paths overlap. /// private EditLengthResult CalculateEditLength( string left, int startLeft, int endLeft, string right, int startRight, int endRight, int[] forward, int[] reverse) { Edit lastEdit; int remainingLeft = endLeft - startLeft; int remainingRight = endRight - startRight; int max = remainingRight + remainingLeft + 1; int half = max / 2; EditLengthResult editLengthResult = new EditLengthResult(); bool overlapNotFound = true;

Wouter Vos

42 / 53

Eindverslag


// How far the endpoint diagonal is from the startpoint diagonal. int delta = remainingLeft - remainingRight; bool deltaEven = delta % 2 == 0; // Set the algorithms initial values. forward[1 + half] = 0; reverse[1 + half] = remainingLeft + 1; // Searching from two directions so each direction does half the distance. for (int depth = 0; depth <= half && overlapNotFound; depth++) { // Calculate the forward path. // Search as far to each side of the path as it is deep. for (int diagonal = -depth; diagonal <= depth && overlapNotFound; diagonal += 2) { // Index numbers cannot be negative. int diagonalIndex = diagonal + half; int col, row; if (diagonal == -depth || (diagonal != depth && forward[diagonalIndex - 1] < forward[diagonalIndex + 1])) { // row up move down from previous diagonal col = forward[diagonalIndex + 1]; lastEdit = Edit.InsertDown; } else { // col up move right from previous diagonal col = forward[diagonalIndex - 1] + 1; lastEdit = Edit.DeleteRight; } // Calculate new row position. row = col - diagonal; int startX = col; int startY = row; // Skip over copies. while (col < remainingLeft && row < remainingRight && left[col + startLeft].Equals(right[row + startRight])) { col += 1; row += 1; } // Store the col position the snake moved to. forward[diagonalIndex] = col; if (!deltaEven) { int middleDiagonalOffset = diagonal - delta; if (middleDiagonalOffset >= (-depth + 1) && middleDiagonalOffset <= (depth - 1)) { int reverseDiagonalIndex = (middleDiagonalOffset) + half; // Check if forward and reverse paths overlap. if (reverse[reverseDiagonalIndex] <= col && reverse[reverseDiagonalIndex] - diagonal <= row) { editLengthResult.EditLength = 2 * depth - 1; editLengthResult.StartLeft = startX + startLeft; editLengthResult.StartRight = startY + startRight; editLengthResult.EndLeft = col + startLeft; editLengthResult.EndRight = row + startRight; editLengthResult.LastEdit = lastEdit; // Return the values we just found. overlapNotFound = false; } } } } // Calculate the reverse path. // Search as far to each side of the path as it is deep.

Wouter Vos

43 / 53

Eindverslag


for (int diagonal = -depth; diagonal <= depth && overlapNotFound; diagonal += 2) { int diagonalIndex = diagonal + half; int col, row; if (diagonal == -depth || (diagonal != depth && reverse[diagonalIndex + 1] <= reverse[diagonalIndex - 1])) { // move left from diagonal + 1 col = reverse[diagonalIndex + 1] - 1; lastEdit = Edit.DeleteLeft; } else { col = reverse[diagonalIndex - 1]; //move up from diagonal - 1 lastEdit = Edit.InsertUp; } row = col - (diagonal + delta); int endX = col; int endY = row; while (col > 0 && row > 0 && left[startLeft + col - 1].Equals(right[startRight + row - 1])) { col -= 1; row -= 1; } reverse[diagonalIndex] = col; if (deltaEven) { int forX, forY; int middleDiagonalOffset = diagonal + delta; if (middleDiagonalOffset >= -depth && middleDiagonalOffset <= depth) { int forKIndex = middleDiagonalOffset + half; forX = forward[forKIndex]; forY = forX - middleDiagonalOffset; // Check if forward and reverse paths overlap. if (forX >= col && forY >= row) { editLengthResult.EditLength = 2 * depth; editLengthResult.StartLeft = col + startLeft; editLengthResult.StartRight = row + startRight; editLengthResult.EndLeft = endX + startLeft; editLengthResult.EndRight = endY + startRight; editLengthResult.LastEdit = lastEdit; // Return the values we just found overlapNotFound = false; } } } } } return editLengthResult; }

13.6

PL/SQL snelle verschil berekening

-type t_diff_diagonal is table of integer ; -type t_diff_modified is

Wouter Vos

44 / 53

Eindverslag


table of Boolean ; --- Global variables for diff. -g_word_left varchar2(32767); g_word_right varchar2(32767); g_forward_diagonal t_diff_diagonal; g_reverse_diagonal t_diff_diagonal; g_modified_left t_diff_modified; g_modified_right t_diff_modified; --- diff_fast private helper procedures, documentation can be found above implementation. -procedure build_modification_data ( p_start_left in number , p_end_left in number , p_start_right in number , p_end_right in number ); -procedure calculate_edit_length ( p_start_left in number , p_end_left in number , p_start_right in number , p_end_right in number , p_edit_length out number , p_start_col out number , p_end_col out number , p_start_row out number , p_end_row out number , p_last_change out char ); --- Quickly finds a correct way to convert p_left into p_right. -- Theory based on: http://www.xmailserver.org/diff2.pdf, An O(ND) Difference Algorithm and Its Variations, Myers -- Implementation based on: http://diffplex.codeplex.com/ 2010, mmanela --- Parameters: -- * p_left: the number of operations needed to complete the change. -- * p_right: a letter for each operation needed to complete the change. --- This function is optimized for speed, not quality and the following scenario: -- Large collection of data with small amount of changes. -- To save storage space we only store the last collection, so to produce an old version -- the old version itself cannot be required. This eliminates the replace -- as it requires both collections to be present. The best edit path often contains replaces. -- Note that with many changes the performance of this function becomes quadratic. -- Then it may be better to use the normal diff procedure for accuracy. --- Algorithm assumes you want to change one collection into another without having the resulting collection available. -- Edit cost depends on what direction you are converting. -- From left to right: inserts_count + copy_count (deletes can be handled by skipping those elements). -- From right to left: same but now treat the deletes as inserts and the inserts as deletes. --- Returns a table with deletes and inserts per block. -- Space that blocks provide no information over are considered copies. --- Debug messages are commented instead of removed because the algorithm is very complex. -function diff_fast ( p_left in varchar2 , p_right in varchar2 ) return varchar2 --- A series of operations to be performed. -- Also how many times it must be performed. -- Also for Inserts and Deletes which elements where inserted or deleted in parenthesis -- This method allows creating either collection with only the other collection and this result.

Wouter Vos

45 / 53

Eindverslag


--- * C = Copy, -- * D = Delete, -- * I = Insert, -- * R = Replace, Use inserts and deletes instead. --- 'length_left=500,length_right=500,C200,I1(a),D1(b),C100,I2(cd),D3(efg),C196,I1(h)' -is l_length_left pls_integer; l_length_right pls_integer; l_max pls_integer; l_index_left pls_integer; l_index_right pls_integer; l_begin_left pls_integer; l_begin_right pls_integer; l_total_index pls_integer; l_do_loop boolean; l_diff_result varchar2(32767); -begin --- If both parameters are null, return. -if p_left is not null or p_right is not null then l_length_left := coalesce(length(p_left), 0); l_length_right := coalesce(length(p_right), 0); l_max := l_length_left + l_length_right + 1; --- Edit string starts with telling how long each of the collections is. -l_diff_result := 'length_left=' || to_char(l_length_left) || ',length_right=' || to_char(l_length_right); --- Set global variables to avoid passing parameters. -g_word_left := p_left; g_word_right := p_right; --- Forward and reverse diagonals, instead of a two-dimensional edit matrix. -g_forward_diagonal := t_diff_diagonal(null); g_reverse_diagonal := t_diff_diagonal(null); g_forward_diagonal.extend(l_max + 1); g_reverse_diagonal.extend(l_max + 1); -for i in 1..l_max + 1 loop g_forward_diagonal(i) := 0; g_reverse_diagonal(i) := 0; end loop; --- Stores whether corrosponding element in the collection will be changed by conversion. -g_modified_left := t_diff_modified(); g_modified_right := t_diff_modified(); g_modified_left.extend(l_length_left); g_modified_right.extend(l_length_right); -for i in 1..l_length_left loop g_modified_left(i) := false; end loop; -for i in 1..l_length_right loop g_modified_right(i) := false; end loop; --- Calculate which elements of each collection must be modified. -build_modification_data(0, l_length_left, 0, l_length_right); -l_index_left := 0; l_index_right := 0;

Wouter Vos

46 / 53

Eindverslag


--- Check whether data was modified, atleast once. -l_do_loop := true; while l_do_loop loop l_total_index := l_index_left + l_index_right; l_begin_left := l_index_left; l_begin_right := l_index_right; --- Skip the part where nothing was modified in both collections. -while l_index_left < l_length_left and l_index_right < l_length_right and not g_modified_left(l_index_left + 1) and not g_modified_right(l_index_right + 1) loop -- This element can be copied from either collection. l_index_left := l_index_left + 1; l_index_right := l_index_right + 1; end loop; -if l_index_left > l_begin_left then -- Both left and right indexes have been changed by the same amount. l_diff_result := l_diff_result || ',C' || to_char(l_index_left - l_begin_left); end if; --- Starting point of the inserts and/or deletes. -l_begin_left := l_index_left; l_begin_right := l_index_right; --- Step over all elements in the left collection that must be deleted. -while l_index_left < l_length_left and g_modified_left(l_index_left + 1) loop -- One more element to be deleted. l_index_left := l_index_left + 1; end loop; -if (l_index_left - l_begin_left) > 0 then --- Store than a delete was made. -l_diff_result := l_diff_result || ',D' || to_char(l_index_left - l_begin_left) || --- Store how many deletes where made. -'(' || substr(g_word_left, l_begin_left + 1, l_index_left - l_begin_left) || ')'; -end if; --- Step over all elements in the right colleciton that must be inserted. -while l_index_right < l_length_right and g_modified_right(l_index_right + 1) loop -- One more element to be inserted. l_index_right := l_index_right + 1; end loop; -if (l_index_right - l_begin_right) > 0 then --- Store that an insert was made. -l_diff_result := l_diff_result || ',I' || to_char(l_index_right - l_begin_right) || --- Store how many inserts where made. -'(' || substr(g_word_right, l_begin_right + 1, l_index_right - l_begin_right) || ')'; -end if;

Wouter Vos

47 / 53

Eindverslag


-if l_index_left >= l_length_left and l_index_right >= l_length_right then -- End while loop. l_do_loop := false; end if; end loop; end if; -- Return the constructed list of copies, deletes and inserts. return l_diff_result; end; --- Finds out for each element in both collections whether they will be changed at conversion. -procedure build_modification_data ( p_start_left in number , p_end_left in number , p_start_right in number , p_end_right in number ) is l_start_left pls_integer; l_end_left pls_integer; l_start_right pls_integer; l_end_right pls_integer; l_edit_length pls_integer; l_start_col pls_integer; l_end_col pls_integer; l_start_row pls_integer; l_end_row pls_integer; l_last_change char(1 byte); begin -- Copy these parameters because they are used as variables. l_start_left := p_start_left; l_end_left := p_end_left; l_start_right := p_start_right; l_end_right := p_end_right; --- Identify leading copies -while l_start_left < l_end_left and l_start_right < l_end_right and substr(g_word_left, l_start_left + 1, 1) = substr(g_word_right, l_start_right + 1, 1) loop -- One more element (at start) that does not have to be considered in the algorithm. l_start_left := l_start_left + 1; l_start_right := l_start_right + 1; end loop; --- Identify trailing copies. -while l_start_left < l_end_left and l_start_right < l_end_right and substr(g_word_left, l_end_left, 1) = substr(g_word_right, l_end_right, 1) loop -- one more element (at end) that does not have to be considered in the algorithm. l_end_left := l_end_left - 1; l_end_right := l_end_right - 1; end loop; --- If both left and right collections have unconsidered values, calculated the difference. -if l_end_left - l_start_left > 0 and l_end_right - l_start_right > 0 then -calculate_edit_length( -- These parameters determine the range over which the edit length will be calculated. l_start_left, l_end_left, l_start_right, l_end_right, -- These parameters will contain the calculation result. l_edit_length, l_start_col, l_end_col, l_start_row, l_end_row, l_last_change); -if l_edit_length > 0 then

Wouter Vos

48 / 53

Eindverslag


--- Handle edit results. -if l_last_change = 'D' and l_start_col - 1 > l_start_left then -- The first element of the result block in the left collection must be deleted. g_modified_left(l_start_col) := true; l_start_col := l_start_col - 1; -elsif l_last_change = 'I' and l_start_row - 1 > l_start_right then -- The first element of the result block in the right collection must be inserted. g_modified_right(l_start_row) := true; l_start_row := l_start_row - 1; -elsif l_last_change = 'd' and l_end_col < l_end_left then l_end_col := l_end_col + 1; -- The last element of the result block in the left collection must be deleted. g_modified_left(l_end_col) := true; -elsif l_last_change = 'i' and l_end_row < l_end_right then l_end_row := l_end_row + 1; -- The last element of the result block in the right collection must be inserted. g_modified_right(l_end_row) := true; end if; --- Construct the information for the left part of this result block. -build_modification_data(l_start_left, l_start_col, l_start_right, l_start_row); --- Construct the information for the right part of this result block. -build_modification_data(l_end_col, l_end_left, l_end_row, l_end_right); --- Edit results handled, return. -end if; --- Check if the left collection still has values left. -elsif (l_end_left - l_start_left) > 0 then for remainder_left in (l_start_left + 1)..l_end_left loop -- These left values must be deleted. g_modified_left(remainder_left) := true; end loop; --- If left has no values right may have some. -elsif (l_end_right - l_start_right) > 0 then for remainder_right in (l_start_right + 1)..l_end_right loop -- These right values must be inserted. g_modified_right(remainder_right) := true; end loop; end if; end; --- Calculates the edits within the given range. --- Parameters: -- * p_edit_length: How long the edit block is that this procedure found. -- * p_start_col: Start point in the left collection. -- * p_end_col: End point in the left collection. -- * p_start_row: Start point in the right collection. -- * p_end_row: End point in the right collection. -- * p_last_change: Last delete or insert made in this block. Also says direction of the edit. --

Wouter Vos

49 / 53

Eindverslag


-- * I = InsertDown Insert made for the forward snake. -- * i = InsertUp Insert made for the reverse snake. -- * D = DeleteRight Delete made for the forward snake. -- * d = DeleteLeft Delete made for the reverse snake. -- * C = Copy, can be assumed when information is absent. -- * N = None, maybe default value, should never be part of a result. -procedure calculate_edit_length ( p_start_left in number , p_end_left in number , p_start_right in number , p_end_right in number , p_edit_length out number , p_start_col out number , p_end_col out number , p_start_row out number , p_end_row out number , p_last_change out char ) is --- Many local variables are needed. -l_length_left pls_integer; l_length_right pls_integer; l_max pls_integer; l_half pls_integer; l_delta pls_integer; l_delta_even boolean; l_middle_diagonal_offset pls_integer; l_current_diagonal_index pls_integer; l_col pls_integer; l_row pls_integer; l_start_col pls_integer; l_end_col pls_integer; l_start_row pls_integer; l_end_row pls_integer; l_result_found boolean; l_depth_ctr pls_integer; l_current_diagonal pls_integer; begin --- Initialize base values. -l_length_left := p_end_left - p_start_left; l_length_right := p_end_right - p_start_right; l_max := l_length_left + l_length_right + 1; l_half := floor(l_max / 2) + 1; l_delta := l_length_left - l_length_right; l_delta_even := mod(l_delta, 2) = 0; g_forward_diagonal(1 + l_half) := 0; g_reverse_diagonal(1 + l_half) := l_length_left + 1; --- The algorithm calculates edit paths from 2 corners of an edit matrix. -- So each path should travel half the total length. --l_result_found := false; l_depth_ctr := 0; while not l_result_found -- Half is one bigger than in the original formula because of indexing. and l_depth_ctr < l_half loop --- Calculate diagonal values to find the forward path, starting in the upper-left corner. -l_current_diagonal := -l_depth_ctr; while not l_result_found and l_current_diagonal <= l_depth_ctr loop -- Index number to access edit matrix variables stored in the diagonals. l_current_diagonal_index := l_current_diagonal + l_half; --- If this is the first diagonal or not the last and going up is better than going down. -if l_current_diagonal = -l_depth_ctr

Wouter Vos

50 / 53

Eindverslag


or (l_current_diagonal != l_depth_ctr and g_forward_diagonal(l_current_diagonal_index - 1) < g_forward_diagonal(l_current_diagonal_index + 1)) then -- Always insert when it's the first diagonal. l_col := g_forward_diagonal(l_current_diagonal_index + 1); p_last_change := 'I'; else -- Always delete when it's the last diagonal. l_col := g_forward_diagonal(l_current_diagonal_index - 1) + 1; p_last_change := 'D'; end if; --- Calculate the current row -l_row := l_col - l_current_diagonal; l_start_col := l_col; l_start_row := l_row; --- Skip any elements that can be copied. -while l_col < l_length_left and l_row < l_length_right and substr(g_word_left, l_col + p_start_left + 1, 1) = substr(g_word_right, l_row + p_start_right + 1, 1) loop -- One more element in the forward path that's copied. l_col := l_col + 1; l_row := l_row + 1; end loop; -g_forward_diagonal(l_current_diagonal_index) := l_col; --- Determines how far the current diagonal is from the middle diagonal. -- If left and right are equal size 0 means current diagonal is the middle diagonal. -l_middle_diagonal_offset := l_current_diagonal - l_delta; --- If middle diagonal offset is odd. Using a variable because 1 = mod(l_delta, 2) will not always work, as l_delta can be negative. -if not l_delta_even then if l_middle_diagonal_offset > -l_depth_ctr and l_middle_diagonal_offset < l_depth_ctr then if g_reverse_diagonal(l_middle_diagonal_offset + l_half) <= l_col and g_reverse_diagonal(l_middle_diagonal_offset + l_half) - l_current_diagonal <= l_row then --- Edit paths from both directions overlap. -- Set out parameters and return the function. -p_edit_length := 2 * l_depth_ctr - 1; -- Calculated paths from 2 directions, so resulting path is twice each length. p_start_col := l_start_col + p_start_left; -- Left start point for this edit block = skipped collumns + procedure left start point. p_start_row := l_start_row + p_start_right; -- Right start point for this edit block = skipped rows + procedure right start point. p_end_col := l_col + p_start_left; -- Left end point for this edit block = skipped collumns + procedure left end point. p_end_row := l_row + p_start_right; -- Right end point for this edit block = skipped rows + procedure right end point. --- Last edit has already been set. -- Effectively a return because it breaks out of both loops. -l_result_found := true; end if; end if; end if; -l_current_diagonal := l_current_diagonal + 2; end loop; --

Wouter Vos

51 / 53

Eindverslag


-- Calculate diagonals to find the reverse path starting in the lower-right corner. -l_current_diagonal := -l_depth_ctr; while not l_result_found and l_current_diagonal <= l_depth_ctr loop -- Index number to access edit matrix variables stored in the diagonals. l_current_diagonal_index := l_current_diagonal + l_half; --- If this is the first diagonal or not the last and going up is better than going down. -if l_current_diagonal = -l_depth_ctr or (l_current_diagonal != l_depth_ctr and g_reverse_diagonal(l_current_diagonal_index + 1) <= g_reverse_diagonal(l_current_diagonal_index - 1)) then -- Always delete when it's the first diagonal. l_col := g_reverse_diagonal(l_current_diagonal_index + 1) - 1; p_last_change := 'd'; else -- Always insert whent it's the last diagonal. l_col := g_reverse_diagonal(l_current_diagonal_index - 1); p_last_change := 'i'; end if; --- Determines how far the current diagonal is from the middle diagonal. -- If left and right are equal size 0 means current diagonal is the middle diagonal. -l_middle_diagonal_offset := l_current_diagonal + l_delta; --- Calculate the current row. -l_row := l_col - l_middle_diagonal_offset; l_end_col := l_col; l_end_row := l_row; --- Skip elements that can be copied. -while l_col > 0 and l_row > 0 and substr(g_word_left, p_start_left + l_col, 1) = substr(g_word_right, p_start_right + l_row, 1) loop -- One more element to the final skip sequence. l_col := l_col - 1; l_row := l_row - 1; end loop; --- Fill in a value of the edit matrix. -g_reverse_diagonal(l_current_diagonal_index) := l_col; --- If the middle diagonal offset is even. -if l_delta_even then if l_middle_diagonal_offset >= -l_depth_ctr and l_middle_diagonal_offset <= l_depth_ctr then if g_forward_diagonal(l_middle_diagonal_offset + l_half) >= l_col and (g_forward_diagonal(l_middle_diagonal_offset + l_half) (l_middle_diagonal_offset)) >= l_row then --- Snakes from both directions overlap. -- Set out parameters and return the function. --- Calculated paths from 2 directions, so resulting path is twice each length. p_edit_length := 2 * l_depth_ctr; -- Left start point for this edit block = skipped collumns + procedure left start point. p_start_col := l_col + p_start_left; -- Right start point for this edit block = skipped rows + procedure right start point. p_start_row := l_row + p_start_right;

Wouter Vos

52 / 53

Eindverslag

Versiebeheer Repository IP -- Left end point for this edit block = skipped collumns + procedure left end

point. p_end_col := l_end_col + p_start_left; -- Right end point for this edit block = skipped rows + procedure right end point. p_end_row := l_end_row + p_start_right; --- Last edit has already been set. -- Effectively a return because it breaks out of all loops. -l_result_found := true; end if; end if; end if; -l_current_diagonal := l_current_diagonal + 2; end loop; l_depth_ctr := l_depth_ctr + 1; end loop; -- Outside while loop. end;

Wouter Vos

53 / 53

Eindverslag. Versiebeheer Repository Invantive Producer. Versie 1.0 Wouter Vos Project: C412 Proces: t20879 Laatst bewerkt:

Recommend Documents