Re: Cube extension kNN support

diff --git a/contrib/cube/cube--1.0.sql b/contrib/cube/cube--1.0.sql
new file mode 100644
index 0307811..97258dd
*** a/contrib/cube/cube--1.0.sql
--- b/contrib/cube/cube--1.0.sql
*************** LANGUAGE C IMMUTABLE STRICT;
*** 135,142 ****
--- 135,158 ----
  
  -- proximity routines
  
+ CREATE FUNCTION distance_taxicab(cube, cube)
+ RETURNS float8
+ AS 'MODULE_PATHNAME'
+ LANGUAGE C IMMUTABLE STRICT;
+ 
+ CREATE FUNCTION distance_euclid(cube, cube)
+ RETURNS float8
+ AS 'MODULE_PATHNAME'
+ LANGUAGE C IMMUTABLE STRICT;
+ 
+ -- Alias for backword compatibility
  CREATE FUNCTION cube_distance(cube, cube)
  RETURNS float8
+ AS 'MODULE_PATHNAME', 'distance_euclid'
+ LANGUAGE C IMMUTABLE STRICT;
+ 
+ CREATE FUNCTION distance_chebyshev(cube, cube)
+ RETURNS float8
  AS 'MODULE_PATHNAME'
  LANGUAGE C IMMUTABLE STRICT;
  
*************** RETURNS float8
*** 157,162 ****
--- 173,183 ----
  AS 'MODULE_PATHNAME'
  LANGUAGE C IMMUTABLE STRICT;
  
+ CREATE FUNCTION cube_coord(cube, int4)
+ RETURNS float8
+ AS 'MODULE_PATHNAME'
+ LANGUAGE C IMMUTABLE STRICT;
+ 
  CREATE FUNCTION cube(float8) RETURNS cube
  AS 'MODULE_PATHNAME', 'cube_f8'
  LANGUAGE C IMMUTABLE STRICT;
*************** CREATE OPERATOR <@ (
*** 246,251 ****
--- 267,291 ----
  	RESTRICT = contsel, JOIN = contjoinsel
  );
  
+ CREATE OPERATOR -> (
+ 	LEFTARG = cube, RIGHTARG = int, PROCEDURE = cube_coord
+ );
+ 
+ CREATE OPERATOR <#> (
+ 	LEFTARG = cube, RIGHTARG = cube, PROCEDURE = distance_taxicab,
+ 	COMMUTATOR = '<#>'
+ );
+ 
+ CREATE OPERATOR <-> (
+ 	LEFTARG = cube, RIGHTARG = cube, PROCEDURE = distance_euclid,
+ 	COMMUTATOR = '<->'
+ );
+ 
+ CREATE OPERATOR <=> (
+ 	LEFTARG = cube, RIGHTARG = cube, PROCEDURE = distance_chebyshev,
+ 	COMMUTATOR = '<=>'
+ );
+ 
  -- these are obsolete/deprecated:
  CREATE OPERATOR @ (
  	LEFTARG = cube, RIGHTARG = cube, PROCEDURE = cube_contains,
*************** RETURNS internal
*** 296,301 ****
--- 336,345 ----
  AS 'MODULE_PATHNAME'
  LANGUAGE C IMMUTABLE STRICT;
  
+ CREATE FUNCTION g_cube_distance (internal, cube, smallint, oid)
+ RETURNS internal
+ AS 'MODULE_PATHNAME'
+ LANGUAGE C IMMUTABLE STRICT;
  
  -- Create the operator classes for indexing
  
*************** CREATE OPERATOR CLASS gist_cube_ops
*** 316,325 ****
  	OPERATOR	8	<@ ,
  	OPERATOR	13	@ ,
  	OPERATOR	14	~ ,
  	FUNCTION	1	g_cube_consistent (internal, cube, int, oid, internal),
  	FUNCTION	2	g_cube_union (internal, internal),
  	FUNCTION	3	g_cube_compress (internal),
  	FUNCTION	4	g_cube_decompress (internal),
  	FUNCTION	5	g_cube_penalty (internal, internal, internal),
  	FUNCTION	6	g_cube_picksplit (internal, internal),
! 	FUNCTION	7	g_cube_same (cube, cube, internal);
--- 360,376 ----
  	OPERATOR	8	<@ ,
  	OPERATOR	13	@ ,
  	OPERATOR	14	~ ,
+ 	OPERATOR	15	-> (cube, int) FOR ORDER BY float_ops,
+ 	OPERATOR	16	<#> (cube, cube) FOR ORDER BY float_ops,
+ 	OPERATOR	17	<-> (cube, cube) FOR ORDER BY float_ops,
+ 	OPERATOR	18	<=> (cube, cube) FOR ORDER BY float_ops,
+ 
  	FUNCTION	1	g_cube_consistent (internal, cube, int, oid, internal),
  	FUNCTION	2	g_cube_union (internal, internal),
  	FUNCTION	3	g_cube_compress (internal),
  	FUNCTION	4	g_cube_decompress (internal),
  	FUNCTION	5	g_cube_penalty (internal, internal, internal),
  	FUNCTION	6	g_cube_picksplit (internal, internal),
! 	FUNCTION	7	g_cube_same (cube, cube, internal),
! 	FUNCTION	8	g_cube_distance (internal, cube, smallint, oid);
! 
diff --git a/contrib/cube/cube.c b/contrib/cube/cube.c
new file mode 100644
index b0305ef..35315ea
*** a/contrib/cube/cube.c
--- b/contrib/cube/cube.c
*************** PG_FUNCTION_INFO_V1(cube_c_f8_f8);
*** 45,50 ****
--- 45,51 ----
  PG_FUNCTION_INFO_V1(cube_dim);
  PG_FUNCTION_INFO_V1(cube_ll_coord);
  PG_FUNCTION_INFO_V1(cube_ur_coord);
+ PG_FUNCTION_INFO_V1(cube_coord);
  PG_FUNCTION_INFO_V1(cube_subset);
  
  /*
*************** PG_FUNCTION_INFO_V1(g_cube_penalty);
*** 58,63 ****
--- 59,66 ----
  PG_FUNCTION_INFO_V1(g_cube_picksplit);
  PG_FUNCTION_INFO_V1(g_cube_union);
  PG_FUNCTION_INFO_V1(g_cube_same);
+ PG_FUNCTION_INFO_V1(g_cube_distance);
+ 
  
  /*
  ** B-tree support functions
*************** PG_FUNCTION_INFO_V1(cube_size);
*** 84,90 ****
  /*
  ** miscellaneous
  */
! PG_FUNCTION_INFO_V1(cube_distance);
  PG_FUNCTION_INFO_V1(cube_is_point);
  PG_FUNCTION_INFO_V1(cube_enlarge);
  
--- 87,95 ----
  /*
  ** miscellaneous
  */
! PG_FUNCTION_INFO_V1(distance_taxicab);
! PG_FUNCTION_INFO_V1(distance_euclid);
! PG_FUNCTION_INFO_V1(distance_chebyshev);
  PG_FUNCTION_INFO_V1(cube_is_point);
  PG_FUNCTION_INFO_V1(cube_enlarge);
  
*************** cube_overlap(PG_FUNCTION_ARGS)
*** 1207,1220 ****
  	PG_RETURN_BOOL(res);
  }
  
- 
  /* Distance */
  /* The distance is computed as a per axis sum of the squared distances
     between 1D projections of the boxes onto Cartesian axes. Assuming zero
     distance between overlapping projections, this metric coincides with the
     "common sense" geometric distance */
  Datum
! cube_distance(PG_FUNCTION_ARGS)
  {
  	NDBOX	   *a = PG_GETARG_NDBOX(0),
  			   *b = PG_GETARG_NDBOX(1);
--- 1212,1224 ----
  	PG_RETURN_BOOL(res);
  }
  
  /* Distance */
  /* The distance is computed as a per axis sum of the squared distances
     between 1D projections of the boxes onto Cartesian axes. Assuming zero
     distance between overlapping projections, this metric coincides with the
     "common sense" geometric distance */
  Datum
