The ScopeTransform experiment was a good one, but I think that scope transformation should be part of XSet, not a separate operation. We'll work on that ... and it turns out pretty nicely. More to do, of course, and things are a bit fuzzy, but I think we're on a good path.

A New Requirement

Experiences with Scope Transformation, ShiftedRecord, and the thinking that was described in the preceding article lead me to state a new requirement:

Rather than representing Scope Transformation as an operation of its own, producing a new set, Scope Transformation should be an "embedded" characteristic of a set, causing the set to produce its elements with differing scopes than it otherwise would.

I want to be clear up front that I’m not certain about this new idea, but it seems to me to be a good one. It’s entirely possible to build a ScopeTransform set that acts like a “view” on another set. The one we wrote a few articles back works like that, and it’s not entirely bad. But it seems to me that our more physical sets may want to do their own iteration rather than be accessed randomly. So I’m going to do a quick experiment with embedding Scope Transformation right inside our main set type, XSet.

Reviewing the Code

Take a look at the XSet code with me. I’ll highlight the bits that jump out at me as interesting in this context.

  class XSet
    include Enumerable
    attr_reader :contents

    def initialize(element_length, contents, rank=2)
      @element_length = element_length
      @contents = contents
      @rank = rank
    end

    def each
      for scope in element_range
        yield ScopedElement.new(element(scope), scope)
      end
    end

    def restrict(selector)
      matching_scopes = []
      each do | scoped_element |
        if selector.matches(scoped_element)
          matching_scopes << scoped_element.scope
        end
      end
      ScopeTransform.new(self, matching_scopes)
    end

    def matches(a_scoped_element)
      any? { | scoped_element |
        match(a_scoped_element, scoped_element)
      }
    end

    def match(my_scoped_element, selector_scoped_element)
      selector_scoped_element.element.subset?(my_scoped_element.element)
    end

    def subset?(larger_set)
      element_range.all? { | scope |
        larger_set.contains?(element(scope), scope)
      }
    end

#    def subset? set
#      each do  | se |
#        if ( set.element(se.scope) != se.element ) 
#          return false
#        end
#      end
#      return true
#    end

    def element(scope)
      element_contents = @contents[scope*@element_length,@element_length]
      if (@rank > 1)
        return XSet.new(1,element_contents, self.rank-1)
      else
        return element_contents
      end
    end

    def contains?(an_element, scope)
      element(scope) == an_element
    end

    def element_range
      0...cardinality
    end

    def cardinality
      @contents.length / @element_length
    end

    def rank
      @rank
    end

The methods :each and :element are surely impacted by any Scope Transform that is in effect, in that they must produce and respond to the mapped scopes rather than the ones in the base set. The method :cardinality is interesting because it is possible for a Scope Transform to change the cardinality of a set (its number of records), by mapping some records completely out of existence. Review the ScopeTransformTest tests – they do that.

Cardinality looks like a problem to me, in that we really don’t know the cardinality of a set given just a Scope Transform on it. If the set is a vector, however, the cardinality of the result is the cardinality of the map, I believe. That is, if the map only maps three elements from the set, that’s how many records will be in the output. But there are more complex examples than the ones I have used in these articles. A Scope Transform can map all the elements to the same place, taking, for example: <J, e, f, f, r, i, e, s> to { J3, e3, f3, f3, r11, i11, e11, s11}.

We’ll burn that bridge when we come to it. For now, let’s put some simple embedding into XSet. I plan to implement the feature by replacing references to scope with messages sent to a mapper in the XSet. The first step will be an identity transform, and the existing tests should suffice for that.

    def initialize(element_length, contents, rank=2)
      @element_length = element_length
      @contents = contents
      @rank = rank
      @scope_transform = nil
    end

    def each
      for scope in element_range
        new_scope = output_scope(scope)
        if (scope != nil)
          yield ScopedElement.new(element(scope), scope)
        end
      end
    end

    def output_scope(input_scope)
      if (@scope_transform == nil)
        return input_scope
      end
    end

