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