Imported Upstream version 1.3upstream/1.3

6 files changed, 84 insertions, 18 deletions

diff --git a/src/pkg/container/heap/example_pq_test.go b/src/pkg/container/heap/example_pq_test.go
index 8cbeb8d70..7017095cb 100644
--- a/src/pkg/container/heap/example_pq_test.go
+++ b/src/pkg/container/heap/example_pq_test.go
@@ -52,13 +52,12 @@ func (pq *PriorityQueue) Pop() interface{} {
 
 // update modifies the priority and value of an Item in the queue.
 func (pq *PriorityQueue) update(item *Item, value string, priority int) {
-	heap.Remove(pq, item.index)
 	item.value = value
 	item.priority = priority
-	heap.Push(pq, item)
+	heap.Fix(pq, item.index)
 }
 
-// This example inserts some items into a PriorityQueue, manipulates an item,
+// This example creates a PriorityQueue with some items, adds and manipulates an item,
 // and then removes the items in priority order.
 func Example_priorityQueue() {
 	// Some items and their priorities.
@@ -66,28 +65,31 @@ func Example_priorityQueue() {
 		"banana": 3, "apple": 2, "pear": 4,
 	}
 
-	// Create a priority queue and put the items in it.
-	pq := &PriorityQueue{}
-	heap.Init(pq)
+	// Create a priority queue, put the items in it, and
+	// establish the priority queue (heap) invariants.
+	pq := make(PriorityQueue, len(items))
+	i := 0
 	for value, priority := range items {
-		item := &Item{
+		pq[i] = &Item{
 			value:    value,
 			priority: priority,
+			index:    i,
 		}
-		heap.Push(pq, item)
+		i++
 	}
+	heap.Init(&pq)
 
 	// Insert a new item and then modify its priority.
 	item := &Item{
 		value:    "orange",
 		priority: 1,
 	}
-	heap.Push(pq, item)
+	heap.Push(&pq, item)
 	pq.update(item, item.value, 5)
 
 	// Take the items out; they arrive in decreasing priority order.
 	for pq.Len() > 0 {
-		item := heap.Pop(pq).(*Item)
+		item := heap.Pop(&pq).(*Item)
 		fmt.Printf("%.2d:%s ", item.priority, item.value)
 	}
 	// Output:
diff --git a/src/pkg/container/heap/heap.go b/src/pkg/container/heap/heap.go
index 52c8507b4..c467a1191 100644
--- a/src/pkg/container/heap/heap.go
+++ b/src/pkg/container/heap/heap.go
@@ -22,7 +22,7 @@ import "sort"
 // min-heap with the following invariants (established after
 // Init has been called or if the data is empty or sorted):
 //
-//	!h.Less(j, i) for 0 <= i < h.Len() and j = 2*i+1 or 2*i+2 and j < h.Len()
+//	!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()
 //
 // Note that Push and Pop in this interface are for package heap's
 // implementation to call.  To add and remove things from the heap,
@@ -78,7 +78,7 @@ func Remove(h Interface, i int) interface{} {
 	return h.Pop()
 }
 
-// Fix reestablishes the heap ordering after the element at index i has changed its value.
+// Fix re-establishes the heap ordering after the element at index i has changed its value.
 // Changing the value of the element at index i and then calling Fix is equivalent to,
 // but less expensive than, calling Remove(h, i) followed by a Push of the new value.
 // The complexity is O(log(n)) where n = h.Len().
diff --git a/src/pkg/container/list/example_test.go b/src/pkg/container/list/example_test.go
index 7361212d7..362178401 100644
--- a/src/pkg/container/list/example_test.go
+++ b/src/pkg/container/list/example_test.go
@@ -17,7 +17,7 @@ func Example() {
 	l.InsertBefore(3, e4)
 	l.InsertAfter(2, e1)
 
-	// Iterate through list and and print its contents.
+	// Iterate through list and print its contents.
 	for e := l.Front(); e != nil; e = e.Next() {
 		fmt.Println(e.Value)
 	}
diff --git a/src/pkg/container/list/list.go b/src/pkg/container/list/list.go
index ed2d15a45..0256768ef 100644
--- a/src/pkg/container/list/list.go
+++ b/src/pkg/container/list/list.go
@@ -65,7 +65,7 @@ func New() *List { return new(List).Init() }
 // The complexity is O(1).
 func (l *List) Len() int { return l.len }
 
-// Front returns the first element of list l or nil
+// Front returns the first element of list l or nil.
 func (l *List) Front() *Element {
 	if l.len == 0 {
 		return nil
@@ -180,18 +180,18 @@ func (l *List) MoveToBack(e *Element) {
 }
 
 // MoveBefore moves element e to its new position before mark.
-// If e is not an element of l, or e == mark, the list is not modified.
+// If e or mark is not an element of l, or e == mark, the list is not modified.
 func (l *List) MoveBefore(e, mark *Element) {
-	if e.list != l || e == mark {
+	if e.list != l || e == mark || mark.list != l {
 		return
 	}
 	l.insert(l.remove(e), mark.prev)
 }
 
 // MoveAfter moves element e to its new position after mark.
-// If e is not an element of l, or e == mark, the list is not modified.
+// If e or mark is not an element of l, or e == mark, the list is not modified.
 func (l *List) MoveAfter(e, mark *Element) {
-	if e.list != l || e == mark {
+	if e.list != l || e == mark || mark.list != l {
 		return
 	}
 	l.insert(l.remove(e), mark)
diff --git a/src/pkg/container/list/list_test.go b/src/pkg/container/list/list_test.go
index ee52afe82..4d8bfc2bf 100644
--- a/src/pkg/container/list/list_test.go
+++ b/src/pkg/container/list/list_test.go
@@ -285,3 +285,59 @@ func TestMove(t *testing.T) {
 	checkListPointers(t, l, []*Element{e1, e3, e2, e4})
 	e1, e2, e3, e4 = e1, e3, e2, e4
 }
+
+// Test PushFront, PushBack, PushFrontList, PushBackList with uninitialized List
+func TestZeroList(t *testing.T) {
+	var l1 = new(List)
+	l1.PushFront(1)
+	checkList(t, l1, []interface{}{1})
+
+	var l2 = new(List)
+	l2.PushBack(1)
+	checkList(t, l2, []interface{}{1})
+
+	var l3 = new(List)
+	l3.PushFrontList(l1)
+	checkList(t, l3, []interface{}{1})
+
+	var l4 = new(List)
+	l4.PushBackList(l2)
+	checkList(t, l4, []interface{}{1})
+}
+
+// Test that a list l is not modified when calling InsertBefore with a mark that is not an element of l.
+func TestInsertBeforeUnknownMark(t *testing.T) {
+	var l List
+	l.PushBack(1)
+	l.PushBack(2)
+	l.PushBack(3)
+	l.InsertBefore(1, new(Element))
+	checkList(t, &l, []interface{}{1, 2, 3})
+}
+
+// Test that a list l is not modified when calling InsertAfter with a mark that is not an element of l.
+func TestInsertAfterUnknownMark(t *testing.T) {
+	var l List
+	l.PushBack(1)
+	l.PushBack(2)
+	l.PushBack(3)
+	l.InsertAfter(1, new(Element))
+	checkList(t, &l, []interface{}{1, 2, 3})
+}
+
+// Test that a list l is not modified when calling MoveAfter or MoveBefore with a mark that is not an element of l.
+func TestMoveUnkownMark(t *testing.T) {
+	var l1 List
+	e1 := l1.PushBack(1)
+
+	var l2 List
+	e2 := l2.PushBack(2)
+
+	l1.MoveAfter(e1, e2)
+	checkList(t, &l1, []interface{}{1})
+	checkList(t, &l2, []interface{}{2})
+
+	l1.MoveBefore(e1, e2)
+	checkList(t, &l1, []interface{}{1})
+	checkList(t, &l2, []interface{}{2})
+}
diff --git a/src/pkg/container/ring/ring_test.go b/src/pkg/container/ring/ring_test.go
index 099d92b25..552f0e24b 100644
--- a/src/pkg/container/ring/ring_test.go
+++ b/src/pkg/container/ring/ring_test.go
@@ -218,3 +218,11 @@ func TestLinkUnlink(t *testing.T) {
 		}
 	}
 }
+
+// Test that calling Move() on an empty Ring initializes it.
+func TestMoveEmptyRing(t *testing.T) {
+	var r Ring
+
+	r.Move(1)
+	verify(t, &r, 1, 0)
+}