libgo: Update to October 24 version of master library.

From-SVN: r204466

4 files changed, 115 insertions, 4 deletions

diff --git a/libgo/go/container/heap/heap.go b/libgo/go/container/heap/heap.go
index c37e50e3c40..52c8507b421 100644
--- a/libgo/go/container/heap/heap.go
+++ b/libgo/go/container/heap/heap.go
@@ -6,6 +6,8 @@
 // heap.Interface. A heap is a tree with the property that each node is the
 // minimum-valued node in its subtree.
 //
+// The minimum element in the tree is the root, at index 0.
+//
 // A heap is a common way to implement a priority queue. To build a priority
 // queue, implement the Heap interface with the (negative) priority as the
 // ordering for the Less method, so Push adds items while Pop removes the
@@ -54,7 +56,7 @@ func Push(h Interface, x interface{}) {
 
 // Pop removes the minimum element (according to Less) from the heap
 // and returns it. The complexity is O(log(n)) where n = h.Len().
-// Same as Remove(h, 0).
+// It is equivalent to Remove(h, 0).
 //
 func Pop(h Interface) interface{} {
 	n := h.Len() - 1
@@ -76,6 +78,15 @@ 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.
+// 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().
+func Fix(h Interface, i int) {
+	down(h, i, h.Len())
+	up(h, i)
+}
+
 func up(h Interface, j int) {
 	for {
 		i := (j - 1) / 2 // parent
diff --git a/libgo/go/container/heap/heap_test.go b/libgo/go/container/heap/heap_test.go
index 274d587d874..b3d054c5f39 100644
--- a/libgo/go/container/heap/heap_test.go
+++ b/libgo/go/container/heap/heap_test.go
@@ -5,6 +5,7 @@
 package heap
 
 import (
+	"math/rand"
 	"testing"
 )
 
@@ -182,3 +183,31 @@ func BenchmarkDup(b *testing.B) {
 		}
 	}
 }
+
+func TestFix(t *testing.T) {
+	h := new(myHeap)
+	h.verify(t, 0)
+
+	for i := 200; i > 0; i -= 10 {
+		Push(h, i)
+	}
+	h.verify(t, 0)
+
+	if (*h)[0] != 10 {
+		t.Fatalf("Expected head to be 10, was %d", (*h)[0])
+	}
+	(*h)[0] = 210
+	Fix(h, 0)
+	h.verify(t, 0)
+
+	for i := 100; i > 0; i-- {
+		elem := rand.Intn(h.Len())
+		if i&1 == 0 {
+			(*h)[elem] *= 2
+		} else {
+			(*h)[elem] /= 2
+		}
+		Fix(h, elem)
+		h.verify(t, 0)
+	}
+}
diff --git a/libgo/go/container/list/list.go b/libgo/go/container/list/list.go
index 562a5badbd3..ed2d15a4575 100755
--- a/libgo/go/container/list/list.go
+++ b/libgo/go/container/list/list.go
@@ -29,7 +29,7 @@ type Element struct {
 
 // Next returns the next list element or nil.
 func (e *Element) Next() *Element {
-	if p := e.next; p != &e.list.root {
+	if p := e.next; e.list != nil && p != &e.list.root {
 		return p
 	}
 	return nil
@@ -37,7 +37,7 @@ func (e *Element) Next() *Element {
 
 // Prev returns the previous list element or nil.
 func (e *Element) Prev() *Element {
-	if p := e.prev; p != &e.list.root {
+	if p := e.prev; e.list != nil && p != &e.list.root {
 		return p
 	}
 	return nil
@@ -62,6 +62,7 @@ func (l *List) Init() *List {
 func New() *List { return new(List).Init() }
 
 // Len returns the number of elements of list l.
+// The complexity is O(1).
 func (l *List) Len() int { return l.len }
 
 // Front returns the first element of list l or nil
@@ -126,7 +127,7 @@ func (l *List) Remove(e *Element) interface{} {
 	return e.Value
 }
 
-// Pushfront inserts a new element e with value v at the front of list l and returns e.
+// PushFront inserts a new element e with value v at the front of list l and returns e.
 func (l *List) PushFront(v interface{}) *Element {
 	l.lazyInit()
 	return l.insertValue(v, &l.root)
@@ -178,6 +179,24 @@ func (l *List) MoveToBack(e *Element) {
 	l.insert(l.remove(e), l.root.prev)
 }
 
+// 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.
+func (l *List) MoveBefore(e, mark *Element) {
+	if e.list != l || e == mark {
+		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.
+func (l *List) MoveAfter(e, mark *Element) {
+	if e.list != l || e == mark {
+		return
+	}
+	l.insert(l.remove(e), mark)
+}
+
 // PushBackList inserts a copy of an other list at the back of list l.
 // The lists l and other may be the same.
 func (l *List) PushBackList(other *List) {
diff --git a/libgo/go/container/list/list_test.go b/libgo/go/container/list/list_test.go
index b4fc77d1403..ee52afe82b9 100755
--- a/libgo/go/container/list/list_test.go
+++ b/libgo/go/container/list/list_test.go
@@ -233,3 +233,55 @@ func TestIssue4103(t *testing.T) {
 		t.Errorf("l1.Len() = %d, want 3", n)
 	}
 }
+
+func TestIssue6349(t *testing.T) {
+	l := New()
+	l.PushBack(1)
+	l.PushBack(2)
+
+	e := l.Front()
+	l.Remove(e)
+	if e.Value != 1 {
+		t.Errorf("e.value = %d, want 1", e.Value)
+	}
+	if e.Next() != nil {
+		t.Errorf("e.Next() != nil")
+	}
+	if e.Prev() != nil {
+		t.Errorf("e.Prev() != nil")
+	}
+}
+
+func TestMove(t *testing.T) {
+	l := New()
+	e1 := l.PushBack(1)
+	e2 := l.PushBack(2)
+	e3 := l.PushBack(3)
+	e4 := l.PushBack(4)
+
+	l.MoveAfter(e3, e3)
+	checkListPointers(t, l, []*Element{e1, e2, e3, e4})
+	l.MoveBefore(e2, e2)
+	checkListPointers(t, l, []*Element{e1, e2, e3, e4})
+
+	l.MoveAfter(e3, e2)
+	checkListPointers(t, l, []*Element{e1, e2, e3, e4})
+	l.MoveBefore(e2, e3)
+	checkListPointers(t, l, []*Element{e1, e2, e3, e4})
+
+	l.MoveBefore(e2, e4)
+	checkListPointers(t, l, []*Element{e1, e3, e2, e4})
+	e1, e2, e3, e4 = e1, e3, e2, e4
+
+	l.MoveBefore(e4, e1)
+	checkListPointers(t, l, []*Element{e4, e1, e2, e3})
+	e1, e2, e3, e4 = e4, e1, e2, e3
+
+	l.MoveAfter(e4, e1)
+	checkListPointers(t, l, []*Element{e1, e4, e2, e3})
+	e1, e2, e3, e4 = e1, e4, e2, e3
+
+	l.MoveAfter(e2, e3)
+	checkListPointers(t, l, []*Element{e1, e3, e2, e4})
+	e1, e2, e3, e4 = e1, e3, e2, e4
+}