Remove source

In the newvtree branch the full source was removed to start
from scratch. Since then the master branch has move on. This
commit does restore that state on current HEAD and then all
changes from the newvtree branch are applied. This way we end
up in a source tree which is exactly the one of the newvtree
branch, but is based on current HEAD. This way a merge commit
is easily possible.

In order to get to the same state as the newvtree branch
originally was, we need to add back the original Makefile that
existed before the move to CMake.

The original commit message in the newvtree branch for this
change was:

    Remove source

    Remove everything except for the Makefile and rebar. The
    new vtree is implemented from scratch.

Change-Id: I2f6d08958c903358498a42883488d49a0b88b274
Reviewed-on: http://review.couchbase.org/15700
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Reviewed-by: Volker Mische <volker.mische@gmail.com>
Tested-by: Volker Mische <volker.mische@gmail.com>

Conflicts:
	README.md
	rebar.config
	share/www/script/test/spatial_design_docs.js
	src/geocouch/couch_httpd_spatial.erl
	src/geocouch/couch_httpd_spatial_merger.erl
	src/geocouch/couch_spatial.erl
	src/geocouch/couch_spatial.hrl
	src/geocouch/couch_spatial_compactor.erl
	src/geocouch/couch_spatial_group.erl
	src/geocouch/couch_spatial_merger.erl
	src/geocouch/couch_spatial_updater.erl
	src/geocouch/geocouch_duplicates.erl
	test/100-updater.t
	test/200-compact.t
CBD-72: First part of the split algorithm

This commit implements the first part of the split algorithm
of the RR*-tree (section 4.1).

Change-Id: If97f6397f5974e1c0ab46841387655ab14c500f1
Reviewed-on: http://review.couchbase.org/15701
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Tested-by: Volker Mische <volker.mische@gmail.com>
Reviewed-by: Volker Mische <volker.mische@gmail.com>
asym() function (part of CBD-76)

The asym() function determines the imbalance of a split.

Change-Id: If72b8a5ba070439dff9ee54ddcc5c2bee958918c
Reviewed-on: http://review.couchbase.org/15702
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Reviewed-by: Volker Mische <volker.mische@gmail.com>
Tested-by: Volker Mische <volker.mische@gmail.com>
Added README

The README contains instructions how to get/build GeoCouch and
how to run the tests.

Change-Id: I34fbdbac7fbb4419ed64adddfe24a3c8324a0d07
Reviewed-on: http://review.couchbase.org/15777
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Reviewed-by: Volker Mische <volker.mische@gmail.com>
Tested-by: Volker Mische <volker.mische@gmail.com>
GC-2: Improving build

The build now fails on warnings and "make check" runs dialzyer.

Change-Id: I2d3d81363707bd7224a0c61423e489c728a6a5fb
Reviewed-on: http://review.couchbase.org/15778
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
GC-3: Make COUCH_SRC parsing less fragile

Previously parsing the COUCH_SRC envirnment variable, to get it
into the Erlang include path was rather hacky. With the new
dynamic script functionality in Rebar it is possible in a much
nicer way.

Rebar had to be updated in order to have this functionality.

Change-Id: Iab3de2b0482bd245ba339ddbcf1274bffa261c3e
Reviewed-on: http://review.couchbase.org/15858
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>

Conflicts:
	rebar
CBD-76: Implementation of the weight function

This commit implements the weight function for the RR*-tree split
algorithm. The final goal function was also implemented. Now
everything should be set to call it from the split function, which
makes a destinction between inner and leaf nodes.

There was also a change in the test files, as somehow Etap didn't
display error messages correctly when some error occured.

Change-Id: Iecc8477202557c32c5249d5aaf7138f09743690c
Reviewed-on: http://review.couchbase.org/16066
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
CBD-124: Move type information into header file

No functional change, just moving code.

Change-Id: Iea5a5f15f83efdbe821530e5ec9cd5137ea95d76
Reviewed-on: http://review.couchbase.org/16360
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
CBD-124: Add helper function to find minimum element

`find_min_value/2` takes a list of items and a function that
will return numbers. One item at a time is passed into that
function. The item that returns the smallest value will be
returned. It's a 2-tuple containing the minimum value and the
item itself.

