/* ----------------------------------------------------------------------- *//**
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 *
 *//* ----------------------------------------------------------------------- */


DROP TABLE IF EXISTS vertex,"EDGE",edge_grp;

CREATE TABLE vertex(
                  id INTEGER
                );
INSERT INTO vertex VALUES
(0),
(1),
(2),
(3),
(4),
(5),
(6),
(7),
(8),
(9),
(10),
(11)
;

CREATE TABLE "EDGE"(
                  "SRC" INTEGER,
                  dest INTEGER,
                  weight DOUBLE PRECISION
                );
INSERT INTO "EDGE" VALUES
(0, 5, 1),
(1, 0, 1),
(1, 3, 1),
(2, 6, 1),
(3, 4, 1),
(3, 5, 1),
(4, 2, 1),
(8, 9, 1),
(9, 10, 1),
(9, 11, 1),
(10, 8, 1)
;

CREATE TABLE edge_grp(
                  g1 INTEGER,
                  g2 TEXT,
                  "SRC" INTEGER,
                  dest INTEGER,
                  weight DOUBLE PRECISION
                );
INSERT INTO edge_grp VALUES
(100, 'a', 0, 5, 1),
(100, 'a', 1, 0, 1),
(100, 'a', 1, 3, 1),
(100, 'a', 2, 6, 1),
(100, 'a', 3, 4, 1),
(100, 'a', 3, 5, 1),
(100, 'a', 4, 2, 1),
(100, 'a', 8, 9, 1),
(100, 'a', 9, 10, 1),
(100, 'a', 9, 11, 1),
(100, 'a', 10, 8, 1),
(100, 'b', 0, 5, 1),
(100, 'b', 1, 0, 1),
(100, 'b', 1, 3, 1),
(100, 'b', 2, 6, 1),
(100, 'b', 3, 4, 1),
(100, 'b', 3, 5, 1),
(100, 'b', 4, 2, 1),
(100, 'b', 8, 9, 1),
(100, 'b', 9, 10, 1),
(100, 'b', 9, 11, 1),
(100, 'b', 10, 8, 1),
(202, 'c', 8, 9, 1),
(202, 'c', 9, 10, 1),
(202, 'c', 9, 11, 1),
(202, 'c', 10, 8, 1),
(NULL, 'b', 8, 9, 1),
(NULL, 'b', 9, 10, 1),
(NULL, 'b', 9, 11, 1),
(NULL, 'b', 10, 8, 1);

---------------------
-- Undirected Graph
---------------------
-- Results to check against - uncomment if needed
-- -- source_vertex = 3
-- DROP TABLE IF EXISTS out_actual;
-- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT);
-- INSERT INTO out_actual VALUES
-- (3,3,0,NULL),
-- (3,1,1,3),
-- (3,4,1,3),
-- (3,5,1,3),
-- (3,0,2,1),
-- (3,2,2,4),
-- (3,6,3,2)
-- ;
-- -- source_vertex = 7
-- DROP TABLE IF EXISTS out_actual;
-- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT);
--
-- -- source_vertex = 8
-- DROP TABLE IF EXISTS out_actual;
-- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT);
-- INSERT INTO out_actual VALUES
-- (8,8,0,NULL),
-- (8,9,1,8),
-- (8,10,1,8),
-- (8,11,2,9)
-- ;

-- Undirected graph
-- source_vertex = 3
DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary;
SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',3,'out_frombfs');

SELECT assert(
	(array_agg(id ORDER BY id) = ARRAY[1,4,5]::INT[])
	AND
	(array_agg(parent ORDER BY id) = ARRAY[3,3,3]::INT[]),
	'Wrong output in graph (BFS)')
	FROM out_frombfs WHERE dist = 1 GROUP BY dist;

SELECT assert(max(dist) = 3, 'Wrong output in graph (BFS)')
	FROM out_frombfs;

-- source_vertex = 7
DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary;
SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',7,'out_frombfs');

SELECT assert(COUNT(*) = 0, 'Wrong output in graph (BFS)') FROM out_frombfs;

-- source_vertex = 8
DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary;
SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',8,'out_frombfs',NULL,FALSE,NULL);

SELECT assert(parent = 8, 'Wrong output in graph (BFS)')
	FROM out_frombfs WHERE dist = 2 AND id = 10;

-------------------
-- Directed graph
-------------------
-- Results to check against - uncomment if needed

-- -- source_vertex = 3
-- DROP TABLE IF EXISTS out_actual;
-- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT);
-- INSERT INTO out_actual VALUES
-- (3,3,0,NULL),
-- (3,4,1,3),
-- (3,5,1,3),
-- (3,2,2,4),
-- (3,6,3,2)
-- ;
-- -- source_vertex = 7
-- DROP TABLE IF EXISTS out_actual;
-- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT);
-- -- source_vertex = 8
-- DROP TABLE IF EXISTS out_actual;
-- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT);
-- (8, 8, 0, NULL),
-- (8, 9, 1, 8),
-- (8, 10, 2, 9),
-- (8, 11, 2, 9)
-- ;

-- source_vertex = 3
DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary;
SELECT graph_bfs('vertex','id','"EDGE"','src="SRC",dest',3,'out_frombfs',NULL,TRUE,NULL);

