Go-原生包源码看看（container包）

//要实现这个接口需要写5个方法
type Interface interface {
  继承 sort.Interface，也就是下面的那个
    sort.Interface
    Push(x interface{})  add x as element Len()
    Pop() interface{}    remove and return element Len() - 1.
}
//sort.Interface
type Interface interface {
     Len is the number of elements in the collection.
    Len() int
     Less reports whether the element with
     index i should sort before the element with index j.
    Less(i, j int) bool
     Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

func up(h Interface, j int) {
    for {
    一直找j的父节点
        i := (j - 1)  2  parent
        if i == j || !h.Less(j, i) {
      如果自己就是或者小于父节点就退出
            break
        }
    /否则交换
        h.Swap(i, j)
        j = i
    }
}


func down(h Interface, i0, n int) bool {
  //i0代表需要down的元素在数组中的索引
  //n代表长度
    i := i0
    for {
        j1 := 2*i + 1
        if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
      //越界跳出
            break
        }
    //左子节点索引
        j := j1 // left child
        if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
      //j2 右子节点索引
            j = j2 
        }
    //父节点 > 右子节点，则交换位置
        if !h.Less(j, i) {
            break
        }
        h.Swap(i, j)
        i = j
    }
    return i > i0
}

/ Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x interface{}) {
  //在最后头添加一个元素
    h.Push(x)
  //然后上升
    up(h, h.Len()-1)
}

// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = h.Len().
func Remove(h Interface, i int) interface{} {
    n := h.Len() - 1
    if n != i {
    //把要删除的跟最后一个交换
        h.Swap(i, n)
    //然后下沉或上升到合适的位置
        if !down(h, i, n) {
            up(h, i)
        }
    }
  //把最后一个干掉
    return h.Pop()
}




// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to Remove(h, 0).
//删除最上面的元素
func Pop(h Interface) interface{} {
    n := h.Len() - 1
  //把根节点跟最后一个交换
    h.Swap(0, n)
  //然后下沉到合适的位置
    down(h, 0, n)
  //把最后一个干掉
    return h.Pop()
}

//元素
type Element struct {
    // Next and previous pointers in the doubly-linked list of elements.
    // To simplify the implementation, internally a list l is implemented
    // as a ring, such that &l.root is both the next element of the last
    // list element (l.Back()) and the previous element of the first list
    // element (l.Front()).
  //前指针、后指针
    next, prev *Element


    // The list to which this element belongs.
    list *List


    // The value stored with this element.
    Value interface{}
}




// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
//双向链表
//双向是由Element里的next/prev决定的。如果只有一个就是单链表
type List struct {
    root Element // sentinel list element, only &root, root.prev, and root.next are used
    len  int     // current list length excluding (this) sentinel element
}

//初始化一个双向链表，前后指针都指向自己
// Init initializes or clears list l.
func (l *List) Init() *List {
    l.root.next = &l.root
    l.root.prev = &l.root
    l.len = 0
    return l
}


// New returns an initialized list.
func New() *List { return new(List).Init() }

//在at元素的后面插入一个e元素
// insert inserts e after at, increments l.len, and returns e.
func (l *List) insert(e, at *Element) *Element {
    //
    n := at.next
    //修改指针指向，先修改要插入的那个元素的前一个元素后指针，指向e元素
    at.next = e
    //修改要插入的元素的前指针
    e.prev = at
    //把e元素的后指针指向原来at元素的后面一个元素
    e.next = n
    //原本at元素的前指针就指向e元素了
    n.prev = e
    e.list = l
    l.len++
    //返回要插入的元素
    return e
}


//移出一个元素
// remove removes e from its list, decrements l.len, and returns e.
func (l *List) remove(e *Element) *Element {
  //把e前一个元素的后指针指向e的下一个元素
    e.prev.next = e.next
  //再把e后一个元素的前指针指向e的前一个元素
    e.next.prev = e.prev
  //销毁指针值
    e.next = nil // avoid memory leaks
    e.prev = nil // avoid memory leaks
  //销毁data域
    e.list = nil
  // - len
    l.len--
    return e
}




// move moves e to next to at and returns e.
//移动元素
//其实就是把插入跟移出结合了
//把e元素挪到at元素后面
func (l *List) move(e, at *Element) *Element {
    if e == at {
        return e
    }
    e.prev.next = e.next
    e.next.prev = e.prev


    n := at.next
    at.next = e
    e.prev = at
    e.next = n
    n.prev = e


    return e
}

type Ring struct {
    next, prev *Ring
    Value      interface{} // for use by client; untouched by this library
}

// New creates a ring of n elements.
func New(n int) *Ring {
    if n <= 0 {
        return nil
    }
    r := new(Ring)
    p := r
    for i := 1; i < n; i++ {
    //多个元素，首尾相连起来
        p.next = &Ring{prev: p}
        p = p.next
    }
  //再把最后一个后指针指向第一个元素
    p.next = r
  //把第一个元素的前指针指向最后一个元素
    r.prev = p
    return r
}

//由有一个do方法遍历huan
// Do calls function f on each element of the ring, in forward order.
// The behavior of Do is undefined if f changes *r.
func (r *Ring) Do(f func(interface{})) {
    if r != nil {
        f(r.Value)
        for p := r.Next(); p != r; p = p.next {
            f(p.Value)
        }
    }
}