HASHING 9/9

 BBS: Inland Empire Archive
Date: 05-09-92 (01:17)             Number: 194
From: TOM HAMMOND                  Refer#: NONE
  To: LYN BORCHERT                  Recvd: NO  
Subj: HASHING     9/9                Conf: (2) Quik_Bas
Continued from HASHING 8/9

  IF NextEntry% <= 0 THEN
     PRINT "No Data Was Found To Display."
  ELSE
  'now that all the data has been moved from A$() to SortSpace$(), we
  'need to sort it.  How about an exchange sort?
     LastItem% = NextEntry% - 1
     IF LastItem% > 1 THEN
        PRINT "Sorting"; LastItem% + 1; "items.  Please Wait....."
        FOR I% = 0 TO LastItem% - 1
        Lowest% = I%
        FOR J% = I% + 1 TO LastItem%
            CompareCount! = CompareCount! + 1
            IF SortSpace$(J%, 0) < SortSpace$(Lowest%, 0) THEN
           Lowest% = J%
            END IF
        NEXT J%
        IF Lowest% <> I% THEN
           SWAP SortSpace$(I%, 0), SortSpace$(Lowest%, 0)
           SWAP SortSpace$(I%, 1), SortSpace$(Lowest%, 1)
        END IF
        NEXT I%
     ELSE
        PRINT "1 item found, the sort will be skipped this time...."
     END IF

     'Now the keys are sorted, so let's display the data....
     PRINT "Order", "Name", "Phone #", "Place in A$"

     DisplayCount% = 0
     FOR I% = 0 TO LastItem%
         Pointer% = VAL(SortSpace$(I%, 1))
         PRINT I%, a$(Pointer%, 0), a$(Pointer%, 1), Pointer%
         DisplayCount% = DisplayCount% + 1
         IF DisplayCount% > ScreenLimit% THEN
        CALL Waiter
        DisplayCount% = 0
         END IF
     NEXT I%
  END IF
  CALL Waiter
  RETURN

  SorryFull:
  PRINT "Sorry, but there is no space available in the array."
  PRINT "Try saving your data, stopping this program, resizing";_
CHR$(34); "ArraySize%"; CHR$(34); ","
  PRINT "reloading the saved data, and then retry this load."
  RETURN

  SUB GetData (Key$, Index%, SeekCount%, SaveIndex%)
  ' Try to get the index to the record that that contains Key$ as it's_
key
  ' Key$ - the value are looking for
  ' Found% - did we find Key$ - True/False returned
  ' Index% - a pointer to where Key$ was found
  ' SeekCount% - how many tries it took us to fing Key$
  ' SaveIndex% - the pointer to the first deleted value we found, if any

  Index% = Hash(Key$) 'start the search
  SaveIndex% = -1
  SeekCount% = 1

  IF a$(Index%, 0) <> "" AND a$(Index%, 0) <> Key$ THEN
     'if data in entry, and not a match, do a retry
     ReHashCount% = 0

      DO WHILE SeekCount% < RetryLimit% AND A$(Index%, 0) <> "" AND_
A$(Index%,0) <> Key$
        IF a$(Index%, 0) = DeletedValue$ AND SaveIndex% = -1 THEN
      'if this is the first deleted value, save it for data insertion
      SaveIndex% = Index%
        END IF

        Index% = Index% + PowersOfTwo%(ReHashCount%)
        DO WHILE Index% > ArraySize%
       Index% = Index% - ArraySize%
        LOOP

        ReHashCount% = ReHashCount% + 1
        IF ReHashCount% > PowerMax% THEN
       ReHashCount% = 0
        END IF

        SeekCount% = SeekCount% + 1
     LOOP
  END IF

  END SUB

  FUNCTION Hash (TestString$)
  ' turn TestString into a number in the range of 0 - ArraySize%
  ' the function can be tailored to suit the users needs

  Trial = 0

  FOR I% = 1 TO LEN(TestString$)
      Trial = Trial + ASC(MID$(TestString$, I%, 1))
  NEXT I%

  Hash = (Trial * Trial) MOD ArraySize%

  END FUNCTION

  SUB Waiter
  ' wait for a keypress, then return to caller
  PRINT "Press (almost) any key to continue..."
  K$ = ""
  DO WHILE K$ = ""
     K$ = INKEY$
  LOOP
  END SUB

  FUNCTION WhackIt$ (InputString$)
  'whack the input string -
  ' strip leading and trailing spaces,
  ' make the remainder upper case, and
  ' make it a single letter response.
  TestString$ = UCASE$(RTRIM$(LTRIM$(InputString$)))
  IF LEN(TestString$) > 1 THEN
     TestString$ = LEFT$(TestString$, 1)
  END IF
  WhackIt$ = TestString$
  END FUNCTION

End of 9 parts


--- WM v2.00/91-0231
 * Origin: The Modem Zone BBS (314) 893-5106 (1:289/2)
Outer Court
Echo Basic Postings

Books at Amazon:

Back to BASIC: The History, Corruption, and Future of the Language

Hackers: Heroes of the Computer Revolution (including Tiny BASIC)

Go to: The Story of the Math Majors, Bridge Players, Engineers, Chess Wizards, Scientists and Iconoclasts who were the Hero Programmers of the Software Revolution

The Advent of the Algorithm: The Idea that Rules the World

Moths in the Machine: The Power and Perils of Programming

Mastering Visual Basic .NET