[Løst] DLL som subclass av SLL, (double/single linked list)

[ladetskje]

Hei!
Jeg har en pakke sll med klassene SLL og SLLNode:

package sll;
public class SLL{
    public SLL() {}
    public void prepend(int x){
        SLLNode n = new SLLNode(x);
        n.next = head;
        head = n;
    }
    public SLLNode getFirst(){
        return head;
    }
    public SLLNode findFirstGreaterThan(int x) {
        SLLNode n = head;
        while (n!=null)
            if (n.getVal()>x)
                return n;
            else
                n=n.next;
        return null;
    }
    protected SLLNode head = null;
}

public class SLLNode{
    protected SLLNode(int x){
       value = x;
    }
    public int getVal(){
       return value;
    }
    public SLLNode getNext(){
        return next;
    }
    private int value;
    private SLLNode next = null;
}

Og en pakke dll, som er subclass

package dll;
class DLL extends SLL{
    public DLL() {...}
    public DLLNode getFirst(){ ... }
    public DLLNode findFirstGreaterThan(int x){...}
    ...
}

class DLLNode extends SLLNode{
    protected DLLNode(int x){...}
    public DLLNode getNext(){...}
    public DLLNode getPrev(){...}
    private DLLNode prev;
}

Hvis formålet med subclassen er at koden skal brukes på nytt, uten å endre koden i sll, hvilken metode fra sll kan helt klart ikke brukes og må derfor dupliseres? Mitt første instinkt var at dette er metoden findFirstGreaterThan(), er dette korrekt?

Takker for hjelp

Endret 21. oktober 2013 av ladetskje

[jonny]

Metoden "prepend()" må skrives spesielt for DLL, da det er den eneste metoden der du legger noe inn i lista. Du må passe på å legge DLLNode-objekter inn i DLL-lista (metodene som returnerer DLLNode, f.eks. findFirstGreaterThan(), kan f.eks. bare inneholde "(DLLNode)super.findFirstGreaterThan(x);", men da må verdiene i lista selvfølgelig være DLLNode-objekter).

[ladetskje]

Metoden "prepend()" må skrives spesielt for DLL, da det er den eneste metoden der du legger noe inn i lista. Du må passe på å legge DLLNode-objekter inn i DLL-lista (metodene som returnerer DLLNode, f.eks. findFirstGreaterThan(), kan f.eks. bare inneholde "(DLLNode)super.findFirstGreaterThan(x);", men da må verdiene i lista selvfølgelig være DLLNode-objekter).

Ah, så klart! Takk!

 

Hvis jeg nå vil bruke prepend metoden i DLL også, (er en skoleoppgave), hvordan kan jeg endre implementasjonen av sll pakken? Dette uten å endre public interface og client visible behavior for verken SLL eller SLLNode klassene. sll pakken kan ikke referere til dll pakken eller dets innhold på noen måte, og kan ikke selv implementere en double linked list.

 

Tenker da at jeg må prøve å skrive en metode som ikke bruker SLLNode, men sitter veldig fast på hvordan dette eventuelt kan utføres.

[jonny]

Du kan kalle "super.prepend(x)" i DLL.prepend(). Da vet du at "head" peker på et nytt SLLNode-objekt. Det må du bytte ut med et DLLNode-objekt, og samtidig passe på å sette "prev" for det DLLNode-objektet som ble flyttet (hvis det fantes noen elementer i lista fra før).

 

Edit: Hvordan ble oppgaven gitt i utgangspunktet? Det er enkelte ting som ikke fungerer slik koden er oppgitt i første post, bl.a. kan ikke SLLNode.next ha "private" modifier, da vil ikke SLL kunne bruke den direkte slik koden gjør nå...

Endret 22. oktober 2013 av jonny

[ladetskje]

Her er oppgaven, så jeg SLLNode.next må vel endres til protected eller?

How can we modify the implementation of the sll package in order to allow reuse of this

method, without changing the public interface and client visible behaviour for either the

SLL or SLLNode classes (the protected and private parts can be changed as long as these

changes are not visible to clients of the classes that are outside the sll package). The

sll package is not allowed to refer to the dll package or its contents in any way, and

must not implement a doubly linked list itself. Write the code for all the changes that

are necessary to make this method reusable.

Så det du mener er at jeg i DLL:

public void prepend (int x) {

super.prepend(x);

....

også vet jeg ikke hvordan jeg kan endre SLLNode-objektet med et DLLNode-objekt?

Endret 22. oktober 2013 av ladetskje

[jonny]

Ja, SLLNode.next må være protected for at DLLNode skal få tilgang, fordi disse klassene ikke tilhører samme pakke (hvis de hadde gjort det, kunne du bare ha fjernet private).

 

Du kan ikke endre SLLNode-objektet, du må bare bytte det ut. Noe slikt:

super.prepend(x);
DLLNode newHead = new DLLNode(head);
DLLNode next = (DLLNode)newHead.getNext();
if (next != null) next.prev = newHead;
head = newHead;

// samtidig må du endre constructor i DLLNode slik:

protected DLLNode(sll.SLLNode sllnode) {
  super(sllnode.getVal());
  next = (DLLNode)sllnode.getNext();
}

Dette blir utrolig klønete, jeg ville aldri ha latt DLL arve SLL eller omvendt. Begge klassene er lister, og kan dermed implementere et felles List-interface eller lignende, og evt. arve en AbstractList-klasse (som er abstrakt) med kode som med stor sannsynlighet er felles for dem.

 

Men hvordan var koden oppgitt i oppgaven? Koden i første post inneholder feil, som tidligere nevnt...

[ladetskje]

Ok, takk! Ja, enig i at det ikke er det optimale.

 

Koden er copy/paste fra oppgaven, så da er nok koden gitt med feil.