HashTable ver 1.0 (M2000)

Υπάρχει ανώτερος κώδικας στην έκδοση 2.0


Προχωρημένο θέμα!
Αυτός ο κώδικας γράφτηκε στα αγγλικά (θα φτιαχτεί και στα ελληνικά). Θέλει την αναθεώρηση 133

Δημιουργώ μια κλάση HashTable που δίνει ένα αντικείμενο Alfabeta με δυνατότητα να αποθηκεύω για ένα κλειδί (εδώ ένα όνομα) κάποια στοιχεία. Χρησιμοποιώ μια συνάρτηση κατακερματισμού (hash), και θέλω να δω τη συμπεριφορά της, για έξι εισαγωγές. Θα χρησιμοποιήσω αρχικά έναν πίνακα 6 στοιχείων, δηλαδή θα τον γεμίσω 100%. Η δοκιμή πρέπει να γίνει και για άλλα μεγέθη πίνακα, π.χ. 10, 12, 20, 30. (Έχει σχεδιαστεί το πρόγραμμα για όσες περίπου γραμμές κειμένου έχει η οθόνη μας).

Με κόκκινο χρώμα μας εμφανίζει τα κλειδιά που μας δίνουν με τη συνάρτηση κατακερματισμού "πιασμένη" θέση. Στις πιασμένες θέσεις  η κλάση HashTable επιλέγει την επόμενη θέση, αν δεν υπάρχει άλλη γυρίζει από την αρχή και ψάχνει για άδεια θέση. Σε περίπτωση που ζητήσουμε κλειδί που δεν υπάρχει ή ζητήσουμε να βάλουμε περισσότερα στοιχεία απ΄όσα χωράει ο πίνακας τότε βγαίνει λάθος. Η κλάση παρέχει μια ακόμα ευκολία. Κρατάει μια λίστα κλειδιών ταξινομημένα. Κάθε εισαγωγή κάνει νέα ταξινόμηση των κλειδιών. Η κλάση HashTable δίνει ένα αντικείμενο Iterator, με την συνάρτηση .iterator() που το χρησιμοποιούμε για να μετακινηθούμε στα ταξινομημένα στοιχεία.
Μπορούμε να αλλάζουμε δεδομένα για κάποιο κλειδί με μεγάλη ευκολία διότι δεν χρειάζεται "πολύ" ψάξιμο...Η συνάρτηση κατακερματισμού μας πάει στην πιθανή θέση...Αν δεν το βρούμε εκεί συνεχίζουμε παραπάνω (και κυκλικά αν χρειαστεί).
Μπορούμε να διαγράψουμε κάποιο κλειδί. Όμως εδώ έχουμε ένα πέναλτι...Διότι η διαγραφή κλειδιού θα κάνει νέο κατακερματισμό για όλα τα κλειδιά, δημιουργώντας νέο πίνακα.
Ένας άλλος τρόπος θα ήταν να κρατηθεί το κλειδί και να γραφτεί στα δεδομένα μια "σημαία" διαγραφή. Αν ψάχνουμε να βάλουμε ένα νέο κλειδί και πέσουμε πάνω σε "διαγραμμένο" τότε το αντικαθιστούμε με αυτό! Το πρόβλημα με αυτή την προσέγγιση είναι ότι μπορεί να γεμίσει ο πίνακας με "άχρηστα". Εδώ λοιπόν χρειάζεται ο επανακερματισμός. Αυτός ο τρόπος με τη σημαία δεν εμφανίζεται σε αυτή την ανάρτηση. Εδώ κάνουμε σε κάθε διαγραφή αφαίρεση και επανακερματισμό.

Είναι 258 γραμμές! Χρησιμοποιώ μια ρουτίνα απλή (gosub return) για να βάλω την κλάση στο τέλος (ενώ κανονικά πρέπει να τρέξει πρώτα αυτή για να δημιουργηθεί η συνάρτηση που επιστρέφει το αντικείμενο hashTable). Επίσης χρησιμοποιώ τρεις ρουτίνες κανονικές (Sub End Sub) για να εμφανίσω τα στοιχεία.

