:returns: the lowest common ancestor of u and v
        :complexity: O(log n)
166936
def query(self, u, v):
        
        # -- assume w.l.o.g. that v is not higher than u in the tree
        if self.level[u] > self.level[v]:
            u, v = v, u
        # -- put v at the same level as u
        depth = len(self.anc)
        for k in range(depth-1, -1, -1):
            if self.level[u] <= self.level[v] - (1 << k):
                v = self.anc[k][v]
        assert self.level[u] == self.level[v]
        if u == v:
            return u
        # -- climb until the lowest common ancestor
        for k in range(depth-1, -1, -1):
            if self.anc[k][u] != self.anc[k][v]:
                u = self.anc[k][u]
                v = self.anc[k][v]
        assert self.anc[0][u] == self.anc[0][v]
        return self.anc[0][u]
296792
def get_ancestor_list(n)
      raise ArgumentError, "n must be greater or equal than zero" unless n >= 0

      return [] if n == 0 || number == 0
      parent = get_parent
      [parent] + parent.get_ancestor_list(n-1)
    end
1148587
def sdiv(self, o):
        
        # TODO: copy the code from wrapped interval
        splitted_dividends = self._psplit()
        splitted_divisors = o._psplit()

        resulting_intervals = set()
        for dividend in splitted_dividends:
            for divisor in splitted_divisors:
                tmp = self._wrapped_signed_div(dividend, divisor)
                resulting_intervals.add(tmp)

        return StridedInterval.least_upper_bound(*resulting_intervals).normalize()
382513
def bounding_cylinder(self):
        
        from . import primitives, bounds
        kwargs = bounds.minimum_cylinder(self)
        mincyl = primitives.Cylinder(mutable=False, **kwargs)
        return mincyl
1018190
def minimum(self):
        
        return min([(x, energy) for _, x, energy, _, _ in self.get_kinks()],
                   key=lambda i: i[1])
406802
def udiv(self, o):
        
        #FIXME: copy the code fromm wrapped interval
        splitted_dividends = self._ssplit()
        splitted_divisors = o._ssplit()

        resulting_intervals = set()
        for dividend in splitted_dividends:
            for divisor in splitted_divisors:
                tmp = self._wrapped_unsigned_div(dividend, divisor)
                resulting_intervals.add(tmp)

        return StridedInterval.least_upper_bound(*resulting_intervals).normalize()
1089350
def min(self, key=None):
        
        if key is None:
            return self.reduce(min)
        return self.reduce(lambda a, b: min(a, b, key=key))
1213437
function getDepth(ancestor, descendant) {
      var ret = 0;
      while (descendant !== ancestor) {
          ret++;
          descendant = descendant.parentNode;
          if (!descendant)
              throw new Error("not a descendant of ancestor!");
      }
      return ret;
  }
1240868
def parent(self) -> Optional['CtsReference']:
        
        if self.start.depth == 1 and (self.end is None or self.end.depth <= 1):
            return None
        else:
            if self.start.depth > 1 and (self.end is None or self.end.depth == 0):
                return CtsReference("{0}{1}".format(
                    ".".join(self.start.list[:-1]),
                    self.start.subreference or ""
                ))
            elif self.start.depth > 1 and self.end is not None and self.end.depth > 1:
                _start = self.start.list[0:-1]
                _end = self.end.list[0:-1]
                if _start == _end and \
                        self.start.subreference is None and \
                        self.end.subreference is None:
                    return CtsReference(
                        ".".join(_start)
                    )
                else:
                    return CtsReference("{0}{1}-{2}{3}".format(
                        ".".join(_start),
                        self.start.subreference or "",
                        ".".join(_end),
                        self.end.subreference or ""
                    ))
832030
def smallest(self):
        

        heap = self._heap
        v, k = heap[0]
        while k not in self or self[k] != v:
            heappop(heap)
            v, k = heap[0]

        return k
