Az előző fejezetben láttuk az új típusok létrehozásának egy módszerét. A nehézség az volt, hogy C#-ban kellett megadni a definíciót, ami nem biztos, hogy mindenkinek egyszerűen megy. PowerShell 5.0-tól jelent meg az az új lehetőség, hogy PowerShell szintaxissal hozhatunk létre új típusokat.
Ezzel az új lehetőséggel tehát nem csak PSObject típusú egyedi objektumokat hozhatunk létre, hanem teljesen új típust definiálva hozhatjuk létre egyedi objektumainkat, C# forráskód használata nélkül, natívan PowerShell segítségével. Ráadásul rendelkezésünkre áll az öröklődés és a metódusok újra definiálása (overload).
Nézzük mindezt néhány egyszerű példán! Szeretnénk szabályos síkidomokat kezelni PowerShellben. A szabályos síkidomok esetében leggyakrabban 2 paramétert kell megadni, gondoljunk a téglalapra, ellipszisre, vagy akár deltoidra. Elsőként ábrázoljuk ezt a közös jellegzetességet egy osztályban, amit nevezzük szabályos síkidomnak:
class SzabályosSíkidom {
[double] $a = 1
[double] $b = 1
SzabályosSíkidom ([double] $ai, [double] $bi) {
$this.a = $ai
$this.b = $bi
}
SzabályosSíkidom () {
}
[String] ToString () {
return "a:$($this.a) b:$($this.b)"
}
}
A típus, vagy más szóval osztály definiálására a class kulcsszó áll rendelkezésünkre. Ezután kell szerepeltetni a típus, osztály nevét, majd kapcsos zárójelek között jön az osztály definíciója. Ez áll tulajdonságokból, amelyeket mint változókat rakunk bele. És áll metódusokból, amelyek különösebb kulcsszó nélkül állnak, de fontos, hogy a metódus neve mögött ott kell állnia a gömbölyű zárójel-párnak.
A szabályos síkidomokra, ahogy korábban említettem, általánosan jellemző, hogy két adatot kell megadni velük kapcsolatban, ezek lettek az ’a’ és ’b’ tulajdonság. Amit láthatunk, hogy kötelező a tulajdonságok típusát jelölni, mindkettő [double] típusú és mindkettőnek 1 itt most az alaphelyzet szerinti értéke. A tulajdonságok nyilvánosak, azaz „kívülről” hozzáférhetők, értékük kiolvasható és át is írható.
Az osztálydefinícióban metódusokat is létrehozhatunk. Elsőként nézzük a legalsó, ToString metódust! Itt látható, hogy kötelező a metódusok visszatérési értékének típusát jelölni, ami itt [string]. Valamint kötelező szerepeltetni a return kulcsszót a kimenet jelzésére. Ha a metódusokban hivatkozni szeretnénk a tulajdonságokra, akkor nem $a és $b-vel tehetjük ezt meg, hanem $this.a és $this.b formában, ahol $this az osztály példányát magát szimbolizálja.
A fenti példában láthatunk még két ugyanolyan metódust, amelyeknek a neve megegyezik az osztály nevével. Ezek az osztály konstruktorai. A konstruktor egy speciális metódus, ami akkor hívódik meg, amikor az osztály egy új példányát hozzuk létre. A konstruktor neve tehát kötelezően megegyezik az osztály nevével, és itt nem kell jelezni a visszatérési érték típusát, hiszen pont az osztály egy példányát fogja visszaadni, és a return kulcsszót sem kell szerepeltetni, implicit módon a ’return $this’ kifejezést képzelhetjük oda.
Látható tehát, hogy ugyanazzal a névvel több metódusunk, akár konstruktorunk is lehet. Ezeknek valamilyen paraméterben el kell térniük egymástól. Az első konstruktorom két [double] típusú paramétert vár, a második meg semmit, így ezek egymástól különbözővé teszik a két konstruktort.
Ha lefuttatjuk a fenti típusdefiníciót, akkor az alábbi két módon is hozhatok létre példányt, azaz futtathatom a konstruktort. Hogy éppen melyiket használom a több lehetőség közül, azt a paraméterek döntik el:
PS C:\> $idom1 = New-Object -TypeName SzabályosSíkidom -ArgumentList 5,6
PS C:\> $idom1
a b
- -
5 6
PS C:\> $idom2 = [szabályossíkidom]::new()
PS C:\> $idom2
a b
- -
1 1
Az első esetben a New-Object-et használtam a példány létrehozására. Itt az első konstruktort használtam, hiszen két számot adtam át paraméterként. Ugyan nem közvetlenül [double] típusúakat, de a használt [int]-eket a PowerShell könnyedén át tudta lebegőpontos számokká alakítani.
Ha egy osztálynak nincs konstruktora, akkor is implicit módon van. Ha ezt az osztályt definiáljuk:
class Egyszerű {
[int] $a
}
Akkor ennek a statikus metódusai között ott látjuk a new()konstruktort:
PS C:\> [egyszerű] | Get-Member -Static
TypeName: Egyszerű
Name MemberType Definition
---- ---------- ----------
Equals Method static bool Equals(System.Object objA, System.Object objB)
new Method Egyszerű new()
ReferenceEquals Method static bool ReferenceEquals(System.Object objA, System.Object objB)
Az igazi előnye az osztályok használatának, hogy ha egy meglévőhöz hasonló tudású osztályt akarok létrehozni, akkor nem kell „nulláról” kezdeni, hanem a meglevőből öröklődéssel hozhatom létre az újat, ami az eredetihez képest valamit másképp vagy valamivel többet tud.
Nézzük a téglalapot, mint az előző általános szabályos síkidomból képzett új osztályt:
class Téglalap : SzabályosSíkidom {
Téglalap () : Base (){
}
Téglalap ([double] $a, [double] $b) : Base ($a, $b) {
}
[double] Terület (){
return $this.a * $this.b
}
}
Az öröklődést az osztály neve melletti kettőspont utáni alap osztály nevével jelezzük. Ha az új osztály konstruktora ugyanaz, mint az eredeti osztályé, akkor csak egyszerűen jelezzük kettőspont után, hogy az eredeti konstruktort akarjuk meghívni a Base névvel. Például ez a részlet:
Téglalap () : Base (){
}
Ez annyit jelent, hogy a Téglalap konstruktoraként meghívjuk a SzabályosSíkidom konstruktorát, és az ottaniakhoz képest nem kell semmi mást csinálni, így üresen hagytam a metódus törzsét. Az eredeti osztályhoz képest itt már tudunk területet számolni, így készítettem egy Terület metódust.
Nézzük, hogy egy téglalap példány milyen tagjellemzőkkel bír:
PS C:\> $téglalap = [téglalap]::new(12,3)
PS C:\> $téglalap | gm
TypeName: Téglalap
Name MemberType Definition
---- ---------- ----------
Equals Method bool Equals(System.Object obj)
GetHashCode Method int GetHashCode()
GetType Method type GetType()
Terület Method double Terület()
ToString Method string ToString()
a Property double a {get;set;}
b Property double b {get;set;}
Látható, hogy az újonnan létrehozott Terület mellett ott van az öröklött ToString is, ami jól működik téglalappal is:
PS C:\> $téglalap.ToString()
a:12 b:3
A Get-Member kimenetén látható, hogy „gyárilag” van Equals metódusunk is, ami mindig False értéket ad, de inkább adjunk neki értelmet akár már a SzabályosSíkidom szintjén:
[bool] Equals ([object] $object){
return ($this.a -eq $object.a -and $this.b -eq $object.b)
}
Azaz akkor adunk True-t vissza, ha az a-k és a b-k is egyenlők. Ezzel tényleg összehasonlíthatóvá válik két egyforma téglalap:
PS C:\> $t1 = [téglalap]::new(2,5)
PS C:\> $t2 = [téglalap]::new(2,5)
PS C:\> $t1 -eq $t2
True
Van még egy lehetőségünk az osztályokkal kapcsolatban. Tegyük fel, hogy a síkidom nevét is szeretnénk tárolni:
class Téglalap : SzabályosSíkidom {
hidden [string] $név = "Téglalap"
Téglalap () : Base (){
}
Téglalap ([double] $a, [double] $b) : Base ($a, $b) {
}
[double] Terület (){
return $this.a * $this.b
}
}
Látható, hogy felvettem egy új $név tulajdonságot, amihez az új hidden kulcsszót használtam.
PS C:\> $tgllp = [téglalap]::new(4,7)
PS C:\> $tgllp
a b
- -
4 7
Idáig semmi különleges nem történt. Látszólag nincsen név tulajdonságunk, de ha explicit rákérdezünk, akkor azért kiderül, hogy van:
PS C:\> $tgllp.név
Téglalap
Ez azonban nem látható sem format-list, sem get-member-el:
PS C:\> $tgllp | fl *
a : 4
b : 7
PS C:\> $tgllp | gm
TypeName: Téglalap
Name MemberType Definition
---- ---------- ----------
Equals Method bool Equals(System.Object object)
GetHashCode Method int GetHashCode()
GetType Method type GetType()
Terület Method double Terület()
ToString Method string ToString()
a Property double a {get;set;}
b Property double b {get;set;}
Sajnos jelenleg még nem tudjuk ezt csak olvashatóvá tenni, azaz felül is tudjuk bírálni, bár ha valaki nem tud ennek a tulajdonságnak a létezéséről, akkor ennek esélye kicsi:
PS C:\> $tgllp.név = "amőba"
PS C:\> $tgllp.név
amőba
Valószínű ezen a területen sok fejlesztés lesz várható a következő verziókban.
Új lehetőség szintén PowerShell 5.0-tól kezdve, hogy egyéni felsorolás-típusokat már beépítetten támogatja a nyelv, nincs szükség C# kód beágyazására. Nézzünk egy egyszerű felsorolást:
enum Színek {
Kék = 1
Zöld = 2
Sárga = 3
Piros = 4
Barna = 5
Fehér = 6
Fekete = 7
}
A felsorolás osztály létrehozásához az enum kulcsszót kell használnunk, majd az osztály nevét és ezután szkriptblokkban meg kell adni – hasonlóan a hashtáblákhoz – a címke-érték párokat. Ezután használjuk ezt:
PS C:\> $szín = [színek]::Fekete
PS C:\> $szín
Fekete
PS C:\> [int] $szín
7
Látszik, hogy minden színhez egy szám tartozik.
Van egy másik fajtája is a felsorolás típusnak, ahol nem egy-egy szám feleltethető meg a felsorolás címkéihez, hanem egy-egy bit. Ez azért jó, mert nem csak egy-egy címkét vehet fel a változó értéke, hanem címkék különböző kombinációját is. Ez a Flags típusú felsorolás, nézzünk erre is egy példát:
[Flags()] enum Bitjeim {
Egy = 1
Kettő = 2
Négy = 4
Nyolc = 8
Tizehat = 16
}
Itt az értékek 1-1 helyiértéknek feleltethetők meg a 2-es számrendszerben, így akár egyszerre többet is megadhatunk:
PS C:\> $b = [Bitjeim] "Egy, Kettő"
PS C:\> $b
Egy, Kettő
PS C:\> [int] $b
3
Látható, hogy egy olyan sztringet használtam értékadásnál, amiben vesszővel választottam el az értékeket, és a [Bitjeim] típuskonverzió ezt a formátumot ügyesen felismerte és a mögöttes szám a bebillentett biteknek megfelelő 3. Akár fordítva is megadhattam volna és a kis-nagy betű sem számít:
PS C:\> $b = [Bitjeim] "Kettő, egy"
PS C:\> $b
Egy, Kettő
Tömb formátumban is megadhatjuk az értéket:
PS C:\> $b = [Bitjeim] ("Négy", "Nyolc", "Egy")
PS C:\> [int]$b
13
Azt is lehet, hogy nem csak 1 bitet tartalmazó értékek szerepelnek a felsorolásban:
[Flags()] enum Bitjeim {
Egy = 1
Kettő = 2
Három = 3
Négy = 4
Nyolc = 8
Tizehat = 16
}
Itt a „Három” is szerepel az értékek között, így ez az értékadás erre fordul le:
PS C:\> $b = [Bitjeim] "Kettő, egy"
PS C:\> $b
Három
PS C:\> $b = [Bitjeim] "Kettő, egy, négy"
PS C:\> $b
Három, Négy
Az ilyen flag típusú felsorolások nagyon hasznosak lehetnek saját függvényeink paramétereinek megadásánál.
Az egyéni osztályok illusztrálására nézzünk egy összetettebb példát. Ugyan nem vagyok híve a nagyon hosszú kódok szerepeltetésének a könyvben, de mivel ezt úgyis elektronikusan olvassák, ezért könnyű kimásolni ezt és felhasználni, elemezni a szkriptszerkesztőben.
A példa egy láncolt lista létrehozása lesz. Ugyan a .NET keretrendszerben van ilyen ([system.collections.generic.LinkedList]), de nekem nem tetszik túlzottan, hiszen az csak egynemű elemek tárolását teszi lehetővé, én meg tetszőleges elemet szeretnék tárolni.
Eleve, miért kell nekünk ilyen láncolt lista? Miért nem jó például a [system.collections.arraylist]? Vannak olyan feladatok, ahol az elemek egymáshoz képesti helyzete fontos, azaz például nagyon sok elemet kell beszúrni meglevő elemek közé. Az ArrayList-nek van Insert metódusa, de az nagy elemszámnál nagyon belassul, főleg ha a lista elejére szúrjuk be az új elemeket.
Nézzük a saját láncolt lista osztályomat:
class MyLinkedListElement {
[PSObject] $Value = $null
[MyLinkedListElement] $NextElement = $null
[MyLinkedListElement] $PreviousElement = $null
hidden [MyLinkedList] $List
MyLinkedListElement ($iValue, $iList){
$this.Value = $iValue
$this.List = $iList
$this
}
LinkAfter ([PSObject] $newvalue) {
$newelement = [MyLinkedListElement]::new($newvalue, $this.List)
if($this.NextElement){
$this.NextElement.PreviousElement = $newelement
}
$newelement.PreviousElement = $this
$newelement.NextElement = $this.nextelement
$this.nextelement = $newelement
$this.List.Count++
$this.List.CurrentElement = $newelement
}
LinkBefore ([PSObject] $newvalue){
$newelement = [MyLinkedListElement]::new($newvalue, $this.List)
if($this.PreviousElement){
$this.PreviousElement.NextElement = $newelement
}
$newelement.PreviousElement = $this.previouselement
$newelement.NextElement = $this
$this.previouselement = $newelement
$this.List.Count++
$this.List.CurrentElement = $newelement
}
BreakRing(){
if($this.List.ListElements().Where({$_.PreviousElement -eq $null -or $_.NextElement -eq $null})){
return
}
$this.NextElement.PreviousElement = $null
$this.NextElement = $null
}
Remove () {
$this.Value = $null
$this.List.Count--
if($this.GetHashCode() -eq $this.List.RootElement.GetHashCode()){
if($this.NextElement){
$this.List.RootElement = $this.NextElement
}
elseif($this.PreviousElement){
$this.List.RootElement = $this.PreviousElement
}
}
if($this.GetHashCode() -eq $this.List.CurrentElement.GetHashCode()){
if($this.NextElement){
$this.List.CurrentElement = $this.NextElement
}
elseif($this.PreviousElement){
$this.List.CurrentElement = $this.PreviousElement
}
}
if($this.NextElement -ne $null){
$this.NextElement.PreviousElement = $null
}
if($this.PreviousElement -ne $null){
$this.PreviousElement.NextElement = $null
}
}
[string] ToString (){
return $this.Value.ToString()
}
}
class MyLinkedList {
[MyLinkedListElement]$RootElement
[MyLinkedListElement]$CurrentElement
[uint32] $Count = 0
MyLinkedList ([PSObject[]] $ElementValues) {
$this.RootElement = [MyLinkedListElement]::new($ElementValues[0], $this)
$this.CurrentElement = $this.RootElement
$this.Count = 1
if($ElementValues.Count -gt 1){
for($i = 1; $i -lt $ElementValues.Count; $i++){
$this.CurrentElement.LinkAfter($ElementValues[$i])
}
}
}
Reset(){
$this.CurrentElement = $this.RootElement
}
[PSObject[]] MakeRing (){
$prev = $this.ListElements().where({$_.PreviousElement -eq $null})
$next = $this.ListElements().where({$_.NextElement -eq $null})
if($prev -and $next){
$prev[0].PreviousElement = $next[0]
$next[0].NextElement = $prev[0]
return $prev[0], $next[0]
}
else{
return $null
}
}
[PSObject] GetNextElement ([uint32] $step){
$fail = $false
$savecurrent = $this.CurrentElement
for($i = 0; $i -lt $step; $i++){
if($this.CurrentElement.nextelement -eq $null){
$fail = $true
break
}
$this.CurrentElement = $this.CurrentElement.NextElement
}
if($fail){
$this.CurrentElement = $savecurrent
return $null
}
else{
return $this.CurrentElement
}
}
[PSObject] GetNextElement (){
return $this.GetNextElement(1)
}
[PSObject] GetPreviousElement ([uint32] $step){
$fail = $false
$savecurrent = $this.CurrentElement
for($i = 0; $i -lt $step; $i++){
if($this.currentelement.PreviousElement -eq $null){
$fail = $true
break
}
$this.CurrentElement = $this.CurrentElement.PreviousElement
}
if($fail){
$this.CurrentElement = $savecurrent
return $null
}
else{
return $this.CurrentElement
}
}
[PSObject] GetPreviousElement (){
return $this.GetPreviousElement(1)
}
[PSObject[]] ListElements (){
$i = $this.Count
return $(
($this.CurrentElement = $this.RootElement)
$i--
while($i -ge 1 -and $this.CurrentElement.NextElement){
($this.CurrentElement = $this.CurrentElement.NextElement)
$i--
}
if($i -ge 1){
$this.CurrentElement = $this.RootElement
while($i -ge 1 -and $this.CurrentElement.PreviousElement){
($this.CurrentElement = $this.CurrentElement.PreviousElement)
$i--
}
}
)
}
}
A láncolt lista valójában 2 osztályból áll. Az első a láncolt lista eleme ([MyLinkedListElement]) és maga a lista ([MyLinkedList]). Az elemnek 4 tulajdonsága van: az adott elem értéke, a következő elem, az előző elem és egy rejtett tulajdonság, ami magára a MyLinkedList objektumra mutat, amihez az elem tartozik. Metódusai:
a konstruktor, paramétere az elem értéke
LinkAfter: az elem után fűzök be egy új elemet, a láncolt lista CurrentElement értékét az új elemre állítja
LinkBefore: az elem elé fűzök be egy új elemet, a láncolt lista CurrentElement értékét az új elemre állítja
BreakRing: ha gyűrűt csináltam a linkelésekkel, akkor ezzel lehet azt felszakítani az adott elem után
Remove: egy elem eltávolítása és a felszakított linkek begyógyítása
ToString: az elem szöveges reprezentációja
A MyLinkedList objektumnak 3 tulajdonsága van: a kezdő elem, aktuális elem és az összes elem száma. A metódusok:
a konstruktor, paramétereként ez első elem értéke, vagy a felfűzendő elemek értékeinek gyűjteménye lehet.
Reset: az aktuális elemet a kezdő elemre állítja
MakeRing: gyűrűt csinál az láncolt listából, azaz a lánc két végét összeköti
GetNextElement: az adott elemhez képes előre megy megadott lépést, az lesz az új aktuális elem, amit vissza is ad. Ennek a metódusnak van egy olyan változata, amikor nem adunk meg lépésszámot, ilyenkor egyet lép előre.
GetPreviousElement: ugyanúgy működik, mint a GetNextElement, csak hátra lép.
ListElements: kilistázza az összes elemet a listából. Elsőként a kezdő elemhez képest a következőket adja vissza, majd az előzőket. Az aktuális elemet az utoljára kilistázott elemre állítja.
Hozzunk létre egy egyszerű listát először egy elemmel:
PS C:\> $ll = [mylinkedlist]::new("Root")
PS C:\> $ll
RootElement CurrentElement Count
----------- -------------- -----
Root Root 1
PS C:\> $ll.ListElements()
Value NextElement PreviousElement
----- ----------- ---------------
Root
Miután egy elemünk van, az egyben a RootElement és a CurrentElement is. Fűzzünk a listába további elemeket:
PS C:\> $ll.CurrentElement.LinkAfter("Egy")
PS C:\> $ll.CurrentElement.LinkAfter("Kettő")
PS C:\> $ll.CurrentElement.LinkAfter("Három")
Ha listázzuk az elemeket:
PS C:\> $ll.ListElements()
Value NextElement PreviousElement
----- ----------- ---------------
Root Egy
Egy Kettő Root
Kettő Három Egy
Három Kettő
Grafikusan ábrázolva így néz ki a listánk:
62 . ábra Láncolt lista példa
Miután mindig a CurrentElement-hez képes illesztettük be az újabb elemeket, ezért alakult ki a fenti egyszerű láncolat. Ha a Root elé akarok beilleszteni egy elemet azt is egyszerűen megtehetem:
PS C:\> $ll.RootElement.LinkBefore("Mínuszegy")
PS C:\> $ll.ListElements()
Value NextElement PreviousElement
----- ----------- ---------------
Root Egy Mínuszegy
Egy Kettő Root
Kettő Három Egy
Három Kettő
Mínuszegy Root
Látszik, hogy a felsorolásban ez az új Mínuszegy elem került a végére, mert először a Root-hoz képest a következő elemek jönnek, majd a megelőzőek. A láncnak most is van két vége, a Mínuszegy és a Három, ezeknek vagy megelőző, vagy következő elemük nincsen. A CurrentElement most is az utoljára berakott elem lett.
Lépkedjünk egy kicsit! Ha előre lépünk kettőt, akkor az Egy elemhez jutunk:
PS C:\> $ll.GetNextElement(2)
Value NextElement PreviousElement
----- ----------- ---------------
Egy Kettő Root
Ezzel az aktuális elem is ez lett:
PS C:\> $ll
RootElement CurrentElement Count
----------- -------------- -----
Root Egy 5
63 . ábra Lista állapota 2 lépés előre után
Itt a listánk nyitott, de a szabad végeket össze is köthetjük:
PS C:\> PS C:\> $ll.MakeRing()
Value NextElement PreviousElement
----- ----------- ---------------
Mínuszegy Root Három
Három Mínuszegy Kettő
Látható, hogy így már minden NextElement és PreviousElement mutat egy másik elemre. Így néz ki most a listánk, a CurrentElement a lánc volt vége lett:
64 . ábra Lista gyűrűvé alakítva
Ha már gyűrűnk van, akkor akár 101 elemmel is léphetünk hátra, ami 5 elem esetében pont a Három-at fogja megadni:
PS C:\> $ll.GetPreviousElement(101)
Value NextElement PreviousElement
----- ----------- ---------------
Három Mínuszegy Kettő
Ha ez Egy és a Kettő közé be akarom illeszteni a Másfél nevű elemet, akkor vagy a Kettő utáni, vagy az Egy előtti elemként kell ezt megtennünk, az előbbi így néz ki:
PS C:\> $ll.CurrentElement.PreviousElement.LinkBefore("Másfél")
PS C:\> $ll.ListElements()
Value NextElement PreviousElement
----- ----------- ---------------
Root Egy Mínuszegy
Egy Másfél Root
Másfél Kettő Egy
Kettő Három Másfél
Három Mínuszegy Kettő
Mínuszegy Root Három
Ha el akarunk távolítani egy elemet, akkor először arra kell állni. Én most a Root-ot akarom törölni:
PS C:\> $ll.RootElement.Remove()
PS C:\> $ll.ListElements()
Value NextElement PreviousElement
----- ----------- ---------------
Egy Másfél
Másfél Kettő Egy
Kettő Három Másfél
Három Mínuszegy Kettő
Mínuszegy Három
PS C:\> $ll
RootElement CurrentElement Count
----------- -------------- -----
Egy Mínuszegy 5
Látszik, hogy a új RootElement elemünk lett, az Egy. Szakítsuk szét a körbezárt láncot:
PS C:\> $ll.CurrentElement.BreakRing()
PS C:\> $ll.ListElements()
Value NextElement PreviousElement
----- ----------- ---------------
Egy Másfél
Másfél Kettő Egy
Kettő Három Másfél
Három Mínuszegy Kettő
Mínuszegy Három
Illetve láncolt listát eleve sok elemmel is létre tudok hozni:
PS C:\> $l1 = [mylinkedlist]::new((1,22,333,4444,55555))
PS C:\> $l1.ListElements()
Value NextElement PreviousElement
----- ----------- ---------------
1 22
22 333 1
333 4444 22
4444 55555 333
55555 4444
Itt fontos, hogy a new után két zárójelpár legyen, ha csak egyet használnánk, akkor hibát kapunk, mert nincs olyan szintaxisunk, ami több értéket fogadna, egy értéket vár, ami persze lehet egy gyűjtemény is.
Nézzük, mennyire hatékony ez a láncolt lista adattípus, ha 200.000 új elemet illesztek bele, összehasonlítva egy ArrayList-hez képest:
$s = Get-Date
$l2 = [mylinkedlist]::new("Root")
for($i = 0; $i -lt 200000;$i++){
$l2.RootElement.LinkAfter($i)
}
((Get-Date) - $s).totalseconds
$s = Get-Date
$l3 = [collections.arraylist]@()
for($i = 0; $i -lt 200000;$i++){
[void]($l3.Insert(0,$i))
}
((Get-Date) - $s).totalseconds
Ennek eredménye két futási idő másodpercben:
5,3780101
11,6048898
Látható, hogy a MyLinkedList kétszer olyan gyors volt, mint az ArrayList! Pedig a drámai lassulása az ArrayList-nek csak 500 ezer elem felett kezdődik igazán.
A láncolt listával akár quque (sor) vagy zsák (stack) adattípust is tudunk szimulálni.
A láncolt lista mellett egy másik gyakran használható adattípus a gráf. Ebben elemek vannak, melyek között lehetnek irányított összeköttetések. Gráfokkal – többek között – legrövidebb útvonal meghatározásával kapcsolatos problémákat tudunk megoldani.
A gráfot is két osztály segítségével valósítottam meg, az egyik a MyGraphElemenet, ami a gráf elemeit adja. Itt is, hasonlóan a láncolt lista elemeihez, az elemek kapcsolódnak a gráfjukhoz a $Graph tulajdonságon keresztül. Érdekes módon itt kénytelen voltam explicit referencia adattípussal ábrázolni ezt, egyéb esetben futási időben hibát kaptam. A kapcsolódásokat $IncomingLinks és $OutgoingLinks tulajdonságokban tárolom, mindkettő egy gráfelem típusú lista típus. Egy kapcsolat valamelyik elemből kiindul (Outgoing), a másik elembe befut (Incoming). Ha kétirányú a kapcsolat, akkor fordítva is van egy ilyen kapcsolatpár.
class MyGraphElement {
[PSObject] $Value = $null
[collections.generic.list[MyGraphElement]] $IncomingLinks = @()
[collections.generic.list[MyGraphElement]] $OutgoingLinks = @()
hidden [ref] $Graph
MyGraphElement ([PSObject]$iValue, [ref]$iGraph){
$this.Value = $iValue
$this.Graph = $iGraph
$iGraph.value.Elements.Add($this)
}
[MyGraphElement] AddNew ([PSObject] $newvalue) {
$newelement = [MyGraphElement]::new($newvalue, [ref]$this.Graph)
$this.OutgoingLinks.Add($newelement)
$newelement.IncomingLinks.Add($this)
return $newelement
}
[MyGraphElement] AddNewBidirectional ([PSObject] $newvalue) {
$newelement = [MyGraphElement]::new($newvalue, [ref]$this.Graph)
$this.OutgoingLinks.Add($newelement)
$newelement.IncomingLinks.Add($this)
$this.IncomingLinks.Add($newelement)
$newelement.OutgoingLinks.Add($this)
return $newelement
}
[string] ToString (){
return $this.Value.ToString()
}
}
A gráfelemnek természetesen van egy értéke ($Value) és konstruktora. Ezeken kívül van egy AddNew metódusa, amivel az adott elemhez lehet csatolni egyirányú módon egy teljesen új elemet. Ez az új elem ugyanahhoz a gráfhoz fog tartozni. Az AddNewBidirectional metódussal ugyancsak egy teljesen új elemet lehet a meglevő elemhez fűzni, de itt a kapcsolat kétirányú lesz. Ezen kívül van még egy ToString metódusunk is, ami egyszerűen az elem értékének szöveges formáját adja vissza.
Maga a gráf osztály a MyGraph definícióval a következő:
class MyGraph {
[collections.generic.list[MyGraphElement]] $Elements = @()
MyGraph (){
}
MyGraph ([PSObject] $FirstElementValue){
$this.AddNewElement($FirstElementValue)
}
[bool] Remove([MyGraphElement]$GraphElement){
$removed = $this.Elements.remove($GraphElement)
if($removed){
foreach($element in $this.Elements){
[void]$element.IncomingLinks.Remove($GraphElement)
[void]$element.OutgoingLinks.Remove($GraphElement)
}
}
return $removed
}
[bool] Remove([int]$ElementIndex){
$toremove = $this.Elements[$ElementIndex]
return $this.Remove($toremove)
}
AddNewElement ([PSObject] $GraphElementValue){
$newElement = [MyGraphElement]::new($GraphElementValue, [ref]$this)
}
AddNewElement ([PSObject] $GraphElementValue, [mygraphelement] $element){
$element.AddNew($GraphElementValue)
}
AddNewElementBidirectional ([PSObject] $GraphElementValue, [mygraphelement] $element){
$element.AddNewBidirectional($GraphElementValue)
}
LinkElements ([MyGraphElement] $From, [MyGraphElement] $To){
if(!$From.OutgoingLinks.contains($To)){
$From.OutgoingLinks.Add($To)
}
if(!$To.IncomingLinks.Contains($From)){
$To.IncomingLinks.Add($From)
}
}
LinkElements ([int] $FromIndex, [int] $ToIndex){
$this.LinkElements($this.Elements[$FromIndex], $this.Elements[$ToIndex])
}
LinkElementsBidirectional ([MyGraphElement] $Element1, [MyGraphElement] $Element2){
$this.LinkElements($Element1, $Element2)
$this.LinkElements($Element2, $Element1)
}
LinkElementsBidirectional ([int] $Element1Index, [int] $Element2Index){
$Element1 = $this.Elements[$Element1Index]
$Element2 = $this.Elements[$Element2Index]
$this.LinkElementsBidirectional($Element1, $Element2)
}
BreakLink ([MyGraphElement] $From, [MyGraphElement] $To){
[void] $From.OutgoingLinks.Remove($To)
[void] $To.IncomingLinks.Remove($From)
}
BreakLink ([int] $FromIndex, [int] $ToIndex){
$From = $this.Elements[$FromIndex]
$To = $this.Elements[$ToIndex]
$this.BreakLink($From, $To)
}
BreakLinkBidirectional ([MyGraphElement] $Element1, [MyGraphElement] $Element2){
$this.BreakLink($Element1, $Element2)
$this.BreakLink($Element2, $Element1)
}
BreakLinkBidirectional ([int] $Element1Index, [int] $Element2Index){
$Element1 = $this.Elements[$Element1Index]
$Element2 = $this.Elements[$Element2Index]
$this.BreakLinkBidirectional($Element1, $Element2)
}
}
Neki csak egy tulajdonsága van: az elemeinek tömbje ($Elements). Két konstruktora van, az első csak visszaadja az üres gráfot, a másik rögtön egy elemet is berak a gráfba. A további metódusok a következők:
Remove: kiszedi a paramétereként megadott elemet, ezt az elemet minden másik elem hivatkozásai közül is kiszedi. Mivel a gráf $Elements tulajdonsága egy lista, így indexelhető is, ezért van a Remove-nak egy olyan változata is, ahol nem gráfelemet adunk paraméterként meg, hanem egy indexet, amúgy ez is ugyanazt csinálja, mint az előző változat.
AddNewElement: ennek a metódusnak is több változata van. Az elsővel egy új elemet hozunk létre a paraméterként megadott értékkel, de ez az új elem nem kapcsolódik semelyik meglevő elemhez. A második változatban nem csak egy értéket, hanem egy meglevő elemet is megadunk paraméternek, az új elem ehhez lesz összefűzve. A harmadik változat már új nevet kapott, AddNewElementBidirectional, ennél az új elem a megadott harmadik elemhez kétirányú kapcsolattal jön létre.
LinkElements: ezzel két elemet lehet összefűzni egyirányú kapcsolattal. Az első változatban elemekre hivatkozunk a paraméterekben, a második változatban indexszel hivatkoznunk. Ezeknek is van Bidirectional változata is.
BreakLink: Ezzel lehet egyirányú kapcsolatokat felszakítani, elemes és indexes változat is van, valamint van ennek is Bidirectional változata is.
Nézzük ennek használatát pár egyszerű példán keresztül! Egy családot szeretnék ábrázolni, a családtagok viszonyrendszerével együtt. A család első tagja az Apa, vele együtt jön létre maga a gráf:
PS C:\> $család = [MyGraph]::new("Apa")
Az Anya vele egyenrangú, szimmetrikus kapcsolatban van:
PS C:\> $család.Elements[0].AddNewBidirectional("Anya")
Value IncomingLinks OutgoingLinks
----- ------------- -------------
Anya {Apa} {Apa}
Mind az Incoming, mind az Outgoing linkel összekapcsolódnak. Majd jönnek a gyerekek, ők már alárendelt viszonyban vannak az Apához képest:
PS C:\> $család.Elements[0].AddNew("Bence")
Value IncomingLinks OutgoingLinks
----- ------------- -------------
Bence {Apa} {}
PS C:\> $család.Elements[0].AddNew("András")
Value IncomingLinks OutgoingLinks
----- ------------- -------------
András {Apa} {}
PS C:\> $család.Elements[0].AddNew("Fanni")
Value IncomingLinks OutgoingLinks
----- ------------- -------------
Fanni {Apa} {}
A család most így áll:
PS C:\> $család.Elements
Value IncomingLinks OutgoingLinks
----- ------------- -------------
Apa {Anya} {Anya, Bence, András, Fanni}
Anya {Apa} {Apa}
Bence {Apa} {}
András {Apa} {}
Fanni {Apa} {}
Egészítsük ki a kapcsolatokat az Anya és a gyerekek között. Anya az 1-es elem, a gyerkőcök a 2,3,4:
PS C:\> $család.LinkElements(1,2)
PS C:\> $család.LinkElements(1,3)
PS C:\> $család.LinkElements(1,4)
PS C:\> $család.Elements
Most már teljes a kapcsolatrendszer:
Value IncomingLinks OutgoingLinks
----- ------------- -------------
Apa {Anya} {Anya, Bence, András, Fanni}
Anya {Apa} {Apa, Bence, András, Fanni}
Bence {Apa, Anya} {}
András {Apa, Anya} {}
Fanni {Apa, Anya} {}
Ha még van lét házikedvenc, azokat is betehetjük a gráfba, ők nem kapcsolódnak senkihez most a mi modellünkben:
PS C:\> $család.AddNewElement("Jenő")
PS C:\> $család.AddNewElement("Pamacs")
Az összes családtag így:
PS C:\> $család.Elements
Value IncomingLinks OutgoingLinks
----- ------------- -------------
Apa {Anya} {Anya, Bence, András, Fanni}
Anya {Apa} {Apa, Bence, András, Fanni}
Bence {Apa, Anya} {}
András {Apa, Anya} {}
Fanni {Apa, Anya} {}
Jenő {} {}
Pamacs {} {}
Ha esetleg a szülők elválnának, akkor így nézne ki a kapcsolatrendszer:
PS C:\> $család.BreakLinkBidirectional(0,1)
PS C:\> $család.Elements
Value IncomingLinks OutgoingLinks
----- ------------- -------------
Apa {} {Bence, András, Fanni}
Anya {} {Bence, András, Fanni}
Bence {Apa, Anya} {}
András {Apa, Anya} {}
Fanni {Apa, Anya} {}
Jenő {} {}
Pamacs {} {}
Ha az Apa kilép a családból:
PS C:\> $család.Remove(0)
True
PS C:\> $család.Elements
Value IncomingLinks OutgoingLinks
----- ------------- -------------
Anya {} {Bence, András, Fanni}
Bence {Anya} {}
András {Anya} {}
Fanni {Anya} {}
Jenő {} {}
Pamacs {} {}
És Anya hoz egy apapótlékot:
PS C:\> $család.Elements[0].AddNew("Apapótlék")
Value IncomingLinks OutgoingLinks
----- ------------- -------------
Apapótlék {Anya} {}
PS C:\> $család.Elements
Value IncomingLinks OutgoingLinks
----- ------------- -------------
Anya {} {Bence, András, Fanni, Apapótlék}
Bence {Anya} {}
András {Anya} {}
Fanni {Anya} {}
Jenő {} {}
Pamacs {} {}
Apapótlék {Anya} {}
A gráffal lehet fa (Tree) adatstruktúrát is megvalósítani, ilyekor egy elemnek csak maximum két elemmel lehet kapcsolata és nem szabad hurkot kialakítanunk.