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