Conflicts:
	containers.cabal

Add comment to tests/Makefile that users should use cabal to build and
run tests.

The resulting implementations are a bit faster, and there seems to be no
increased heap-allocation. I will confirm this by examining GHC memory
allocation.

The resulting implementations are approximately 40-50% faster, although
for some input data the performance is worse. This happens
* in unionWithKey, if the data are disjunct: 15% slowdown
* in differenceWithKey, as now we recurse over the first tree and not
  the second. The slowdown happens also only for disjunct data: 30%.

See the SetOperations benchmark for yourself if you are interested.

Instead of having a special case set `union` set_of_size_1 in union,
move it to hedgeUnion, so it can be used recursively. Benchmark shows up
to 30% speedup.

Use the hedge-intersection algorithm, similar to hedge-union and
hedge-difference.

Depending on inputs, this causes up to 80% speedup.

Also remove Set.splitLookup, which was used only to define intersection.

At last I found an example, where capturing the argument in local 'go'
function in 'member' causes increased heap-allocation. It is caused by
'go' function floating out of 'member' and allocating a dictionary and
the key argument.

This happens only with Map and Set methods. Therefore in IntMap and IntSet,
'go' function still captures the argument (and GHC shows no increased
heap-allocation as a result of that).

Avoid allocating the closure for local function 'merge'.

Following a proposal on libraries@..., we add fromSet method to Map and
IntMap:
  Map.fromSet :: (k -> a) -> Set k -> Map k a
  IntMap.fromSet :: (Key -> a) -> IntSet -> IntMap a
It is implemented using exported Set and IntSet constructors.

Map.fromSet is trivial, as Map and Set have the same structure.

The IntMap.fromSet implementation is more complicated, as IntSet uses
dense representation of several last leves of the trie.

Leave dependencies on GHC instead of make.

The keysSet method is now implemented using the exported constructors of
Data.{Set, IntSet}.Base.

The implementation of Map.keysSet is trivial, as Set and Map use same
tree structure.

The implementation of IntMap.keysSet is slightly complicated, because of
the dense representation of IntSet, where several last levels of the
tree are flatten into a bitmap.

Similarly to Map and IntMap, the whole functionality is in
Data.IntSet.Base. The Data.IntSet module just reexports methods from
Data.IntSet.

The only difference between Data.IntSet.Base and Data.IntSet is that
Data.IntSet.Base exports the constructors of IntSet data type. This will
be used in IntMap to define efficient versions of keysSet and fromSet.

Similarly to Map and IntMap, the whole functionality is in
Data.Set.Base. The Data.Set module just reexports methods from Data.Set.

The only difference between Data.Set.Base and Data.Set is that
Data.Set.Base exports the constructors of Set data type. This will be
used in Map to define efficient versions of keysSet and fromSet.

Following the proposal on libraries@..., we add lookupLT, lookupGT,
lookupLE, lookupGE methods to Set, Map, IntSet and IntMap.

The implementations were chosen using the LookupLE benchmark.
Current implementations do not heap-allocate apart from the result.

Corresponding tests are added. The test suites for Set and IntSet
now use HUnit too.

Even on 32-bit architectures, bit shift of size 32 was performed.

We use the following:
  -- [Note: Some superimportant message]
  -- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Unfortunately, -- ^ is wrongly picked up by Haddock.
Instead we now use
  -- [Note: Some superimportant message]
  -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

As mentioned previously, INLINE - INLINABLE method chain does not result
in specialization, it has to be INLINABLE - INLINABLE.

Most of the code is by Twan van Laarhoven, thanks.

Also improve the infrastructure to handle benchmarks in different
subdirectories.

Inlining folds when 2 arguments are given is consistent
with Prelude.foldr and {IntMap,IntSeT}.fold*.

DeleteWith is no longer method of any collection.

When a local 'go' function is using methods from Ord dictionary,
this dictionary is heap-allocated at the entry to the outer function.
If it is given explicit type mentioning the Ord class, the dictionary is
passed on the stack, decreasing heap allocation.

* Manually inline findIndex and deleteAt to avoid allocation.

* Give type to local 'go' function of findIndex and lookupIndex
  to avoid heap allocation.

As documented in the Note: Local 'go' functions and capturing,
it is safe to use captured key argument in query functions.

Also, in order to decrease allocation, the query functions in Map
are manually inlined, so 'member' does not have to call 'lookup'
and heap-allocate 'Just a'.

Tests of query functions are much improved too.

Prevent multiple warnings caused by unsuccessful SpecConstr pass.
We do so by not inlining helper testing function.

These are probably inlined anyway, but we explicitly INLINE
them in Map and Set, so we do also in IntMap and IntSet for consistency.

As documented in the Note: Local 'go' functions and capturing,
it is safe to use captured key argument in query functions.

Also, in order to decrease allocation, the query functions in IntMap
are manually inlined, so 'member' does not have to call 'lookup'
and heap-allocate 'Just a'.

Tests of query functions are much improved too.

The order of constructors has clearly no effect on corectness.

Inspired by the change in order of constructors of IntMap and IntSet,
the benchmark shows slight improvement when changing the data
constructors from Tip | Bin to Bin | Tip.

Also, we now consistently use the same order of constructors in all
these structures: Map, Set, IntMap, IntSet.

Move important programming comments to the beginning of the source file,
give them names and refer to the from the source code where necessarry.

The INLINABLE pragma works only for GHC >= 7.0 and generates
warning for older compilers.