Uploaded image for project: 'Spatial Information Systems'
  1. Spatial Information Systems
  2. SIS-79

Implement RangeSet.remove(E, E)

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 0.3, 0.4
    • Fix Version/s: 0.5
    • Component/s: Utilities
    • Labels:

      Description

      The org.apache.sis.util.collection.RangeSet class has been ported to Apache SIS at the exclusion of the implementation of the remove(E,E) method, which has been excluded for licensing reasons. We need volunteer work for implementing that method.

      A copy of the add(E,E) can be used as a starting point, then modified. The basic idea is it to get the index of the given minValue and maxValue arguments using the binarySearch method, then make some choices:

      • If the given range is completely outside all RangeSet ranges, do nothing.
      • If the given range fully contains one or many RangeSet ranges, remove all those ranges by invoking the removeAt(int, int) method.
      • If the given range is fully contained inside an existing range, split that existing range in two smaller ranges: one for the part before the range to remove, and one for the part after the range to remove. The insertAt(int, E, E) method will need to be invoked.
      • If the given range partially overlaps an existing RangeSet range, edits the endpoints of that range. No range are removed or inserted.

      There is some tricks to keep in mind for hacking RangeSet:

      • The internal array is a sequence of (minimal, maximal) value tupples for all ranges included in this RangeSet instance.Even index are for minimal values and odd index are for maximal values.
      • If binarySearch returns a negative value, no exact match was found. To get the insertion point (the index of the first value greater than the searched value), use index = ~index (the tild operation, not the minus sign).
      • To test if an index points to a minimal value (i.e. the index is an even number), use ((index & 1) == 0).
      • To test if an index points to a maximal value (i.e. the index is an odd number), use ((index & 1) != 0).
      • To force an index to be even (i.e. to point to the minimal value of the range) either be leaving the index unchanged, or if the index was odd decrease the value by one, use index &= ~1.
      • To force an index to be odd (i.e. to point to the maximal value of the range) either by leaving the index unchanged, or if the index was even increase the value by one, use index |= 1.

        Attachments

        1. RangeSetTest.patch
          10 kB
          Rémi Maréchal
        2. RangeSet.patch
          8 kB
          Rémi Maréchal

          Activity

            People

            • Assignee:
              desruisseaux Martin Desruisseaux
              Reporter:
              desruisseaux Martin Desruisseaux
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: