Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

The following is more of a statement than a question - it describes something that may be a pattern. The question is: is this a known pattern? Or, if it's not, should it be?

I've had a situation where I had to iterate over two dissimilar multi-layer data structures and copy information from one to the other. Depending on particular use case, I had around eight different kinds of layers, combined in about eight different combinations:

A-B-C
B-C
A-C
D-E
A-D-E

and so on

After a few unsuccessful attempts to factor out the repetition of per-layer iteration code, I realized that the key difficulty in this refactoring was the fact that the bottom level needed access to data gathered at higher levels. To explicitly accommodate this requirement, I introduced IterationContext class with a number of get() and set() methods for accumulating the necessary information.

In the end, I had the following class structure:

class Iterator {
  virtual void iterateOver(const Structure &dataStructure1, IterationContext &ctx) const = 0;
};

class RecursingIterator : public Iterator {
  RecursingIterator(const Iterator &below);
};


class IterateOverA : public RecursingIterator {
  virtual void iterateOver(const Structure &dataStructure1, IterationContext &ctx) const {
    // Iterate over members in dataStructure1
      // locate corresponding item in dataStructure2 (passed via context)
      // and set it in the context
      // invoke the sub-iterator
};

class IterateOverB : public RecursingIterator {
  virtual void iterateOver(const Structure &dataStructure1, IterationContext &ctx) const {
    // iterate over members dataStructure2 (form context)
      // set dataStructure2's item in the context
      // locate corresponding item in dataStructure2 (passed via context)
      // invoke the sub-iterator
};


void main() 
{
  class FinalCopy : public Iterator {
      virtual void iterateOver(const Structure &dataStructure1, IterationContext &ctx) const {
          // copy data from structure 1 to structure 2 in the context,
          // using some data from higher levels as needed
      }
   }

  IterationContext ctx(dateStructure2);
  IterateOverA(IterateOverB(FinalCopy())).iterate(dataStructure1, ctx);
}

It so happens that dataStructure1 is a uniform data structure, similar to XML DOM in that respect, while dataStructure2 is a legacy data structure made of various structs and arrays. This allows me to pass dataStructure1 outside of the context for convenience. In general, either side of the iteration or both sides may be passed via context, as convenient.

The key situation points are:

  • complicated code that needs to be invoked in "layers", with multiple combinations of layer types possible
  • at the bottom layer, the information from top layers needs to be visible.

The key implementation points are:

  • use of context class to access the data from all levels of iteration
  • complicated iteration code encapsulated in implementation of pure virtual function
  • two interfaces - one aware of underlying iterator, one not aware of it.
  • use of const & to simplify the usage syntax.
share|improve this question
9  
How many times have you seen this in practice? More than twice? It's a pattern. –  S.Lott Apr 7 '11 at 13:57
2  
"Should it be?" -- let me go ask the central authority on programming patterns and see what they have to say... –  Greg Jackson Jun 23 '11 at 16:25
2  
This looks like some sort of combination of memoization and plain old recursion. If you pull out those parts, are you still left with an interesting pattern? –  Alex Feinman Jun 23 '11 at 17:23
    
Couldn't understand the problem at all. All I see is some similarity with combinatorics, lots of extra copies and a lot of virtual + interface + smthn. else I wouldn't want to dig through during maintenance. Do you need a deep copy? –  Coder Sep 21 '11 at 22:53
    
Re-write this algorithm in Clojure and see if it still looks interesting. –  Job Oct 22 '11 at 14:58

4 Answers 4

The pattern you currently describe appears to do several things intertwined. So you could define it as a new pattern for a very specific case of directly traversing some type of language (because that's basically what some ordering of data structures is), but it's probably easier to split it up.

An example to deal with this: The ordering of separate data structures you enumerate will fall into some class of language (it looks like a regular language as you describe it, but the nesting sounds like it could also be expressed as a context-free language, or a context-sensitive language if some data structures' contents define what follows next).

Based on the qualification of the language, you can define a grammar and use that to use any of a host of existing parsing algorithms to turn the data you encounter into an abstract syntax tree (AST) and traverse that using the Visitor or Interpreter-pattern.

You can split this up even further by developing multiple visitors or interpreters to implement the separate steps you need to copy data around (or perform any other action).

share|improve this answer

I don't know enough about what you are doing, but it would seem more practical to have something upstream that can be used as a prototype for the generation of both data structures. The fact that your are copying data back and forth between 2 data structures says something isn't right because it's a violation of DRY.

If it's not possible to prototype the 2 data structures, another options would be to create a delegate for the legacy data structure that returns the values from the that structure in an expected manner.

share|improve this answer

I really do not know if that is a pattern, but there is already a design pattern that can help you (i think) to acomplish what you want with that data structure.

The pattern is called Iterator (it is a behavioral pattern presented in the book "Design Patterns: Elements of reusable Object Oriented Software" by the Gang of Four), it provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation. I recomend you to take a look at it, may be it can help you.

share|improve this answer

The pattern I see is the Decorator pattern whereby you have a class that performs the work (FinalCopy) which can be 'decorated' by the classes IterateOverA and IterateOverB. The 'decorating' classes augment the FinalCopy class by performing additional tasks before and after invocations on it. Since all three of these classes implement the same interface (Iterator), they are interchangeable and the client need not know of their nesting.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.