Collections algorithms as infrastructure

March 14 2009

this week i’ve performed my first public kata, at the local XPUG, here in Milan. meeting’s topic was “internal iterators and blocks”, very close to my heart. i just had the idea a few days ago, and the eXtreme guys approved my session as soon as i proposed. (this year seems promising, a lot of pratical sessions planned… stay tuned!)

the main idea for a (code) kata is to perform a short pratical exercise you feel confident with, almost with no braining; fingers should go on smoothly, like a dance. i chose to start from Matteo’s “birthday greetings” session on exagonal architecture, as coded by Milo and me during an XPUG meeting. i did the kata at home a few times and collected on paper some guidelines. then i printed out “brief instructions”, which i distributed to the audience before starting. the plan was a three short exercises kata.

first, i refactored existing code, splitting loops, extracting the InternalIterator / Predicate pair and then moving construction to facades like On an Being. second exercise was adding a new functionality, “send a kiss to female employees”; i drove implementation with unit tests, and focused on using just extracted iterator and predicate code. it finally looked like this:


public class BirthdayService { ...

  public void sendGreetings(OurDate ourDate) throws Exception {
    List employees = employeeFacade.loadEmployees();

    for (Employee employee : On.items(employees).collect(Being.bornOn(ourDate))) {
      sendGreetingTo(employee, happyBirthday(employee));
    }

    for (Employee employee : On.items(employees).collect(Being.female())) {
      sendGreetingTo(employee, "A kiss for you");
    }
  }
}

then, the mini collections library – On.items().collect(predicate) – was first modified to be generic (with Java’s Generics) and then improved with other functionalities such as:

  • findFirst(predicate)
  • reject(predicate)
  • contains(predicate)
  • apply(transformation)

final code consisted of 3 interfaces for blocks, one class for internal iterator, a Not predicate implementation and, finally, the On facade.

the leitmotif for the session was “you know, i don’t really like algorithms, so i don’t want to write them twice!”. that funny sentence was just trying to show how much more readable and understandable the code was without noisy algorithm details (like useless foreach, if/else, results.add(), if not null, etc). even if it was late evening, audience was really following me (and i have to admit, i was going a bit too fast!). they also asked me some good questions.

Gabriele pointed out that maybe findFirst() should provide a default value parameter, instead or returning a null reference. with Roberto we also discussed how difficult could be to implement returning a generic NullObject instance. Matteo went further on the idea of literal programming, suggesting something like:


employees.collect(bornToday).do(sendGreeting)

this would require iterator returning another iterator instead of a collection, or encapsulating every collection into a domain object.

something that really catched my attention was Gabriele suggesting moving predicates from Being facade into domain classes, with the pleasant side effect of removing useless getters on domain objects. that’s really a good idea! i’ll consider this for sure next time (kata was insipired by code from a project i no more work on).

then, Matteo finally asked me how many “collection traverse” algorithms i would have encapsulated into an iterator. i could not answer, i thougth it depends on business scenarios. but i just didn’t understand well the question: he was referring to the foreach loops, and that’s why he suggested me that probably i would not have written another foreach loop, they’re just MAP and REDUCE (transform and collect). nice hint, i should study some more functional programming; or even better, some more Smalltalk-Rubysh idioms! (yes, i’ve done a Google search for that. first rule to learn more: admit your ignorance)

here it comes the best part. before going home, i pushed for this methapor. exagonal architecture (and DIP) promotes to encapsulate low-level infrastructure behind an interface (a facade), to which high-level client code interacts with passing around domain objects; you just have to write and adapter once. for example, an EmployeeFacade interface and a DatabaseEmployeeAdapter – written just once – which takes Conditions to filter data searches; new business scenarios can be achieved providing different Conditions, without the need to modify infrastructure code.

in the same way, i consider collection manipulation an infrastructure issue: what really matters is behaviour to be run on collection items. that’s why i really like writing algorithms just once, and reuse them heavly providing specific behaviour for a given user story: concrete predicates, transformations and other blocks are the only domain code i have to write; iterators are hidden behind a (creation) facade, like On.