The code works. The output_scope method is just noticing that the @scope_transform is nil, and returns the input scope. Now let’s build an identity scope transform object and use that instead:

  
class IdentityScopeTransform
    def output_scope(input_scope)
      return input_scope
    end
  end

    def initialize(element_length, contents, rank=2)
      @element_length = element_length
      @contents = contents
      @rank = rank
      @scope_transform = IdentityScopeTransform.new
    end

    def each
      for scope in element_range
        new_scope = output_scope(scope)
        if (scope != nil)
          yield ScopedElement.new(element(scope), scope)
        end
      end
    end

    def output_scope(input_scope)
      return @scope_transform.output_scope(input_scope)
    end

Well, that was simple enough. Now let’s map some records out of a collection, and change a selection result. Time for a test:

    def test_scope_transform_removes_records
      select_data = "Johnson    "
      select = XSet.new(11, select_data)
      result = @name_set.restrict(select)
      assert_equal("Johnson     Lee ", result.contents)

      @name_set.scope_transform = IntegerScopeTransform.new([0,1])
      result = @name_set.restrict(select)
      assert_equal("", result.contents)

      select_data = "Jeffries   "
      select = XSet.new(11, select_data)
      result = @name_set.restrict(select)
      assert_equal("Jeffries    Ron ", result.contents)
    end

This is fairly aggressive, and in fact it took some time to get it right. Here’s the result:

  class XSet
    include Enumerable
    attr_reader :contents
    attr_writer :scope_transform

    def initialize(element_length, contents, rank=2)
      @element_length = element_length
      @contents = contents
      @rank = rank
      @scope_transform = IdentityScopeTransform.new
    end

    def each
      for scope in element_range
        new_scope = output_scope(scope)
        if (new_scope != nil)
          yield ScopedElement.new(element(new_scope), scope)
        end
      end
    end

    def output_scope(input_scope)
      return @scope_transform.output_scope(input_scope)
    end

    def restrict(selector)
      matching_scopes = []
      each do | scoped_element |
        if selector.matches(scoped_element)
          matching_scopes << output_scope(scoped_element.scope)
        end
      end
      ScopeTransform.new(self, matching_scopes)
    end

Here’s the new Transform:

  class IntegerScopeTransform
    def initialize(array)
      @transform = array
    end

    def output_scope(input_scope)
      return @transform[input_scope]
    end
  end

As I mentioned, this turned out to be a bit tricky to get right, for two reasons. First, I had forgotten that restrict was returning a ScopeTransform set, and I stumbled there for a bit before I realized I needed that output_scope call there. I also had to write a second test, because the first one used the first two records of the set, which wasn’t sufficient to let me check the values and scopes, since they were the same. (The first test’s transform is the identify transform, for two records.) Here’s the other test:

    def test_scope_transform_removes_records_2
      select_data = "Johnson    "
      select = XSet.new(11, select_data)
      result = @name_set.restrict(select)
      assert_equal("Johnson     Lee ", result.contents)

      @name_set.scope_transform = IntegerScopeTransform.new([2,3])
      result = @name_set.restrict(select)
      assert_equal("Johnson     Lee ", result.contents)

      select_data = "Anderson   "
      select = XSet.new(11, select_data)
      result = @name_set.restrict(select)
      assert_equal("Anderson    Ann ", result.contents)

      select_data = "Jeffries   "
      select = XSet.new(11, select_data)
      result = @name_set.restrict(select)
      assert_equal("", result.contents)
    end

There wasn’t any long debugging or any big sign of evil, but there were a couple of moments there when I was feeling confused. One reason, certainly, is that there was just a fair amount of code to type in. Another is that the changes to :each and :restrict are a bit intricate. End of the day, though, I like the way this functions, if not quite the way it looks. There are some issues …

We should probably get rid of the ScopeTransform set return, and instead return an XSet with an appropriate embedded transform. I expect that to be easy, and it will allow us to remove an entire class. That’s a good thing, I believe.

Another issue is in :each. Take a look:

    def each
      for scope in element_range
        new_scope = output_scope(scope)
        if (new_scope != nil)
          yield ScopedElement.new(element(new_scope), scope)
        end
      end
    end

    def element_range
      0...cardinality
    end

    def cardinality
      @contents.length / @element_length
    end

This code is iterating over the complete element_range of the original base set, even though there are probably fewer records in the transformed set. If there’s a scope transform in place, we should just use it directly to produce the records. My intuition is telling me that if we do that, we’re going to find some kind of duplication somewhere. Possibly we should let the transforms return the record range to use. The IdentityRange, however, is a virtual range, and doesn’t really now how big the set is.

