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 Element interface{}
  13 type SeqChan chan Element
  14 type Sequence func()SeqChan
  15
  16 func IsSeq(s interface{}) bool {
  17         _, test := s.(Sequence)
  18         return test
  19 }
  20
  21 func Seq(f func(c SeqChan)) Sequence {
  22         return func() SeqChan {
  23                 c := make(SeqChan)
  24                 go func() {
  25                         f(c)
  26                         close(c)
  27                 }()
  28                 return c
  29         }
  30 }
  31
  32 func From(el... interface{}) Sequence {
  33         return Seq(func(c SeqChan) {Output(c, el...)})
  34 }
  35
  36 func Output(c SeqChan, el... interface{}) {
  37         for _, v := range el {
  38                 c <- v
  39         }
  40 }
  41
  42 func Bleed(c SeqChan) {
  43         for !closed(c) {
  44                 <- c
  45         }
  46 }
  47
  48 func (s Sequence) First() Element {
  49         c := s()
  50         defer Bleed(c)
  51         return <- c
  52 }
  53
  54 func (s Sequence) Rest() Sequence {
  55         return func()SeqChan{
  56                 c := s()
  57                 <- c
  58                 return c
  59         }
  60 }
  61
  62 func (s Sequence) AddFirst(els... interface{}) Sequence {
  63         return Seq(func(c SeqChan){
  64                 for el := range els {
  65                         c <- el
  66                 }
  67                 s.Output(c)
  68         })
  69 }
  70
  71 func (s Sequence) AddLast(els... interface{}) Sequence {
  72         return Seq(func(c SeqChan){
  73                 s.Output(c)
  74                 for el := range els {
  75                         c <- el
  76                 }
  77         })
  78 }
  79
  80 func (s Sequence) IsEmpty() bool {
  81         c := s()
  82         <- c
  83         result := closed(c)
  84         if !result {defer Bleed(c)}
  85         return result
  86 }
  87
  88 func (s Sequence) Append(s2 Sequence) Sequence {
  89         return Seq(func(c SeqChan){
  90                 s.Output(c)
  91                 s2.Output(c)
  92         })
  93 }
  94
  95 func (s Sequence) Len() int {
  96         len := 0
  97         c := s()
  98         for !closed(c) {
  99                 <- c
 100                 len++
 101         }
 102         return len - 1
 103 }
 104
 105 func (s Sequence) Output(c chan Element) {
 106         for el := range s() {
 107                 c <- el
 108         }
 109 }
 110
 111 func Upto(limit int) Sequence {
 112         return Seq(func(c SeqChan) {
 113                 for i := 0; i < limit; i++ {
 114                         c <- i
 115                 }
 116         })
 117 }
 118
 119 func (s Sequence) Filter(filter func(e Element)bool) Sequence {
 120         return Seq(func(c SeqChan){
 121                 for el := range s() {
 122                         if filter(el) {
 123                                 c <- el
 124                         }
 125                 }
 126         })
 127 }
 128
 129 func (s Sequence) Do(f func(el Element)) {
 130         for v := range s() {
 131                 f(v)
 132         }
 133 }
 134
 135 func (s Sequence) Map(f func(i Element)Element) Sequence {
 136         return Seq(func(c SeqChan) {
 137                 for v := range s() {
 138                         c <- f(v)
 139                 }
 140         })
 141 }
 142
 143 func (s Sequence) FlatMap(f func(i Element) Sequence) Sequence {
 144         return Seq(func(c SeqChan) {
 145                 for v := range s() {
 146                         for sub := range f(v)() {
 147                                 c <- sub
 148                         }
 149                 }
 150         })
 151 }
 152
 153 func (s Sequence) Fold(init Element, f func(acc, el Element)Element) Element {
 154         for el := range s() {
 155                 init = f(init, el)
 156         }
 157         return init
 158 }
 159
 160 //maybe convert this to use an accumulator instead of append?
 161 func (s Sequence) Combinations(number int) Sequence {
 162         if number == 0 || s.IsEmpty() {return From(From())}
 163         return s.Rest().Combinations(number - 1).Map(func(el Element)Element{
 164                 return el.(Sequence).AddFirst(s.First())
 165         }).Append(s.Rest().Combinations(number))
 166 }
 167
 168 //returns the product of the Sequences contained in sequences
 169 func (sequences Sequence) Product() Sequence {
 170         return sequences.Fold(From(From()), func(acc, el Element)Element{
 171                 return el.(Sequence).peelOnto(acc.(Sequence))
 172         }).(Sequence)
 173 }
 174
 175 func (s Sequence) peelOnto(seq Sequence) Sequence {
 176         return seq.FlatMap(func(old Element)Sequence{
 177                 return s.Map(func(i Element) Element {
 178                         return old.(Sequence).Append(From(i))
 179                 })
 180         })
 181 }
 182
 183 func (s Sequence) Reify() Sequence {
 184         vec := vector.Vector(make([]interface{}, 0, 128))
 185         for v := range s() {
 186                 sv, is := v.(Sequence)
 187                 if is {
 188                         vec.Push(sv.Reify())
 189                 } else {
 190                         vec.Push(v)
 191                 }
 192         }
 193         return From([]interface{}(vec)...)
 194 }
 195
 196 func (s Sequence) Prettyln(names map[Element]string, writer... io.Writer) {
 197         if len(writer) == 0 {
 198                 writer = []io.Writer{os.Stdout}
 199         }
 200         s.Pretty(names, writer...)
 201         fmt.Fprintln(writer[0])
 202 }
 203 func (s Sequence) Pretty(names map[Element]string, writer... io.Writer) {
 204         if len(writer) == 0 {
 205                 writer = []io.Writer{os.Stdout}
 206         }
 207         s.prettyLevel(0, names, writer[0])
 208 }
 209
 210 //This is pretty ugly :)
 211 func (s Sequence) prettyLevel(level int, names map[Element]string, w io.Writer) {
 212         name, hasName := names[s]
 213         if hasName {
 214                 fmt.Fprint(w, name)
 215         } else {
 216                 c := s()
 217                 fmt.Fprintf(w, "%*s%s", level, "", "[")
 218                 first := true
 219                 innerSeq := false
 220                 named := false
 221                 for v := range c {
 222                         _, named = names[v]
 223                         _,innerSeq = v.(Sequence)
 224                         if first {
 225                                 first = false
 226                                 if !named && innerSeq {
 227                                         fmt.Fprintln(w)
 228                                 }
 229                         } else if !named && innerSeq {
 230                                 fmt.Fprintln(w, ",")
 231                         } else {
 232                                 fmt.Fprint(w, ", ")
 233                         }
 234                         if innerSeq {
 235                                 v.(Sequence).prettyLevel(level + 4, names, w)
 236                         } else {
 237                                 fmt.Fprintf(w, "%v", v)
 238                         }
 239                 }
 240                 if innerSeq {
 241                         if !named {
 242                                 fmt.Fprintf(w, "\n%*s", level, "")
 243                         }
 244                 }
 245                 fmt.Fprintf(w, "]")
 246         }
 247 }