Change-Id: Id5815937bf59b6f78112cf3cee4d28cf356ea354
Reviewed-on: http://review.couchbase.org/16361
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
CBD-124: Make vtree_split use the more general find_min_value/2

The find_min_candidate/2 function was refactored out to a more
general function that will also be used by the vtree_choose
module.

Change-Id: Icf4d6cb21ae8ee2d6b6a500cb0032d3e5788158a
Reviewed-on: http://review.couchbase.org/16369
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Tested-by: buildbot <build@couchbase.com>
CBD-124: Move functions to vtree_util

Move some functions from vtree_split to the vtree_util module
in preparation for the vtree_choose module.

This is a no functional change, functions where only moved.

Change-Id: I43ef843893dd1b32baabe9f4123d94e1e2b16260
Reviewed-on: http://review.couchbase.org/16379
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
MB-100: Remove wrong comment

Change-Id: I145a839406fedc7f3648410fbb9e082cf50335cf
Reviewed-on: http://review.couchbase.org/16410
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
CBD-124: Implementation of the ChooseSubtree algorithm

This commit is an implementation of the ChooseSubtree algorithm
as described in the RR*-tree paper.

Change-Id: I4582604efe6583afe22e5618193cd1bf05034139
Reviewed-on: http://review.couchbase.org/16411
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
CBD-65: Make vtree_split:split_axis/4 return the dimension

For forther steps in the algorithm we need to know on which
dimension the data was split for the resulting split axis.

Change-Id: Ia0c3f3d104d8155a96343beb6eddebfffbb1e149
Reviewed-on: http://review.couchbase.org/21019
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Reviewed-by: Volker Mische <volker.mische@gmail.com>
CBD-65: Public API for splitting nodes

There's no a public API for splitting a list of nodes into
two partitions. This is used when a node overflows, which
happens when an already full nodes gets another one added.

The RR*-tree makes a distinction between inner and leaf nodes
when splitting.

Change-Id: Iec5d182ce6c76efc492c0632980c5086c09d1437
Reviewed-on: http://review.couchbase.org/21020
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Reviewed-by: Volker Mische <volker.mische@gmail.com>
CBD-65: Be more precise about types

FillMin and FillMax are always positive integers, take this into
account.

Change-Id: Iaa63e0cbbb1fce2821301dc6831065e0f5cbb12e
Reviewed-on: http://review.couchbase.org/21021
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Reviewed-by: Volker Mische <volker.mische@gmail.com>
MB-100: Move calc_mbb/2 to vtree_util

Change-Id: I67ad0b1a6cc318163f023072493e72e26b0ca14d
Reviewed-on: http://review.couchbase.org/21022
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Reviewed-by: Volker Mische <volker.mische@gmail.com>
CBD-51: Encoding/decoding for termless format

GeoCouch doesn't store Erlang terms, but binary data. This needs
to be encoded/decoded for the use within the Erlang code. The
vtree_io module handles all that. You can easily write and read
a node.

Change-Id: I70429013fdf3dcf8b7f215c6fb382092a81f4014
Reviewed-on: http://review.couchbase.org/21023
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Reviewed-by: Volker Mische <volker.mische@gmail.com>
CBD-65: Throw exception for non valid fill values

There are values for the minimum and maximum number of child nodes
that are not valid. For example you can't split 7 nodes into two
partitions with a minimum of 4 and a maximum of 6 nodes. If those
values are given, throw an exception.

Change-Id: I4fed4464c4067425f9a7fe882a9e9ac822d65c79
Reviewed-on: http://review.couchbase.org/21024
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Reviewed-by: Volker Mische <volker.mische@gmail.com>
CBD-65: Fix asym/3

vtree_split:asym/3 broke when the length of the MBB is zero. The
solution is to return zero immediately.

Change-Id: I443e01ca3c7233eb03fa32c751bf7aad10b80ecb
Reviewed-on: http://review.couchbase.org/21025
Tested-by: buildbot <build@couchbase.com>
Reviewed-by: Filipe David Borba Manana <fdmanana@gmail.com>
Reviewed-by: Volker Mische <volker.mische@gmail.com>