SELECT assert(
	(array_agg(id ORDER BY id) = ARRAY[4,5]::INT[])
	AND
	(array_agg(parent ORDER BY id) = ARRAY[3,3]::INT[]),
	'Wrong output in graph (BFS)')
	FROM out_frombfs WHERE dist = 1 GROUP BY dist;
SELECT assert(COUNT(*) = 5, 'Wrong output in graph (BFS)') FROM out_frombfs;

-- source_vertex = 7
DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary;
SELECT graph_bfs('vertex','id','"EDGE"','src="SRC",dest',7,'out_frombfs',NULL,TRUE,NULL);

SELECT assert(COUNT(*) = 0, 'Wrong output in graph (BFS)') FROM out_frombfs;

-- source_vertex = 8
DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary;
SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',8,'out_frombfs',NULL,TRUE);

SELECT assert(COUNT(*) = 2, 'Wrong output in graph (BFS)')
	FROM out_frombfs WHERE dist = 2;

-----------------------
-- max_distance check
-----------------------
-- source_vertex = 3
-- Undirected graph
DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary;
SELECT graph_bfs('vertex','id','"EDGE"','src="SRC",dest',3,'out_frombfs',2,FALSE);

SELECT assert(MAX(dist) = 2 AND COUNT(*) = 6,
	'Wrong output in graph (BFS)') FROM out_frombfs;

-- Directed graph
DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary;
SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',3,'out_frombfs',2,TRUE);

SELECT assert(MAX(dist) = 2 AND COUNT(*) = 4,
	'Wrong output in graph (BFS)') FROM out_frombfs;

---------------------
-- Grouping columns
---------------------
-- -- source_vertex = 3
-- -- Undirected graph
-- DROP TABLE IF EXISTS out_actual;
-- CREATE TABLE out_actual ("SRC" INT, id INT, dist INT, parent INT);
-- INSERT INTO out_actual VALUES
-- (3,100,'a',3,0,NULL),
-- (3,100,'a',1,1,3),
-- (3,100,'a',4,1,3),
-- (3,100,'a',5,1,3),
-- (3,100,'a',0,2,1),
-- (3,100,'a',2,2,4),
-- (3,100,'a',6,3,2),
-- (3,100,'b',3,0,NULL),
-- (3,100,'b',1,1,3),
-- (3,100,'b',4,1,3),
-- (3,100,'b',5,1,3),
-- (3,100,'b',0,2,1),
-- (3,100,'b',2,2,4),
-- (3,100,'b',6,3,2)
-- ;

DROP TABLE IF EXISTS out_frombfs, out_frombfs_summary;
SELECT graph_bfs('vertex',NULL,'edge_grp','src="SRC"',3,'out_frombfs',NULL,NULL,'g1,g2');

SELECT assert( COUNT(*) = 14,'Wrong output in graph (BFS)') FROM out_frombfs;
SELECT assert(COUNT(*) = 7,
	'Wrong output in graph (BFS)') FROM out_frombfs WHERE g2 = 'a'
;
SELECT assert(
	array_agg(id ORDER BY id) = ARRAY[0,2]::INT[]
	AND
	array_agg(parent ORDER BY id) = ARRAY[1,4]::INT[],
	'Wrong output in graph (BFS)')
	FROM out_frombfs WHERE dist = 2 AND g1 = 100 AND g2 = 'a'
;
SELECT assert(
	array_agg(id ORDER BY id) = ARRAY[0,2]::INT[]
	AND
	array_agg(parent ORDER BY id) = ARRAY[1,4]::INT[],
	'Wrong output in graph (BFS)')
	FROM out_frombfs WHERE dist = 2 AND g1 = 100 AND g2 = 'b'
;
SELECT assert(MIN(g1) = 100 AND MAX(g1) = 100,
	'Wrong output in graph (BFS)') FROM out_frombfs GROUP BY g1,g2
;

-- Test for common column names in vertex and edge tables
DROP TABLE IF EXISTS out, out_summary;
ALTER TABLE vertex RENAME COLUMN id TO "SRC";

SELECT graph_bfs('vertex','"SRC"','edge_grp','src="SRC"',3,'out',NULL,NULL,'g1');
SELECT * FROM out;

DROP TABLE IF EXISTS out, out_summary;
ALTER TABLE vertex RENAME COLUMN "SRC" TO dest;

SELECT graph_bfs('vertex','dest','edge_grp','src="SRC"',3,'out',NULL,NULL,'g1');
SELECT * FROM out;

ALTER TABLE vertex RENAME COLUMN dest TO id;

-- Test for bigint columns
CREATE TABLE v2 AS SELECT id::bigint FROM vertex;
CREATE TABLE e2 AS SELECT "SRC"::bigint, dest::bigint, weight FROM "EDGE";

DROP TABLE IF EXISTS pg_temp.out2, pg_temp.out2_summary;
SELECT graph_bfs('v2',NULL,'e2','src="SRC"',3,'pg_temp.out2');
SELECT count(*) from pg_temp.out2;
SELECT * from pg_temp.out2_summary;

-- Test for infinite paths
DROP TABLE IF EXISTS out, out_summary, out_path;
DELETE FROM "EDGE" WHERE dest = 7;

SELECT graph_bfs('vertex',NULL,'"EDGE"','src="SRC"',3,'out');

SELECT assert(count(*) = 0, 'Null parent in the out table')
    FROM (SELECT * FROM out WHERE parent IS NULL)q1;