Contest 42: Set Symmetric Difference (part 3)

[Ryan]

Contest 42: Set Symmetric Difference (part 3)
Difficulty: Advanced
Deadline: 7 August 2004 at 19:00 GMT

Description
In set theory, the difference operator, expressed A-B, is the set of all elements of A that are not in B. For example, if A = {1,2,3,4,5} and B = {3,4,5,6,7}, A-B = {1,2}.

The symmetric difference operator of two sets A and B, expressed as A\B, is defined as (A-B) union (B-A). It consists of all the elements in A not in B as well as the elements in B not in A. Using A = {1,2,3,4,5} and B = {3,4,5,6,7} as above, A\B = {1,2,6,7}.

You will write a template metaprogram that receives two lists of integers and performs a symmetric difference operation on them at compile time.

Prototype

Code: Select all

template <class List1, class List2>
struct symmetric_difference : counter< symmetric_difference<List1,List2> >
{
  typedef /*implementation here*/ result;
};


A list is constructed in a manner similar to lists in Lisp or Scheme, from the following types:

Code: Select all

namespace list
{
  template <int N, class Next>
  struct element { };

  struct end { };
}

element is a 2-tuple container that holds one integer in the list (N) and the rest of the list (Next). The list is terminated by the end structure. An example of the lists corresponding to A and B:

Code: Select all

using namespace list;

  typedef element<1,
  element<2,
  element<3,
  element<4,
  element<5, end> > > > > A;

  typedef element<3,
  element<4,
  element<5,
  element<6,
  element<7, end> > > > > B;
}

Each type you create to aid your computation must inherit from counter<Type>, where Type is the typename you are creating. See the prototype for an example. The counter type will count the number of template instantiations in your metaprogram.

Two header files are provided for your use: counter.hpp and list.hpp.

Optimize for: minimum template instantiation
Each unique type generated in the computation of your answer counts as one template instantiation. The count gathers in static_counter::count.

Example
Given the types from above, your code should satisfy the following:

Code: Select all

using namespace list;
typedef element<1,
element<2,
element<6,
element<7, end> > > > A_diff_B;

typedef symmetric_difference<A,B>::result your_answer;
assert(is_same_type<your_answer, A_diff_B>::result);

// the following should print "1 2 6 7"
print<your_answer>();

// the following outputs the total number of template instantiations
cout << static_counter::count << endl;


Notes

• You must compute the values at compile-time.
• Your solution must be source-compatible to the provided prototype.
• No number will occur more than once in any input list, but the input lists will not necessarily be sorted.
• Your answer must be sorted.

Submissions
Please attach your solution as a single header file in an email to ryan@cpp-home.com, with the subject line as "Contest 42".

Post any questions or comments in this thread. Good luck and enjoy!

[jgbauman]

nice contest, but I don't think the static_counter will work.

[Ryan]

nice contest, but I don't think the static_counter will work.

How come? I've tested it with GCC and VC7.1.

[Ryan]

No takers on this one? The contest ends in just a few hours -- is anyone interested in extending the deadline?

[Bladesniper]

It's a little late now, but i have 2 questions:
1.

Code: Select all

template <int N, class Next>
  struct element { };

Are you sure that's how the structure should be? How are we going to access the Ns? I expected it to be like:

Code: Select all

template <int N, class Next>
struct element {
    enum { value = N };
    typedef Next NextElement;
};

2. If the two lists are the same ( A\B = {} ), what should the 'result' be?

[Ryan]

It's a little late now, but i have 2 questions:
1.

Code: Select all

template <int N, class Next>
  struct element { };

Are you sure that's how the structure should be? How are we going to access the Ns? I expected it to be like:

Code: Select all

template <int N, class Next>
struct element {
    enum { value = N };
    typedef Next NextElement;
};

EIther way would work. Look at the print() code for an example of working with lists structured that way. Basically, it's like this:

Code: Select all

// initial definition
template <class List> struct DoSomething { };

// specialization
template <int N, class Next>
struct DoSomething< element<N,Next> >
{
  // N and Next are accessible here
};


2. If the two lists are the same ( A\B = {} ), what should the 'result' be?

Just the "end" type.

[Bladesniper]

Ok now i see; i was viewing the problem from a different view-point.
I think i can't solve it, but i'll try later or tomorrow to see what i can do about it...

[Ryan]

Since this contest is gathering no interest, let's kill it. Maybe next time.

Is anyone interested at all in seeing the solution?

[Guest]

That is obviously Dave Sinkula so go back to http://cboard.cprogramming.com/index.php? and stay there.

[schloob]