Finally, I think there’s something a bit off about the need to map the scopes in the restrict. That’s two things that the restrict needs, so I’ll start there, removing the ScopeTransform set and replacing it with an XSet with an embedded transform. The code starts this way:

    def restrict(selector)
      matching_scopes = []
      each do | scoped_element |
        if selector.matches(scoped_element)
          matching_scopes << output_scope(scoped_element.scope)
        end
      end
      ScopeTransform.new(self, matching_scopes)
    end

The matching scopes are surely just what we want. We should be able to just return a new XSet. To do that cleanly, we’ll have to add the embedded scope transform to the XSet constructor:

    def initialize(element_length, contents, rank=2, transform=IdentityScopeTransform.new)
      @element_length = element_length
      @contents = contents
      @rank = rank
      @scope_transform = transform
    end

Note that Ruby lets me default the transform to an expression, right in the initialize parameters. I love this language! Now we should be able to make :restrict use an XSet:

    def restrict(selector)
      matching_scopes = []
      each do | scoped_element |
        if selector.matches(scoped_element)
          matching_scopes << output_scope(scoped_element.scope)
        end
      end
      transform = IntegerScopeTransform.new(matching_scopes)
      XSet.new(@element_length, @contents, @rank, transform)
    end

Now this seems right, but it doesn’t quite work. A bunch of tests blow. They are all calling :contents on their result, which is just returning the @contents attribute. We need to be more clever, and if we have a transform in effect, construct the string on the fly. Another problem with the notion of “contents”. This method is useful but its definition is weak. Must think on that. For now, what about updating contents? I tried a few things, up to this:

    def contents
      result = ""
      each do | se |
        element = se.element
        if element.isSet? then
          result += element.contents
        else
          result += element
        end
      end
      result
    end

I needed to define isSet? to return true for XSet, and false for object:

  class Object
    def isSet?
      false
    end
  end

That’s a crock. We should never need to ask an object what it is … more evidence that :contents is off. Basically what’s happening is that :contents is supposed to return a string, whether the set in question is a set of sets, or a set of characters. I really need to do something about that.

On the bright side, the ScopeTransform set is removed from use. I’ll remove its code and tests from the project and run the tests. The rest all run. Byebye ScopeTransform set. It’s still in the archive, though, in case I need it.

Now that :contents is stable again, let’s see about getting :each to iterate just over the records the set is supposed to know about. I expect this to take a couple of passes before it’s clean. The code again:

    def each
      for scope in element_range
        new_scope = output_scope(scope)
        if (new_scope != nil)
          yield ScopedElement.new(element(new_scope), scope)
        end
      end
    end

    def element_range
      0...cardinality
    end

    def cardinality
      @contents.length / @element_length
    end

