Loading ...
Sorry, an error occurred while loading the content.

[eiffel-nice-library] Re: ARRAY 'is_equal' and 'subarray'

Expand Messages
  • James McKim
    Roger Browne wrote: [..] ... Hmmm... I don t see why it would have to.... Note that `copy will have to be redefined in ARRAY whichever way we go. But I don t
    Message 1 of 21 , Dec 1, 1999
    • 0 Attachment
      Roger Browne wrote:

      [..]

      >
      > If the redefinition of 'is_equal' (in ARRAY) uses anything except "="
      > to compare the elements, won't it mess up the postcondition of
      > 'clone' and 'copy' inherited from GENERAL?

      Hmmm... I don't see why it would have to.... Note that `copy' will have
      to be redefined in ARRAY whichever way we go. But I don't _think_ its
      postcondition would be affected.


      [..]

      > I wrote:
      > > > (1) add a new feature 'normalise' to rebase an array
      > > > such that 'lower' becomes one, or (2) add a new comparison feature
      > > > such as 'same_content' or 'same_elements'.
      >
      > Jim wrote:
      > > I think an argument could be made for both of these...
      >
      > If 'same_elements' is available, I'm struggling to think of a need

      I agree that `same_elements' seems more generally useful than `normalize'.

      > for 'normalize'. On the other hand, a more general command such as
      > 'move_indexes' might be useful. Then, we could normalize an ARRAY like
      > this...
      >
      > move_indexes(lower, upper, 1)
      >
      > ...and we could also program operations like 'insert' and 'remove'
      > efficiently.
      >

      I'm not entirely sure what you have in mind here. It'd be good to see
      the pre/postconditions. I do recall Dominique, Marcel, and perhaps others
      suggesting a `reindex' feature that I think would look something like this:

      reindex (new_lower : INTEGER)
      -- Reindex array so that smallest index is `new_lower'.
      -- Do not lose any items.
      ensure
      new_lower: lower = new_lower
      same_items: same_items (old clone (Current))

      Normalization would be effected by `reindex (1)'. It looks like you're
      thinking of something more general....

      > But anyway, one new feature might be plenty for this aspect of
      > ELKS 2000. Let's keep it simple!

      If there's just gonna be one along these lines, then I think it should
      be 'same_items'. One could argue (as I think Marcel already has) that
      _any_ Container class could benefit from such a feature.

      >
      > > I'd recommend the following specs:
      > >
      > > same_items(other : like Current) : BOOLEAN
      > > -- Does `other' have the same items as Current
      > > require
      > > other_not_void: other /= Void
      > > ensure
      > > definition: Result =
      > > (count = other.count) and then
      > > -- Same number of elements and ...
      > > (count = 0 or else
      > > -- empty array or ...
      > > (item (upper) = other.item (upper) and
      >
      > Presumably the line above should be:
      >
      > (item (upper) = other.item (other.upper) and
      >
      > > -- Upper elements are the same and ...
      > > subarray (lower, upper-1).same_items (other.subarray (lower, upper - 1))))
      > > -- All the remaining elements are the same.
      >
      > Similarly, I guess this should be:
      >
      > subarray(lower, upper-1).same_items(other.subarray(other.lower,
      > other.upper-1))))

      Yes, thank you. I should always wait a day after I write these before I
      publish them anywhere. 'Course I just broke that rule again with `reindex'....

      Hope this helps,
      -- Jim

      >
      > Regards,
      > Roger
      > --
      > Roger Browne - roger@... - Everything Eiffel
      > 19 Eden Park Lancaster LA1 4SJ UK - Phone +44 01542 32428
      >
      > ------------------------------------------------------------------------
      > ---------------------------
      > http://www.eiffel-nice.org/
      > --------------------------
      >
      > ------------------------------------------------------------------------
      > -- 20 megs of disk space in your group's Document Vault
      > -- http://www.egroups.com/docvault/eiffel-nice-library/?m=1
      >
      >
      >
    • Le Vourch, Xavier
      ... We agree that `is_equal should check the bounds of the array in the new 2000 standard. This will create compatibility issues with our current libraries
      Message 2 of 21 , Dec 1, 1999
      • 0 Attachment
        Roger Browne wrote:
        >
        > I wrote:
        > > > ... 'is_equal' ...
        > > >
        > > > 1. Should it compare only the elements, or should it compare
        > > > upper and lower bounds also? ELKS 1995 is not
        > > > specific about this.
        > > >
        > > > Currently, VE and SE appear to check 'lower' and 'upper'...
        > > > ISE and HACT appear not to...
        >
        > Jim McKim wrote:
        > > ... it does look like ISE is happy with this.
        >
        > Xavier (or any other HACT representative): is it acceptable
        > for ARRAY 'is_equal' to compare upper and lower bounds?
        >

        We agree that `is_equal' should check the bounds of the array in the new
        2000 standard.

        This will create compatibility issues with our current libraries and our
        customers' code but this is not a valid enough reason for not comparing the
        bounds in `is_equal' in the new standard. In the future, we will most likely
        provide two versions of iss-baselib based on the current behavior and the
        ELKS 2000 version as well as an upgrade path for our customers to migrate
        from the old library to the new one to make the transition as smoothly as
        possible.


        Best regards,
        Xavier

        --
        Xavier Le Vourch mailto:xavier@...
        Halstenbach ACT GmbH http://www.halstenbach.com
        827 State Street Tel.: +1 805 568 0023
        Santa Barbara, CA 93101 Fax.: +1 805 884 0806
      • Roger Browne
        ... Here s the ELKS95 signature and postcondition of copy in GENERAL: copy (other: like current) -- Update current object using fields of object attached --
        Message 3 of 21 , Dec 1, 1999
        • 0 Attachment
          I wrote:
          > > If the redefinition of 'is_equal' (in ARRAY) uses anything except "="
          > > to compare the elements, won't it mess up the postcondition of
          > > 'clone' and 'copy' inherited from GENERAL?

          James McKim wrote:
          > Hmmm... I don't see why it would have to.... Note that `copy' will have
          > to be redefined in ARRAY whichever way we go. But I don't _think_ its
          > postcondition would be affected.

          Here's the ELKS95 signature and postcondition of 'copy' in GENERAL:

          copy (other: like current)
          -- Update current object using fields of object attached
          -- to 'other', so as to yield equal objects.
          ensure
          is_equal: is_equal(other)

          In ELKS95 class ARRAY there is no change to the specification of 'copy',
          but there is a new comment:

          copy (other: like current)
          -- Reinitialize by copying all the items of 'other'
          -- (This is also used by 'clone'.)

          I think I am on safe ground to say that the usual interpretation of
          ELKS95
          ARRAY.copy is that it should copy 'lower', 'upper' and the sequence of
          references (or expanded values) (the 'area' in ISE/HACT ARRAY) - but not
          the referenced objects. That is, if we have ARRAY[CUSTOMER] then 'copy'
          will not create any new CUSTOMER objects.

          If this is the case, then the postcondition to ARRAY.copy will only
          fully
          specify its behaviour if 'is_equal' uses "=" to compare the array
          elements.
          On the other hand, if ARRAY.is_equal uses 'is_equal' to compare the
          array elements then the postcondition to ARRAY.copy doesn't tell us
          whether 'copy' should create new objects or simply copy references to
          the
          existing objects.

          > > move_indexes(lower, upper, 1)

          > I'm not entirely sure what you have in mind here. It'd be good to see
          > the pre/postconditions...

          If 'normalize' becomes a strong contender for ELKS 2000 I'll put
          together
          some pre/postconditions, but...

          > I do recall Dominique, Marcel, and perhaps others
          > suggesting a `reindex' feature that I think would look something like this:
          >
          > reindex (new_lower : INTEGER)
          > -- Reindex array so that smallest index is `new_lower'.
          > -- Do not lose any items.
          > ensure
          > new_lower: lower = new_lower
          > same_items: same_items (old clone (Current))
          >
          > Normalization would be effected by `reindex (1)'. It looks like you're
          > thinking of something more general....

          I was - but 'reindex' and 'move' are really orthogonal and are probably
          better as two separate features rather than combined into one as
          'move_indexes'. So forget about 'move_indexes' for now.

          By the way, 'reindex' is implemented in Eiffel/S, and also in
          Visual Eiffel (where it is marked obsolete):

          reindex (new_lower : INTEGER) is
          -- Change index interval so that it starts at 'new_lower'.
          -- No elements will be lost
          ensure
          bounds_adjusted : lower = new_lower and then
          upper = new_lower + count - 1

          > > But anyway, one new feature might be plenty for this aspect of
          > > ELKS 2000. Let's keep it simple!
          >
          > If there's just gonna be one along these lines, then I think it should
          > be 'same_items'.

          I agree.

          > ... One could argue (as I think Marcel already has) that
          > _any_ Container class could benefit from such a feature.

          It would be useful, but is difficult to implement efficiently. For
          example, it would be nice to apply 'same_items' to two HASH_TABLEs. But
          to do this it is necessary to first create two equivalent SORTED_LISTs
          (to avoid the test failing because the HASH_TABLEs have different bucket
          counts, or because the same items were added to the two HASH_TABLEs in a
          different order causing different chaining on hash-code collisions).

          Anyway, the decision for ARRAY doesn't affect the decision for some
          CONTAINER library, so we don't need to sweat too much about that.

          > ... I should always wait a day after I write these before I
          > publish them anywhere ...

          No way! Rapid posting helps to keep things moving. No-one minds
          suggesting the occasional correction.

          Regards,
          Roger
          --
          Roger Browne - roger@... - Everything Eiffel
          19 Eden Park Lancaster LA1 4SJ UK - Phone +44 01542 32428
        • Roger Browne
          ... Thank you. I appreciate that, as I m sure do many other Eiffel programmers. is_equal is such a fundamental feature that it really needs to be
          Message 4 of 21 , Dec 1, 1999
          • 0 Attachment
            "Le Vourch, Xavier" wrote:

            > We agree that `is_equal' should check the bounds of the array in the new
            > 2000 standard.

            Thank you. I appreciate that, as I'm sure do many other Eiffel
            programmers. 'is_equal' is such a fundamental feature that it really
            needs to be standardised.

            This is now acceptable to all vendors, and I'm not aware of any
            counter-arguments from users. I'll start a vote after any further
            discussions have died down, or within a few days if there is no further
            discussion.

            Regards,
            Roger
            --
            Roger Browne - roger@... - Everything Eiffel
            19 Eden Park Lancaster LA1 4SJ UK - Phone +44 01542 32428
          • Durchholz, Joachim
            ... No, it s much easier. 1) Check whether both have the same count. 2) Check whether any element of hashtable a is also present in hashtable b. This is O(N)
            Message 5 of 21 , Dec 1, 1999
            • 0 Attachment
              Roger wrote on hashing:

              > It would be useful, but is difficult to implement efficiently. For
              > example, it would be nice to apply 'same_items' to two
              > HASH_TABLEs. But
              > to do this it is necessary to first create two equivalent SORTED_LISTs
              > (to avoid the test failing because the HASH_TABLEs have
              > different bucket
              > counts, or because the same items were added to the two
              > HASH_TABLEs in a
              > different order causing different chaining on hash-code collisions).

              No, it's much easier.
              1) Check whether both have the same count.
              2) Check whether any element of hashtable a is also present in hashtable b.

              This is O(N) for N = hashtable.count, and zero object construction, so this
              sounds as if this algorithm is as fast as an ARRAY comparison (modulo the
              hashtable lookup times).
              You do need a way to enumerate all keys in the hash table to make this work.
              I think this is in ELKS though (and if it isn't we should add it because
              it's generally useful IMO).

              Regards,
              Joachim
              --
              This is a private communication, not a statement from my employer.
            • Roger Browne
              ... You are right. I even submitted a HASH_TABLE class to this year s Eiffel Struggle competition which implemented is_equal exactly that way. But it s easy
              Message 6 of 21 , Dec 1, 1999
              • 0 Attachment
                I wrote:
                > > ... it would be nice to apply 'same_items' to two HASH_TABLEs. But
                > > to do this it is necessary to first create two equivalent SORTED_LISTs...

                Joachim Durchholz wrote:
                > No, it's much easier.
                > 1) Check whether both have the same count.
                > 2) Check whether any element of hashtable a is also present in hashtable b.

                You are right. I even submitted a HASH_TABLE class to this year's Eiffel
                Struggle competition which implemented 'is_equal' exactly that way. But
                it's easy to find other containers for which 'same_items' is not so
                simple - for example unsorted lists.

                > You do need a way to enumerate all keys in the hash table to make this work.
                > I think this is in ELKS though ...

                I don't see how key-enumeration can be in ELKS, because HASH_TABLE is
                not in ELKS ... or did I misunderstand you here?

                Regards,
                Roger
                --
                Roger Browne - roger@... - Everything Eiffel
                19 Eden Park Lancaster LA1 4SJ UK - Phone +44 01542 32428
              • James McKim
                ... Yes, I see. Usually we don t care if a routine actually supports a stronger postcondition than the one specified, but in this case we do. So we really want
                Message 7 of 21 , Dec 2, 1999
                • 0 Attachment
                  Roger Browne wrote:

                  >
                  > I wrote:
                  > > > If the redefinition of 'is_equal' (in ARRAY) uses anything except "="
                  > > > to compare the elements, won't it mess up the postcondition of
                  > > > 'clone' and 'copy' inherited from GENERAL?
                  >
                  > James McKim wrote:
                  > > Hmmm... I don't see why it would have to.... Note that `copy' will have
                  > > to be redefined in ARRAY whichever way we go. But I don't _think_ its
                  > > postcondition would be affected.
                  >
                  > Here's the ELKS95 signature and postcondition of 'copy' in GENERAL:
                  >
                  > copy (other: like current)
                  > -- Update current object using fields of object attached
                  > -- to 'other', so as to yield equal objects.
                  > ensure
                  > is_equal: is_equal(other)
                  >
                  > In ELKS95 class ARRAY there is no change to the specification of 'copy',
                  > but there is a new comment:
                  >
                  > copy (other: like current)
                  > -- Reinitialize by copying all the items of 'other'
                  > -- (This is also used by 'clone'.)
                  >
                  > I think I am on safe ground to say that the usual interpretation of
                  > ELKS95
                  > ARRAY.copy is that it should copy 'lower', 'upper' and the sequence of
                  > references (or expanded values) (the 'area' in ISE/HACT ARRAY) - but not
                  > the referenced objects. That is, if we have ARRAY[CUSTOMER] then 'copy'
                  > will not create any new CUSTOMER objects.
                  >
                  > If this is the case, then the postcondition to ARRAY.copy will only
                  > fully
                  > specify its behaviour if 'is_equal' uses "=" to compare the array
                  > elements.
                  > On the other hand, if ARRAY.is_equal uses 'is_equal' to compare the
                  > array elements then the postcondition to ARRAY.copy doesn't tell us
                  > whether 'copy' should create new objects or simply copy references to
                  > the
                  > existing objects.

                  Yes, I see. Usually we don't care if a routine actually supports a
                  stronger postcondition than the one specified, but in this case we do.
                  So we really want to say that for each i, item(i).is_equal(other.item (i)) but
                  item(i) /= other.item(i). Except of course when the
                  items are expanded, in which case the two versions of equality
                  would be the same. Ouch. Well, if it comes to that I'll try to
                  figure out a rigorous spec, but my guess is we'd have to do
                  it as a comment: "Each item of `other' is copied to the corresponding
                  element of `Current'". Something like that.

                  Of course, as you note, if we use `=' to compare the elements this
                  problem goes away. Dominique, Olivier, have you thought about this
                  any further?

                  Hope this helps,
                  -- Jim

                  [..]

                  > Regards,
                  > Roger
                  > --
                  > Roger Browne - roger@... - Everything Eiffel
                  > 19 Eden Park Lancaster LA1 4SJ UK - Phone +44 01542 32428
                  >
                  > ------------------------------------------------------------------------
                  > ---------------------------
                  > http://www.eiffel-nice.org/
                  > --------------------------
                  >
                  > ------------------------------------------------------------------------
                  > eGroups.com Home: http://www.egroups.com/group/eiffel-nice-library/
                  > http://www.egroups.com - Simplifying group communications
                  >
                  >
                  >
                • Durchholz, Joachim
                  ... No, I just didn t check. I never quite realized that ELKS has no data structures beyond ARRAY :(( Regards, Joachim -- This is a private communication, not
                  Message 8 of 21 , Dec 2, 1999
                  • 0 Attachment
                    Roger wrote on 'is_equal' for hash tables:

                    > > You do need a way to enumerate all keys in the hash table
                    > > to make this work.
                    > > I think this is in ELKS though ...
                    >
                    > I don't see how key-enumeration can be in ELKS, because HASH_TABLE is
                    > not in ELKS ... or did I misunderstand you here?

                    No, I just didn't check.
                    I never quite realized that ELKS has no data structures beyond ARRAY :((

                    Regards,
                    Joachim
                    --
                    This is a private communication, not a statement from my employer.
                  Your message has been successfully submitted and would be delivered to recipients shortly.