// Recursively flattens a list by splicing any sub-lists into their parent until
// depth is reached. If a negative number is passed for depth then it continues
// until no elements of the returned list are lists
185937
func DeepFlatten(slice []interface{}, depth int) []interface{} {
	if depth == 0 {
		return slice
	}
	returnSlice := []interface{}{}

	for _, element := range slice {
		if s, ok := element.([]interface{}); ok {
			returnSlice = append(returnSlice, DeepFlatten(s, depth-1)...)
		} else {
			returnSlice = append(returnSlice, element)
		}

	}

	return returnSlice
}
282415
func (s *parentStack) trim(parents []string) error {
	split := 0
	for ; split < len(parents) && split < len(s.stack); split++ {
		if parents[split] != s.stack[split] {
			break
		}
	}
	for i := len(s.stack) - 1; i >= split; i-- {
		if err := s.p.writeEnd(Name{Local: s.stack[i]}); err != nil {
			return err
		}
	}
	s.stack = parents[:split]
	return nil
}
302634
func (s *ShapeIndex) updateEdges(pcell *PaddedCell, edges []*clippedEdge, t *tracker, disjointFromIndex bool) {
	// This function is recursive with a maximum recursion depth of 30 (maxLevel).

	// Incremental updates are handled as follows. All edges being added or
	// removed are combined together in edges, and all shapes with interiors
	// are tracked using tracker. We subdivide recursively as usual until we
	// encounter an existing index cell. At this point we absorb the index
	// cell as follows:
	//
	//   - Edges and shapes that are being removed are deleted from edges and
	//     tracker.
	//   - All remaining edges and shapes from the index cell are added to
	//     edges and tracker.
	//   - Continue subdividing recursively, creating new index cells as needed.
	//   - When the recursion gets back to the cell that was absorbed, we
	//     restore edges and tracker to their previous state.
	//
	// Note that the only reason that we include removed shapes in the recursive
	// subdivision process is so that we can find all of the index cells that
	// contain those shapes efficiently, without maintaining an explicit list of
	// index cells for each shape (which would be expensive in terms of memory).
	indexCellAbsorbed := false
	if !disjointFromIndex {
		// There may be existing index cells contained inside pcell. If we
		// encounter such a cell, we need to combine the edges being updated with
		// the existing cell contents by absorbing the cell.
		iter := s.Iterator()
		r := iter.LocateCellID(pcell.id)
		if r == Disjoint {
			disjointFromIndex = true
		} else if r == Indexed {
			// Absorb the index cell by transferring its contents to edges and
			// deleting it. We also start tracking the interior of any new shapes.
			s.absorbIndexCell(pcell, iter, edges, t)
			indexCellAbsorbed = true
			disjointFromIndex = true
		} else {
			// DCHECK_EQ(SUBDIVIDED, r)
		}
	}

	// If there are existing index cells below us, then we need to keep
	// subdividing so that we can merge with those cells. Otherwise,
	// makeIndexCell checks if the number of edges is small enough, and creates
	// an index cell if possible (returning true when it does so).
	if !disjointFromIndex || !s.makeIndexCell(pcell, edges, t) {
		// TODO(roberts): If it turns out to have memory problems when there
		// are 10M+ edges in the index, look into pre-allocating space so we
		// are not always appending.
		childEdges := [2][2][]*clippedEdge{} // [i][j]

		// Compute the middle of the padded cell, defined as the rectangle in
		// (u,v)-space that belongs to all four (padded) children. By comparing
		// against the four boundaries of middle we can determine which children
		// each edge needs to be propagated to.
		middle := pcell.Middle()

		// Build up a vector edges to be passed to each child cell. The (i,j)
		// directions are left (i=0), right (i=1), lower (j=0), and upper (j=1).
		// Note that the vast majority of edges are propagated to a single child.
		for _, edge := range edges {
			if edge.bound.X.Hi <= middle.X.Lo {
				// Edge is entirely contained in the two left children.
				a, b := s.clipVAxis(edge, middle.Y)
				if a != nil {
					childEdges[0][0] = append(childEdges[0][0], a)
				}
				if b != nil {
					childEdges[0][1] = append(childEdges[0][1], b)
				}
			} else if edge.bound.X.Lo >= middle.X.Hi {
				// Edge is entirely contained in the two right children.
				a, b := s.clipVAxis(edge, middle.Y)
				if a != nil {
					childEdges[1][0] = append(childEdges[1][0], a)
				}
				if b != nil {
					childEdges[1][1] = append(childEdges[1][1], b)
				}
			} else if edge.bound.Y.Hi <= middle.Y.Lo {
				// Edge is entirely contained in the two lower children.
				if a := s.clipUBound(edge, 1, middle.X.Hi); a != nil {
					childEdges[0][0] = append(childEdges[0][0], a)
				}
				if b := s.clipUBound(edge, 0, middle.X.Lo); b != nil {
					childEdges[1][0] = append(childEdges[1][0], b)
				}
			} else if edge.bound.Y.Lo >= middle.Y.Hi {
				// Edge is entirely contained in the two upper children.
				if a := s.clipUBound(edge, 1, middle.X.Hi); a != nil {
					childEdges[0][1] = append(childEdges[0][1], a)
				}
				if b := s.clipUBound(edge, 0, middle.X.Lo); b != nil {
					childEdges[1][1] = append(childEdges[1][1], b)
				}
			} else {
				// The edge bound spans all four children. The edge
				// itself intersects either three or four padded children.
				left := s.clipUBound(edge, 1, middle.X.Hi)
				a, b := s.clipVAxis(left, middle.Y)
				if a != nil {
					childEdges[0][0] = append(childEdges[0][0], a)
				}
				if b != nil {
					childEdges[0][1] = append(childEdges[0][1], b)
				}
				right := s.clipUBound(edge, 0, middle.X.Lo)
				a, b = s.clipVAxis(right, middle.Y)
				if a != nil {
					childEdges[1][0] = append(childEdges[1][0], a)
				}
				if b != nil {
					childEdges[1][1] = append(childEdges[1][1], b)
				}
			}
		}

		// Now recursively update the edges in each child. We call the children in
		// increasing order of CellID so that when the index is first constructed,
		// all insertions into cellMap are at the end (which is much faster).
		for pos := 0; pos < 4; pos++ {
			i, j := pcell.ChildIJ(pos)
			if len(childEdges[i][j]) > 0 || len(t.shapeIDs) > 0 {
				s.updateEdges(PaddedCellFromParentIJ(pcell, i, j), childEdges[i][j],
					t, disjointFromIndex)
			}
		}
	}

	if indexCellAbsorbed {
		// Restore the state for any edges being removed that we are tracking.
		t.restoreStateBefore(s.pendingAdditionsPos)
	}
}
33851
func DepthMatchAll(p MIMEPart, matcher MIMEPartMatcher) []MIMEPart {
	root := p
	matches := make([]MIMEPart, 0, 10)
	for {
		if matcher(p) {
			matches = append(matches, p)
		}
		c := p.FirstChild()
		if c != nil {
			p = c
		} else {
			for p.NextSibling() == nil {
				if p == root {
					return matches
				}
				p = p.Parent()
			}
			p = p.NextSibling()
		}
	}
}
69577
func (m *Matrix) Flatten() []float32 {
	res := make([]float32, m.Rows*m.Cols)
	var wg sync.WaitGroup
	for y := 0; y < int(m.Rows); y++ {
		wg.Add(1)
		go m.flatten(res, y, &wg)
	}
	wg.Wait()
	return res
}
656615
func Flatten(g Grouping) *Table {
	groups := g.Tables()
	switch len(groups) {
	case 0:
		return new(Table)

	case 1:
		return g.Table(groups[0])
	}

	tabs := make([]*Table, len(groups))
	for i, gid := range groups {
		tabs[i] = g.Table(gid)
	}

	return concatRows(tabs...)
}
261873
func (l *List) Append(n int64) {
	i := len(l.tree)
	l.tree = append(l.tree, 0)
	l.tree[i] = n - l.Get(i)
}
547749
func Flatten(path *Path, flattener Flattener, scale float64) {
	// First Point
	var startX, startY float64
	// Current Point
	var x, y float64
	var i int
	for _, cmp := range path.Components {
		switch cmp {
		case MoveToComponent:
			x, y = path.Points[i], path.Points[i+1]
			startX, startY = x, y
			if i != 0 {
				flattener.End()
			}
			flattener.MoveTo(x, y)
			i += 2
		case LineToComponent:
			x, y = path.Points[i], path.Points[i+1]
			flattener.LineTo(x, y)
			flattener.LineJoin()
			i += 2
		case QuadCurveToComponent:
			// we include the previous point for the start of the curve
			TraceQuad(flattener, path.Points[i-2:], 0.5)
			x, y = path.Points[i+2], path.Points[i+3]
			flattener.LineTo(x, y)
			i += 4
		case CubicCurveToComponent:
			TraceCubic(flattener, path.Points[i-2:], 0.5)
			x, y = path.Points[i+4], path.Points[i+5]
			flattener.LineTo(x, y)
			i += 6
		case ArcToComponent:
			x, y = TraceArc(flattener, path.Points[i], path.Points[i+1], path.Points[i+2], path.Points[i+3], path.Points[i+4], path.Points[i+5], scale)
			flattener.LineTo(x, y)
			i += 6
		case CloseComponent:
			flattener.LineTo(startX, startY)
			flattener.Close()
		}
	}
	flattener.End()
}
134381
func (s *parentStack) Push(node *treapNode) {
	if s.index < staticDepth {
		s.items[s.index] = node
		s.index++
		return
	}

	// This approach is used over append because reslicing the slice to pop
	// the item causes the compiler to make unneeded allocations.  Also,
	// since the max number of items is related to the tree depth which
	// requires expontentially more items to increase, only increase the cap
	// one item at a time.  This is more intelligent than the generic append
	// expansion algorithm which often doubles the cap.
	index := s.index - staticDepth
	if index+1 > cap(s.overflow) {
		overflow := make([]*treapNode, index+1)
		copy(overflow, s.overflow)
		s.overflow = overflow
	}
	s.overflow[index] = node
	s.index++
}
100437
func LoadIteratorToDepth(ctx context.Context, qs graph.QuadStore, dst reflect.Value, depth int, list graph.Iterator) error {
	return global.LoadIteratorToDepth(ctx, qs, dst, depth, list)
}
1315636
func (n *TreeNode) CollapseAll() *TreeNode {
	n.Walk(func(node, parent *TreeNode) bool {
		n.expanded = false
		return true
	})
	return n
}
1074535
func list_clear(fnname string, recv_ Value, args Tuple, kwargs []Tuple) (Value, error) {
	if err := UnpackPositionalArgs(fnname, args, kwargs, 0); err != nil {
		return nil, err
	}
	return None, recv_.(*List).Clear()
}
1201768
func splitBound(edgeBound r2.Rect, uEnd, vEnd int, u, v float64) [2]r2.Rect {
	var childBounds = [2]r2.Rect{
		edgeBound,
		edgeBound,
	}

	if uEnd == 1 {
		childBounds[0].X.Lo = u
		childBounds[1].X.Hi = u
	} else {
		childBounds[0].X.Hi = u
		childBounds[1].X.Lo = u
	}

	if vEnd == 1 {
		childBounds[0].Y.Lo = v
		childBounds[1].Y.Hi = v
	} else {
		childBounds[0].Y.Hi = v
		childBounds[1].Y.Lo = v
	}

	return childBounds
}
992086
func recursAddNode(node *client.Node, list []string) []string {
	for _, innerNode := range node.Nodes {
		// add only the files.
		if !innerNode.Dir {
			list = append(list, innerNode.Value)
		} else {
			list = recursAddNode(innerNode, list)
		}
	}

	return list
}
943579
func expandRefRecursive(ctx *resolveCtx, r *Resolver, v interface{}) (ret interface{}, err error) {
	if pdebug.Enabled {
		g := pdebug.Marker("expandRefRecursive")
		defer g.End()
	}
	for {
		ref, err := findRef(v)
		if err != nil {
			if pdebug.Enabled {
				pdebug.Printf("No refs found. bailing out of loop")
			}
			break
		}

		if pdebug.Enabled {
			pdebug.Printf("Found ref '%s'", ref)
		}

		newv, err := expandRef(ctx, r, v, ref)
		if err != nil {
			if pdebug.Enabled {
				pdebug.Printf("Failed to expand ref '%s': %s", ref, err)
			}
			return nil, errors.Wrap(err, "failed to expand ref")
		}

		v = newv
	}

	return v, nil
}
1022517
func recursiveVM(src []byte, insts []inst, pc, sp int, ms ...*MatchData) (bool, int, *MatchData) {
	var m *MatchData
	if len(ms) == 0 {
		m = newMatchState()
	} else {
		m = ms[0]
	}
redo:
	inst := insts[pc]
	switch inst.OpCode {
	case opChar:
		if sp >= len(src) || !inst.Class.Matches(int(src[sp])) {
			return false, sp, m
		}
		pc++
		sp++
		goto redo
	case opMatch:
		return true, sp, m
	case opTailMatch:
		return sp >= len(src), sp, m
	case opJmp:
		pc = inst.Operand1
		goto redo
	case opSplit:
		if ok, nsp, _ := recursiveVM(src, insts, inst.Operand1, sp, m); ok {
			return true, nsp, m
		}
		pc = inst.Operand2
		goto redo
	case opSave:
		s := m.setCapture(inst.Operand1, sp)
		if ok, nsp, _ := recursiveVM(src, insts, pc+1, sp, m); ok {
			return true, nsp, m
		}
		m.restoreCapture(inst.Operand1, s)
		return false, sp, m
	case opPSave:
		m.addPosCapture(inst.Operand1, sp+1)
		pc++
		goto redo
	case opBrace:
		if sp >= len(src) || int(src[sp]) != inst.Operand1 {
			return false, sp, m
		}
		count := 1
		for sp = sp + 1; sp < len(src); sp++ {
			if int(src[sp]) == inst.Operand2 {
				count--
			}
			if count == 0 {
				pc++
				sp++
				goto redo
			}
			if int(src[sp]) == inst.Operand1 {
				count++
			}
		}
		return false, sp, m
	case opNumber:
		idx := inst.Operand1 * 2
		if idx >= m.CaptureLength()-1 {
			panic(newError(_UNKNOWN, "invalid capture index"))
		}
		capture := src[m.Capture(idx):m.Capture(idx+1)]
		for i := 0; i < len(capture); i++ {
			if i+sp >= len(src) || capture[i] != src[i+sp] {
				return false, sp, m
			}
		}
		pc++
		sp += len(capture)
		goto redo
	}
	panic("should not reach here")
}
399232
func (r *Router) depth() int {
	max := 0
	for _, child := range r.children {
		childDepth := child.depth()
		if childDepth > max {
			max = childDepth
		}
	}
	return max + 1
}