// Insert inserts a value and string into the tree
// Returns true on succesful insertion, false if duplicate exists
971312
func (t *redBlackTree) Insert(key keytype, value valuetype) (ret bool) {
	if t.root == nil {
		t.root = &redBlackNode{
			key:   key,
			value: value,
		}
		ret = true
	} else {
		var head = &redBlackNode{}

		var dir = true
		var last = true

		var parent *redBlackNode  // parent
		var gparent *redBlackNode // grandparent
		var ggparent = head       // great grandparent
		var node = t.root

		ggparent.right = t.root

		for {
			if node == nil {
				// insert new node at bottom
				node = &redBlackNode{
					key:   key,
					value: value,
					red:   true,
				}
				parent.setChild(dir, node)
				ret = true
			} else if isRed(node.left) && isRed(node.right) {
				// flip colors
				node.red = true
				node.left.red, node.right.red = false, false
			}
			// fix red violation
			if isRed(node) && isRed(parent) {
				dir2 := ggparent.right == gparent

				if node == parent.Child(last) {
					ggparent.setChild(dir2, singleRotate(gparent, !last))
				} else {
					ggparent.setChild(dir2, doubleRotate(gparent, !last))
				}
			}

			cmp := node.key.Compare(key)

			// stop if found
			if cmp == 0 {
				break
			}

			last = dir
			dir = cmp < 0

			// update helpers
			if gparent != nil {
				ggparent = gparent
			}
			gparent = parent
			parent = node

			node = node.Child(dir)
		}

		t.root = head.right
	}

	// make root black
	t.root.red = false

	if ret {
		t.size++
	}

	return ret
}
996537
func (t *Table) Insert() (stmt string, names []string) {
	return t.insert.stmt, t.insert.names
}
214330
func (d *Diet) Insert(x, y uint64) {
	x, y = sortBoundaries(x, y)
	d.root = insert(x, y, d.root)
}
801843
func (entries *Entries) insert(entry Entry) Entry {
	i := entries.search(entry.Key())

	if i == len(*entries) {
		*entries = append(*entries, entry)
		return nil
	}

	if (*entries)[i].Key() == entry.Key() {
		oldEntry := (*entries)[i]
		(*entries)[i] = entry
		return oldEntry
	}

	(*entries) = append(*entries, nil)
	copy((*entries)[i+1:], (*entries)[i:])
	(*entries)[i] = entry
	return nil
}
1287753
func (s Int64Slice) Insert(x int64) Int64Slice {
	i := s.Search(x)
	if i == len(s) {
		return append(s, x)
	}

	if s[i] == x {
		return s
	}

	s = append(s, 0)
	copy(s[i+1:], s[i:])
	s[i] = x
	return s
}
297630
func Insert(db DB, table string, src interface{}) error {
	return Default.Insert(db, table, src)
}
364667
func (b *Builder) Insert(eq Eq) *Builder {
	b.inserts = eq
	b.optype = insertType
	return b
}
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
}
907255
func (t *Txn) Insert(k []byte, v interface{}) (interface{}, bool) {
	newRoot, oldVal, didUpdate := t.insert(t.root, k, k, v)
	if newRoot != nil {
		t.root = newRoot
	}
	if !didUpdate {
		t.size++
	}
	return oldVal, didUpdate
}
514159
func (t *Tree) Add(o interface{}) (val interface{}, isDupe bool) {
	d := &addData{o, nil, t}
	taller := false
	isDupe = false
	val = d.add(&t.root, &taller)
	if val == nil {
		isDupe = true
		val = d.duplicate
	}
	return
}
1256679
func (t *table) insert(s string) bool {
	h1, h2 := t.hash(s)
	if t.tab[h1] == "" {
		t.tab[h1] = s
		return true
	}
	if t.tab[h2] == "" {
		t.tab[h2] = s
		return true
	}
	if t.push(h1, 0) {
		t.tab[h1] = s
		return true
	}
	if t.push(h2, 0) {
		t.tab[h2] = s
		return true
	}
	return false
}
824439
func (g *Group) Insert(e *GroupExpr) bool {
	if g.Exists(e) {
		return false
	}

	operand := GetOperand(e.ExprNode)
	var newEquiv *list.Element
	mark, hasMark := g.FirstExpr[operand]
	if hasMark {
		newEquiv = g.Equivalents.InsertAfter(e, mark)
	} else {
		newEquiv = g.Equivalents.PushBack(e)
		g.FirstExpr[operand] = newEquiv
	}
	g.Fingerprints[e.FingerPrint()] = newEquiv
	return true
}
1162377
func (cki *ComputedKeyInfos) Insert(i *ComputedKeyInfo) {
	cki.Infos[i.KID] = i
	cki.dirty = true
}
169968
func (s Int64) Insert(items ...int64) {
	for _, item := range items {
		s[item] = Empty{}
	}
}
829353
func (s Byte) Insert(items ...byte) {
	for _, item := range items {
		s[item] = Empty{}
	}
}
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
}
133899
func (b *BinaryTree) Insert(value Comparable) {
	newNode := new(node)
	newNode.value = value
	y := (*node)(nil)
	x := b.root
	for x != nil {
		y = x
		if value.CompareTo(x.value) == -1 { // less
			x = x.left
		} else {
			x = x.right
		}
	}
	newNode.parent = y
	if newNode.parent == nil {
		b.root = newNode
	} else if newNode.value.CompareTo(y.value) == -1 {
		y.left = newNode
	} else {
		y.right = newNode
	}
	b.size++
}