That code is basically considering all record scopes, testing to see if they are in range, and using the ones that are. If we have a scope transform in effect, we should use its scope list instead. But in that case, we won’t need to map the scopes … they will already be mapped. (Think of that second mapping test, with the array [3,4]. That means we only want records 3 and 4, and their scopes in the output are 0 and 1. This is tricky.

I was going to use “Programming by Intention” here, rewriting the method, but on a moment’s reflection it’s easy to see that this code is just fine, with one exception … the element range is sometimes too large. We want 0…cardinality if our scope transformation is an identity. Otherwise we want zero to whatever the size of the transform is. We’ll do this with a call-back, since the identity guy doesn’t know our size:

In XSet:

    def element_range
      @scope_transform.element_range(self)
    end

    def prim_element_range
      0...cardinality
    end

  class IdentityScopeTransform
    def output_scope(input_scope)
      return input_scope
    end

    def element_range(set)
      return set.prim_element_range
    end
  end

  class IntegerScopeTransform
    def initialize(array)
      @transform = array
    end

    def output_scope(input_scope)
      return @transform[input_scope]
    end

    def element_range(set)
      return 0...@transform.size
    end
  end

Let’s talk a bit about that callback. The issue is that, though the IntegerScopeTransform knows its length, the IdentityScopeTransform is “virtual”, just mapping whatever you give it back to its input. So, to help it out, we have to ask “what is the element_range you would use for this set?” We pass it ourself. It doesn’t know, so it calls back to ask us: “what’s your actual size?”. We answer that result. This two stage process is called “callback”, and it is quite common to add a method, here called “prim_element_range” to support the bottom of the call chain. If this wasn’t in your bag of tricks before … it can be now!

The tests are all good, and I’m tired and it is nearly time for my wife get home and to head to Zukey Lake Tavern. So let’s retrospect, and put this article to bed.

How Are We Doing?

The idea of the embedded scope transform works nicely (so far), and it has let us remove a class that we don’t need any more. Since this is all a bit experimental, it’s nice when things start to collapse together already.

On the other hand, my guess is that you may be a bit overwhelmed at this point. Our XSet has gained some very interesting power, and its implemented in a very simple way, all just with some subscripting and simple mapping of integers. I’m a bit whelmed myself, as a matter of fact, and I’ve worked on this problem a few times in the past, though not quite along these same lines. Next time, I’ll put together a bit of a summary of where we are, but in fact we’re in pretty good shape. We really only have one real object, XSet, which is doing a lot of nifty things. It has only a few operational methods, and most of them are reasonable. We’ll look at it in an upcoming article to see whether it could profit from some cleanup … and that :contents thing has to be dealt with!

The code went fairly smoothly, but I took some big bites and felt some fear along the way when things didn’t work the first or second time. This probably means that I should slow down a bit.

I’m finding the ScopeTransform stuff a bit hard to think about. It’s difficult to think about the mapping when it’s stored in an array, might be easier as a hash: 2=>0, 3=>1, but that would be much harder to type in. I’m thinking that, as a rule, people won’t be using the feature much, but we’ll see. It should be easy enough to build a suitable map from a hash or the like, if it’s needed.

Summing up my sense of things at the moment, I need to be a bit more careful, and it’s probably time to take an overall look at cleaning the code, and at getting everything back into my head – and yours, if you’re out there! Until next time, here’s the code and tests for XSet. And that last commented-out test? I think we’re close to having a good way to do it. Have you ever heard of ConstituentScopeTransform? ;->

XSet Code and Tests

require 'project.rb'  
  class XSet
    include Enumerable
    attr_writer :scope_transform

    def initialize(element_length, contents, rank=2, transform=IdentityScopeTransform.new)
      @element_length = element_length
      @contents = contents
      @rank = rank
      @scope_transform = transform
    end

    def isSet?
      true
    end

    def each
      for scope in element_range
        new_scope = output_scope(scope)
        if (new_scope != nil)
          yield ScopedElement.new(element(new_scope), scope)
        end
      end
    end

    def output_scope(input_scope)
      return @scope_transform.output_scope(input_scope)
    end

    def restrict(selector)
      matching_scopes = []
      each do | scoped_element |
        if selector.matches(scoped_element)
          matching_scopes << output_scope(scoped_element.scope)
        end
      end
      transform = IntegerScopeTransform.new(matching_scopes)
      XSet.new(@element_length, @contents, @rank, transform)
    end

    def matches(a_scoped_element)
      any? { | scoped_element |
        match(a_scoped_element, scoped_element)
      }
    end

    def match(my_scoped_element, selector_scoped_element)
      selector_scoped_element.element.subset?(my_scoped_element.element)
    end

    def subset?(larger_set)
      element_range.all? { | scope |
        larger_set.contains?(element(scope), scope)
      }
    end

#    def subset? set
#      each do  | se |
#        if ( set.element(se.scope) != se.element ) 
#          return false
#        end
#      end
#      return true
#    end

    def element(scope)
      element_contents = @contents[scope*@element_length,@element_length]
      if (@rank > 1)
        return XSet.new(1,element_contents, self.rank-1)
      else
        return element_contents
      end
    end

    def contents
      result = ""
      each do | se |
        element = se.element
        if element.isSet? then
          result += element.contents
        else
          result += element
        end
      end
      result
    end

    def contains?(an_element, scope)
      element(scope) == an_element
    end

    def element_range
      @scope_transform.element_range(self)
    end

    def prim_element_range
      0...cardinality
    end

    def cardinality
      @contents.length / @element_length
    end

    def rank
      @rank
    end

    def to_s
     "{#{contents}}"
    end
  end

  class Object
    def isSet?
      false
    end
  end

require 'project.rb'
  class TC_MyTest < Test::Unit::TestCase

    def setup
      name_data = "Jeffries    Ron Hendrickson ChetAnderson    Ann Johnson     Lee "
      @name_set = XSet.new(16, name_data)
      @five_element_set = XSet.new(4, "123 234 132 342 abc ")
    end

    def test_cardinality
      assert_equal(5, @five_element_set.cardinality)
    end

    def test_one_byte_record
      input = XSet.new(1,"abcdef")
      assert_equal("b", input.element(1).element(0))
    end

    def test_record_bytes
      johnson = @name_set.element(3);
      assert_equal(2, @name_set.rank)
      assert_equal(1, johnson.rank)
      assert_equal("J", johnson.element(0))
    end

    def test_element_range
      assert_equal(0...5, @five_element_set.element_range)
    end

    def test_element_extraction
      assert_equal("132 ", @five_element_set.element(2).contents)
    end

    def test_restrict
      select = XSet.new(1,"1")
      expected = "123 132 "
      result = @five_element_set.restrict(select)
      assert_equal(expected,result.contents)
    end

    def test_name_restrict
      select_data = "HendricksonJeffries   "
      select = XSet.new(11, select_data)
      expected = "Jeffries    Ron Hendrickson Chet"
      result = @name_set.restrict(select)
      assert_equal(expected, result.contents)
    end

    def test_single_selection
      select_data = "Jeffries   Jeffries   "
      select = XSet.new(11, select_data)
      expected = "Jeffries    Ron "
      result = @name_set.restrict(select)
      assert_equal(expected, result.contents)
    end

    def test_each_using_scope
      ann = ""
      @name_set.each do 
        | scope_element | 
        if (scope_element.scope==2) 
          ann = scope_element.element.contents 
        end
      end
      assert_equal("Anderson    Ann ", ann)
    end

    def test_detect
      chet_scope_element = @name_set.detect { 
        | scope_element | 
        scope_element.element.contents.include? "Chet" }
      assert_equal("Hendrickson Chet", chet_scope_element.element.contents)
    end

    def test_rank
      assert_equal(2, @name_set.rank)
    end

    def test_element_rank
      element = @name_set.element(2)
      assert_equal(1, element.rank)
    end

    def test_shifted_record
      r = XSet.new(1, "Hendrickson Chet", 1)
      chet = ShiftedRecord.new(12,4,"Chet")
      ron = ShiftedRecord.new(12,4,"Ron ")
      assert(chet.subset?(r), "Chet sought but not found")
      assert(!ron.subset?(r), "Ron incorrectly found")
    end

    def test_scope_transform_removes_records
      select_data = "Johnson    "
      select = XSet.new(11, select_data)
      result = @name_set.restrict(select)
      assert_equal("Johnson     Lee ", result.contents)

      @name_set.scope_transform = IntegerScopeTransform.new([0,1])
      result = @name_set.restrict(select)
      assert_equal("", result.contents)

      select_data = "Jeffries   "
      select = XSet.new(11, select_data)
      result = @name_set.restrict(select)
      assert_equal("Jeffries    Ron ", result.contents)
    end

    def test_scope_transform_removes_records_2
      select_data = "Johnson    "
      select = XSet.new(11, select_data)
      result = @name_set.restrict(select)
      assert_equal("Johnson     Lee ", result.contents)

      @name_set.scope_transform = IntegerScopeTransform.new([2,3])
      result = @name_set.restrict(select)
      assert_equal("Johnson     Lee ", result.contents)

      select_data = "Anderson   "
      select = XSet.new(11, select_data)
      result = @name_set.restrict(select)
      assert_equal("Anderson    Ann ", result.contents)

      select_data = "Jeffries   "
      select = XSet.new(11, select_data)
      result = @name_set.restrict(select)
      assert_equal("", result.contents)
    end

#    def test_firstname_restrict
#      name_data = "Jeffries    Ron Hendrickson ChetAnderson    Ann Johnson     Lee "
#      input = XSet.new(16, name_data)
#      select_data = "Ron Lee "
#      select = XSet.new(4, select_data)
#      expected = "Jeffries    Ron Johnson     Lee "
#      result = input.restrict(select)
#      assert_equal(expected, result.contents)
#    end
  end