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