! distance_euclid(PG_FUNCTION_ARGS)
  {
  	NDBOX	   *a = PG_GETARG_NDBOX(0),
  			   *b = PG_GETARG_NDBOX(1);
*************** cube_distance(PG_FUNCTION_ARGS)
*** 1262,1267 ****
--- 1266,1421 ----
  	PG_RETURN_FLOAT8(sqrt(distance));
  }
  
+ Datum
+ distance_taxicab(PG_FUNCTION_ARGS)
+ {
+ 	NDBOX	   *a = PG_GETARG_NDBOX(0),
+ 			   *b = PG_GETARG_NDBOX(1);
+ 	bool		swapped = false;
+ 	double		distance;
+ 	int			i;
+ 
+ 	/* swap the box pointers if needed */
+ 	if (DIM(a) < DIM(b))
+ 	{
+ 		NDBOX	   *tmp = b;
+ 		b = a;
+ 		a = tmp;
+ 		swapped = true;
+ 	}
+ 
+ 	distance = 0.0;
+ 	/* compute within the dimensions of (b) */
+ 	for (i = 0; i < DIM(b); i++)
+ 		distance += abs(distance_1D(LL_COORD(a,i), UR_COORD(a,i), LL_COORD(b,i), UR_COORD(b,i)));
+ 
+ 	/* compute distance to zero for those dimensions in (a) absent in (b) */
+ 	for (i = DIM(b); i < DIM(a); i++)
+ 		distance += abs(distance_1D(LL_COORD(a,i), UR_COORD(a,i), 0.0, 0.0));
+ 
+ 	if (swapped)
+ 	{
+ 		PG_FREE_IF_COPY(b, 0);
+ 		PG_FREE_IF_COPY(a, 1);
+ 	}
+ 	else
+ 	{
+ 		PG_FREE_IF_COPY(a, 0);
+ 		PG_FREE_IF_COPY(b, 1);
+ 	}
+ 
+ 	PG_RETURN_FLOAT8(distance);
+ }
+ 
+ Datum
+ distance_chebyshev(PG_FUNCTION_ARGS)
+ {
+ 	NDBOX	   *a = PG_GETARG_NDBOX(0),
+ 			   *b = PG_GETARG_NDBOX(1);
+ 	bool		swapped = false;
+ 	double		d, distance;
+ 	int			i;
+ 
+ 	/* swap the box pointers if needed */
+ 	if (DIM(a) < DIM(b))
+ 	{
+ 		NDBOX	   *tmp = b;
+ 		b = a;
+ 		a = tmp;
+ 		swapped = true;
+ 	}
+ 
+ 	distance = 0.0;
+ 	/* compute within the dimensions of (b) */
+ 	for (i = 0; i < DIM(b); i++)
+ 	{
+ 		d = abs(distance_1D(LL_COORD(a,i), UR_COORD(a,i), LL_COORD(b,i), UR_COORD(b,i)));
+ 		if (d > distance)
+ 			distance = d;
+ 	}
+ 
+ 	/* compute distance to zero for those dimensions in (a) absent in (b) */
+ 	for (i = DIM(b); i < DIM(a); i++)
+ 	{
+ 		d = abs(distance_1D(LL_COORD(a,i), UR_COORD(a,i), 0.0, 0.0));
+ 		if (d > distance)
+ 			distance = d;
+ 	}
+ 
+ 	if (swapped)
+ 	{
+ 		PG_FREE_IF_COPY(b, 0);
+ 		PG_FREE_IF_COPY(a, 1);
+ 	}
+ 	else
+ 	{
+ 		PG_FREE_IF_COPY(a, 0);
+ 		PG_FREE_IF_COPY(b, 1);
+ 	}
+ 
+ 	PG_RETURN_FLOAT8(distance);
+ }
+ 
+ Datum
+ g_cube_distance(PG_FUNCTION_ARGS)
+ {
+ 	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
+ 	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+ 	NDBOX      *cube = DatumGetNDBOX(entry->key);
+ 	double      retval;
+ 
+ 	if (strategy == 15)
+ 	{
+ 		int coord = PG_GETARG_INT32(1);
+ 
+ 		if(coord > 0)
+ 			if IS_POINT(cube)
+ 				retval = (cube)->x[(coord-1)%DIM(cube)];
+ 			else
+ 			{
+ 				/* This is for right traversal of non-leaf elements */
+ 				retval = Min(
+ 					(cube)->x[(coord-1)%DIM(cube)],
+ 					(cube)->x[(coord-1)%DIM(cube) + DIM(cube)]
+ 				);
+ 			}
+ 
+ 		/* negative coordinate user for descending sort */
+ 		else
+ 			if IS_POINT(cube)
+ 				retval = -(cube)->x[(-coord-1)%DIM(cube)];
+ 			else
+ 			{
+ 				/* This is for right traversal of non-leaf elements */
+ 				retval = Min(
+ 					-(cube)->x[(-coord-1)%DIM(cube)],
+ 					-(cube)->x[(-coord-1)%DIM(cube) + DIM(cube)]
+ 				);
+ 			}
+ 	}
+ 	else
+ 	{
+ 		NDBOX *query = PG_GETARG_NDBOX(1);
+ 		switch(strategy)
+ 		{
+ 		case 17:
+ 			retval = DatumGetFloat8(DirectFunctionCall2(distance_euclid,
+ 				PointerGetDatum(cube), PointerGetDatum(query)));
+ 			break;
+ 		case 18:
+ 			retval = DatumGetFloat8(DirectFunctionCall2(distance_chebyshev,
+ 				PointerGetDatum(cube), PointerGetDatum(query)));
+ 			break;
+ 		case 16:
+ 		default:
+ 			retval = DatumGetFloat8(DirectFunctionCall2(distance_taxicab,
+ 				PointerGetDatum(cube), PointerGetDatum(query)));
+ 			break;
+ 		}
+ 	}
+ 	PG_RETURN_FLOAT8(retval);
+ }
+ 
  static double
  distance_1D(double a1, double a2, double b1, double b2)
  {
*************** cube_ur_coord(PG_FUNCTION_ARGS)
*** 1357,1362 ****
--- 1511,1552 ----
  	PG_RETURN_FLOAT8(result);
  }
  
+ /*
+  * Function returns cube coordinate.
+  * Numbers from 1 to DIM denotes Lower Left corner coordinates.
+  * Numbers from DIM+1 to 2*DIM denotes Upper Right cube corner coordinates.
+  * If negative number passed to function it is treated as it's absolut value,
+  * but resulting coordinate will be returned with changed sign. This
+  * convention useful for descending sort by this coordinate.
+  */
+ Datum
+ cube_coord(PG_FUNCTION_ARGS)
+ {
+ 	NDBOX	   *cube = PG_GETARG_NDBOX(0);
+ 	int			coord = PG_GETARG_INT16(1);
+ 
+ 	if ((coord > 0) && (coord <= 2*DIM(cube)))
+ 	{
+ 		if IS_POINT(cube)
+ 			PG_RETURN_FLOAT8( (cube)->x[(coord-1)%DIM(cube)] );
+ 		else
+ 			PG_RETURN_FLOAT8( (cube)->x[coord-1] );
+ 	}
+ 	else if (coord >= (-2*DIM(cube)) && (coord < 0))
+ 	{
+ 		if IS_POINT(cube)
+ 			PG_RETURN_FLOAT8( -(cube)->x[(-coord-1)%DIM(cube)] );
+ 		else
+ 			PG_RETURN_FLOAT8( -(cube)->x[-coord-1] );
+ 	}
+ 	else
+ 	{
+ 		ereport(ERROR,
+ 					(errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
+ 					 errmsg("Index out of bounds")));
+ 	}
+ }
+ 
  /* Increase or decrease box size by a radius in at least n dimensions. */
  Datum
  cube_enlarge(PG_FUNCTION_ARGS)
diff --git a/contrib/cube/expected/cube.out b/contrib/cube/expected/cube.out
new file mode 100644
index ca9555e..a3db4f7
*** a/contrib/cube/expected/cube.out
--- b/contrib/cube/expected/cube.out
*************** SELECT cube_size('(42,137)'::cube);
*** 1381,1386 ****
--- 1381,1490 ----
           0
  (1 row)
  
