// Adding directed arc to graph
func (gr *MixedMatrix) AddArc(tail, head VertexId) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Add arc to mixed graph.", e)
			err.AddV("tail", tail)
			err.AddV("head", head)
			panic(err)
		}
	}()

	conn := gr.getConnectionId(tail, head, true)
	if gr.nodes[conn] != CT_NONE {
		err := erx.NewError("Duplicate edge.")
		err.AddV("connection id", conn)
		err.AddV("type", gr.nodes[conn])
		panic(err)
	}

	if tail < head {
		gr.nodes[conn] = CT_DIRECTED
	} else {
		gr.nodes[conn] = CT_DIRECTED_REVERSED
	}

	gr.arcsCnt++
}

// Getting all nodes, connected to given one
func (gr *MixedMatrix) GetNeighbours(node VertexId) VertexesIterable {
	iterator := func() <-chan VertexId {
		ch := make(chan VertexId)

		go func() {
			defer func() {
				if e := recover(); e != nil {
					err := erx.NewSequent("Get node neighbours in mixed graph.", e)
					err.AddV("node", node)
					panic(err)
				}
			}()

			for neighbour, _ := range gr.VertexIds {
				if node == neighbour {
					// skipping loops
					continue
				}

				connId := gr.getConnectionId(node, neighbour, false)
				if gr.nodes[connId] == CT_UNDIRECTED {
					ch <- neighbour
				}
			}
			close(ch)
		}()

		return ch
	}

	return VertexesIterable(&nodesIterableLambdaHelper{iterFunc: iterator})
}

// Removding directed arc
func (gr *MixedMatrix) RemoveArc(tail, head VertexId) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Remove arc from mixed graph.", e)
			err.AddV("tail", tail)
			err.AddV("head", head)
			panic(err)
		}
	}()

	conn := gr.getConnectionId(tail, head, true)
	expectedType := CT_NONE
	if tail < head {
		expectedType = CT_DIRECTED
	} else {
		expectedType = CT_DIRECTED_REVERSED
	}

	if gr.nodes[conn] != expectedType {
		err := erx.NewError("Arc doesn't exists.")
		err.AddV("connection id", conn)
		err.AddV("type", gr.nodes[conn])
		panic(err)
	}

	gr.nodes[conn] = CT_NONE
	gr.arcsCnt--
}

func (g *MixedMap) CheckEdgeType(tail VertexId, head VertexId) MixedConnectionType {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Check edge type in mixed graph.", e)
			err.AddV("tail", tail)
			err.AddV("head", head)
			panic(err)
		}
	}()

	connectedVertexes, ok := g.connections[tail]
	if !ok {
		panic(erx.NewError("Fist node doesn't exist."))
	}

	if _, ok = g.connections[head]; !ok {
		panic(erx.NewError("Second node doesn't exist."))
	}

	direction, ok := connectedVertexes[head]
	if !ok {
		direction = CT_NONE
	}

	return direction
}

func (gr *MixedMatrix) getConnectionId(node1, node2 VertexId, create bool) int {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Calculating connection id.", e)
			err.AddV("node 1", node1)
			err.AddV("node 2", node2)
			panic(err)
		}
	}()

	var id1, id2 int
	node1Exist := false
	node2Exist := false
	id1, node1Exist = gr.VertexIds[node1]
	id2, node2Exist = gr.VertexIds[node2]

	// checking for errors
	{
		if node1 == node2 {
			panic(erx.NewError("Equal nodes."))
		}
		if !create {
			if !node1Exist {
				panic(erx.NewError("First node doesn't exist in graph"))
			}
			if !node2Exist {
				panic(erx.NewError("Second node doesn't exist in graph"))
			}
		} else if !node1Exist || !node2Exist {
			if node1Exist && node2Exist {
				if gr.size-len(gr.VertexIds) < 2 {
					panic(erx.NewError("Not enough space to create two new nodes."))
				}
			} else {
				if gr.size-len(gr.VertexIds) < 1 {
					panic(erx.NewError("Not enough space to create new node."))
				}
			}
		}
	}

	if !node1Exist {
		id1 = int(len(gr.VertexIds))
		gr.VertexIds[node1] = id1
	}

	if !node2Exist {
		id2 = int(len(gr.VertexIds))
		gr.VertexIds[node2] = id2
	}

	// switching id1, id2 in order to id1 < id2
	if id1 > id2 {
		id1, id2 = id2, id1
	}

	// id from upper triangle matrix, stored in vector
	connId := id1*(gr.size-1) + id2 - 1 - id1*(id1+1)/2
	return connId
}