793219
def closest_common_ancestor(self, other):
        
        our_history_iter = reversed(HistoryIter(self))
        their_history_iter = reversed(HistoryIter(other))
        sofar = set()

        while True:
            our_done = False
            their_done = False

            try:
                our_next = next(our_history_iter)
                if our_next in sofar:
                    # we found it!
                    return our_next
                sofar.add(our_next)
            except StopIteration:
                # we ran out of items during iteration
                our_done = True

            try:
                their_next = next(their_history_iter)
                if their_next in sofar:
                    # we found it!
                    return their_next
                sofar.add(their_next)
            except StopIteration:
                # we ran out of items during iteration
                their_done = True

            # if we ran out of both lists, there's no common ancestor
            if our_done and their_done:
                return None
865309
def strictly_monotonic(bb):
    '''
    

    '''
    cc=bb[np.where(bb>=0)]
    cc.sort()
    dc=cc[1:]-cc[:-1] # subsequent equal entries have 0 in db
    dc=np.insert(dc,0,1) # the first element is always unique (the second occurence is the dublicate)
    dc_mask=np.ma.masked_equal(dc,0)
    return np.ma.array(cc,mask=dc_mask.mask).compressed()
95471
def kth_smallest(self, root, k):
        
        count = []
        self.helper(root, count)
        return count[k-1]
866863
def query(self, u, v):
        
        lu = self.last[u]
        lv = self.last[v]
        if lu > lv:
            lu, lv = lv, lu
        return self.rmq.range_min(lu, lv + 1)[1]
806851
function getLowestCommonAncestor(instA, instB) {
  var depthA = 0;
  for (var tempA = instA; tempA; tempA = getParent(tempA)) {
    depthA++;
  }
  var depthB = 0;
  for (var tempB = instB; tempB; tempB = getParent(tempB)) {
    depthB++;
  }

  // If A is deeper, crawl up.
  while (depthA - depthB > 0) {
    instA = getParent(instA);
    depthA--;
  }

  // If B is deeper, crawl up.
  while (depthB - depthA > 0) {
    instB = getParent(instB);
    depthB--;
  }

  // Walk in lockstep until we find a match.
  var depth = depthA;
  while (depth--) {
    if (instA === instB || instA === instB.alternate) {
      return instA;
    }
    instA = getParent(instA);
    instB = getParent(instB);
  }
  return null;
}
741734
def previous_sibling(self):
        
        stmts = self.parent.child_sequence(self)
        index = stmts.index(self)
        if index >= 1:
            return stmts[index - 1]
        return None
575484
private static <T> Optional<T> lowestCommonAncestor(TreeDef.Parented<T> treeDef, T nodeA, T nodeB) {
		class TreeSearcher {
			private T tip;
			private final Set<T> visited;

			public TreeSearcher(T start) {
				this.tip = start;
				this.visited = new HashSet<>();
			}

			public boolean hasMore() {
				return tip != null;
			}

			public Optional<T> march(TreeSearcher other) {
				if (other.visited.contains(tip)) {
					return Optional.of(tip);
				} else {
					visited.add(tip);
					tip = treeDef.parentOf(tip);
					return Optional.empty();
				}
			}
		}

		// make a list of a's parents (bottom of stack is 'a' itself, top of is root)
		TreeSearcher searchA = new TreeSearcher(nodeA);
		TreeSearcher searchB = new TreeSearcher(nodeB);

		Optional<T> commonAncestor = searchB.march(searchA);
		// so long as both searches
		while (searchA.hasMore() && searchB.hasMore()) {
			commonAncestor = searchA.march(searchB);
			if (commonAncestor.isPresent()) {
				return commonAncestor;
			}
			commonAncestor = searchB.march(searchA);
			if (commonAncestor.isPresent()) {
				return commonAncestor;
			}
		}
		while (searchA.hasMore() && !commonAncestor.isPresent()) {
			commonAncestor = searchA.march(searchB);
		}
		while (searchB.hasMore() && !commonAncestor.isPresent()) {
			commonAncestor = searchB.march(searchA);
		}
		return commonAncestor;
	}