OpenEuphoria

1. String Type

• Posted by Mathew Hounsell <mat.hounsell at EXCITE.COM> Mar 16, 1999
• 693 views
• Last edited Mar 17, 1999

Hello All,

The following is my design for a string type. I would prefer if it were
directly implemented by the compiler but it could be implemented by
libraries. As will undoubtablely be pointed out it is usually faster to read
a word (literal meaning) but the space saved in memmory plus all the
advantages to speed of having a restricted type would make it far out way
the advantages of reading a word. That and it would have less time and space
overhead of a sequence.

String Library Design.
======================

Author : Mathew Hounsell

Purpose : To provide a library capable of providing string functions
              to Euphoria.

Reason For Use Over Internal Types : The sequence use four bytes per
              character, wasting three.

Goals : * Minimum storage per string.
            - 1 byte per character.
            - + x Bytes overhead.
        * Euphoria style internl handling.
            - Reference Counts.
            - Stored Length.
        * Variablle length.

Other Considerations : Four byte boundaries.

Data Structure Design : Length.
                        Reference Count.
                        String...

The length of a string should be variable. However the greater the maximum
    size the greater the over head. Therefore a size of a reasonable length
    is needed. If one byte is used the string is limited to 256 bytes,
    often too small. If two bytes are used the string length is 64Kb which
    should in most cases be adequate.

A maximum number for the refence count needs to be decided. One byte (256)
    should be adequate.

Since Euphoria &/ OS will allocate memmory on four byte boundaries and of
an
    actual length of a multiple of 4 then we will do the same and use the
    extra space if needed. Since the padding is to make the size a
muultiple
    of four it will be a maximum of 3 bytes.

Data Structure Re-Design : Length (2B).
                           Reference Count (1B)
                           Size of Padding (2bits-1B)
                           String... ( < 64K )
                           Padding... ( < 3B )

User Interaction : Will be based on a virtual address, the start of the
                       string after the overhead.

Actions : - Creation
          - Deletion
          - Determining Length
          - Duplication
          - Replacing
          - Getting a Character
          - Changing a Character
          - Finding a Character
          - Comparing
          - Outputing
          - Concaternating a String and a Character
          - Concaternating two Strings
          - Make a String Upper Case
          - Make a String Lower Case

          - Transforming to a C String
          - Transforming to a Euphoria Sequence
          - Transforming from a C String
          - Transforming from a Euphoria Sequence
          - Slicing
          - Matching a Partial String
          - Inputing

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
INTERNAL TYPE VVA : a <-- Valid Virtual Adrress

    IF a THEN
        RETURN OK
    ENDIF

    ERROR : "String Does Not Exist"
    RETURN NOT_OK
END TYPE

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB Create : Length

    determine needed memmory including over head
    determine amount of padding
    allocate total needed memmory
    IF the memmory was allocated THEN
        store the Length
        store 0 for the refernce count
        store the ammount of padding
        RETURN the virtual address
    END IF
    RETURN 0
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB Delete : Address

    IF refernce count > 1 THEN
        decrement reference count
    ELSE
        free the memmory
    END IF
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB Length : VVA Address

    RETURN string length
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
INTERNAL SUB copy_str : VVA Address

    NewAddress = ( Create: ( Length:Address ) )
    IF NewAddress THEN
        copy contents of string into new string
    END IF
    RETURN NewAddress
END IF

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB Duplicate : VVA Address

    IF refence count < max THEN
        increment reference count
        RETURN Address
    END IF
    RETURN ( copy_str:Address )
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB Replace : VVA Destenation, VVA Source

    Delete:Destenation
    RETURN ( Duplicate:Source )
END IF

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB Get_Char : VVA Address, INT Index

    IF Index >= 1 AND Index <= ( Length:Address ) THEN
        RETURN Address[Index]
    END IF
    ERROR : "Invalid Index"
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB Set_Char : VVA Addres, INT Index, CHAR c

    IF Index >= 1 AND Index <= ( Length:Address ) THEN
        IF Address's refence count > 1 THEN
            decrement Address's refernce count
            NewAddress = ( copy_str : Address )
            IF NewAddress THEN
                NewAddress[Index] = c
            END IF
            RETURN NewAddress
        END IF
        Address[Index] = c
        RETURN Address
    END IF
    ERROR : "Invalid Index"
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB Find_Char : VVA Address, CHAR c

    FOR i = 1 TO ( Length : Address ) DO
        IF Address[i] = c THEN
            RETURN i
        END IF
    END FOR
    RETURN 0
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB Compare : VVA One : VVA Two

    FOR i = 1 TO ( Smaller: ( Length:One ),( Length:Two ) ) DO
        IF One[i] < Two[i] THEN
            RETURN -1
        ELSIF One[i] > Two[i] THEN
            RETURN 1
        END IF
    END FOR
    RETURN 0
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB Output : FileNum FN, VVA Address

    PUTS : FN, contents of string
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB ConCat_Char : VVA Address, CHAR c


    IF reference count > 1 THEN
        IF NOT padding THEN
            NewAddress = ( Create: ( Length:Address )+1 )
        ELSE
            NewAddress = ( Create: ( Length:Address ) )
        END IF
        IF NOT NewAddress THEN
            RETURN 0
        END IF
        copy contents of string into new string
        Delete:Address
        Address = NewAddress
    END IF
    IF padding THEN
        decrement Address's padding
    END IF
    Address[ (Length:Address)+1 ] = c
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB ConCat_String : VVA Address, VVA Add

    NewAddress = ( Create: ( Length:Address)+(Length:Add ) )
    IF NOT NewAddress THEN
        RETURN 0
    END IF
    copy contents of Address into new string
    copy contents of Add into new string after contents of Address
    Delete:Address
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB To_Upper_Str : VVA Address

    IF Address's refence count > 1 THEN
        decrement Address's refernce count
        NewAddress = ( copy_str : Address )
        IF not NewAddress THEN
            RETURN NewAddress
        END IF
        Address = NewAddress
    END IF
    ITERATE i IN string
        Address[i] = upper case Address[i]
    END ITERATE
END SUB

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
SUB To_Lower_Str : VVA Address

    IF Address's refence count > 1 THEN
        decrement Address's refernce count
        NewAddress = ( copy_str : Address )
        IF not NewAddress THEN
            RETURN NewAddress
        END IF
        Address = NewAddress
    END IF
    ITERATE i IN string
        Address[i] = lower case Address[i]
    END ITERATE
END SUB

--------------------
Sincerely,
Mathew Hounsell

Mat.Hounsell at Excite.Com




_______________________________________________________
Get your free, private email at http://mail.excite.com/