COMPM%
                                ======

             Compare two values of any type stored in memory


Compatibility:
==============

SBASIC (ie SMSQ/E) or compiled (all systems).


Usage:
======

        result% = COMPM%((X), (Y), <comp%>)

Where

        result% is either  1 => (X) > (Y) or
                           0 => (X) = (Y) or
                          -1 => (X) < (Y)
                          unless reversed

        (X) and (Y) are pointers to (= addresses of) the two values stored
                somewhere in memory that are to be compared. These values
                must be of the same type as no coersion (conversion) takes
                place with direct memory values.

        <comp%> = <sign><cmptype.b><vartype.b)

        <cmptype.b> in bits 0 to 2 in the most significant byte [msb] of
                the word is the Qdos code for string comparision types
                0..3 (see below for details)

                C-strings and N-strings only accept 0 or <> 0 as
                comparison types, with 0 => case sensitive and <> 0 =>
                case agnostice (more details below).

                Apart from the top bit, <cmptype> is only significant for
                string comparisions and is otherwise ignored.

                For C- and N-strings you can also specify a skip number.
                This is the number of C- or N-strings that must be skipped
                to reach the string we want. The figure can be 0 (default)
                to 15, and is supplied in bit 3 to 6 in the msb of the
                parameter.

                Finally, if bit #7 of the msb is set, the result of the
                comparison is reversed.

        <vartype.b> in the least significant byte of the parameter is a
                code defining the kind of parameters to be compared:


Variable types (vartype%):
==========================

        sbyte = $00  =  0       signed byte
        ubyte = $02  =  2       unsigned byte
        sword = $04  =  4       signed 16 bit word
        uword = $06  =  6       unsigned 16 bit word
        slong = $08  =  8       signed 32 bit long word
        ulong = $0A  = 10       unsigned 32 bit long word
        fltpt = $0C  = 12       48 bit float
        qstrg = $0E  = 14       Q-string (len.w + bytes)
        cstrg = $10  = 16       C-string (zero-terminated)
        nstrg = $12  = 18       Name string (1 byte length)

Note: Except for types 0, 2, 16 and 18, (byte, unsigned byte and C- and
      N-strings) all addresses must be even! (Does not necessarily apply
      where the CPU >= MC68020, but for the sake of compatibility better
      stick with that rule.)

Note: S*BASIC doesnt normally deal with unsigned integer word or
      longword, so, for example, the unsigned word 64302 has to be entered
      as -31534 (= 32768 - 64302). Bytes in S*BASIC are normally treated
      as unsiged. COMP% lets you treat them as signed or unsigned.

A few other types are planned, such as negative types => the current pair
of variables are just long word pointers to two fields of abs(type). This
would be most useful for q-strings of widely variable lengths kept outside
the record, but might also have other uses..


String comparison (cmptype%):
=============================

Comparisons may be:

Type 0  Made directly on a character by character basis

Type 1  Made ignoring the case of the letters

Type 2  Made using the value of any embedded numbers

Type 3  Both ignoring the case of letters and using the value of embedded
        numbers.

More detail of the order of characters etc, may be found in the
various QL Concepts manuals, or in the text accompanying my CMP% keyword
at Knoware.no


Examples:
=========

If case% = 1 (case agostic string comparison) and var% = 14
(variable type Q-string), and if adr1 -> 03,'abc' and
adr2 -> 03,'ABC' then use

        type% = case% * 256 + var%

r% = COMPM%(adr1, adr2, case% * 256 + var%) returns r% = 0 and
r% = COMPM%(adr1, adr2, var%) returns r% = -1 (case% = 0: case sensitive)

C-strings and N-strings can only take 0 and 1 as comparison type codes.
0 => case sensitive and 1 => case agnostic. These are not lexical
comparisons as for the Qdos types above, but straight character-by-
character comparisions.


cmptype% example:
-----------------

Variable type   = $10 - c-string = 16
Comparison type =   1 - case agnostic
Skip strings    =   2 - we want the third string after the pointer

In the formula below the result of the comparison can be straight or
reversed.

Straight: (a2z = 0)

  type% = (skip% * 8 + case% - a2z) * 256 + var%

       => type% = 4368 = $1110 = %0001000100010000

If the result is to be reversed (eg for sorting purposes):


Reversed: (a2z = $80, ie -1 in sbyte)

  type% = (skip% * 8 + case% - a2z) * 256 + var%

       => type% = -28400 = $9110 = %1001000100010000


For non-string comparisons, to reverse the order of the comparison:

  eg: var% = 4: a2z = $8000 (= 32768 = -1 in sword)

  type% = var% - a2z

       => -32764 = $8004 = %1000000000000100 = signed word reverse comp


Example of use:
===============

Included in the zip with this toolkit is an SBASIC program called Sort_bas.
It is not a complete and working program. (It works perfectly in the context
where it is being used!)

To make it work you need some data. The data would consist of Records, like
in a database. Each record contains a number of fields, such as
First_name, Surname, Address, Country, Telephone, Customer number, etc.
Fields may be of different types - some text, some numeric, some of fixed
length and some of variable length.

Each record is stored some place in memory, it may be convenient that
records are not of fixed size nor stored in consecutive locations in memory.
So, to keep track of them, you need to make an index, which is updated each
time a new record is created or loaded from disk.