// Getting node predecessors
func (g *MixedMap) GetNeighbours(node VertexId) VertexesIterable {
	iterator := func() <-chan VertexId {
		ch := make(chan VertexId)

		go func() {
			defer func() {
				if e := recover(); e != nil {
					err := erx.NewSequent("Get node neighbours.", e)
					err.AddV("node id", node)
					panic(err)
				}
			}()

			if connectedMap, ok := g.connections[node]; ok {
				for VertexId, connType := range connectedMap {
					if connType == CT_UNDIRECTED {
						ch <- VertexId
					}
				}
			} else {
				panic(erx.NewError("Node doesn't exists."))
			}

			close(ch)
		}()

		return ch
	}

	return VertexesIterable(&nodesIterableLambdaHelper{iterFunc: iterator})
}

// Getting node predecessors
func (g *MixedMap) GetPredecessors(node VertexId) VertexesIterable {
	iterator := func() <-chan VertexId {
		ch := make(chan VertexId)

		go func() {
			defer func() {
				if e := recover(); e != nil {
					err := erx.NewSequent("Getting node predecessors.", e)
					err.AddV("node id", node)
					panic(err)
				}
			}()

			accessorsMap, ok := g.connections[node]
			if !ok {
				panic(erx.NewError("Node doesn't exists."))
			}

			for VertexId, connType := range accessorsMap {
				if connType == CT_DIRECTED_REVERSED {
					ch <- VertexId
				}
			}

			close(ch)
		}()

		return ch
	}

	return VertexesIterable(&nodesIterableLambdaHelper{iterFunc: iterator})
}

// Adding edge to graph.
func (g *MixedMap) AddEdge(from, to VertexId) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Add edge to graph.", e)
			err.AddV("node 1", from)
			err.AddV("node 2", to)
			panic(err)
		}
	}()

	g.touchNode(from)
	g.touchNode(to)

	if direction, ok := g.connections[from][to]; ok {
		err := erx.NewError("Duplicate connection.")
		err.AddV("connection type", direction)
		panic(err)
	}

	g.connections[from][to] = CT_UNDIRECTED
	g.connections[to][from] = CT_UNDIRECTED
	g.edgesCnt++

	return
}

// Removing arrow  'from' and 'to' nodes
func (g *MixedMap) RemoveArc(from, to VertexId) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Remove arc from graph.", e)
			err.AddV("tail", from)
			err.AddV("head", to)
			panic(err)
		}
	}()

	if _, ok := g.connections[from]; ok {
		panic(erx.NewError("Tail node doesn't exist."))
	}

	if _, ok := g.connections[to]; ok {
		panic(erx.NewError("Head node doesn't exist."))
	}

	if dir, ok := g.connections[from][to]; !ok || dir != CT_DIRECTED {
		panic(erx.NewError("Arc doesn't exist."))
	}

	g.connections[from][to] = CT_NONE, false
	g.connections[to][from] = CT_NONE, false
	g.arcsCnt--

	return
}

// Getting node predecessors
func (g *DirectedMap) GetPredecessors(node VertexId) VertexesIterable {
	iterator := func() <-chan VertexId {
		ch := make(chan VertexId)

		go func() {
			defer func() {
				if e := recover(); e != nil {
					err := erx.NewSequent("Get node accessors in mixed graph.", e)
					err.AddV("node", node)
					panic(err)
				}
			}()
			accessorsMap, ok := g.reversedArcs[node]
			if !ok {
				panic(erx.NewError("Node doesn't exists."))
			}

			for VertexId, _ := range accessorsMap {
				ch <- VertexId
			}
			close(ch)
		}()

		return ch
	}

	return VertexesIterable(&nodesIterableLambdaHelper{iterFunc: iterator})
}

func readGraphLine(gr graphWriterGeneric, line string, connectionDelimiter string) {
	line = strings.Trim(line, " \t\n")
	if commentPos := strings.Index(line, "#"); commentPos != -1 {
		// truncate comments
		line = strings.Trim(line[0:commentPos], " \t\n")
	}

	if line == "" {
		// skip empty lines
		return
	}

	if isMatch, err := regexp.MatchString("^[0-9]+$", line); isMatch && err == nil {
		// only one number - it's vertex id
		vertexId, err := strconv.Atoi(line)
		if err != nil {
			panic(err)
		}

		gr.AddNode(VertexId(vertexId))
	} else if err != nil {
		panic(err)
	}

	{
		// removing spaces between delimiter and vertexes
		reg1 := regexp.MustCompile("[ \t]*" + connectionDelimiter + "[ \t]*")
		line = reg1.ReplaceAllString(line, connectionDelimiter)

		// replace spaces to delimiter between vertexes
		reg2 := regexp.MustCompile("[ \t]+")
		line = reg2.ReplaceAllString(line, " ")
		line = strings.Replace(line, " ", connectionDelimiter, -1)
	}

	var prevVertexId VertexId
	hasPrev := false
	for _, nodeAsStr := range strings.Split(line, connectionDelimiter, -1) {
		nodeAsStr = strings.Trim(nodeAsStr, " \t\n")
		nodeAsInt, err := strconv.Atoi(nodeAsStr)
		if err != nil {
			errErx := erx.NewSequent("Can't parse node id.", err)
			errErx.AddV("chunk", nodeAsStr)
			panic(errErx)
		}

		VertexId := VertexId(nodeAsInt)
		if hasPrev {
			gr.AddConnection(prevVertexId, VertexId)
		} else {
			hasPrev = true
		}
		prevVertexId = VertexId
	}
	return
}

func ReadUgraphLine(gr UndirectedGraphWriter, line string) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Parsing graph edges from line.", e)
			err.AddV("line", line)
			panic(err)
		}
	}()

	readGraphLine(&graphWriterGeneric_ugraph{gr: gr}, line, "-")
}

// Add new item to queue
func (q *nodesPriorityQueueSimple) Add(node VertexId, priority float64) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("", e)
			err.AddV("node", node)
			err.AddV("priority", priority)
			panic(err)
		}
	}()

	found := false
	if id, ok := q.nodesIndex[node]; ok {
		if priority > q.data[id].Priority {
			q.data[id].Priority = priority
			// changing position
			newId := id + 1
			for q.data[newId].Priority < priority && newId < q.size {
				newId++
			}

			if newId > id+1 {
				// need to move
				copy(q.data[id:newId-1], q.data[id+1:newId])
				q.data[newId-1].Node = node
				q.data[newId-1].Priority = priority
			}
		}
		found = true
	}

	if !found {
		if q.size == len(q.data) {
			// resize
			// 2 is just a magic number
			newData := make(nodesPriority, 2*len(q.data))
			copy(newData, q.data)
			q.data = newData
		}
		id := 0
		for q.data[id].Priority < priority && id < q.size {
			id++
		}
		if id < q.size {
			copy(q.data[id+1:q.size+1], q.data[id:q.size])
		}
		q.data[id].Node = node
		q.data[id].Priority = priority
		q.nodesIndex[node] = id
		q.size++
	}
}

// Retrieving path from path marks.
func PathFromMarks(marks PathMarks, destination VertexId) Vertexes {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Retrieving path from path marks.", e)
			err.AddV("marks", marks)
			err.AddV("destination", destination)
			panic(err)
		}
	}()
	destInfo, ok := marks[destination]
	if !ok || destInfo.Weight == math.MaxFloat64 {
		// no path from any source to destination
		return nil
	}

	curVertexInfo := destInfo
	path := make(Vertexes, 10)
	curPathPos := 0
	path[curPathPos] = destination
	curPathPos++
	for curVertexInfo.Weight > 0.0 {
		if len(path) == curPathPos {
			// reallocate memory for path
			tmp := make(Vertexes, 2*curPathPos)
			copy(tmp, path)
			path = tmp
		}
		path[curPathPos] = curVertexInfo.PrevVertex
		curPathPos++
		var ok bool
		curVertexInfo, ok = marks[curVertexInfo.PrevVertex]
		if !ok {
			err := erx.NewError("Can't find path mark info for vertex in path.")
			err.AddV("vertex", curVertexInfo.PrevVertex)
			err.AddV("cur path", path)
			panic(err)
		}
	}

	path = path[0:curPathPos]

	// reversing path
	pathLen := len(path)
	for i := 0; i < pathLen/2; i++ {
		path[i], path[pathLen-i-1] = path[pathLen-i-1], path[i]
	}

	return path
}

func (g *UndirectedMatrix) CheckEdge(node1, node2 VertexId) bool {
	defer func() {
		// warning! such code generates wrong file/line info about error!
		// see http://groups.google.com/group/golang-nuts/browse_thread/thread/66bd57dcdac63aa
		// for details
		if err := recover(); err != nil {
			errErx := erx.NewSequent("Checking edge", err)
			errErx.AddV("node 1", node1)
			errErx.AddV("node 2", node2)
			panic(errErx)
		}
	}()

	return g.nodes[g.getConnectionId(node1, node2, false)]
}

// Checking edge existance between node1 and node2
//
// node1 and node2 must exist in graph or error will be returned
func (gr *MixedMatrix) CheckEdge(node1, node2 VertexId) bool {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Check edge in mixed graph.", e)
			err.AddV("node 1", node1)
			err.AddV("node 2", node2)
			panic(err)
		}
	}()

	if node1 == node2 {
		return false
	}

	return gr.nodes[gr.getConnectionId(node1, node2, false)] == CT_UNDIRECTED
}

func readGraphFile(f io.Reader, lineParser func(string)) {
	reader := bufio.NewReader(f)
	var err os.Error
	var line string
	line, err = reader.ReadString('\n')
	for err == nil || err == os.EOF {
		lineParser(line)
		if err == os.EOF {
			break
		}
		line, err = reader.ReadString('\n')
	}
	if err != nil && err != os.EOF {
		erxErr := erx.NewSequent("Error while reading file.", err)
		panic(erxErr)
	}
}

func (gr *MixedMatrix) CheckEdgeType(tail VertexId, head VertexId) MixedConnectionType {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Check edge type in mixed graph.", e)
			err.AddV("tail", tail)
			err.AddV("head", head)
			panic(err)
		}
	}()

	conn := gr.getConnectionId(tail, head, false)
	connType := gr.nodes[conn]
	if connType == CT_DIRECTED && tail > head {
		return CT_DIRECTED_REVERSED
	}
	return connType
}

// Adding single node to graph
func (g *MixedMap) AddNode(node VertexId) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Add node to graph.", e)
			err.AddV("node id", node)
			panic(err)
		}
	}()

	if _, ok := g.connections[node]; ok {
		panic(erx.NewError("Node already exists."))
	}

	g.connections[node] = make(map[VertexId]MixedConnectionType)

	return
}

// Generic function to check if graph contain specific path.
//
// First argument gr is an interface with two functions to check node existance and
// connection existance between two nodes in graph.
//
// unexistNodePanic flag is used to point wether or not to panic if we figure out that
// one of the nodes in path doesn't exist in graph. If unexistNodePanic is false, then
// result of the function will be false.
func ContainPath(gr NodeAndConnectionChecker, path []VertexId, unexistNodePanic bool) bool {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Checking if graph contain path", e)
			err.AddV("path", path)
			err.AddV("panic if node doesn't exist in graph", unexistNodePanic)
			panic(err)
		}
	}()
	if len(path) == 0 {
		// emty path always exists
		return true
	}

	prev := path[0]
	if !gr.CheckNode(prev) {
		if unexistNodePanic {
			err := erx.NewError("Node doesn't exist in graph.")
			err.AddV("node", prev)
			panic(err)
		}
		return false
	}

	if len(path) == 1 {
		return true
	}

	for i := 1; i < len(path); i++ {
		cur := path[i]
		if !gr.CheckNode(cur) {
			if unexistNodePanic {
				err := erx.NewError("Node doesn't exist in graph.")
				err.AddV("node", cur)
				panic(err)
			}
			return false
		}
		if !gr.CheckConnection(prev, cur) {
			return false
		}
		prev = cur
	}
	return true
}