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 uint;
 178         result El
 179 }
 180
 181 // create and return an output channel
 182 // spawn a goroutine that does the following for each of up to 64 values:
 183 //   spawn a goroutine to apply f to the value and send the result back in a channel
 184 // send the results in order to the ouput channel as they are completed
 185 // then, close the channel
 186 func bulkMap(values []interface{}, f func(el El) El) SeqChan {
 187         output := make(SeqChan, len(values))
 188         go func(){
 189                 received := int64(0)
 190                 replyChannel := make(chan reply)
 191                 results := make([]interface{}, len(values))
 192                 for i,v := range values {
 193                         go func(index uint, value interface{}) {
 194                                 replyChannel <- reply{index, f(value)}
 195                         }(uint(i), v)
 196                 }
 197                 for expect := 0; expect < len(values); {
 198                         rep := <- replyChannel
 199                         received |= (1 << rep.index)
 200                         results[rep.index] = rep.result
 201                         for ; (1 << uint(expect)) & received != 0; expect++ {
 202                                 output <- results[expect]
 203                         }
 204                 }
 205                 close(output)
 206         }()
 207         return output
 208 }
 209
 210 func CMap(s Seq, f func(el El) El) Seq {
 211         return Gen(func(c SeqChan) {
 212                 Do(s, func(v El){c <- f(v)})
 213         })
 214 }
 215
 216 func FlatMap(s Seq, f func(el El) Seq) Seq {return s.FlatMap(f)}
 217
 218 func SFlatMap(s Seq, f func(i El) Seq) Seq {
 219         vec := make(vector.Vector, 0, quickLen(s, 8))
 220         Do(s, func(el El){
 221                 Do(f(el), func(sub El){vec.Push(sub)})
 222         })
 223         return (*SequentialSeq)(&vec)
 224 }
 225
 226 func CFlatMap(s Seq, f func(i El) Seq) Seq {
 227         return Gen(func(c SeqChan) {
 228                 Do(s, func(v El){
 229                         Do(f(v), func(sub El){c <- sub})
 230                 })
 231         })
 232 }
 233
 234 func Fold(s Seq, init interface{}, f func(acc, el El)El) interface{} {
 235         Do(s, func(el El){init = f(init, el)})
 236         return init
 237 }
 238
 239 //maybe convert this to use an accumulator instead of append?
 240 func Combinations(s Seq, number int) Seq {
 241         if number == 0 || IsEmpty(s) {return From(From())}
 242         return Combinations(s.Rest(), number).Prepend(Combinations(s.Rest(), number - 1).Map(func(el El)El{
 243                 return el.(Seq).Prepend(From(First(s)))
 244         }))
 245 }
 246
 247 //returns the product of the Seqs contained in sequences
 248 func Product(sequences Seq) Seq {
 249         return Fold(sequences, From(From()), func(result, each El)El{
 250 //fmt.Print("folding: ");Pretty(each);fmt.Print(" into ");Prettyln(result)
 251                 return result.(Seq).FlatMap(func(seq El)Seq{
 252 //fmt.Print("flat map with: ");Prettyln(seq)
 253                         return each.(Seq).Map(func(i El) El {
 254 //fmt.Print("map with: ");Prettyln(i)
 255                                 return seq.(Seq).Append(From(i))
 256                         })
 257                 })
 258         }).(Seq)
 259 }
 260
 261 func Prettyln(s interface{}, rest... interface{}) {
 262         writer := Pretty(s, rest...)
 263         fmt.Fprintln(writer)
 264 }
 265 func Pretty(s interface{}, args... interface{}) io.Writer {
 266         var writer io.Writer = os.Stdout
 267         var names map[interface{}]string
 268         for i := 0; i < len(args); i++ {
 269                 switch arg := args[i].(type) {
 270                 case map[interface{}]string: names = arg
 271                 case io.Writer: writer = arg
 272                 }
 273         }
 274         if names == nil {names = map[interface{}]string{}}
 275         prettyLevel(s, 0, names, writer)
 276         return writer
 277 }
 278
 279 //This is pretty ugly :)
 280 func prettyLevel(s interface{}, level int, names map[interface{}]string, w io.Writer) {
 281         name, hasName := names[s]
 282         if hasName {
 283                 fmt.Fprint(w, name)
 284         } else switch arg := s.(type) {
 285         case Seq:
 286                 fmt.Fprintf(w, "%*s%s", level, "", "[")
 287                 first := true
 288                 innerSeq := false
 289                 named := false
 290                 Do(arg, func(v El) {
 291                         _, named = names[v]
 292                         _,innerSeq = v.(Seq)
 293                         if first {
 294                                 first = false
 295                                 if !named && innerSeq {
 296                                         fmt.Fprintln(w)
 297                                 }
 298                         } else if !named && innerSeq {
 299                                 fmt.Fprintln(w, ",")
 300                         } else {
 301                                 fmt.Fprint(w, ", ")
 302                         }
 303                         if innerSeq {
 304                                 prettyLevel(v.(Seq), level + 4, names, w)
 305                         } else {
 306                                 fmt.Fprintf(w, "%v", v)
 307                         }
 308                 })
 309                 if innerSeq {
 310                         if !named {
 311                                 fmt.Fprintf(w, "\n%*s", level, "")
 312                         }
 313                 }
 314                 fmt.Fprintf(w, "]")
 315         default:
 316                 fmt.Print(arg)
 317         }
 318 }
 319
 320 //ConcurrentSeq
 321
 322 type SeqChan chan interface{}
 323
 324 type ConcurrentSeq func()SeqChan
 325
 326 // f must behave properly when the channel is closed, so that IsEmpty and First work properly
 327 func Gen(f func(c SeqChan)) ConcurrentSeq {
 328         return func() SeqChan {
 329                 c := make(SeqChan)
 330                 go func() {
 331                         defer close(c)
 332                         f(c)
 333                 }()
 334                 return c
 335         }
 336 }
 337
 338 func CUpto(limit int) ConcurrentSeq {
 339         return Gen(func(c SeqChan) {
 340                 for i := 0; i < limit; i++ {
 341                         c <- i
 342                 }
 343         })
 344 }
 345
 346 func (s ConcurrentSeq) While(f func(el El)bool) {
 347         c := s()
 348         defer close(c)
 349         for el := <- c; !closed(c) && f(el); el = <- c {}
 350 }
 351
 352 func (s ConcurrentSeq) Rest() Seq {
 353         return ConcurrentSeq(func()SeqChan{
 354                 c := s()
 355                 <- c
 356                 return c
 357         })
 358 }
 359
 360 func (s ConcurrentSeq) Len() int {
 361         len := 0
 362         Do(s, func(el El){
 363                 len++
 364         })
 365         return len
 366 }
 367
 368 func (s ConcurrentSeq) Append(s2 Seq) Seq {return CAppend(s, s2)}
 369
 370 func (s ConcurrentSeq) Prepend(s2 Seq) Seq {return CAppend(s2, s)}
 371
 372 func (s ConcurrentSeq) Filter(f func(e El)bool) Seq {return CFilter(s, f)}
 373
 374 func (s ConcurrentSeq) Map(f func(i El)El) Seq {return CMap(s, f)}
 375
 376 func (s ConcurrentSeq) FlatMap(f func(i El) Seq) Seq {return CFlatMap(s, f)}
 377
 378 func toSequentialSeq(el interface{}) interface{} {
 379         switch seq := el.(type) {
 380         case ConcurrentSeq: return seq.ToSequentialSeq()
 381         case []interface{}:
 382                 cpy := make([]interface{}, len(seq))
 383                 copy(cpy, seq)
 384                 return cpy
 385         }
 386         return el
 387 }
 388
 389 func (s ConcurrentSeq) ToSequentialSeq() *SequentialSeq {
 390         vec := make(vector.Vector, 0, 8)
 391         Do(s, func(v El){vec.Push(toSequentialSeq(v))})
 392         return (*SequentialSeq)(&vec)
 393 }
 394
 395
 396 // SequentialSeq
 397
 398 type SequentialSeq []interface{}
 399
 400 func From(els... interface{}) *SequentialSeq {return (*SequentialSeq)(&els)}
 401
 402 func AUpto(limit int) *SequentialSeq {
 403         a := make([]interface{}, limit)
 404         for i := 0; i < limit; i++ {
 405                 a[i] = i
 406         }
 407         return (*SequentialSeq)(&a)
 408 }
 409
 410 func (s *SequentialSeq) While(f func(el El)bool) {
 411         for i := 0; i < len(*s) && f((*s)[i]); i++ {}
 412 }
 413
 414 func (s *SequentialSeq) Rest() Seq {
 415         s2 := (*s)[1:]
 416         return (*SequentialSeq)(&s2)
 417 }
 418
 419 func (s *SequentialSeq) Len() int {return len(*s)}
 420
 421 func (s *SequentialSeq) Append(s2 Seq) Seq {return SAppend(s, s2)}
 422
 423 func (s *SequentialSeq) Prepend(s2 Seq) Seq {return SAppend(s2, s)}
 424
 425 func (s *SequentialSeq) Filter(f func(e El)bool) Seq {return SFilter(s, f)}
 426
 427 func (s *SequentialSeq) Map(f func(i El)El) Seq {return SMap(s, f)}
 428
 429 func (s *SequentialSeq) FlatMap(f func(i El) Seq) Seq {return SFlatMap(s, f)}