So, base is some heap space in memory that contains the index - a series
of long words. Each long word points to (is the address of) the base of a
record in some other heap in memory. Offset from the base of each record
are the different fields. The field offsets and their respective types are
the same for every record.


                      +-------> [rec 0]
                      |         : offs 00 [field 1] (float)
location    index     |         : offs 06 [field 2] (uword)
- - - - -  - - - -    |         : offs 08 [field 3] (qstrg, variable length)
base + 00  [rec 0] ---+
                         +--------------------> [rec 2]
                         |                      : offs 00
base + 04  [rec 1] ------)--+                   : offs 06
                         |  |                   : offs 08
                         |  |
base + 08  [rec 2] ------+  +---> [rec 1]
                                  :
...                               :
                                  :


To find the Q-string of record #1, you start with the index base, which is
known by the program or person that created it, and go to its 1st (one
past the 0th) posistion: ptr = peek_l(base + #1 * 4). ptr now contains the
address of record #1. Add to that the offset to Q-strings (which is known to
the creator of the database) to find the Q-string: qstr$ = peekstr$(ptr +
[offs 08])

To search for stuff you need to be able to compare fields against your
search criteria. The same if you need to order your records for whatever
reason (making searches faster is one very good reason.)

COMPM% can help with all that, provided you tell it where your records
are, how much each field is offset from the base of each record, and what
type of data each field contains.

The sort routine, BISM, makes use of that information to perform a simple
Binary Insertion Sort in Memory. It doesnt rearrange any records, but it
does rearrange the pointers to those record (the index) based on the results
of the comparisons.

rem + ------------------------------------------------------------------------ +
rem |<                                  BISM                                  >|
rem + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +
rem |                      Binary Insertion Sort (Memory)                      |
rem |                                                                          |
rem | TAOCP 5.2.1. Modified to sort a long word memory index The indexes       |
rem | point to records, also in memory. Individual fields are offset from      |
rem | the main record address.                                                 |
rem |                                                                          |
rem |         ix      is the base of the index                                 |
rem |         n       is the number of items in index (0..N)                   |
rem |         ofs     is an array of offsets pointing to the various fields    |
rem |                    to be included in the sort                            |
rem |         typ%    is an array of corresponding types for those fields      |
rem |                    In the case of strings the typ also specifies the     |
rem |                    comparison type in the msb of the lsw.                |
rem |                                                                          |
rem | Dependencies: McmpMo% and tk COMPM%                                      |
rem + ------------------------------------------------------------------------ +
rem | V0.01, pjw, 2023 Jul 31                                                  |
rem | V0.02, pjw, 2023 Aug 08, changed to nstrg, COMPM% has new parameters     |
rem + ------------------------------------------------------------------------ +
:
DEFine PROCedure BISM(ix, n, ofs, typ%)
LOCal j, i, sl, t
FOR j = 1 TO n - 1
 rem t$ = arr(j%): i% = j% - 1
 t = PEEK_L(ix + j * 4): i = j - 1
 REPeat sl
  rem IF t$ >= arr(i%): EXIT sl
  IF McmpMo%(t, PEEK_L(ix + i * 4)) >= 0: EXIT sl
  rem arr(i% + 1) = arr(i%)
  POKE_L ix + (i + 1) * 4, PEEK_L(ix + i * 4)
  rem i% = i% - 1: IF i% <= -1: EXIT sl
  i = i - 1: IF i <= -1: EXIT sl
 END REPeat sl
 rem arr(i% + 1) = t$
 POKE_L ix + (i + 1) * 4, t
END FOR j
END DEFine BISM
:
:
rem + ------------------------------------------------------------------------ +
rem |<                                McmpMo%                                 >|
rem + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +
rem |         Compare multiple elements stored in memory using offsets         |
rem |                                                                          |
rem | Subroutine of BISM                                                       |
rem |                                                                          |
rem | Compare each element/field in a record: Comparison ends when the         |
rem | result is either "greater" or "less" or until there are no further       |
rem | elements left to compare in which case the result is "equal".            |
rem |                                                                          |
rem | baseX/Y are abs location of pointers to a record                         |
rem | ofs     is an array containing offsets to fields within record           |
rem | typ%    is an array holding the type of each pair of fields              |
rem |                                                                          |
rem | Dependency: COMPM%                                                       |
rem + ------------------------------------------------------------------------ +
rem | V0.01, pjw, 2023 Jul 30                                                  |
rem | V0.02, pjw, 2023 Aug 08, changed to nstrg, COMPM% has new parameters     |
rem + ------------------------------------------------------------------------ +
:
DEFine FuNction McmpMo%(baseX, baseY)
LOCal i%, r%
FOR i% = 0 TO DIMN(ofs)
 r% = COMPM%(baseX + ofs(i%), baseY + ofs(i%), typ%(i%))
 IF r%: RETurn r%:    rem Dont return yet if zero..
END FOR i%
RETurn 0:             rem Equals!
END DEFine McmpMo%
:
:

Binary Insertion Sorts are not terribly efficient on lots of unsorted data,
but for a small number of records - or a large number of records that are
nearly in order - it is reasonably fast. For the purpose of illustration
the main point here is that it is simple.


ToDo:
=====

The next step will be to modify my Quicksort toolkit work with the same sort
of data types as COMPM% does. That should make for a fast and versatile
sorting solution.


Status of This software:
========================

V0.01, pjw, 2023 Jul 28, first release

                  Conditions and DISCLAIMER as per Knoware.no

Generated by QuickHTM, 2023 Sep 19