1package list 2 3import ( 4 "bytes" 5 "encoding/binary" 6 "fmt" 7 "hash/fnv" 8 "log" 9 "sort" 10 "strings" 11) 12 13import ( 14 "github.com/timtadh/data-structures/errors" 15 "github.com/timtadh/data-structures/types" 16) 17 18type MList struct { 19 List 20 MarshalItem types.ItemMarshal 21 UnmarshalItem types.ItemUnmarshal 22} 23 24func NewMList(list *List, marshal types.ItemMarshal, unmarshal types.ItemUnmarshal) *MList { 25 return &MList{ 26 List: *list, 27 MarshalItem: marshal, 28 UnmarshalItem: unmarshal, 29 } 30} 31 32func (m *MList) MarshalBinary() ([]byte, error) { 33 items := make([][]byte, 0, m.Size()) 34 _cap := make([]byte, 4) 35 size := make([]byte, 4) 36 binary.LittleEndian.PutUint32(size, uint32(m.Size())) 37 if m.List.fixed { 38 binary.LittleEndian.PutUint32(_cap, uint32(cap(m.List.list))) 39 items = append(items, []byte{1}) 40 } else { 41 binary.LittleEndian.PutUint32(_cap, uint32(m.Size())) 42 items = append(items, []byte{0}) 43 } 44 items = append(items, _cap) 45 items = append(items, size) 46 for item, next := m.Items()(); next != nil; item, next = next() { 47 b, err := m.MarshalItem(item) 48 if err != nil { 49 return nil, err 50 } 51 size := make([]byte, 4) 52 binary.LittleEndian.PutUint32(size, uint32(len(b))) 53 items = append(items, size, b) 54 } 55 return bytes.Join(items, []byte{}), nil 56} 57 58func (m *MList) UnmarshalBinary(bytes []byte) error { 59 m.List.fixed = bytes[0] == 1 60 _cap := int(binary.LittleEndian.Uint32(bytes[1:5])) 61 size := int(binary.LittleEndian.Uint32(bytes[5:9])) 62 off := 9 63 m.list = make([]types.Hashable, 0, _cap) 64 for i := 0; i < size; i++ { 65 s := off 66 e := off + 4 67 size := int(binary.LittleEndian.Uint32(bytes[s:e])) 68 s = e 69 e = s + size 70 item, err := m.UnmarshalItem(bytes[s:e]) 71 if err != nil { 72 return err 73 } 74 m.Append(item) 75 off = e 76 } 77 return nil 78} 79 80type Sortable struct { 81 List 82} 83 84func NewSortable(list *List) sort.Interface { 85 return &Sortable{*list} 86} 87 88func (s *Sortable) Len() int { 89 return s.Size() 90} 91 92func (s *Sortable) Less(i, j int) bool { 93 a, err := s.Get(i) 94 if err != nil { 95 log.Panic(err) 96 } 97 b, err := s.Get(j) 98 if err != nil { 99 log.Panic(err) 100 } 101 return a.Less(b) 102} 103 104func (s *Sortable) Swap(i, j int) { 105 a, err := s.Get(i) 106 if err != nil { 107 log.Panic(err) 108 } 109 b, err := s.Get(j) 110 if err != nil { 111 log.Panic(err) 112 } 113 err = s.Set(i, b) 114 if err != nil { 115 log.Panic(err) 116 } 117 err = s.Set(j, a) 118 if err != nil { 119 log.Panic(err) 120 } 121} 122 123type List struct { 124 list []types.Hashable 125 fixed bool 126} 127 128// Creates a list. 129func New(initialSize int) *List { 130 return newList(initialSize, false) 131} 132 133// Creates a Fixed Size list. 134func Fixed(size int) *List { 135 return newList(size, true) 136} 137 138func newList(initialSize int, fixedSize bool) *List { 139 return &List{ 140 list: make([]types.Hashable, 0, initialSize), 141 fixed: fixedSize, 142 } 143} 144 145func FromSlice(list []types.Hashable) *List { 146 l := &List{ 147 list: make([]types.Hashable, len(list)), 148 } 149 copy(l.list, list) 150 return l 151} 152 153func (l *List) Copy() *List { 154 list := make([]types.Hashable, len(l.list), cap(l.list)) 155 copy(list, l.list) 156 return &List{list, l.fixed} 157} 158 159func (l *List) Clear() { 160 l.list = l.list[:0] 161} 162 163func (l *List) Size() int { 164 return len(l.list) 165} 166 167func (l *List) Full() bool { 168 return l.fixed && cap(l.list) == len(l.list) 169} 170 171func (l *List) Empty() bool { 172 return len(l.list) == 0 173} 174 175func (l *List) Has(item types.Hashable) (has bool) { 176 for i := range l.list { 177 if l.list[i].Equals(item) { 178 return true 179 } 180 } 181 return false 182} 183 184func (l *List) Equals(b types.Equatable) bool { 185 if o, ok := b.(types.IterableContainer); ok { 186 return Equals(l, o) 187 } else { 188 return false 189 } 190} 191 192func Equals(a, b types.IterableContainer) bool { 193 if a.Size() != b.Size() { 194 return false 195 } 196 ca, ai := a.Items()() 197 cb, bi := b.Items()() 198 for ai != nil || bi != nil { 199 if !ca.Equals(cb) { 200 return false 201 } 202 ca, ai = ai() 203 cb, bi = bi() 204 } 205 return true 206} 207 208func (l *List) Less(b types.Sortable) bool { 209 if o, ok := b.(types.IterableContainer); ok { 210 return Less(l, o) 211 } else { 212 return false 213 } 214} 215 216func Less(a, b types.IterableContainer) bool { 217 if a.Size() < b.Size() { 218 return true 219 } else if a.Size() > b.Size() { 220 return false 221 } 222 ca, ai := a.Items()() 223 cb, bi := b.Items()() 224 for ai != nil || bi != nil { 225 if ca.Less(cb) { 226 return true 227 } else if !ca.Equals(cb) { 228 return false 229 } 230 ca, ai = ai() 231 cb, bi = bi() 232 } 233 return false 234} 235 236func (l *List) Hash() int { 237 h := fnv.New32a() 238 if len(l.list) == 0 { 239 return 0 240 } 241 bs := make([]byte, 4) 242 for _, item := range l.list { 243 binary.LittleEndian.PutUint32(bs, uint32(item.Hash())) 244 h.Write(bs) 245 } 246 return int(h.Sum32()) 247} 248 249func Hash(a types.ListIterable) int { 250 h := fnv.New32a() 251 bs := make([]byte, 4) 252 for item, next := a.Items()(); next != nil; item, next = next() { 253 binary.LittleEndian.PutUint32(bs, uint32(item.Hash())) 254 h.Write(bs) 255 } 256 return int(h.Sum32()) 257} 258 259func (l *List) Items() (it types.KIterator) { 260 i := 0 261 return func() (item types.Hashable, next types.KIterator) { 262 if i < len(l.list) { 263 item = l.list[i] 264 i++ 265 return item, it 266 } 267 return nil, nil 268 } 269} 270 271func (l *List) ItemsInReverse() (it types.KIterator) { 272 i := len(l.list) - 1 273 return func() (item types.Hashable, next types.KIterator) { 274 if i >= 0 { 275 item = l.list[i] 276 i-- 277 return item, it 278 } 279 return nil, nil 280 } 281} 282 283func (l *List) Get(i int) (item types.Hashable, err error) { 284 if i < 0 || i >= len(l.list) { 285 return nil, errors.Errorf("Access out of bounds. len(*List) = %v, idx = %v", len(l.list), i) 286 } 287 return l.list[i], nil 288} 289 290func (l *List) Set(i int, item types.Hashable) (err error) { 291 if i < 0 || i >= len(l.list) { 292 return errors.Errorf("Access out of bounds. len(*List) = %v, idx = %v", len(l.list), i) 293 } 294 l.list[i] = item 295 return nil 296} 297 298func (l *List) Push(item types.Hashable) error { 299 return l.Append(item) 300} 301 302func (l *List) Append(item types.Hashable) error { 303 return l.Insert(len(l.list), item) 304} 305 306func (l *List) Insert(i int, item types.Hashable) error { 307 if i < 0 || i > len(l.list) { 308 return errors.Errorf("Access out of bounds. len(*List) = %v, idx = %v", len(l.list), i) 309 } 310 if len(l.list) == cap(l.list) { 311 if err := l.expand(); err != nil { 312 return err 313 } 314 } 315 l.list = l.list[:len(l.list)+1] 316 for j := len(l.list) - 1; j > 0; j-- { 317 if j == i { 318 l.list[i] = item 319 break 320 } 321 l.list[j] = l.list[j-1] 322 } 323 if i == 0 { 324 l.list[i] = item 325 } 326 return nil 327} 328 329func (l *List) Extend(it types.KIterator) (err error) { 330 for item, next := it(); next != nil; item, next = next() { 331 if err := l.Append(item); err != nil { 332 return err 333 } 334 } 335 return nil 336} 337 338func (l *List) Pop() (item types.Hashable, err error) { 339 item, err = l.Get(len(l.list) - 1) 340 if err != nil { 341 return nil, err 342 } 343 err = l.Remove(len(l.list) - 1) 344 if err != nil { 345 return nil, err 346 } 347 return item, nil 348} 349 350func (l *List) Remove(i int) error { 351 if i < 0 || i >= len(l.list) { 352 return errors.Errorf("Access out of bounds. len(*List) = %v, idx = %v", len(l.list), i) 353 } 354 dst := l.list[i : len(l.list)-1] 355 src := l.list[i+1 : len(l.list)] 356 copy(dst, src) 357 l.list = l.list[:len(l.list)-1] 358 if err := l.shrink(); err != nil { 359 return err 360 } 361 return nil 362} 363 364func (l *List) String() string { 365 if len(l.list) <= 0 { 366 return "{}" 367 } 368 items := make([]string, 0, len(l.list)) 369 for _, item := range l.list { 370 items = append(items, fmt.Sprintf("%v", item)) 371 } 372 return "{" + strings.Join(items, ", ") + "}" 373} 374 375func (l *List) expand() error { 376 if l.fixed { 377 return errors.Errorf("Fixed size list is full!") 378 } 379 list := l.list 380 if cap(list) < 100 && cap(list) != 0 { 381 l.list = make([]types.Hashable, len(list), cap(list)*2) 382 } else { 383 l.list = make([]types.Hashable, len(list), cap(list)+100) 384 } 385 copy(l.list, list) 386 return nil 387} 388 389func (l *List) shrink() error { 390 if l.fixed { 391 return nil 392 } 393 if (len(l.list)-1)*2 >= cap(l.list) || cap(l.list)/2 <= 10 { 394 return nil 395 } 396 list := l.list 397 l.list = make([]types.Hashable, len(list), cap(list)/2+1) 398 copy(l.list, list) 399 return nil 400} 401