internal/pieceordering: Switch to a different skiplist implementation

diff --git a/internal/pieceordering/pieceordering.go b/internal/pieceordering/pieceordering.go
index 60ab0c77a3a75d4dd357dfd300235a766603bb3b..acf3cc0cacf3ff7a6b98b3eb637a688ea67acedc 100644 (file)
--- a/internal/pieceordering/pieceordering.go
+++ b/internal/pieceordering/pieceordering.go
@@ -1,17 +1,19 @@
 package pieceordering
 
 import (
-       "github.com/glenn-brown/skiplist"
+       "math/rand"
+
+       "github.com/ryszard/goskiplist/skiplist"
 )
 
 type Instance struct {
-       sl        *skiplist.T
+       sl        *skiplist.SkipList
        pieceKeys map[int]int
 }
 
 func New() *Instance {
        return &Instance{
-               sl: skiplist.New(),
+               sl: skiplist.NewIntMap(),
        }
 }
 
@@ -24,19 +26,48 @@ func (me *Instance) SetPiece(piece, key int) {
                }
                me.removeKeyPiece(existingKey, piece)
        }
-       me.sl.Insert(key, piece)
+       var itemSl []int
+       if exItem, ok := me.sl.Get(key); ok {
+               itemSl = exItem.([]int)
+       }
+       me.sl.Set(key, append(itemSl, piece))
        if me.pieceKeys == nil {
                me.pieceKeys = make(map[int]int)
        }
        me.pieceKeys[piece] = key
+       me.shuffleItem(key)
+}
+
+func (me *Instance) shuffleItem(key int) {
+       _item, ok := me.sl.Get(key)
+       if !ok {
+               return
+       }
+       item := _item.([]int)
+       for i := range item {
+               j := i + rand.Intn(len(item)-i)
+               item[i], item[j] = item[j], item[i]
+       }
+       me.sl.Set(key, item)
 }
 
 func (me *Instance) removeKeyPiece(key, piece int) {
-       if me.sl.Remove(key).Value.(int) != piece {
-               panic("piecekeys map lied to us")
+       item, ok := me.sl.Get(key)
+       if !ok {
+               panic("no item for key")
+       }
+       itemSl := item.([]int)
+       for i, piece1 := range itemSl {
+               if piece1 == piece {
+                       itemSl[i] = itemSl[len(itemSl)-1]
+                       itemSl = itemSl[:len(itemSl)-1]
+                       break
+               }
        }
-       if me.sl.Remove(key) != nil {
-               panic("duplicate key")
+       if len(itemSl) == 0 {
+               me.sl.Delete(key)
+       } else {
+               me.sl.Set(key, itemSl)
        }
 }
 
@@ -50,11 +81,11 @@ func (me *Instance) DeletePiece(piece int) {
 }
 
 func (me Instance) First() Element {
-       e := me.sl.Front()
-       if e == nil {
+       i := me.sl.SeekToFirst()
+       if i == nil {
                return nil
        }
-       return element{e}
+       return &element{i, i.Value().([]int)}
 }
 
 type Element interface {
@@ -63,17 +94,23 @@ type Element interface {
 }
 
 type element struct {
-       sle *skiplist.Element
+       i  skiplist.Iterator
+       sl []int
 }
 
-func (e element) Next() Element {
-       sle := e.sle.Next()
-       if sle == nil {
+func (e *element) Next() Element {
+       e.sl = e.sl[1:]
+       if len(e.sl) > 0 {
+               return e
+       }
+       ok := e.i.Next()
+       if !ok {
                return nil
        }
-       return element{sle}
+       e.sl = e.i.Value().([]int)
+       return e
 }
 
 func (e element) Piece() int {
-       return e.sle.Value.(int)
+       return e.sl[0]
 }

diff --git a/internal/pieceordering/pieceordering_test.go b/internal/pieceordering/pieceordering_test.go
index 59849ba6bc59f3aa4ce2906695a7bc526e5f5466..b2b19e11497bf4f823beec332386aefbe25fdea1 100644 (file)
--- a/internal/pieceordering/pieceordering_test.go
+++ b/internal/pieceordering/pieceordering_test.go
@@ -1,6 +1,7 @@
 package pieceordering
 
 import (
+       "sort"
        "testing"
 )
 
@@ -11,16 +12,34 @@ func instanceSlice(i *Instance) (sl []int) {
        return
 }
 
-func checkOrder(t *testing.T, i *Instance, pp []int) {
+func sameContents(a, b []int) bool {
+       if len(a) != len(b) {
+               panic("y u pass different length slices")
+       }
+       sort.IntSlice(a).Sort()
+       sort.IntSlice(b).Sort()
+       for i := range a {
+               if a[i] != b[i] {
+                       return false
+               }
+       }
+       return true
+}
+
+func checkOrder(t *testing.T, i *Instance, ppp ...[]int) {
        fatal := func() {
-               t.Fatalf("have %v, expected %v", instanceSlice(i), pp)
+               t.Fatalf("have %v, expected %v", instanceSlice(i), ppp)
        }
        e := i.First()
-       for _, p := range pp {
-               if p != e.Piece() {
+       for _, pp := range ppp {
+               var pp_ []int
+               for len(pp_) != len(pp) {
+                       pp_ = append(pp_, e.Piece())
+                       e = e.Next()
+               }
+               if !sameContents(pp, pp_) {
                        fatal()
                }
-               e = e.Next()
        }
        if e != nil {
                fatal()
@@ -47,7 +66,7 @@ func TestPieceOrdering(t *testing.T) {
        checkOrder(t, i, []int{3, 1, 2})
        // Move a piece that isn't the youngest in a key.
        i.SetPiece(1, -1)
-       checkOrder(t, i, []int{1, 3, 2})
+       checkOrder(t, i, []int{1}, []int{3, 2})
        i.DeletePiece(2)
        i.DeletePiece(3)
        i.DeletePiece(1)