Yes I have no idea how to do things at COMPILE time.. thats just insane :[

[Ryan]

The algorithm I used is the same one used by several people in contest 41. See Beer Hunter's or DrunkenCoder's or Dudi HaTotah's code for an example. Basically, it goes like this:

Code: Select all

sort list1
sort list2
index1 = 0
index2 = 0
while (index1 < list1.size && index2 < list2.size)
  if (list1[index1] == list2[index2])
    ++index1
    ++index2
  else if (list1[index1] < list2[index2])
    list[index1] is in the symmetric difference
    ++index1
  else
    list[index2] is in the symmetric difference
    ++index2
end while

the remainder of list1 or list2 (whichever is not at the end) is in the symmetric difference


My algorithm to do it at compile time is in the next post.

[Ryan]

Code: Select all

#include "list.hpp"

namespace list
{
  ////////////////////////////////////////////////////////////////////////////
  // get_element<Element>
  // a utility metafunction to extract the data from an element<>
  template <class Element>
  struct get_element
  { };

  template <int N, class Next>
  struct get_element< element<N,Next> >
  {
    enum { value = N };
    typedef Next next;
  };

  ////////////////////////////////////////////////////////////////////////////
  // insert<List, N>
  // a utility metafunction to insert an int into its sorted position in a list
  template <class List, int N>
  struct insert;
 
  template <class List, int N, bool insert_here>
  struct insert_helper
  {
    // default implementation -- insert_here == true
    typedef element<N, List> result;
  };
 
  template <class List, int N>
  struct insert_helper<List, N, false>
  {
    // insert_here == false
    // just recurse
    typedef get_element<List> el;
    typedef element<el::value, typename insert<typename el::next, N>::result> result;
  };
 
  template <class List, int N>
  struct insert
  {
    static const bool insert_here = (N < get_element<List>::value);
    typedef typename insert_helper<List,N,insert_here>::result result;
  };

  // end condition for insert
  template <int N>
    struct insert<end,N>
  {
    typedef element<N,end> result;
  };

  ////////////////////////////////////////////////////////////////////////////
  // sort<List>
  // metafunction to sort a list
  template <class List>
  struct sort
  {
    // recursive insertion sort
    // recursively sort the rest of the list, then insert this element into the sorted list
    typedef typename insert<
      typename sort<typename get_element<List>::next>::result,
      get_element<List>::value
    >::result result;   
  };

  // recursion termination -- sort the end marker
  template <>
  struct sort<end>
  {
    typedef end result;
  };


  ////////////////////////////////////////////////////////////////////////////
  // symmetric_difference
 
  template <class List1, class List2>
  struct do_symmetric_difference;

  template <class List1, class List2>
  struct symmetric_difference
  {
    // sort the lists and hand them off to do_symmetric_difference
    typedef typename sort<List1>::result SortedList1;
    typedef typename sort<List2>::result SortedList2;
    typedef typename do_symmetric_difference<SortedList1, SortedList2>::result result;
  };

  enum CompareResult {Less,Greater,Equal};
 
  template <class List1, class List2, CompareResult cr>
  struct sd_helper { };
 
  template <class List1, class List2>
  struct sd_helper<List1, List2, Equal>
  {
    // cr == Equal
    // N1==N2, so neither are in the symmetric difference -- skip them
   
    // in the next recursive step, advance list1 and list2
    typedef typename symmetric_difference<
      typename get_element<List1>::next,
      typename get_element<List2>::next
    >::result result;
  };

  template <class List1, class List2>
  struct sd_helper<List1, List2, Less>
  {
    // cr == Less
    // N1<N2, so N1 must be in the symmetric difference -- add it and recurse
   
    // save ourselves some typing
    typedef get_element<List1> list1;

    // in the next recursive step, advance list1 but keep list2 in the same position
    typedef typename symmetric_difference<typename list1::next, List2>::result recurse_result;

    // add N1 to the result list
    typedef element<list1::value, recurse_result> result;
  };

  template <class List1, class List2>
  struct sd_helper<List1, List2, Greater>
  {
    // cr == Greater
    // N1>N2, so N2 must be in the symmetric difference -- add it and recurse
   
    // save ourselves some typing
    typedef get_element<List2> list2;

    // in the next recursive step, advance list2 but keep list1 in the same position
    typedef typename symmetric_difference<List1, typename list2::next>::result recurse_result;

    // add N2 to the result list
    typedef element<list2::value, recurse_result> result;
  };

  template <class List1, class List2>
  struct do_symmetric_difference
  {
    // save ourselves some typing
    typedef get_element<List1> list1;
    typedef get_element<List2> list2;
    enum { N1 = list1::value, N2 = list2::value };

    // compute CompareResult
    static const CompareResult choice =
      N1<N2 ? Less : (N1>N2 ? Greater : Equal);   
   
    // use CompareResult to choose between sd_helper implementations
    typedef typename sd_helper<List1,List2,choice>::result result;
  };
 
  // recursive end conditions -- when we hit the end of one of the lists,
  // the entirety of the other list is in the symmetric_difference
  template <class List1>
  struct do_symmetric_difference<List1, end>
  {
    typedef List1 result;
  };
 
  template <class List2>
  struct do_symmetric_difference<end, List2>
  {
    typedef List2 result;
  }; 
}


typedef list::element<5,
  list::element<2,
  list::element<4,
  list::element<3,
  list::element<1, list::end> > > > > A;

typedef list::element<5,
  list::element<3,
  list::element<4,
  list::element<7,
  list::element<6, list::end> > > > > B;


int main()
{
  list::print<A>();
  list::print<B>();
 
  typedef list::symmetric_difference<A,B>::result test1;
  list::print<test1>();
}

[Ryan]

Sheesh, that's awfully hard to read.

http://contests.cpp-home.com/42/contest42.cpp

[schloob]

what on earth is that?