(Είχε ένα θέμα στην αντιγραφή στο Blog, αλλα διορθώθηκε - είχε μπει μια αλλαγή γραμμής μετά από ένα  Then και σε αυτή τη περίπτωση δεν βρήκε ο διερμηνευτής το End If και έβγαλε λάθος στην ρουτίνα που κάλεσε τη ρουτίνα, επειδή δεν βρήκε το "σωρό επιστροφής" των ρουτινών σωστό!)

Linespace 0 : Window 12,1 : Linespace 30 : Form 84 : Pen 14 : Cls 1 : Back { Cls 1 } \ "back" for frame behind
Refresh 100
Report 2,"Hash Table ver1.0"
Gosub MyClass   \\ define class first
\\ Change Here the size of hash table
\\ try  Hashtable(6)  Hashtable(10) Hashtable(20)
Alfabeta=Hashtable(6)  '' we can make 100 or 1000 or 10000 and time to read and write is the same
\\
\\
Print $(0,6), "Items in table:";Alfabeta.ValidItems()   ' normal printing, 10 chars per column
Alfabeta.ItemNew "Zorro The Great", "data123456"
Alfabeta.ItemNew "Black Smith", "data1334245", "Alexander III", "data345678"
Alfabeta.ItemNew "Singer Sofia", "data1313113", "Panatha Maria", "data234234"
Print "Search Alfabeta key ";
Profiler
Print Alfabeta.Item$("Black Smith")
Print Timecount
Print Alfabeta.Item$("Panatha Maria")
Print "Search Alfabeta key ";
Profiler
Print Alfabeta.Item$("Alexander III")
Print Timecount
Alfabeta.ItemNew "HelloBoy IV","data431254"
Print format$("Per cent use of table:{0}%", Alfabeta.percentfull())
Gosub Col2()
if Alfabeta.ExistItem("Black", True) then print "Bleck", Alfabeta.item_no
Print "Items in table:";Alfabeta.ValidItems()
if Alfabeta.ExistItem("Singer", True) then {
      print "Singer", Alfabeta.item_no
      For Alfabeta {
            Print format$("Found the real key as:{0}", .ItemKey$(.Item_no))


           aaaa=.RemoveItem(.ItemKey$(.Item_no)) 
      }
}
If Alfabeta.RemoveItem("Black Smith") then Print "ok"
Gosub Col2()
Alfabeta.ItemNew "Singer Sofia", "data1313113"
Alfabeta.ItemNew "Black Smith", "data1334245"


Print "Items in table:";Alfabeta.ValidItems()
Gosub Col2()
Print "End"


Sub Display(x)
      local i   \\ now i is Alfabeta new one
      For i=0 to Alfabeta.items-1 {
      Aa$=Alfabeta.data$(i,0)
      if Aa$<>"" then Print @(x),i,") "+ Aa$, Alfabeta.data$(i,1)
      }
End Sub
Sub DisplayItem(x)
      local i,j, k$ 
      i=Alfabeta.Iterator()
      Print @(x),"Items:"; i.itemmax
      While i.NextItem()  {
            Aa$=i.key$()
            for Alfabeta {
                  k$=.Item$(Aa$)  ' give .item_no also
                  j=.Hash(Aa$)
                  Pen 11-(.item_no<>j) {
                        Print @(x),i.item,") "+ Aa$, k$, j , .item_no
                  }
            }
      }
End Sub
Sub Col2()
      local Row1, Row2, aa$
      Print "Real Position in Table"
      Row1=row
      If row1+Alfabeta.items> height then row1=Height-Alfabeta.items-1 
      Pen 13 {
            Gosub Display(0)
      }
      if row1>=0 then {
            row2=row
            Cursor 0,row1-1
            Gosub DisplayItem(tab(6))
            Cursor 0,Max.Data(Row, Row2)
      } else  Gosub DisplayItem(0) 
      Report 2,"Press any Key"
      aa$=key$
End Sub
MyClass:
Class HashTable {
      item_no, items
      lasts$, spos
      newkey=True
      Document sort1$=""
      nl$={
      }
      dim data$()
      Module HashTable {
            read .items
            Clear .sort1$  \\ need that if we need rehash
            Dim  .data$(.items, 2)=""
      }
      Function PerCentFull {
            if .items=0 Then Error 9999
            k=.items
            for i=0 to .items-1 {
               if .data$(i,0)="" Then k--   
            }
            =k/.items*100
      }
      Function F {
            read A, b 
            b+=52334321*A
            push binary.xor(b,0X3F3C)
      }
      Function Hash {
            Read Alfabeta$
            Push 0 
            for i=1 to len(Alfabeta$)
             call .F(asc(mid$(Alfabeta$,i)))
            next i
            =BINARY.OR(Number,  0XAFFAAFFA) mod .items
      }
      Module Item {
            .newkey<=false
            .ItemNew
            .newkey<=True
      }
      Module ItemNew {
            While match("SS") {
            Read name$, data$
            name$=ucase$(name$)
            i=.Hash(name$)
            j=i
            {
                 if .data$(i,0)<>"" Then  {
                      if .data$(i,0)=name$ Then {
                  
                         if .newkey Then  {
                         ? name$
                         Error 10000
                         }
                         .item_no<=i
                        j=-1 
                        } else i++ : if i=.items Then i=0
                  } else exit
                  if i=j Then Error 10020
                  if j>=0 Then Loop
            }
            .data$(i,0):=name$, data$
            if j=-1 Else .sort1$<=name$+.nl$ : sort .sort1$,1, doc.par(.sort1$)-1
            }
      }
      Function Item$ {
            Read name$
            name$=ucase$(name$)
            i=.Hash(name$)
            j=i
            {
                  if .data$(i,0)=name$ Then  {
                        =.data$(i,1)
                        .item_no<=i
                        j=-1  
                  } else.if .data$(i,0)="" Then {
                       Error 20030 \\ not found
                  } else  i++ : if i=.items Then i=0
                   if i=j Then Error 20020  \\ not found and is full
                  if j>=0 Then Loop
           }
      }
      Function FastExistItem {
            Read name$
            name$=ucase$(name$)
            i=.Hash(name$)
            j=i
            {
                  if .data$(i,0)=name$ Then  {
                        =True
                        .item_no<=i
                        j=-1
  
                  } else.if .data$(i,0)="" Then {
                       Error 20030 \\ not found
                  } else  i++ : if i=.items Then i=0
                   if i=j Then Error 20020  \\ not found and is full
                  if j>=0 Then Loop
           }
      }
      Function ExistItem {
            if match("S") then {
                  read .lasts$
                  .lasts$ <= ucase$(.lasts$)
                  .spos<=1
            }


            Find .sort1$, .lasts$, .spos
            Read .spos
            if .spos=0 then {
        
            } else {
                        Read .item_no, c
                        if match("N") then { read ok } else ok=false
                        if ok then {
                        .spos++ : =True
                         } else {
                        if c=1 then .spos++ : =True
                        }
            }      
            }
            Function ItemKey$ {
                  Read No
                  =Paragraph$(.sort1$,No)
            }
            Function ValidItems {
                  =doc.par(.sort1$)-1
            }
            Function Iterator {          
                  group aa { 
                        item, itemmax
                        ref$
                        Function nextitem {
                              .item++
                              =.item<=.itemmax
                        }
                        Function key$ {
                              if .item=0 then error 101010
                             = function$(.ref$.ItemKey$(), .item)
                        }     
                  }
                  aa.itemmax=.ValidItems() 
                  aa.ref$=&This
                  =aa
            }       
            Function RemoveItem {
            read Alfabeta$
            Alfabeta$=Ucase$(Alfabeta$)
            if .FastExistItem(Alfabeta$) then {
                   A1=This
                  A1.hashtable .items
                  I=.Iterator()
                  While i.NextItem()  {
                        Aa$=i.key$()
                        if Aa$<>Alfabeta$ then  A1.ItemNew Aa$, .Item$(Aa$)
                  }
                  This=A1
                  =True
               }
             }            
            Module ReHash {
                  A1=This
                  A1.hashtable .items
                  I=.Iterator()
                  While i.NextItem()  {
                        Aa$=i.key$()
                        A1.ItemNew Aa$, .Item$(Aa$)
                  }
                  This=A1

            }
}
Return