when i first thought about, this sounded like an epiphany, but i can see it’s not so easy to understand, or to agree with. let me just know what you think about.

ok, and finally, here is the code! tests firts:


@Test
public void sholdCollectItemsMathcingAPredicate() throws Exception {
  assertEquals(Arrays.asList(2, 6), On.items(Arrays.asList(2, 3, 6)).collect(new Even()));
}

@Test
public void shouldFindAnItemMathingAPredicate() throws Exception {
  assertEquals(2, On.items(Arrays.asList(1, 2, 4, 5)).findFirst(new Even()));
}

@Test
public void shouldReturnNullIfNotMatchingItemFound() throws Exception {
  assertNull(On.items(Arrays.asList(1, 3, 5)).findFirst(new Even()));
}

@Test
public void shouldRejectItemsNotMathingAPredicate() throws Exception {
  assertEquals(Arrays.asList(1, 5), On.items(Arrays.asList(1, 2, 5, 4)).reject(new Even()));
}

@Test
public void shouldDetectIfAMatchingItemIsFound() throws Exception {
  assertTrue(On.items(2, 5).contains(new Even()));
}

@Test
public void shouldApplyTransformationOnEacheItem() throws Exception {
  assertEquals(Arrays.asList(2, 4, 6), On.items(1, 2, 3).apply(new Doubler()));
}

public class Even implements Predicate<Integer>{
  public boolean evaluate(Integer item) {
    return item % 2 == 0;
  }
}

public class Doubler implements SimpleTransformation<Integer> {
  public Integer applyOn(Integer item) {
    return item * 2;
  }
}

then application code:

public interface Predicate<TYPE> {
  boolean evaluate(TYPE item);
}

public interface Transformation<FROM, TO> {
  public TO applyOn(FROM item);
}

public interface SimpleTransformation<TYPE> extends Transformation<TYPE, TYPE>{
}

public class InternalIterator<TYPE> {
  private final List<TYPE> items;

  public InternalIterator(List<TYPE> items) {
    this.items = items;
  }

  public List<TYPE> collect(Predicate<TYPE> predicate) {
    List<TYPE> result = new ArrayList<TYPE>();
    for (TYPE eachItem : items) {
      if (predicate.evaluate(eachItem)) {
        result.add(eachItem);
      }
    }
    return result;
  }

  public TYPE findFirst(Predicate<TYPE> predicate) {
    List<TYPE> result = collect(predicate);
    return result.isEmpty() ? null : result.get(0);
  }

  public List<TYPE> reject(Predicate<TYPE> predicate) {
    return collect(new Not<TYPE>(predicate));
  }

  public boolean contains(Predicate<TYPE> predicate) {
    return ! collect(predicate).isEmpty();
  }

  public <TO> List<TO> apply(Transformation<TYPE, TO> tranfromation) {
    List<TO> result = new ArrayList<TO>();
    for (TYPE eachItem : items) {
      result.add(tranfromation.applyOn(eachItem));
    }
    return result;
  }
}

public class Not<TYPE> implements Predicate<TYPE> {
  private final Predicate<TYPE> predicate;

  public Not(Predicate<TYPE> predicate) {
    this.predicate = predicate;
  }

  public boolean evaluate(TYPE item) {
    return ! predicate.evaluate(item);
  }
}

public class On {

  public static <TYPE> InternalIterator<TYPE> items(List<TYPE> items) {
    return new InternalIterator<TYPE>(items);
  }

  public static <TYPE> InternalIterator<TYPE> items(TYPE... items) {
    return On.items(Arrays.asList(items));
  }
}
Advertisements

One Response to “Collections algorithms as infrastructure”


  1. Congrats! Great Post.
    I suggest you to use a syntax highlighting for Java like this:
    http://www.tohtml.com/java/


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: