blob: b9731fa7c24ff24f4d57ae66d868af8cfb3621a7 [file] [log] [blame]
 // Copyright 2016 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. package ssa // Code to compute lowest common ancestors in the dominator tree. // https://en.wikipedia.org/wiki/Lowest_common_ancestor // https://en.wikipedia.org/wiki/Range_minimum_query#Solution_using_constant_time_and_linearithmic_space // lcaRange is a data structure that can compute lowest common ancestor queries // in O(n lg n) precomputed space and O(1) time per query. type lcaRange struct { // Additional information about each block (indexed by block ID). blocks []lcaRangeBlock // Data structure for range minimum queries. // rangeMin[k][i] contains the ID of the minimum depth block // in the Euler tour from positions i to i+1< 0 { n := len(q) - 1 bid := q[n].bid cid := q[n].cid q = q[:n] // Add block to tour. blocks[bid].pos = int32(len(tour)) tour = append(tour, bid) // Proceed down next child edge (if any). if cid == 0 { // This is our first visit to b. Set its depth. blocks[bid].depth = blocks[blocks[bid].parent].depth + 1 // Then explore its first child. cid = blocks[bid].firstChild } else { // We've seen b before. Explore the next child. cid = blocks[cid].sibling } if cid != 0 { q = append(q, queueEntry{bid, cid}, queueEntry{cid, 0}) } } // Compute fast range-minimum query data structure var rangeMin [][]ID rangeMin = append(rangeMin, tour) // 1-size windows are just the tour itself. for logS, s := 1, 2; s < len(tour); logS, s = logS+1, s*2 { r := make([]ID, len(tour)-s+1) for i := 0; i < len(tour)-s+1; i++ { bid := rangeMin[logS-1][i] bid2 := rangeMin[logS-1][i+s/2] if blocks[bid2].depth < blocks[bid].depth { bid = bid2 } r[i] = bid } rangeMin = append(rangeMin, r) } return &lcaRange{blocks: blocks, rangeMin: rangeMin} } // find returns the lowest common ancestor of a and b. func (lca *lcaRange) find(a, b *Block) *Block { if a == b { return a } // Find the positions of a and bin the Euler tour. p1 := lca.blocks[a.ID].pos p2 := lca.blocks[b.ID].pos if p1 > p2 { p1, p2 = p2, p1 } // The lowest common ancestor is the minimum depth block // on the tour from p1 to p2. We've precomputed minimum // depth blocks for powers-of-two subsequences of the tour. // Combine the right two precomputed values to get the answer. logS := uint(log2(int64(p2 - p1))) bid1 := lca.rangeMin[logS][p1] bid2 := lca.rangeMin[logS][p2-1<