+ -- Test of distances
+ -- 
+ SELECT distance_euclid('(1,1)'::cube, '(4,5)'::cube);
+  distance_euclid 
+ -----------------
+                5
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <-> '(4,5)'::cube as d_e;
+  d_e 
+ -----
+    5
+ (1 row)
+ 
+ SELECT distance_chebyshev('(1,1)'::cube, '(4,5)'::cube);
+  distance_chebyshev 
+ --------------------
+                   4
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <=> '(4,5)'::cube as d_c;
+  d_c 
+ -----
+    4
+ (1 row)
+ 
+ SELECT distance_taxicab('(1,1)'::cube, '(4,5)'::cube);
+  distance_taxicab 
+ ------------------
+                 7
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <#> '(4,5)'::cube as d_t;
+  d_t 
+ -----
+    7
+ (1 row)
+ 
+ -- zero for overlapping
+ SELECT distance_euclid('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_euclid 
+ -----------------
+                0
+ (1 row)
+ 
+ SELECT distance_chebyshev('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_chebyshev 
+ --------------------
+                   0
+ (1 row)
+ 
+ SELECT distance_taxicab('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_taxicab 
+ ------------------
+                 0
+ (1 row)
+ 
+ -- coordinate access
+ SELECT cube(array[10,20,30], array[40,50,60])->1;
+  ?column? 
+ ----------
+        10
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->6;
+  ?column? 
+ ----------
+        60
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->0;
+ ERROR:  Index out of bounds
+ SELECT cube(array[10,20,30], array[40,50,60])->7;
+ ERROR:  Index out of bounds
+ SELECT cube(array[10,20,30], array[40,50,60])->-1;
+  ?column? 
+ ----------
+       -10
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->-6;
+  ?column? 
+ ----------
+       -60
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->3;
+  ?column? 
+ ----------
+        30
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->6;
+  ?column? 
+ ----------
+        30
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->-6;
+  ?column? 
+ ----------
+       -30
+ (1 row)
+ 
  -- Load some example data and build the index
  --
  CREATE TABLE test_cube (c cube);
*************** SELECT * FROM test_cube WHERE c && '(300
*** 1407,1409 ****
--- 1511,1709 ----
   (2424, 160),(2424, 81)
  (5 rows)
  
+ -- kNN with index
+ SELECT *, c <-> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <-> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            |       dist       
+ -------------------------+------------------
+  (337, 455),(240, 359)   |                0
+  (759, 187),(662, 163)   |              162
+  (948, 1201),(907, 1156) | 772.000647668122
+  (1444, 403),(1346, 344) |              846
+  (369, 1457),(278, 1409) |              909
+ (5 rows)
+ 
+ SELECT *, c <=> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <=> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            | dist 
+ -------------------------+------
+  (337, 455),(240, 359)   |    0
+  (759, 187),(662, 163)   |  162
+  (948, 1201),(907, 1156) |  656
+  (1444, 403),(1346, 344) |  846
+  (369, 1457),(278, 1409) |  909
+ (5 rows)
+ 
+ SELECT *, c <#> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <#> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            | dist 
+ -------------------------+------
+  (337, 455),(240, 359)   |    0
+  (759, 187),(662, 163)   |  162
+  (1444, 403),(1346, 344) |  846
+  (369, 1457),(278, 1409) |  909
+  (948, 1201),(907, 1156) | 1063
+ (5 rows)
+ 
+ -- kNN-based sorting
+ SELECT * FROM test_cube ORDER BY c->1 LIMIT 15; -- ascending by 1st coordinate
+              c             
+ ---------------------------
+  (54, 38679),(3, 38602)
+  (83, 10271),(15, 10265)
+  (122, 46832),(64, 46762)
+  (167, 17214),(92, 17184)
+  (161, 24465),(107, 24374)
+  (162, 26040),(120, 25963)
+  (154, 4019),(138, 3990)
+  (259, 1850),(175, 1820)
+  (207, 40886),(179, 40879)
+  (288, 49588),(204, 49571)
+  (270, 32616),(226, 32607)
+  (318, 31489),(235, 31404)
+  (337, 455),(240, 359)
+  (270, 29508),(264, 29440)
+  (369, 1457),(278, 1409)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->4 LIMIT 15; -- ascending by 4th coordinate
+              c             
+ ---------------------------
+  (30333, 50),(30273, 6)
+  (43301, 75),(43227, 43)
+  (19650, 142),(19630, 51)
+  (2424, 160),(2424, 81)
+  (3449, 171),(3354, 108)
+  (18037, 155),(17941, 109)
+  (28511, 208),(28479, 114)
+  (19946, 217),(19941, 118)
+  (16906, 191),(16816, 139)
+  (759, 187),(662, 163)
+  (22684, 266),(22656, 181)
+  (24423, 255),(24360, 213)
+  (45989, 249),(45910, 222)
+  (11399, 377),(11360, 294)
+  (12162, 389),(12103, 309)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->-1 LIMIT 15; -- descending by 1st coordinate
+                c               
+ -------------------------------
+  (50027, 49230),(49951, 49214)
+  (49999, 27218),(49908, 27176)
+  (49985, 6436),(49927, 6338)
+  (49981, 34876),(49898, 34786)
+  (49980, 35004),(49937, 34963)
+  (49957, 43390),(49897, 43384)
+  (49954, 1340),(49905, 1294)
+  (49944, 25163),(49902, 25153)
+  (49907, 30225),(49810, 30158)
+  (49902, 41752),(49818, 41746)
+  (49887, 24274),(49805, 24184)
+  (49853, 18504),(49848, 18503)
+  (49847, 7128),(49798, 7067)
+  (49843, 5175),(49808, 5145)
+  (49836, 35965),(49757, 35871)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->-4 LIMIT 15; -- descending by 4th coordinate
+                c               
+ -------------------------------
+  (36311, 50073),(36258, 49987)
+  (30746, 50040),(30727, 49992)
+  (2168, 50012),(2108, 49914)
+  (21551, 49983),(21492, 49885)
+  (17954, 49975),(17865, 49915)
+  (3531, 49962),(3463, 49934)
+  (19128, 49932),(19112, 49849)
+  (31287, 49923),(31236, 49913)
+  (43925, 49912),(43888, 49878)
+  (29261, 49910),(29247, 49818)
+  (14913, 49873),(14849, 49836)
+  (20007, 49858),(19921, 49778)
+  (38266, 49852),(38233, 49844)
+  (37595, 49849),(37581, 49834)
+  (46151, 49848),(46058, 49830)
+ (15 rows)
+ 
+ -- same thing for index with points
+ CREATE TABLE test_point(c cube);
+ INSERT INTO test_point(SELECT cube(array[c->1,c->2,c->3,c->4]) FROM test_cube);
+ CREATE INDEX ON test_point USING gist(c);
+ SELECT * FROM test_point ORDER BY c->1 LIMIT 15; -- ascending by 1st coordinate
+             c             
+ --------------------------
+  (54, 38679, 3, 38602)
+  (83, 10271, 15, 10265)
+  (122, 46832, 64, 46762)
+  (154, 4019, 138, 3990)
+  (161, 24465, 107, 24374)
+  (162, 26040, 120, 25963)
+  (167, 17214, 92, 17184)
+  (207, 40886, 179, 40879)
+  (259, 1850, 175, 1820)
+  (270, 32616, 226, 32607)
+  (270, 29508, 264, 29440)
+  (288, 49588, 204, 49571)
+  (318, 31489, 235, 31404)
+  (326, 18837, 285, 18817)
+  (337, 455, 240, 359)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->5 LIMIT 15; -- should be the same as previous
+             c             
+ --------------------------
+  (54, 38679, 3, 38602)
+  (83, 10271, 15, 10265)
+  (122, 46832, 64, 46762)
+  (154, 4019, 138, 3990)
+  (161, 24465, 107, 24374)
+  (162, 26040, 120, 25963)
+  (167, 17214, 92, 17184)
+  (207, 40886, 179, 40879)
+  (259, 1850, 175, 1820)
+  (270, 32616, 226, 32607)
+  (270, 29508, 264, 29440)
+  (288, 49588, 204, 49571)
+  (318, 31489, 235, 31404)
+  (326, 18837, 285, 18817)
+  (337, 455, 240, 359)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->-1 LIMIT 15; -- descending by 1st coordinate
+               c               
+ ------------------------------
+  (50027, 49230, 49951, 49214)
+  (49999, 27218, 49908, 27176)
+  (49985, 6436, 49927, 6338)
+  (49981, 34876, 49898, 34786)
+  (49980, 35004, 49937, 34963)
+  (49957, 43390, 49897, 43384)
+  (49954, 1340, 49905, 1294)
+  (49944, 25163, 49902, 25153)
+  (49907, 30225, 49810, 30158)
+  (49902, 41752, 49818, 41746)
+  (49887, 24274, 49805, 24184)
+  (49853, 18504, 49848, 18503)
+  (49847, 7128, 49798, 7067)
+  (49843, 5175, 49808, 5145)
+  (49836, 35965, 49757, 35871)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->-5 LIMIT 15; -- should be the same as previous
+               c               
+ ------------------------------
+  (50027, 49230, 49951, 49214)
+  (49999, 27218, 49908, 27176)
+  (49985, 6436, 49927, 6338)
+  (49981, 34876, 49898, 34786)
+  (49980, 35004, 49937, 34963)
+  (49957, 43390, 49897, 43384)
+  (49954, 1340, 49905, 1294)
+  (49944, 25163, 49902, 25153)
+  (49907, 30225, 49810, 30158)
+  (49902, 41752, 49818, 41746)
+  (49887, 24274, 49805, 24184)
+  (49853, 18504, 49848, 18503)
+  (49847, 7128, 49798, 7067)
+  (49843, 5175, 49808, 5145)
+  (49836, 35965, 49757, 35871)
+ (15 rows)
+ 
diff --git a/contrib/cube/expected/cube_1.out b/contrib/cube/expected/cube_1.out
new file mode 100644
index c07d61d..b7acc5e
*** a/contrib/cube/expected/cube_1.out
--- b/contrib/cube/expected/cube_1.out
*************** SELECT cube_size('(42,137)'::cube);
*** 1381,1386 ****
--- 1381,1490 ----
           0
  (1 row)
  
+ -- Test of distances
+ -- 
+ SELECT distance_euclid('(1,1)'::cube, '(4,5)'::cube);
+  distance_euclid 
+ -----------------
+                5
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <-> '(4,5)'::cube as d_e;
+  d_e 
+ -----
+    5
+ (1 row)
+ 
+ SELECT distance_chebyshev('(1,1)'::cube, '(4,5)'::cube);
+  distance_chebyshev 
+ --------------------
+                   4
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <=> '(4,5)'::cube as d_c;
+  d_c 
+ -----
+    4
+ (1 row)
+ 
+ SELECT distance_taxicab('(1,1)'::cube, '(4,5)'::cube);
+  distance_taxicab 
+ ------------------
+                 7
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <#> '(4,5)'::cube as d_t;
+  d_t 
+ -----
+    7
+ (1 row)
+ 
+ -- zero for overlapping
+ SELECT distance_euclid('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_euclid 
+ -----------------
+                0
+ (1 row)
+ 
+ SELECT distance_chebyshev('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_chebyshev 
+ --------------------
+                   0
+ (1 row)
+ 
+ SELECT distance_taxicab('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_taxicab 
+ ------------------
+                 0
+ (1 row)
+ 
+ -- coordinate access
+ SELECT cube(array[10,20,30], array[40,50,60])->1;
+  ?column? 
+ ----------
+        10
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->6;
+  ?column? 
+ ----------
+        60
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->0;
+ ERROR:  Index out of bounds
+ SELECT cube(array[10,20,30], array[40,50,60])->7;
+ ERROR:  Index out of bounds
+ SELECT cube(array[10,20,30], array[40,50,60])->-1;
+  ?column? 
+ ----------
+       -10
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->-6;
+  ?column? 
+ ----------
+       -60
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->3;
+  ?column? 
+ ----------
+        30
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->6;
+  ?column? 
+ ----------
+        30
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->-6;
+  ?column? 
+ ----------
+       -30
+ (1 row)
+ 
  -- Load some example data and build the index
  --
  CREATE TABLE test_cube (c cube);
*************** SELECT * FROM test_cube WHERE c && '(300
*** 1407,1409 ****
--- 1511,1709 ----
   (2424, 160),(2424, 81)
  (5 rows)
  
+ -- kNN with index
+ SELECT *, c <-> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <-> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            |       dist       
+ -------------------------+------------------
+  (337, 455),(240, 359)   |                0
+  (759, 187),(662, 163)   |              162
+  (948, 1201),(907, 1156) | 772.000647668122
+  (1444, 403),(1346, 344) |              846
+  (369, 1457),(278, 1409) |              909
+ (5 rows)
+ 
+ SELECT *, c <=> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <=> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            | dist 
+ -------------------------+------
+  (337, 455),(240, 359)   |    0
+  (759, 187),(662, 163)   |  162
+  (948, 1201),(907, 1156) |  656
+  (1444, 403),(1346, 344) |  846
+  (369, 1457),(278, 1409) |  909
+ (5 rows)
+ 
+ SELECT *, c <#> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <#> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            | dist 
+ -------------------------+------
+  (337, 455),(240, 359)   |    0
+  (759, 187),(662, 163)   |  162
+  (1444, 403),(1346, 344) |  846
+  (369, 1457),(278, 1409) |  909
+  (948, 1201),(907, 1156) | 1063
+ (5 rows)
+ 
+ -- kNN-based sorting
+ SELECT * FROM test_cube ORDER BY c->1 LIMIT 15; -- ascending by 1st coordinate
+              c             
+ ---------------------------
+  (54, 38679),(3, 38602)
+  (83, 10271),(15, 10265)
+  (122, 46832),(64, 46762)
+  (167, 17214),(92, 17184)
+  (161, 24465),(107, 24374)
+  (162, 26040),(120, 25963)
+  (154, 4019),(138, 3990)
+  (259, 1850),(175, 1820)
+  (207, 40886),(179, 40879)
+  (288, 49588),(204, 49571)
+  (270, 32616),(226, 32607)
+  (318, 31489),(235, 31404)
+  (337, 455),(240, 359)
+  (270, 29508),(264, 29440)
+  (369, 1457),(278, 1409)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->4 LIMIT 15; -- ascending by 4th coordinate
+              c             
+ ---------------------------
+  (30333, 50),(30273, 6)
+  (43301, 75),(43227, 43)
+  (19650, 142),(19630, 51)
+  (2424, 160),(2424, 81)
+  (3449, 171),(3354, 108)
+  (18037, 155),(17941, 109)
+  (28511, 208),(28479, 114)
+  (19946, 217),(19941, 118)
+  (16906, 191),(16816, 139)
+  (759, 187),(662, 163)
+  (22684, 266),(22656, 181)
+  (24423, 255),(24360, 213)
+  (45989, 249),(45910, 222)
+  (11399, 377),(11360, 294)
+  (12162, 389),(12103, 309)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->-1 LIMIT 15; -- descending by 1st coordinate
+                c               
+ -------------------------------
+  (50027, 49230),(49951, 49214)
+  (49999, 27218),(49908, 27176)
+  (49985, 6436),(49927, 6338)
+  (49981, 34876),(49898, 34786)
+  (49980, 35004),(49937, 34963)
+  (49957, 43390),(49897, 43384)
+  (49954, 1340),(49905, 1294)
+  (49944, 25163),(49902, 25153)
+  (49907, 30225),(49810, 30158)
+  (49902, 41752),(49818, 41746)
+  (49887, 24274),(49805, 24184)
+  (49853, 18504),(49848, 18503)
+  (49847, 7128),(49798, 7067)
+  (49843, 5175),(49808, 5145)
+  (49836, 35965),(49757, 35871)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->-4 LIMIT 15; -- descending by 4th coordinate
+                c               
+ -------------------------------
+  (36311, 50073),(36258, 49987)
+  (30746, 50040),(30727, 49992)
+  (2168, 50012),(2108, 49914)
+  (21551, 49983),(21492, 49885)
+  (17954, 49975),(17865, 49915)
+  (3531, 49962),(3463, 49934)
+  (19128, 49932),(19112, 49849)
+  (31287, 49923),(31236, 49913)
+  (43925, 49912),(43888, 49878)
+  (29261, 49910),(29247, 49818)
+  (14913, 49873),(14849, 49836)
+  (20007, 49858),(19921, 49778)
+  (38266, 49852),(38233, 49844)
+  (37595, 49849),(37581, 49834)
+  (46151, 49848),(46058, 49830)
+ (15 rows)
+ 
+ -- same thing for index with points
+ CREATE TABLE test_point(c cube);
+ INSERT INTO test_point(SELECT cube(array[c->1,c->2,c->3,c->4]) FROM test_cube);
+ CREATE INDEX ON test_point USING gist(c);
+ SELECT * FROM test_point ORDER BY c->1 LIMIT 15; -- ascending by 1st coordinate
+             c             
+ --------------------------
+  (54, 38679, 3, 38602)
+  (83, 10271, 15, 10265)
+  (122, 46832, 64, 46762)
+  (154, 4019, 138, 3990)
+  (161, 24465, 107, 24374)
+  (162, 26040, 120, 25963)
+  (167, 17214, 92, 17184)
+  (207, 40886, 179, 40879)
+  (259, 1850, 175, 1820)
+  (270, 32616, 226, 32607)
+  (270, 29508, 264, 29440)
+  (288, 49588, 204, 49571)
+  (318, 31489, 235, 31404)
+  (326, 18837, 285, 18817)
+  (337, 455, 240, 359)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->5 LIMIT 15; -- should be the same as previous
+             c             
+ --------------------------
+  (54, 38679, 3, 38602)
+  (83, 10271, 15, 10265)
+  (122, 46832, 64, 46762)
+  (154, 4019, 138, 3990)
+  (161, 24465, 107, 24374)
+  (162, 26040, 120, 25963)
+  (167, 17214, 92, 17184)
+  (207, 40886, 179, 40879)
+  (259, 1850, 175, 1820)
+  (270, 32616, 226, 32607)
+  (270, 29508, 264, 29440)
+  (288, 49588, 204, 49571)
+  (318, 31489, 235, 31404)
+  (326, 18837, 285, 18817)
+  (337, 455, 240, 359)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->-1 LIMIT 15; -- descending by 1st coordinate
+               c               
+ ------------------------------
+  (50027, 49230, 49951, 49214)
+  (49999, 27218, 49908, 27176)
+  (49985, 6436, 49927, 6338)
+  (49981, 34876, 49898, 34786)
+  (49980, 35004, 49937, 34963)
+  (49957, 43390, 49897, 43384)
+  (49954, 1340, 49905, 1294)
+  (49944, 25163, 49902, 25153)
+  (49907, 30225, 49810, 30158)
+  (49902, 41752, 49818, 41746)
+  (49887, 24274, 49805, 24184)
+  (49853, 18504, 49848, 18503)
+  (49847, 7128, 49798, 7067)
+  (49843, 5175, 49808, 5145)
+  (49836, 35965, 49757, 35871)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->-5 LIMIT 15; -- should be the same as previous
+               c               
+ ------------------------------
+  (50027, 49230, 49951, 49214)
+  (49999, 27218, 49908, 27176)
+  (49985, 6436, 49927, 6338)
+  (49981, 34876, 49898, 34786)
+  (49980, 35004, 49937, 34963)
+  (49957, 43390, 49897, 43384)
+  (49954, 1340, 49905, 1294)
+  (49944, 25163, 49902, 25153)
+  (49907, 30225, 49810, 30158)
+  (49902, 41752, 49818, 41746)
+  (49887, 24274, 49805, 24184)
+  (49853, 18504, 49848, 18503)
+  (49847, 7128, 49798, 7067)
+  (49843, 5175, 49808, 5145)
+  (49836, 35965, 49757, 35871)
+ (15 rows)
+ 
diff --git a/contrib/cube/expected/cube_2.out b/contrib/cube/expected/cube_2.out
new file mode 100644
index 3767d0e..964dc6b
*** a/contrib/cube/expected/cube_2.out
--- b/contrib/cube/expected/cube_2.out
*************** SELECT cube_size('(42,137)'::cube);
*** 1381,1386 ****
--- 1381,1490 ----
           0
  (1 row)
  
+ -- Test of distances
+ -- 
+ SELECT distance_euclid('(1,1)'::cube, '(4,5)'::cube);
+  distance_euclid 
+ -----------------
+                5
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <-> '(4,5)'::cube as d_e;
+  d_e 
+ -----
+    5
+ (1 row)
+ 
+ SELECT distance_chebyshev('(1,1)'::cube, '(4,5)'::cube);
+  distance_chebyshev 
+ --------------------
+                   4
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <=> '(4,5)'::cube as d_c;
+  d_c 
+ -----
+    4
+ (1 row)
+ 
+ SELECT distance_taxicab('(1,1)'::cube, '(4,5)'::cube);
+  distance_taxicab 
+ ------------------
+                 7
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <#> '(4,5)'::cube as d_t;
+  d_t 
+ -----
+    7
+ (1 row)
+ 
+ -- zero for overlapping
+ SELECT distance_euclid('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_euclid 
+ -----------------
+                0
+ (1 row)
+ 
+ SELECT distance_chebyshev('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_chebyshev 
+ --------------------
+                   0
+ (1 row)
+ 
+ SELECT distance_taxicab('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_taxicab 
+ ------------------
+                 0
+ (1 row)
+ 
+ -- coordinate access
+ SELECT cube(array[10,20,30], array[40,50,60])->1;
+  ?column? 
+ ----------
+        10
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->6;
+  ?column? 
+ ----------
+        60
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->0;
+ ERROR:  Index out of bounds
+ SELECT cube(array[10,20,30], array[40,50,60])->7;
+ ERROR:  Index out of bounds
+ SELECT cube(array[10,20,30], array[40,50,60])->-1;
+  ?column? 
+ ----------
+       -10
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->-6;
+  ?column? 
+ ----------
+       -60
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->3;
+  ?column? 
+ ----------
+        30
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->6;
+  ?column? 
+ ----------
+        30
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->-6;
+  ?column? 
+ ----------
+       -30
+ (1 row)
+ 
  -- Load some example data and build the index
  --
  CREATE TABLE test_cube (c cube);
*************** SELECT * FROM test_cube WHERE c && '(300
*** 1407,1409 ****
--- 1511,1709 ----
   (2424, 160),(2424, 81)
  (5 rows)
  
+ -- kNN with index
+ SELECT *, c <-> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <-> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            |       dist       
+ -------------------------+------------------
+  (337, 455),(240, 359)   |                0
+  (759, 187),(662, 163)   |              162
+  (948, 1201),(907, 1156) | 772.000647668122
+  (1444, 403),(1346, 344) |              846
+  (369, 1457),(278, 1409) |              909
+ (5 rows)
+ 
+ SELECT *, c <=> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <=> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            | dist 
+ -------------------------+------
+  (337, 455),(240, 359)   |    0
+  (759, 187),(662, 163)   |  162
+  (948, 1201),(907, 1156) |  656
+  (1444, 403),(1346, 344) |  846
+  (369, 1457),(278, 1409) |  909
+ (5 rows)
+ 
+ SELECT *, c <#> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <#> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            | dist 
+ -------------------------+------
+  (337, 455),(240, 359)   |    0
+  (759, 187),(662, 163)   |  162
+  (1444, 403),(1346, 344) |  846
+  (369, 1457),(278, 1409) |  909
+  (948, 1201),(907, 1156) | 1063
+ (5 rows)
+ 
+ -- kNN-based sorting
+ SELECT * FROM test_cube ORDER BY c->1 LIMIT 15; -- ascending by 1st coordinate
+              c             
+ ---------------------------
+  (54, 38679),(3, 38602)
+  (83, 10271),(15, 10265)
+  (122, 46832),(64, 46762)
+  (167, 17214),(92, 17184)
+  (161, 24465),(107, 24374)
+  (162, 26040),(120, 25963)
+  (154, 4019),(138, 3990)
+  (259, 1850),(175, 1820)
+  (207, 40886),(179, 40879)
+  (288, 49588),(204, 49571)
+  (270, 32616),(226, 32607)
+  (318, 31489),(235, 31404)
+  (337, 455),(240, 359)
+  (270, 29508),(264, 29440)
+  (369, 1457),(278, 1409)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->4 LIMIT 15; -- ascending by 4th coordinate
+              c             
+ ---------------------------
+  (30333, 50),(30273, 6)
+  (43301, 75),(43227, 43)
+  (19650, 142),(19630, 51)
+  (2424, 160),(2424, 81)
+  (3449, 171),(3354, 108)
+  (18037, 155),(17941, 109)
+  (28511, 208),(28479, 114)
+  (19946, 217),(19941, 118)
+  (16906, 191),(16816, 139)
+  (759, 187),(662, 163)
+  (22684, 266),(22656, 181)
+  (24423, 255),(24360, 213)
+  (45989, 249),(45910, 222)
+  (11399, 377),(11360, 294)
+  (12162, 389),(12103, 309)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->-1 LIMIT 15; -- descending by 1st coordinate
+                c               
+ -------------------------------
+  (50027, 49230),(49951, 49214)
+  (49999, 27218),(49908, 27176)
+  (49985, 6436),(49927, 6338)
+  (49981, 34876),(49898, 34786)
+  (49980, 35004),(49937, 34963)
+  (49957, 43390),(49897, 43384)
+  (49954, 1340),(49905, 1294)
+  (49944, 25163),(49902, 25153)
+  (49907, 30225),(49810, 30158)
+  (49902, 41752),(49818, 41746)
+  (49887, 24274),(49805, 24184)
+  (49853, 18504),(49848, 18503)
+  (49847, 7128),(49798, 7067)
+  (49843, 5175),(49808, 5145)
+  (49836, 35965),(49757, 35871)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->-4 LIMIT 15; -- descending by 4th coordinate
+                c               
+ -------------------------------
+  (36311, 50073),(36258, 49987)
+  (30746, 50040),(30727, 49992)
+  (2168, 50012),(2108, 49914)
+  (21551, 49983),(21492, 49885)
+  (17954, 49975),(17865, 49915)
+  (3531, 49962),(3463, 49934)
+  (19128, 49932),(19112, 49849)
+  (31287, 49923),(31236, 49913)
+  (43925, 49912),(43888, 49878)
+  (29261, 49910),(29247, 49818)
+  (14913, 49873),(14849, 49836)
+  (20007, 49858),(19921, 49778)
+  (38266, 49852),(38233, 49844)
+  (37595, 49849),(37581, 49834)
+  (46151, 49848),(46058, 49830)
+ (15 rows)
+ 
+ -- same thing for index with points
+ CREATE TABLE test_point(c cube);
+ INSERT INTO test_point(SELECT cube(array[c->1,c->2,c->3,c->4]) FROM test_cube);
+ CREATE INDEX ON test_point USING gist(c);
+ SELECT * FROM test_point ORDER BY c->1 LIMIT 15; -- ascending by 1st coordinate
+             c             
+ --------------------------
+  (54, 38679, 3, 38602)
+  (83, 10271, 15, 10265)
+  (122, 46832, 64, 46762)
+  (154, 4019, 138, 3990)
+  (161, 24465, 107, 24374)
+  (162, 26040, 120, 25963)
+  (167, 17214, 92, 17184)
+  (207, 40886, 179, 40879)
+  (259, 1850, 175, 1820)
+  (270, 32616, 226, 32607)
+  (270, 29508, 264, 29440)
+  (288, 49588, 204, 49571)
+  (318, 31489, 235, 31404)
+  (326, 18837, 285, 18817)
+  (337, 455, 240, 359)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->5 LIMIT 15; -- should be the same as previous
+             c             
+ --------------------------
+  (54, 38679, 3, 38602)
+  (83, 10271, 15, 10265)
+  (122, 46832, 64, 46762)
+  (154, 4019, 138, 3990)
+  (161, 24465, 107, 24374)
+  (162, 26040, 120, 25963)
+  (167, 17214, 92, 17184)
+  (207, 40886, 179, 40879)
+  (259, 1850, 175, 1820)
+  (270, 32616, 226, 32607)
+  (270, 29508, 264, 29440)
+  (288, 49588, 204, 49571)
+  (318, 31489, 235, 31404)
+  (326, 18837, 285, 18817)
+  (337, 455, 240, 359)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->-1 LIMIT 15; -- descending by 1st coordinate
+               c               
+ ------------------------------
+  (50027, 49230, 49951, 49214)
+  (49999, 27218, 49908, 27176)
+  (49985, 6436, 49927, 6338)
+  (49981, 34876, 49898, 34786)
+  (49980, 35004, 49937, 34963)
+  (49957, 43390, 49897, 43384)
+  (49954, 1340, 49905, 1294)
+  (49944, 25163, 49902, 25153)
+  (49907, 30225, 49810, 30158)
+  (49902, 41752, 49818, 41746)
+  (49887, 24274, 49805, 24184)
+  (49853, 18504, 49848, 18503)
+  (49847, 7128, 49798, 7067)
+  (49843, 5175, 49808, 5145)
+  (49836, 35965, 49757, 35871)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->-5 LIMIT 15; -- should be the same as previous
+               c               
+ ------------------------------
+  (50027, 49230, 49951, 49214)
+  (49999, 27218, 49908, 27176)
+  (49985, 6436, 49927, 6338)
+  (49981, 34876, 49898, 34786)
+  (49980, 35004, 49937, 34963)
+  (49957, 43390, 49897, 43384)
+  (49954, 1340, 49905, 1294)
+  (49944, 25163, 49902, 25153)
+  (49907, 30225, 49810, 30158)
+  (49902, 41752, 49818, 41746)
+  (49887, 24274, 49805, 24184)
+  (49853, 18504, 49848, 18503)
+  (49847, 7128, 49798, 7067)
+  (49843, 5175, 49808, 5145)
+  (49836, 35965, 49757, 35871)
+ (15 rows)
+ 
diff --git a/contrib/cube/expected/cube_3.out b/contrib/cube/expected/cube_3.out
new file mode 100644
index 2aa42be..7868514
*** a/contrib/cube/expected/cube_3.out
--- b/contrib/cube/expected/cube_3.out
*************** SELECT cube_size('(42,137)'::cube);
*** 1381,1386 ****
--- 1381,1490 ----
           0
  (1 row)
  
+ -- Test of distances
+ -- 
+ SELECT distance_euclid('(1,1)'::cube, '(4,5)'::cube);
+  distance_euclid 
+ -----------------
+                5
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <-> '(4,5)'::cube as d_e;
+  d_e 
+ -----
+    5
+ (1 row)
+ 
+ SELECT distance_chebyshev('(1,1)'::cube, '(4,5)'::cube);
+  distance_chebyshev 
+ --------------------
+                   4
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <=> '(4,5)'::cube as d_c;
+  d_c 
+ -----
+    4
+ (1 row)
+ 
+ SELECT distance_taxicab('(1,1)'::cube, '(4,5)'::cube);
+  distance_taxicab 
+ ------------------
+                 7
+ (1 row)
+ 
+ SELECT '(1,1)'::cube <#> '(4,5)'::cube as d_t;
+  d_t 
+ -----
+    7
+ (1 row)
+ 
+ -- zero for overlapping
+ SELECT distance_euclid('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_euclid 
+ -----------------
+                0
+ (1 row)
+ 
+ SELECT distance_chebyshev('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_chebyshev 
+ --------------------
+                   0
+ (1 row)
+ 
+ SELECT distance_taxicab('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+  distance_taxicab 
+ ------------------
+                 0
+ (1 row)
+ 
+ -- coordinate access
+ SELECT cube(array[10,20,30], array[40,50,60])->1;
+  ?column? 
+ ----------
+        10
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->6;
+  ?column? 
+ ----------
+        60
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->0;
+ ERROR:  Index out of bounds
+ SELECT cube(array[10,20,30], array[40,50,60])->7;
+ ERROR:  Index out of bounds
+ SELECT cube(array[10,20,30], array[40,50,60])->-1;
+  ?column? 
+ ----------
+       -10
+ (1 row)
+ 
+ SELECT cube(array[10,20,30], array[40,50,60])->-6;
+  ?column? 
+ ----------
+       -60
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->3;
+  ?column? 
+ ----------
+        30
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->6;
+  ?column? 
+ ----------
+        30
+ (1 row)
+ 
+ SELECT cube(array[10,20,30])->-6;
+  ?column? 
+ ----------
+       -30
+ (1 row)
+ 
  -- Load some example data and build the index
  --
  CREATE TABLE test_cube (c cube);
*************** SELECT * FROM test_cube WHERE c && '(300
*** 1407,1409 ****
--- 1511,1709 ----
   (2424, 160),(2424, 81)
  (5 rows)
  
+ -- kNN with index
+ SELECT *, c <-> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <-> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            |       dist       
+ -------------------------+------------------
+  (337, 455),(240, 359)   |                0
+  (759, 187),(662, 163)   |              162
+  (948, 1201),(907, 1156) | 772.000647668122
+  (1444, 403),(1346, 344) |              846
+  (369, 1457),(278, 1409) |              909
+ (5 rows)
+ 
+ SELECT *, c <=> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <=> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            | dist 
+ -------------------------+------
+  (337, 455),(240, 359)   |    0
+  (759, 187),(662, 163)   |  162
+  (948, 1201),(907, 1156) |  656
+  (1444, 403),(1346, 344) |  846
+  (369, 1457),(278, 1409) |  909
+ (5 rows)
+ 
+ SELECT *, c <#> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <#> '(100, 100),(500, 500)'::cube LIMIT 5;
+             c            | dist 
+ -------------------------+------
+  (337, 455),(240, 359)   |    0
+  (759, 187),(662, 163)   |  162
+  (1444, 403),(1346, 344) |  846
+  (369, 1457),(278, 1409) |  909
+  (948, 1201),(907, 1156) | 1063
+ (5 rows)
+ 
+ -- kNN-based sorting
+ SELECT * FROM test_cube ORDER BY c->1 LIMIT 15; -- ascending by 1st coordinate
+              c             
+ ---------------------------
+  (54, 38679),(3, 38602)
+  (83, 10271),(15, 10265)
+  (122, 46832),(64, 46762)
+  (167, 17214),(92, 17184)
+  (161, 24465),(107, 24374)
+  (162, 26040),(120, 25963)
+  (154, 4019),(138, 3990)
+  (259, 1850),(175, 1820)
+  (207, 40886),(179, 40879)
+  (288, 49588),(204, 49571)
+  (270, 32616),(226, 32607)
+  (318, 31489),(235, 31404)
+  (337, 455),(240, 359)
+  (270, 29508),(264, 29440)
+  (369, 1457),(278, 1409)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->4 LIMIT 15; -- ascending by 4th coordinate
+              c             
+ ---------------------------
+  (30333, 50),(30273, 6)
+  (43301, 75),(43227, 43)
+  (19650, 142),(19630, 51)
+  (2424, 160),(2424, 81)
+  (3449, 171),(3354, 108)
+  (18037, 155),(17941, 109)
+  (28511, 208),(28479, 114)
+  (19946, 217),(19941, 118)
+  (16906, 191),(16816, 139)
+  (759, 187),(662, 163)
+  (22684, 266),(22656, 181)
+  (24423, 255),(24360, 213)
+  (45989, 249),(45910, 222)
+  (11399, 377),(11360, 294)
+  (12162, 389),(12103, 309)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->-1 LIMIT 15; -- descending by 1st coordinate
+                c               
+ -------------------------------
+  (50027, 49230),(49951, 49214)
+  (49999, 27218),(49908, 27176)
+  (49985, 6436),(49927, 6338)
+  (49981, 34876),(49898, 34786)
+  (49980, 35004),(49937, 34963)
+  (49957, 43390),(49897, 43384)
+  (49954, 1340),(49905, 1294)
+  (49944, 25163),(49902, 25153)
+  (49907, 30225),(49810, 30158)
+  (49902, 41752),(49818, 41746)
+  (49887, 24274),(49805, 24184)
+  (49853, 18504),(49848, 18503)
+  (49847, 7128),(49798, 7067)
+  (49843, 5175),(49808, 5145)
+  (49836, 35965),(49757, 35871)
+ (15 rows)
+ 
+ SELECT * FROM test_cube ORDER BY c->-4 LIMIT 15; -- descending by 4th coordinate
+                c               
+ -------------------------------
+  (36311, 50073),(36258, 49987)
+  (30746, 50040),(30727, 49992)
+  (2168, 50012),(2108, 49914)
+  (21551, 49983),(21492, 49885)
+  (17954, 49975),(17865, 49915)
+  (3531, 49962),(3463, 49934)
+  (19128, 49932),(19112, 49849)
+  (31287, 49923),(31236, 49913)
+  (43925, 49912),(43888, 49878)
+  (29261, 49910),(29247, 49818)
+  (14913, 49873),(14849, 49836)
+  (20007, 49858),(19921, 49778)
+  (38266, 49852),(38233, 49844)
+  (37595, 49849),(37581, 49834)
+  (46151, 49848),(46058, 49830)
+ (15 rows)
+ 
+ -- same thing for index with points
+ CREATE TABLE test_point(c cube);
+ INSERT INTO test_point(SELECT cube(array[c->1,c->2,c->3,c->4]) FROM test_cube);
+ CREATE INDEX ON test_point USING gist(c);
+ SELECT * FROM test_point ORDER BY c->1 LIMIT 15; -- ascending by 1st coordinate
+             c             
+ --------------------------
+  (54, 38679, 3, 38602)
+  (83, 10271, 15, 10265)
+  (122, 46832, 64, 46762)
+  (154, 4019, 138, 3990)
+  (161, 24465, 107, 24374)
+  (162, 26040, 120, 25963)
+  (167, 17214, 92, 17184)
+  (207, 40886, 179, 40879)
+  (259, 1850, 175, 1820)
+  (270, 32616, 226, 32607)
+  (270, 29508, 264, 29440)
+  (288, 49588, 204, 49571)
+  (318, 31489, 235, 31404)
+  (326, 18837, 285, 18817)
+  (337, 455, 240, 359)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->5 LIMIT 15; -- should be the same as previous
+             c             
+ --------------------------
+  (54, 38679, 3, 38602)
+  (83, 10271, 15, 10265)
+  (122, 46832, 64, 46762)
+  (154, 4019, 138, 3990)
+  (161, 24465, 107, 24374)
+  (162, 26040, 120, 25963)
+  (167, 17214, 92, 17184)
+  (207, 40886, 179, 40879)
+  (259, 1850, 175, 1820)
+  (270, 32616, 226, 32607)
+  (270, 29508, 264, 29440)
+  (288, 49588, 204, 49571)
+  (318, 31489, 235, 31404)
+  (326, 18837, 285, 18817)
+  (337, 455, 240, 359)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->-1 LIMIT 15; -- descending by 1st coordinate
+               c               
+ ------------------------------
+  (50027, 49230, 49951, 49214)
+  (49999, 27218, 49908, 27176)
+  (49985, 6436, 49927, 6338)
+  (49981, 34876, 49898, 34786)
+  (49980, 35004, 49937, 34963)
+  (49957, 43390, 49897, 43384)
+  (49954, 1340, 49905, 1294)
+  (49944, 25163, 49902, 25153)
+  (49907, 30225, 49810, 30158)
+  (49902, 41752, 49818, 41746)
+  (49887, 24274, 49805, 24184)
+  (49853, 18504, 49848, 18503)
+  (49847, 7128, 49798, 7067)
+  (49843, 5175, 49808, 5145)
+  (49836, 35965, 49757, 35871)
+ (15 rows)
+ 
+ SELECT * FROM test_point ORDER BY c->-5 LIMIT 15; -- should be the same as previous
+               c               
+ ------------------------------
+  (50027, 49230, 49951, 49214)
+  (49999, 27218, 49908, 27176)
+  (49985, 6436, 49927, 6338)
+  (49981, 34876, 49898, 34786)
+  (49980, 35004, 49937, 34963)
+  (49957, 43390, 49897, 43384)
+  (49954, 1340, 49905, 1294)
+  (49944, 25163, 49902, 25153)
+  (49907, 30225, 49810, 30158)
+  (49902, 41752, 49818, 41746)
+  (49887, 24274, 49805, 24184)
+  (49853, 18504, 49848, 18503)
+  (49847, 7128, 49798, 7067)
+  (49843, 5175, 49808, 5145)
+  (49836, 35965, 49757, 35871)
+ (15 rows)
+ 
diff --git a/contrib/cube/sql/cube.sql b/contrib/cube/sql/cube.sql
new file mode 100644
index d58974c..d914f72
*** a/contrib/cube/sql/cube.sql
--- b/contrib/cube/sql/cube.sql
*************** SELECT cube_inter('(1,2,3)'::cube, '(5,6
*** 325,330 ****
--- 325,353 ----
  SELECT cube_size('(4,8),(15,16)'::cube);
  SELECT cube_size('(42,137)'::cube);
  
+ -- Test of distances
+ -- 
+ SELECT distance_euclid('(1,1)'::cube, '(4,5)'::cube);
+ SELECT '(1,1)'::cube <-> '(4,5)'::cube as d_e;
+ SELECT distance_chebyshev('(1,1)'::cube, '(4,5)'::cube);
+ SELECT '(1,1)'::cube <=> '(4,5)'::cube as d_c;
+ SELECT distance_taxicab('(1,1)'::cube, '(4,5)'::cube);
+ SELECT '(1,1)'::cube <#> '(4,5)'::cube as d_t;
+ -- zero for overlapping
+ SELECT distance_euclid('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+ SELECT distance_chebyshev('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+ SELECT distance_taxicab('(2,2),(10,10)'::cube, '(0,0),(5,5)'::cube);
+ -- coordinate access
+ SELECT cube(array[10,20,30], array[40,50,60])->1;
+ SELECT cube(array[10,20,30], array[40,50,60])->6;
+ SELECT cube(array[10,20,30], array[40,50,60])->0;
+ SELECT cube(array[10,20,30], array[40,50,60])->7;
+ SELECT cube(array[10,20,30], array[40,50,60])->-1;
+ SELECT cube(array[10,20,30], array[40,50,60])->-6;
+ SELECT cube(array[10,20,30])->3;
+ SELECT cube(array[10,20,30])->6;
+ SELECT cube(array[10,20,30])->-6;
+ 
  -- Load some example data and build the index
  --
  CREATE TABLE test_cube (c cube);
*************** SELECT * FROM test_cube WHERE c && '(300
*** 336,338 ****
--- 359,382 ----
  
  -- Test sorting
  SELECT * FROM test_cube WHERE c && '(3000,1000),(0,0)' GROUP BY c ORDER BY c;
+ 
+ -- kNN with index
+ SELECT *, c <-> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <-> '(100, 100),(500, 500)'::cube LIMIT 5;
+ SELECT *, c <=> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <=> '(100, 100),(500, 500)'::cube LIMIT 5;
+ SELECT *, c <#> '(100, 100),(500, 500)'::cube as dist FROM test_cube ORDER BY c <#> '(100, 100),(500, 500)'::cube LIMIT 5;
+ 
+ -- kNN-based sorting
+ SELECT * FROM test_cube ORDER BY c->1 LIMIT 15; -- ascending by 1st coordinate
+ SELECT * FROM test_cube ORDER BY c->4 LIMIT 15; -- ascending by 4th coordinate
+ SELECT * FROM test_cube ORDER BY c->-1 LIMIT 15; -- descending by 1st coordinate
+ SELECT * FROM test_cube ORDER BY c->-4 LIMIT 15; -- descending by 4th coordinate
+ 
+ -- same thing for index with points
+ CREATE TABLE test_point(c cube);
+ INSERT INTO test_point(SELECT cube(array[c->1,c->2,c->3,c->4]) FROM test_cube);
+ CREATE INDEX ON test_point USING gist(c);
+ SELECT * FROM test_point ORDER BY c->1 LIMIT 15; -- ascending by 1st coordinate
+ SELECT * FROM test_point ORDER BY c->5 LIMIT 15; -- should be the same as previous
+ SELECT * FROM test_point ORDER BY c->-1 LIMIT 15; -- descending by 1st coordinate
+ SELECT * FROM test_point ORDER BY c->-5 LIMIT 15; -- should be the same as previous
+ 
diff --git a/doc/src/sgml/cube.sgml b/doc/src/sgml/cube.sgml
new file mode 100644
index e2da685..800fd90
*** a/doc/src/sgml/cube.sgml
--- b/doc/src/sgml/cube.sgml
***************
*** 74,80 ****
     It does not matter which order the opposite corners of a cube are
     entered in.  The <type>cube</> functions
     automatically swap values if needed to create a uniform
!    <quote>lower left &mdash; upper right</> internal representation.
    </para>
  
    <para>
--- 74,80 ----
     It does not matter which order the opposite corners of a cube are
     entered in.  The <type>cube</> functions
     automatically swap values if needed to create a uniform
!    <quote>lower left &mdash; upper right</> internal representation. When corners coincide cube stores only one corner along with a special flag in order to reduce size wasted.
    </para>
  
    <para>
***************
*** 144,149 ****
--- 144,227 ----
    </para>
  
    <para>
+    GiST index can be used to retrieve nearest neighbours via several metric operators. As always any of them can be used as ordinary function.
+   </para>
+ 
+   <table id="cube-gistknn-operators">
+    <title>Cube GiST-kNN Operators</title>
+    <tgroup cols="2">
+     <thead>
+      <row>
+       <entry>Operator</entry>
+       <entry>Description</entry>
+      </row>
+     </thead>
+     <tbody>
+      <row>
+       <entry><literal>a &lt;-&gt; b</></entry>
+       <entry>Euclidean distance between a and b</entry>
+      </row>
+ 
+      <row>
+       <entry><literal>a &lt;#&gt; b</></entry>
+       <entry>Taxicab (L-1 metric) distance between a and b</entry>
+      </row>
+ 
+      <row>
+       <entry><literal>a &lt;=&gt; b</></entry>
+       <entry>Chebyshev (L-inf metric) distance between a and b</entry>
+      </row>
+     </tbody>
+    </tgroup>
+   </table>
+ 
+   <para>
+    Selection of nearing neigbours can be done in the following way:
+   </para>
+ <programlisting>
+ SELECT c FROM test 
+ ORDER BY cube(array[0.5,0.5,0.5])<->c 
+ LIMIT 1;
+ </programlisting>
+ 
+ 
+   <para>
+    Also kNN framework allows us to cheat with metrics in order to get results sorted by selected coodinate directly from the index without extra sorting step. That technique significantly faster on small values of LIMIT, however with bigger values of LIMIT planner will switch automatically to standart index scan and sort.
+    That behavior can be achieved using special coordinate operator (cube c)-&gt;(int offset), that returns cube coordinate when offset is positive and -1*coordinate when offset is negative.
+   </para>
+ <programlisting>
+ => select cube(array[0.41,0.42,0.43])->2 as coord;
+  coord 
+ -------
+   0.42
+ (1 row)
+ 
+ => select cube(array[0.41,0.42,0.43])->-2 as coord;
+  coord 
+ -------
+  -0.42
+ (1 row)
+ </programlisting>
+ 
+   <para>
+    So using that operator as kNN metric we can obtain cubes sorted by it's coordinate.
+   </para>
+   <para>
+    To get cubes ordered by first coordinate ascending one can use the following query:
+   </para>
+ <programlisting>
+ SELECT c FROM test ORDER BY c->1 LIMIT 5;
+ </programlisting>
+   <para>
+    And to get cubes descending by third coordinate:
+   </para>
+ <programlisting>
+ SELECT c FROM test ORDER BY c->-3 LIMIT 5;
+ </programlisting>
+ 
+ 
+ 
+   <para>
     The standard B-tree operators are also provided, for example
  
     <informaltable>