Τετάρτη 6 Απριλίου 2016

Παράδειγμα με Ουρά Προτεραιότητας ΙΙ

Πρόσθεσα την Merge, την συγχώνευση μια ουράς σε μια άλλη. Αντί να χρησιμοποιώ την Poll() που βρίσκει κάθε φορά τον μεγαλύτερο για την ουρά που θα αδειάσει (και άρα δεν μου χρειάζεται), παίρνω το τελευταίο κάθε φορά και το βάζω με την γρήγορη Add στην ουρά που καταχωρώ.

Προσθήκες  (με το νεότερο διερμηνευτή)
Μπορούμε να βάλουμε  το Class:  πριν την Module Item  {} στη Class Item, ώστε το τελικό αντικείμενο να μην καταχωρεί τον κατασκευαστή.

Εκτέλεση:
Εκτελούμε το M2000.exe
Γράφουμε edit a στη κονσόλα, πατάμε enter, αντιγράφουμε το παρακάτω και πατάμε esc.
Μπορούμε να το εκτελέσουμε με την a και πατάμε enter, ή με την test a και πατάμε enter. Με το δεύτερο τρόπο μπορούμε να εκτελούμε εντολή προς εντολή. Αν θέλουμε μπορούμε να βάλουμε μέσα στο κώδικα την test "a breakpoint name", ώστε να σταματάει κάθε φορά στο σημείο αυτό ο κώδικας και να ανοίγει τη φόρμα ελέγχου αν δεν είναι ανοιχτή. Από τη φόρμα ελέγχου μπορούμε να επιλέξουμε αργή εκτέλεση, και πάλι θα σταματήσει σε μια εντολή test (αν έχουμε βάλει).
Για τα παραπάνω ελληνικές εντολές είναι η  Σ Α (συγραφή Α) και η Δοκιμή Α



Class PriorityQueue {
Private:
      Dim Item()
      many=0, level=0, first
      cmp = lambda->0
      Module Reduce {
            if .many<.first*2 then exit
            If .level<.many/2 then .many/=2 : Dim .Item(.many)
      }
Public:
      Module Clear {
        Dim .Item() \\ erase all
        .many<=0 \\ default
        .Level<=0
      }
      Module PriorityQueue {
            If .many>0 then Error "Clear List First"
            Read .many, .cmp
            .first<=.many
            Dim .Item(.many)
      }
      Module Add {
           If .level=.many Then {
                 If .many=0 then Error "Define Size First"
                  Dim .Item(.many*2)
                  .many*=2
           }
           Read Item
           If .level=0 Then {
                 .Item(0)=Item
           } Else.if .cmp(.Item(0), Item)=-1 Then { \\ Item is max
                 .Item(.level)=Item
                 swap .Item(0), .Item(.level)
           } Else .Item(.level)=Item
           .level++
      }
      Function Peek {
            If .level=0 Then error "empty"
            =.Item(0)
      }
      Function Poll {
            If .level=0 Then error "empty"
            =.Item(0)
            If .level=2 Then {
            swap .Item(0), .Item(1)
            .Item(1)=0
            .Level<=1
            } Else.If .level>2 Then {
                  .Level--
                  Swap .Item(.level), .Item(0)
                  .Item(.level)=0
                  For I=.level-1 to 1 {
                        If .cmp(.Item(I), .Item(I-1))=1 Then Swap .Item(I), .Item(I-1)
                  }
            } else .level<=0 : .Item(0)=0
            .Reduce
      }
      Module Remove {
            If .level=0 Then error "empty"
            Read Item
            k=true
            If .cmp(.Item(0), Item)=0 Then {
                  Item=.Poll()
                  K~  \\ k=false
            } Else.If .Level>1 Then {
                  I2=.Level-1
                      For I=1 to I2 {
                              If k Then {
                                     If .cmp(.Item(I), Item)=0 Then {
                                           If I<I2 Then Swap .Item(I), .Item(I2)
                                           .Item(I2)=0
                                           k=false
                                     }
                              } else exit
                        }
                 .Level--
            }
            If k Then Error "Not Found"
            .Reduce
      }
      Function Size {
            If .many=0 then Error "Define Size First"
            =.Level
      }
      Function DropLast {
            If .level=0 Then error "empty"
            .Level--
            =.Item(.Level)
            .Item(.Level)=0 ' Nil
      }
      Module Merge {
           Read &ExternalQueue
           Try {
                   .Add ExternalQueue.Droplast()
                   Loop
            }
            ExternalQueue.Clear
      }
}
Class Item { X
      Module Item { Read .X}
}
Comp=Lambda -> { Read A,B : =COMPARE(A.X,B.X)}


Queue=PriorityQueue(100,Comp)
Queue.Add Item(10)
Queue.Add Item(20)
Queue.Add Item(5)
Queue2=PriorityQueue(100,Comp)
Queue2.Add Item(4)
Print Queue2.Size(), Queue.Size() \\ 1,  3
Queue2.Merge &Queue
Print Queue2.Size() \\ 4
Try {
      Print Queue.Size()
}
M=Queue2.Peek() : Print "Item ";M.X




Queue=PriorityQueue(100,Comp)
Queue.Add Item(5)
Queue.Add Item(10)
Queue.Add Item(4)
Queue2=PriorityQueue(100,Comp)
Queue2.Add Item(20)
Print Queue2.Size(), Queue.Size() \\ 1,  3
Queue2.Merge &Queue
Print Queue2.Size() \\ 4
Try {
      Print Queue.Size()
}
For i=1 to 4
      M=Queue2.Poll() : Print "Item ";M.X
next i


Queue=PriorityQueue(100,Comp)
Queue.Add Item(20)
Queue.Add Item(10)
Queue.Add Item(4)
Queue2=PriorityQueue(100,Comp)
Queue2.Add Item(5)
Print Queue2.Size(), Queue.Size() \\ 1,  3
Queue2.Merge &Queue
Print Queue2.Size() \\ 4
Try {
      Print Queue.Size()
}
For i=1 to 4
      M=Queue2.Poll() : Print "Item ";M.X
next i


Queue=PriorityQueue(100,Comp)
Queue.Add Item(5)
Queue.Add Item(20)
Queue.Add Item(10)
Queue2=PriorityQueue(100,Comp)
Queue2.Add Item(4)
Print Queue2.Size(), Queue.Size() \\ 1,  3
Queue2.Merge &Queue
Print Queue2.Size() \\ 4
Try {
      Print Queue.Size()
}
For i=1 to 4
      M=Queue2.Poll() : Print "Item ";M.X
next i

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου

You can feel free to write any suggestion, or idea on the subject.