/* Formal Concept Analysis based on Ganter Wyle's Book.
   See 
	http://www.jfsowa.com/pubs/autotalk.htm#s10
   for a quick introduction and example proving
	that beer is champagne.
*/
#include <set>
#include <map>
#include <algorithm>
#include <string>

template <class Object, class Attribute>
class FormalContext{
	set<Object> o;//objects
	set<Attribute> a;//attributes
public:
  typedef set< pair <Object, Attribute> > Relation;
private: 
  typedef map< Object, set<Attribute> > O2A;
	O2A o2a;
  typedef map< Attribute, set<Object> > A2O;
	A2O a2o;
  //- inv. o is the domain of o2a and the image of a2o
  //- inv. a is the domain of a2o and the image of o2a
  //- inv. for all x:o, x is a member( o2a(a2o(x)))
  //- inv. for all y:a, y is a member( a2o(a2o(y)))
public:
	FormalContext(Relation r);

	set<Object> objects(){return o;}
	set<Object> objects(Attribute y){return a2o[y];}

	set<Attribute> attributes(){return a;}
	set<Attribute> attributes(Object x){return o2a[x];}

	set<Attribute> common_attributes(Object  x){return o2a[x];}
	set<Attribute> common_attributes(set<Object>  x);

	set<Object> common_objects(Attribute y){return a2o[y];}
	set<Object> common_objects(set<Attribute> y);

	set<Object> close_object(Object s)
		 { return common_objects(common_attributes(s));}
	set<Object> close_object(set<Object> s)
		 { return common_objects(common_attributes(s));}

	set<Attribute> close_attribute(Attribute s)
		 { return common_attributes(common_objects(s));}
	set<Attribute> close_attribute(set<Attribute> s)
		 { return common_attributes(common_objects(s));}

};

template <class Object, class Attribute>
FormalContext<Object,Attribute>::FormalContext(FormalContext<Object,Attribute>::Relation r)
{
	for(FormalContext<Object,Attribute>::Relation::iterator p=r.begin();
		p!=r.end();
		++p)
	{
		o.insert(p->first);
		a.insert(p->second);
		o2a[p->first].insert(p->second);
		a2o[p->second].insert(p->first);
	}
}

template <class Object, class Attribute>
set<Attribute> FormalContext<Object,Attribute>::common_attributes(set<Object> x)
{
	if(x.empty()) return attributes();
	//else...
	set<Object>::iterator p=x.begin();
	set<Object>::iterator xe=x.end();
	set<Attribute> temp(o2a[*p]);
	set<Attribute> result(temp);
	set<Attribute> next;
	for( ++p; p!=xe; ++p)
	{ temp=o2a[*p];
	  set_intersection
		(result.begin(),result.end(), temp.begin(), temp.end(), 
		inserter(next, next.begin())
		);
	  result=next;
	}
	return result;
}
template <class Object, class Attribute>
set<Object> FormalContext<Object,Attribute>::common_objects(set<Attribute> y)
{

	if(y.empty()) return objects();
	//else
	set<Attribute>::iterator p=y.begin();
	set<Object> temp(a2o[*p]);
	set<Object> result(temp);
	set<Object> next;
	for( ++p, temp=a2o[*p]; p!=y.end(); ++p)
	{ 
	  set_intersection
		(result.begin(),result.end(), temp.begin(), temp.end(), 
		inserter(next, next.begin())
		);
	  result=next;
	}
	return result;
}
template <typename T>
void prin(set<T> s)
{
	cout <<"{ ";
	copy (s.begin(), s.end(), ostream_iterator<T>(cout, " "));
	cout << "}";
}
template <typename T>
void print(set<T> s)
{
	prin(s);
	cout << endl;
}
int main()
{
	typedef FormalContext<int,char> FC;
	FC::Relation r;
	r.insert(make_pair(1,'a'));
	r.insert(make_pair(1,'b'));
	r.insert(make_pair(2,'b'));
	r.insert(make_pair(2,'c'));
	r.insert(make_pair(3,'a'));
 //	r.insert(make_pair(4,'a'));
 //	r.insert(make_pair(4,'c'));
	FC sample(r);

	print(sample.objects());
	{ set<char> nullc;
	  set<int> s0 = sample.common_objects(nullc);
	  print(s0);
	}
	print(sample.attributes());
	{
	  set<int> nulli;
	  set<char> s0 = sample.common_attributes(nulli);
	  print(s0);
	}
	set<char> s1 = sample.common_attributes(1);
	print(s1);
	set<int> s2 = sample.common_objects('b');
	print(s2);
	set<int> s3 = sample.common_objects(s1);
	print(s3);
	set<char> s4 = sample.common_attributes(s3);
	print(s4);
	set<int> s5 = sample.common_objects(sample.common_attributes(2));
	print(s5);
	set<int> s6 = sample.close_object(3);
	print(s6);
	set<char> s7 = sample.close_attribute('a');
	print(s7);
	set<char> ca;
	set<int> os=sample.objects();
	set<int>::iterator oe = os.end();
	for(set<int>::iterator i=os.begin(); i!=oe; ++i)
	{
		cout << *i << " : ";
		ca = sample.common_attributes(*i);
		prin(ca);
		cout << " - ";
		prin(sample.common_objects(ca));
		cout << endl;
	}
}