seq/seq.go

   1 // Copyright 2010 Bill Burdick. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4 //
   5 package seq
   6
   7 import "fmt"
   8 import "io"
   9 import "os"
  10 import "container/vector"
  11
  12 // convenience alias for sequence elements
  13 type El interface{}
  14 // basic sequence support
  15 type Seq interface {
  16         Find(f func(i El)bool) El
  17         Rest() Seq
  18         Len() int
  19         Append(s2 Seq) Seq
  20         Prepend(s2 Seq) Seq
  21         Filter(filter func(e El) bool) Seq
  22         Map(f func(i El) El) Seq
  23         FlatMap(f func(i El) Seq) Seq
  24 }
  25
  26 //convert a sequence to a concurrent sequence (if necessary)
  27 func Concurrent(s Seq) ConcurrentSeq {
  28         switch seq := s.(type) {case ConcurrentSeq: return seq}
  29         return Gen(func(c SeqChan){Output(s, c)})
  30 }
  31
  32 //convert a sequence to a sequential sequence (if necessary)
  33 func Sequential(s Seq) *SequentialSeq {
  34         switch seq := s.(type) {case *SequentialSeq: return seq}
  35         return SMap(s, func(el El)El{return el})
  36 }
  37
  38 //returns a new array of the first N items
  39 func FirstN(s Seq, n int) []interface{} {
  40         r := make([]interface{}, n)
  41         x := 0
  42         Find(s, func(el El)bool{
  43                 r[x] = el
  44                 x++
  45                 return x == n
  46         })
  47         return r
  48 }
  49
  50 //convenience function with multiple return values
  51 func First2(s Seq) (a, b interface{}) {
  52         r := FirstN(s, 2)
  53         return r[0], r[1]
  54 }
  55
  56 //convenience function with multiple return values
  57 func First3(s Seq) (a, b, c interface{}) {
  58         r := FirstN(s, 3)
  59         return r[0], r[1], r[2]
  60 }
  61
  62 //convenience function with multiple return values
  63 func First4(s Seq) (a, b, c, d interface{}) {
  64         r := FirstN(s, 4)
  65         return r[0], r[1], r[2], r[3]
  66 }
  67
  68 //convenience function with multiple return values
  69 func First5(s Seq) (a, b, c, d, e interface{}) {
  70         r := FirstN(s, 5)
  71         return r[0], r[1], r[2], r[3], r[4]
  72 }
  73
  74 //convenience function with multiple return values
  75 func First6(s Seq) (a, b, c, d, e, f interface{}) {
  76         r := FirstN(s, 6)
  77         return r[0], r[1], r[2], r[3], r[4], r[5]
  78 }
  79
  80 //returns whether s can be interpreted as a sequence
  81 func IsSeq(s interface{}) bool {
  82         _, test := s.(Seq)
  83         return test
  84 }
  85
  86 //returns the first item in a sequence
  87 func First(s Seq) interface{} {
  88         var result interface{}
  89         s.Find(func(el El)bool{
  90                 result = el
  91                 return true
  92         })
  93         return result
  94 }
  95
  96 //returns whether a sequence is empty
  97 func IsEmpty(s Seq) bool {
  98         empty := true
  99         s.Find(func(el El)bool{
 100                 empty = false
 101                 return true
 102         })
 103         return empty
 104 }
 105
 106 //returns the first item in a sequence for which f returns true
 107 func Find(s Seq, f func(el El) bool) El {return s.Find(f)}
 108
 109 //applies f to each item in the sequence until f returns false
 110 func While(s Seq, f func(el El) bool) {s.Find(func(el El)bool{return !f(el)})}
 111
 112 //applies f to each item in the sequence
 113 func Do(s Seq, f func(el El)) {
 114         s.Find(func(el El)bool{
 115                 f(el)
 116                 return false
 117         })
 118 }
 119
 120 //applies f concurrently to each element of s, in no particular order
 121 func CDo(s Seq, f func(el El)) {
 122         c := CMap(s, func(el El)El{f(el); return nil})()
 123         for <- c; !closed(c); <- c {}
 124 }
 125
 126 //returns the length of s
 127 func Len(s Seq) int {return s.Len()}
 128
 129 //sends each item of s to c
 130 func Output(s Seq, c SeqChan) {Do(s, func(el El){c <- el})}
 131
 132 //returns a new sequence of the same type as s consisting of all of the elements of s except for the first one
 133 func Rest(s Seq) Seq {return s.Rest()}
 134
 135 //returns a new sequence of the same type as s1 that appends this s1 and s2
 136 func Append(s1 Seq, s2 Seq) Seq {return s1.Append(s2)}
 137
 138 //append a sequence to a vector
 139 func AppendToVector(vec *vector.Vector, s Seq) {
 140         switch arg := s.(type) {
 141         case *SequentialSeq: vec.AppendVector((*vector.Vector)(arg))
 142         default: Do(s, func(el El){vec.Push(el)})
 143         }
 144 }
 145
 146 //returns a new SequentialSeq which consists of appending s and s2
 147 func SAppend(s Seq, s2 Seq) *SequentialSeq {
 148         vec := make(vector.Vector, 0, quickLen(s, 8) + quickLen(s2, 8))
 149         AppendToVector(&vec, s)
 150         AppendToVector(&vec, s2)
 151         return (*SequentialSeq)(&vec)
 152 }
 153
 154 //returns a new ConcurrentSeq which consists of appending s and s2
 155 func CAppend(s Seq, s2 Seq) ConcurrentSeq {
 156         return Gen(func(c SeqChan){
 157                 Output(s, c)
 158                 Output(s2, c)
 159         })
 160 }
 161
 162 func quickLen(s Seq, d int) int {
 163         switch seq := s.(type) {case *SequentialSeq: return s.Len()}
 164         return d
 165 }
 166
 167 //returns a new sequence of the same type as s consisting of the elements of s for which filter returns true
 168 func Filter(s Seq, filter func(e El)bool) Seq {return s.Filter(filter)}
 169
 170 func ifFunc(condition func(e El)bool, op func(e El)) func(el El){return func(el El){if condition(el) {op(el)}}}
 171
 172 //returns a new SequentialSeq consisting of the elements of s for which filter returns true
 173 func SFilter(s Seq, filter func(e El)bool) *SequentialSeq {
 174         //continue shrinking
 175         vec := make(vector.Vector, 0, quickLen(s, 8))
 176         Do(s, ifFunc(filter, func(el El){vec.Push(el)}))
 177         return (*SequentialSeq)(&vec)
 178 }
 179
 180 //returns a new ConcurrentSeq consisting of the elements of s for which filter returns true
 181 func CFilter(s Seq, filter func(e El)bool) ConcurrentSeq {
 182         return Gen(func(c SeqChan){
 183                 Do(s, ifFunc(filter, func(el El){c <- el}))
 184         })
 185 }
 186
 187 //returns a new sequence of the same type as s consisting of the results of appying f to the elements of s
 188 func Map(s Seq, f func(el El) El) Seq {return s.Map(f)}
 189
 190 //returns a new SequentialSeq consisting of the results of appying f to the elements of s
 191 func SMap(s Seq, f func(i El)El) *SequentialSeq {
 192         vec := make(vector.Vector, 0, quickLen(s, 8))
 193         Do(s, func(el El){vec.Push(f(el))})
 194         return (*SequentialSeq)(&vec)
 195 }
 196
 197 type reply struct {
 198         index int;
 199         result El
 200 }
 201
 202 type swEntry struct {
 203         value El
 204         present bool
 205 }
 206
 207 // a vector with limited capacity (power of 2) and a base
 208 type SlidingWindow struct {
 209         start, base, count, mask int
 210         values []swEntry
 211 }
 212 //creates a new SlidingWindow with capacity size
 213 func NewSlidingWindow(sz uint) *SlidingWindow {return &SlidingWindow{0, 0, 0, (1 << sz) - 1, make([]swEntry, 1 << sz)}}
 214 //returns the current maximum available index
 215 func (r *SlidingWindow) Max() int {return r.base + r.Capacity() - 1}
 216 //returns the size of the window
 217 func (r *SlidingWindow) Capacity() int {return len(r.values)}
 218 func (r *SlidingWindow) normalize(index int) int {return (index + r.Capacity()) & r.mask}
 219 //returns whether the window is empty
 220 func (r *SlidingWindow) IsEmpty() bool {return r.count == 0}
 221 //returns whether the window has any available space
 222 func (r *SlidingWindow) IsFull() bool {return r.count == r.Capacity()}
 223 //returns the first item, or nil if there is none, and also returns whether there was an item
 224 func (r *SlidingWindow) GetFirst() (interface{}, bool) {return r.values[r.start].value, r.values[r.start].present}
 225 //removes the first item, if there is one, and also returns whether an item was removed
 226 func (r *SlidingWindow) RemoveFirst() (interface{}, bool) {
 227         result := r.values[r.start]
 228         if !result.present {return nil, false}
 229         r.values[r.start] = swEntry{nil, false}
 230         r.count--
 231         r.start = r.normalize(r.start + 1)
 232         r.base++
 233         return result.value, true
 234 }
 235 //returns item at index, if there is one, and also returns whether an item was there
 236 func (r *SlidingWindow) Get(index int) (interface{}, bool) {
 237         index -= r.base
 238         if index < 0 || index >= r.Capacity() {return nil, false}
 239         index = r.normalize(index + r.start)
 240         value := r.values[index]
 241         return value.value, value.present
 242 }
 243 //sets the item at index to value, if the space is available, and also returns whether an item was set
 244 func (r *SlidingWindow) Set(index int, value interface{}) bool {
 245         index -= r.base
 246         if index < 0 || index >= r.Capacity() {return false}
 247         index = r.normalize(index + r.start)
 248         r.values[index].value = value
 249         if !r.values[index].present {
 250                 r.values[index].present = true
 251                 r.count++
 252         }
 253         return true
 254 }
 255
 256 //returns a new ConcurrentSeq consisting of the results of appying f to the elements of s
 257 func CMap(s Seq, f func(el El) El, sizePowerOpt... uint) ConcurrentSeq {
 258 // spawn a goroutine that does the following for each value, with up to size pending at a time:
 259 //   spawn a goroutine to apply f to the value and send the result back in a channel
 260 // send the results in order to the ouput channel as they are completed
 261         sizePower := uint(6)
 262         if len(sizePowerOpt) > 0 {sizePower = sizePowerOpt[0]}
 263         size := 1 << sizePower
 264         return Gen(func(output SeqChan){
 265                 //punt and convert sequence to concurrent
 266                 //maybe someday we'll handle SequentialSequences separately
 267                 input := Concurrent(s)()
 268                 window := NewSlidingWindow(sizePower)
 269                 replyChannel := make(chan reply)
 270                 inputCount, pendingInput, pendingOutput := 0, 0, 0
 271                 inputClosed := false
 272                 defer close(replyChannel)
 273                 for !inputClosed || pendingInput > 0 || pendingOutput > 0 {
 274                         first, hasFirst := window.GetFirst()
 275                         ic, oc, rc := input, output, replyChannel
 276                         if !hasFirst {oc = nil}
 277                         if inputClosed || pendingInput >= size {ic = nil}
 278                         if pendingOutput >= size {rc = nil}
 279                         select {
 280                         case oc <- first:
 281                                 window.RemoveFirst()
 282                                 pendingOutput--
 283                         case inputElement := <- ic:
 284                                 if closed(ic) {
 285                                         inputClosed = true
 286                                 } else {
 287                                         go func(index int, value interface{}) {
 288                                                 replyChannel <- reply{index, f(value)}
 289                                         }(inputCount, inputElement)
 290                                         inputCount++
 291                                         pendingInput++
 292                                 }
 293                         case replyElement := <- rc:
 294                                 window.Set(replyElement.index, replyElement.result)
 295                                 pendingInput--
 296                                 pendingOutput++
 297                         }
 298                 }
 299         })
 300 }
 301
 302 //returns a new sequence of the same type as s consisting of the concatenation of the sequences f returns when applied to all of the elements of s
 303 func FlatMap(s Seq, f func(el El) Seq) Seq {return s.FlatMap(f)}
 304
 305 //returns a new SequentialSeq consisting of the concatenation of the sequences f returns when applied to all of the elements of s
 306 func SFlatMap(s Seq, f func(i El) Seq) *SequentialSeq {
 307         vec := make(vector.Vector, 0, quickLen(s, 8))
 308         Do(s, func(e El){Do(f(e).(Seq), func(sub El){vec.Push(sub)})})
 309         return (*SequentialSeq)(&vec)
 310 }
 311
 312 //returns a new ConcurrentSeq consisting of the concatenation of the sequences f returns when applied to all of the elements of s
 313 func CFlatMap(s Seq, f func(i El) Seq, sizeOpt... uint) ConcurrentSeq {
 314         return Gen(func(c SeqChan){
 315                 Do(CMap(s, func(e El)El{return f(e)}, sizeOpt...), func(sub El){
 316                         Output(sub.(Seq), c)
 317                 })
 318         })
 319 }
 320
 321 //returns the result of applying f to its previous value and each element of s in succession, starting with init as the initial "previous value" for f
 322 func Fold(s Seq, init interface{}, f func(acc, el El)El) interface{} {
 323         Do(s, func(el El){init = f(init, el)})
 324         return init
 325 }
 326
 327 //returns a new sequence of the same type as s consisting of all possible combinations of the elements of s of size number or smaller
 328 func Combinations(s Seq, number int) Seq {
 329         if number == 0 || IsEmpty(s) {return From(From())}
 330         return Combinations(s.Rest(), number).Prepend(Combinations(s.Rest(), number - 1).Map(func(el El)El{
 331                 return el.(Seq).Prepend(From(First(s)))
 332         }))
 333 }
 334
 335 //returns the product of the elements of sequences, where each element is a sequence
 336 func Product(sequences Seq) Seq {
 337         return Fold(sequences, From(From()), func(result, each El)El{
 338                 return result.(Seq).FlatMap(func(seq El)Seq{
 339                         return each.(Seq).Map(func(i El) El {
 340                                 return seq.(Seq).Append(From(i))
 341                         })
 342                 })
 343         }).(Seq)
 344 }
 345
 346 //pretty print an object, followed by a newline.  Optional arguments are a map of names (map[interface{}]string) and an io.Writer to write output to
 347 func Prettyln(s interface{}, rest... interface{}) {
 348         writer := Pretty(s, rest...)
 349         fmt.Fprintln(writer)
 350 }
 351 //pretty print an object.  Optional arguments are a map of names (map[interface{}]string) and an io.Writer to write output to
 352 func Pretty(s interface{}, args... interface{}) io.Writer {
 353         var writer io.Writer = os.Stdout
 354         var names map[interface{}]string
 355         for i := 0; i < len(args); i++ {
 356                 switch arg := args[i].(type) {
 357                 case map[interface{}]string: names = arg
 358                 case io.Writer: writer = arg
 359                 }
 360         }
 361         if names == nil {names = map[interface{}]string{}}
 362         prettyLevel(s, 0, names, writer)
 363         return writer
 364 }
 365
 366 //This pretty is ugly :)
 367 func prettyLevel(s interface{}, level int, names map[interface{}]string, w io.Writer) {
 368         name, hasName := names[s]
 369         if hasName {
 370                 fmt.Fprint(w, name)
 371         } else switch arg := s.(type) {
 372         case Seq:
 373                 fmt.Fprintf(w, "%*s%s", level, "", "[")
 374                 first := true
 375                 innerSeq := false
 376                 named := false
 377                 Do(arg, func(v El) {
 378                         _, named = names[v]
 379                         _,innerSeq = v.(Seq)
 380                         if first {
 381                                 first = false
 382                                 if !named && innerSeq {
 383                                         fmt.Fprintln(w)
 384                                 }
 385                         } else if !named && innerSeq {
 386                                 fmt.Fprintln(w, ",")
 387                         } else {
 388                                 fmt.Fprint(w, ", ")
 389                         }
 390                         if innerSeq {
 391                                 prettyLevel(v.(Seq), level + 4, names, w)
 392                         } else {
 393                                 fmt.Fprintf(w, "%v", v)
 394                         }
 395                 })
 396                 if innerSeq {
 397                         if !named {
 398                                 fmt.Fprintf(w, "\n%*s", level, "")
 399                         }
 400                 }
 401                 fmt.Fprintf(w, "]")
 402         default:
 403                 fmt.Print(arg)
 404         }
 405 }
 406
 407
 408 //a channel which can transport sequence elements
 409 type SeqChan chan interface{}
 410
 411 //A concurrent sequence.  You can call it to get a channel on a new goroutine, but you must make sure you read all of the items from the channel or else close it
 412 type ConcurrentSeq func()SeqChan
 413
 414 //returns a new ConcurrentSeq which consists of all of the items that f writes to the channel
 415 func Gen(f func(c SeqChan)) ConcurrentSeq {
 416         return func() SeqChan {
 417                 c := make(SeqChan)
 418                 go func() {
 419                         defer close(c)
 420                         f(c)
 421                 }()
 422                 return c
 423         }
 424 }
 425
 426 //returns a new ConcurrentSeq consisting of the numbers from 0 to limit, in succession
 427 func CUpto(limit int) ConcurrentSeq {
 428         return Gen(func(c SeqChan) {
 429                 for i := 0; i < limit; i++ {
 430                         c <- i
 431                 }
 432         })
 433 }
 434
 435 //returns the first item in a sequence for which f returns true
 436 func (s ConcurrentSeq) Find(f func(el El)bool) El {
 437         c := s()
 438         defer close(c)
 439         for el := <- c; !closed(c) ; el = <- c {
 440                 if f(el) {return el}
 441         }
 442         return nil
 443 }
 444
 445 //returns a new ConcurrentSeq consisting of all of the elements of s except for the first one
 446 func (s ConcurrentSeq) Rest() Seq {
 447         return ConcurrentSeq(func()SeqChan{
 448                 c := s()
 449                 <- c
 450                 return c
 451         })
 452 }
 453
 454 //returns the length of s
 455 func (s ConcurrentSeq) Len() int {
 456         len := 0
 457         Do(s, func(el El){
 458                 len++
 459         })
 460         return len
 461 }
 462
 463 //returns a new ConcurrentSeq that appends this one and s2
 464 func (s ConcurrentSeq) Append(s2 Seq) Seq {return CAppend(s, s2)}
 465
 466 //returns a new ConcurrentSeq that appends s2 and this one
 467 func (s ConcurrentSeq) Prepend(s2 Seq) Seq {return CAppend(s2, s)}
 468
 469 //returns a new ConcurrentSeq consisting of the elements of s for which filter returns true
 470 func (s ConcurrentSeq) Filter(f func(e El)bool) Seq {return CFilter(s, f)}
 471
 472 //returns a new ConcurrentSeq consisting of the results of appying f to the elements of s
 473 func (s ConcurrentSeq) Map(f func(i El)El) Seq {return CMap(s, f)}
 474
 475 //returns a new ConcurrentSeq consisting of the concatenation of the sequences f returns when applied to all of the elements of s
 476 func (s ConcurrentSeq) FlatMap(f func(i El) Seq) Seq {return CFlatMap(s, f)}
 477
 478 //returns a new SequentialSeq constructed by recursively converting nested
 479 //ConcurrentSeqs to SequentialSeqs.  Does not descend into nested sequential sequences
 480 func (s ConcurrentSeq) ToSequentialSeq() *SequentialSeq {
 481         return SMap(s, func(el El)El{
 482                 switch seq := el.(type) {case ConcurrentSeq: return seq.ToSequentialSeq()}
 483                 return el
 484         })
 485 }
 486
 487
 488 // a sequential sequence
 489 type SequentialSeq []interface{}
 490
 491 //returns a new SequentialSeq consisting of els
 492 func From(els... interface{}) *SequentialSeq {return (*SequentialSeq)(&els)}
 493
 494 //returns a new SequentialSeq consisting of the numbers from 0 to limit, in succession
 495 func AUpto(limit int) *SequentialSeq {
 496         a := make([]interface{}, limit)
 497         for i := 0; i < limit; i++ {
 498                 a[i] = i
 499         }
 500         return (*SequentialSeq)(&a)
 501 }
 502
 503 //returns the first item in a sequence for which f returns true
 504 func (s *SequentialSeq) Find(f func(el El)bool) El {
 505         for i := 0; i < len(*s); i++ {
 506                 if f((*s)[i]) {return (*s)[i]}
 507         }
 508         return nil
 509 }
 510
 511 //returns a new SequentialSeq consisting of all of the elements of s except for the first one
 512 func (s *SequentialSeq) Rest() Seq {
 513         s2 := (*s)[1:]
 514         return (*SequentialSeq)(&s2)
 515 }
 516
 517 //returns the length of s
 518 func (s *SequentialSeq) Len() int {return len(*s)}
 519
 520 //returns a new SequentialSeq that appends this one and s2
 521 func (s *SequentialSeq) Append(s2 Seq) Seq {return SAppend(s, s2)}
 522
 523 //returns a new SequentialSeq that appends s2 and this one
 524 func (s *SequentialSeq) Prepend(s2 Seq) Seq {return SAppend(s2, s)}
 525
 526 //returns a new SequentialSeq consisting of the elements of s for which filter returns true
 527 func (s *SequentialSeq) Filter(f func(e El)bool) Seq {return SFilter(s, f)}
 528
 529 //returns a new SequentialSeq consisting of the results of appying f to the elements of s
 530 func (s *SequentialSeq) Map(f func(i El)El) Seq {return SMap(s, f)}
 531
 532 //returns a new SequentialSeq consisting of the concatenation of the sequences f returns when applied to all of the elements of s
 533 func (s *SequentialSeq) FlatMap(f func(i El) Seq) Seq {return SFlatMap(s, f)}