// insert does a recursive insertion
358750
func (t *Txn) insert(n *Node, k, search []byte, v interface{}) (*Node, interface{}, bool) {
	// Handle key exhaustion
	if len(search) == 0 {
		var oldVal interface{}
		didUpdate := false
		if n.isLeaf() {
			oldVal = n.leaf.val
			didUpdate = true
		}

		nc := t.writeNode(n, true)
		nc.leaf = &leafNode{
			mutateCh: make(chan struct{}),
			key:      k,
			val:      v,
		}
		return nc, oldVal, didUpdate
	}

	// Look for the edge
	idx, child := n.getEdge(search[0])

	// No edge, create one
	if child == nil {
		e := edge{
			label: search[0],
			node: &Node{
				mutateCh: make(chan struct{}),
				leaf: &leafNode{
					mutateCh: make(chan struct{}),
					key:      k,
					val:      v,
				},
				prefix: search,
			},
		}
		nc := t.writeNode(n, false)
		nc.addEdge(e)
		return nc, nil, false
	}

	// Determine longest prefix of the search key on match
	commonPrefix := longestPrefix(search, child.prefix)
	if commonPrefix == len(child.prefix) {
		search = search[commonPrefix:]
		newChild, oldVal, didUpdate := t.insert(child, k, search, v)
		if newChild != nil {
			nc := t.writeNode(n, false)
			nc.edges[idx].node = newChild
			return nc, oldVal, didUpdate
		}
		return nil, oldVal, didUpdate
	}

	// Split the node
	nc := t.writeNode(n, false)
	splitNode := &Node{
		mutateCh: make(chan struct{}),
		prefix:   search[:commonPrefix],
	}
	nc.replaceEdge(edge{
		label: search[0],
		node:  splitNode,
	})

	// Restore the existing child node
	modChild := t.writeNode(child, false)
	splitNode.addEdge(edge{
		label: modChild.prefix[commonPrefix],
		node:  modChild,
	})
	modChild.prefix = modChild.prefix[commonPrefix:]

	// Create a new leaf node
	leaf := &leafNode{
		mutateCh: make(chan struct{}),
		key:      k,
		val:      v,
	}

	// If the new key is a subset, add to to this node
	search = search[commonPrefix:]
	if len(search) == 0 {
		splitNode.leaf = leaf
		return nc, nil, false
	}

	// Create a new edge for the node
	splitNode.addEdge(edge{
		label: search[0],
		node: &Node{
			mutateCh: make(chan struct{}),
			leaf:     leaf,
			prefix:   search,
		},
	})
	return nc, nil, false
}
1180263
func (b *Builder) Insert(key []byte, val uint64) error {
	// ensure items are added in lexicographic order
	if bytes.Compare(key, b.last) < 0 {
		return ErrOutOfOrder
	}
	if len(key) == 0 {
		b.len = 1
		b.unfinished.setRootOutput(val)
		return nil
	}

	prefixLen, out := b.unfinished.findCommonPrefixAndSetOutput(key, val)
	b.len++
	err := b.compileFrom(prefixLen)
	if err != nil {
		return err
	}
	b.copyLastKey(key)
	b.unfinished.addSuffix(key[prefixLen:], out)

	return nil
}
382040
func (l *ItemList) insert(e, at *ItemElement) *ItemElement {
	n := at.next
	at.next = e
	e.prev = at
	e.next = n
	n.prev = e
	e.list = l
	l.len++
	return e
}
270563
func (l *lNode) inserted(entry *Entry) *lNode {
	return &lNode{l.removed(entry).Add(&sNode{entry})}
}
1039873
func (t *Trie) Insert(key string) {
	curNode := t.root
	for _, v := range key {
		if curNode.child[v] == nil {
			curNode.child[v] = newNode()
		}
		curNode = curNode.child[v]
	}

	if !curNode.exists {
		// increment when new rune child is added.
		t.size++
		curNode.exists = true
	}
	// value is stored for retrieval in future.
	curNode.value = key
}
1030282
func (all *assetLruList) insert(alle, at *assetLruListElement) *assetLruListElement {
	n := at.next
	at.next = alle
	alle.prev = at
	alle.next = n
	n.prev = alle
	alle.list = all
	all.len++
	return alle
}
1017902
func (s IntSet) Insert(items ...int) {
	for _, item := range items {
		s[item] = sets.Empty{}
	}
}
325951
func (t *Trie) insert(key []byte, value interface{}, replace bool) bool {
	// an empty tree
	if t.size == 0 {
		t.root.external = &external{
			key:   key,
			value: value,
		}
		t.size = 1
		return true
	}

	n := t.search(key)
	newOffset, newBit, newCont := n.external.criticalBit(key)

	// already exists in the tree
	if newOffset == -1 {
		if replace {
			n.external.value = value
			return true
		}
		return false
	}

	// allocate new node
	newNode := &internal{
		offset: newOffset,
		bit:    newBit,
		cont:   newCont,
	}
	direction := newNode.direction(key)
	newNode.child[direction].external = &external{
		key:   key,
		value: value,
	}

	// insert new node
	wherep := &t.root
	for in := wherep.internal; in != nil; in = wherep.internal {
		if in.offset > newOffset || (in.offset == newOffset && in.bit < newBit) {
			break
		}
		wherep = &in.child[in.direction(key)]
	}

	if wherep.internal != nil {
		newNode.child[1-direction].internal = wherep.internal
	} else {
		newNode.child[1-direction].external = wherep.external
		wherep.external = nil
	}
	wherep.internal = newNode
	t.size += 1
	return true
}
1050987
func (treeCursor *treeCursor) insert(astNode ast.Node) bool {
	if astNode == nil {
		// End of branch, go up
		treeCursor.currentDepth--
		treeCursor.current = treeCursor.current.Parent
		return false
	}

	// Allocate memory for a new TreeNode
	treeNode := &TreeNode{}

	treeNode.AstNode = astNode
	treeNode.Depth = treeCursor.currentDepth
	treeNode.Parent = treeCursor.current

	// Append new node to children of the current node
	treeCursor.current.Children = append(treeCursor.current.Children, treeNode)

	// Update cursor, go down
	treeCursor.current = treeNode
	treeCursor.currentDepth++
	return true
}
417339
func (aia *AIA) Insert(tx *sql.Tx) error {
	_, err := tx.Exec(`INSERT INTO aia (ski, url) values (?, ?)`, aia.SKI, aia.URL)
	return err
}
296669
func (t *Table) Insert(row Row) error {
	if len(t.rows) > 0 && len(t.rows[0]) != len(row) {
		return InconsistentRowsError{existingRows: len(t.rows), newRow: len(row)}
	}
	t.rows = append(t.rows, row)
	t.nInserts++
	return nil
}
1145910
func (h *heap) insert(value []float64, length float64, srcRowNo int) {
	node := heapNode{}
	node.length = length
	node.srcRowNo = srcRowNo
	node.value = make([]float64, len(value))
	copy(node.value, value)
	h.tree = append(h.tree, node)

	target := len(h.tree)
	for target != 1 {
		if h.tree[(target/2)-1].length >= h.tree[target-1].length {
			break
		}
		h.tree[target-1], h.tree[(target/2)-1] = h.tree[(target/2)-1], h.tree[target-1]
		target /= 2
	}
}
1166755
func (n *node) insert(item Item, maxItems int) Item {
	i, found := n.items.find(item)
	if found {
		out := n.items[i]
		n.items[i] = item
		return out
	}
	if len(n.children) == 0 {
		n.items.insertAt(i, item)
		return nil
	}
	if n.maybeSplitChild(i, maxItems) {
		inTree := n.items[i]
		switch {
		case item.Less(inTree):
			// no change, we want first split node
		case inTree.Less(item):
			i++ // we want second split node
		default:
			out := n.items[i]
			n.items[i] = item
			return out
		}
	}
	return n.mutableChild(i).insert(item, maxItems)
}
94742
func (qt *Quadtree) Insert(item AABBer) {
	qt.Total++
	pRect := item.AABB()
	qt.root.Insert(qt.newQuadtreeNodeData(item, pRect))
}
771184
func (s *RankedSet) Insert(item Item) Item {
	old := s.Delete(item)

	key := item.Key()
	value := &treeItem{item: item}

	s.rank.ReplaceOrInsert(value) // should always return nil because we call Delete first
	s.set[key] = value

	return old
}
297630
func Insert(db DB, table string, src interface{}) error {
	return Default.Insert(db, table, src)
}
188637
func (t *Tree) Insert(e Interface, fast bool) (err error) {
	if e.Start().Compare(e.End()) > 0 {
		return ErrInvertedRange
	}
	var d int
	t.Root, d = t.Root.insert(e, e.Start(), e.ID(), fast)
	t.Count += d
	t.Root.Color = llrb.Black
	return
}