1// Vector.h
2//
3// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
4//
5// Permission is hereby granted, free of charge, to any person obtaining a
6// copy of this software and associated documentation files (the "Software"),
7// to deal in the Software without restriction, including without limitation
8// the rights to use, copy, modify, merge, publish, distribute, sublicense,
9// and/or sell copies of the Software, and to permit persons to whom the
10// Software is furnished to do so, subject to the following conditions:
11//
12// The above copyright notice and this permission notice shall be included in
13// all copies or substantial portions of the Software.
14//
15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21// DEALINGS IN THE SOFTWARE.
22//
23// Except as contained in this notice, the name of a copyright holder shall
24// not be used in advertising or otherwise to promote the sale, use or other
25// dealings in this Software without prior written authorization of the
26// copyright holder.
27
28#ifndef _VECTOR_H
29#define _VECTOR_H
30
31#include <new>
32#include <stdlib.h>
33#include <string.h>
34
35#include <SupportDefs.h>
36
37template<typename Value> class VectorIterator;
38
39// for convenience
40#define _VECTOR_TEMPLATE_LIST template<typename Value>
41#define _VECTOR_CLASS_NAME Vector<Value>
42
43/*!
44	\class Vector
45	\brief A generic vector implementation.
46*/
47template<typename Value>
48class Vector {
49public:
50	typedef VectorIterator<Value>		Iterator;
51	typedef VectorIterator<const Value>	ConstIterator;
52
53private:
54	static const size_t				kDefaultChunkSize = 10;
55	static const size_t				kMaximalChunkSize = 1024 * 1024;
56
57public:
58	Vector(size_t chunkSize = kDefaultChunkSize);
59	~Vector();
60
61	status_t PushFront(const Value &value);
62	status_t PushBack(const Value &value);
63
64	void PopFront();
65	void PopBack();
66
67	status_t Insert(const Value &value, int32 index);
68	status_t Insert(const Value &value, const Iterator &iterator);
69
70	int32 Remove(const Value &value);
71	Iterator Erase(int32 index);
72	Iterator Erase(const Iterator &iterator);
73
74	inline int32 Count() const;
75	inline bool IsEmpty() const;
76	void MakeEmpty();
77
78	inline Iterator Begin();
79	inline ConstIterator Begin() const;
80	inline Iterator End();
81	inline ConstIterator End() const;
82	inline Iterator Null();
83	inline ConstIterator Null() const;
84	inline Iterator IteratorForIndex(int32 index);
85	inline ConstIterator IteratorForIndex(int32 index) const;
86
87	inline const Value &ElementAt(int32 index) const;
88	inline Value &ElementAt(int32 index);
89
90	int32 IndexOf(const Value &value, int32 start = 0) const;
91	Iterator Find(const Value &value);
92	Iterator Find(const Value &value, const Iterator &start);
93	ConstIterator Find(const Value &value) const;
94	ConstIterator Find(const Value &value, const ConstIterator &start) const;
95
96	inline Value &operator[](int32 index);
97	inline const Value &operator[](int32 index) const;
98
99	// debugging
100	int32 GetCapacity() const	{ return fCapacity; }
101
102private:
103	inline static void _MoveItems(Value *values, int32 offset, int32 count);
104	bool _Resize(size_t count);
105	inline int32 _IteratorIndex(const Iterator &iterator) const;
106	inline int32 _IteratorIndex(const ConstIterator &iterator) const;
107
108private:
109	size_t	fCapacity;
110	size_t	fChunkSize;
111	int32	fItemCount;
112	Value	*fItems;
113};
114
115
116// VectorIterator
117template<typename Value>
118class VectorIterator {
119private:
120	typedef VectorIterator<Value>	Iterator;
121
122public:
123	inline VectorIterator<Value>()
124		: fElement(NULL)
125	{
126	}
127
128	inline VectorIterator<Value>(const Iterator &other)
129		: fElement(other.fElement)
130	{
131	}
132
133	inline Iterator &operator++()
134	{
135		if (fElement)
136			++fElement;
137		return *this;
138	}
139
140	inline Iterator operator++(int)
141	{
142		Iterator it(*this);
143		++*this;
144		return it;
145	}
146
147	inline Iterator &operator--()
148	{
149		if (fElement)
150			--fElement;
151		return *this;
152	}
153
154	inline Iterator operator--(int)
155	{
156		Iterator it(*this);
157		--*this;
158		return it;
159	}
160
161	inline Iterator &operator=(const Iterator &other)
162	{
163		fElement = other.fElement;
164		return *this;
165	}
166
167
168	inline bool operator==(const Iterator &other) const
169	{
170		return (fElement == other.fElement);
171	}
172
173	inline bool operator!=(const Iterator &other) const
174	{
175		return !(*this == other);
176	}
177
178	inline Value &operator*() const
179	{
180		return *fElement;
181	}
182
183	inline Value *operator->() const
184	{
185		return fElement;
186	}
187
188	inline operator bool() const
189	{
190		return fElement;
191	}
192
193// private
194public:
195	inline VectorIterator<Value>(Value *element)
196		: fElement(element)
197	{
198	}
199
200	inline Value *Element() const
201	{
202		return fElement;
203	}
204
205protected:
206	Value	*fElement;
207};
208
209
210// Vector
211
212// constructor
213/*!	\brief Creates an empty vector.
214	\param chunkSize The granularity for the vector's capacity, i.e. the
215		   minimal number of elements the capacity grows or shrinks when
216		   necessary.
217*/
218_VECTOR_TEMPLATE_LIST
219_VECTOR_CLASS_NAME::Vector(size_t chunkSize)
220	: fCapacity(0),
221	  fChunkSize(chunkSize),
222	  fItemCount(0),
223	  fItems(NULL)
224{
225	if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize)
226		fChunkSize = kDefaultChunkSize;
227	_Resize(0);
228}
229
230// destructor
231/*!	\brief Frees all resources associated with the object.
232
233	The contained elements are destroyed. Note, that, if the element
234	type is a pointer type, only the pointer is destroyed, not the object
235	it points to.
236*/
237_VECTOR_TEMPLATE_LIST
238_VECTOR_CLASS_NAME::~Vector()
239{
240	MakeEmpty();
241	free(fItems);
242}
243
244// PushFront
245/*!	\brief Inserts a copy of the supplied value at the beginning of the
246		   vector.
247	\param value The element to be inserted.
248	\return
249	- \c B_OK: Everything went fine.
250	- \c B_NO_MEMORY: Insufficient memory for this operation.
251*/
252_VECTOR_TEMPLATE_LIST
253status_t
254_VECTOR_CLASS_NAME::PushFront(const Value &value)
255{
256	return Insert(value, 0);
257}
258
259// PushBack
260/*!	\brief Inserts a copy of the supplied value at the end of the vector.
261	\param value The element to be inserted.
262	\return
263	- \c B_OK: Everything went fine.
264	- \c B_NO_MEMORY: Insufficient memory for this operation.
265*/
266_VECTOR_TEMPLATE_LIST
267status_t
268_VECTOR_CLASS_NAME::PushBack(const Value &value)
269{
270	return Insert(value, fItemCount);
271}
272
273// PopFront
274/*!	\brief Removes the first element of the vector.
275
276	Invocation on an empty vector is harmless.
277*/
278_VECTOR_TEMPLATE_LIST
279void
280_VECTOR_CLASS_NAME::PopFront()
281{
282	if (fItemCount > 0)
283		Erase(0);
284}
285
286// PopBack
287/*!	\brief Removes the last element of the vector.
288
289	Invocation on an empty vector is harmless.
290*/
291_VECTOR_TEMPLATE_LIST
292void
293_VECTOR_CLASS_NAME::PopBack()
294{
295	if (fItemCount > 0)
296		Erase(fItemCount - 1);
297}
298
299// _MoveItems
300/*!	\brief Moves elements within an array.
301	\param items The elements to be moved.
302	\param offset The index to which the elements shall be moved. May be
303		   negative.
304	\param count The number of elements to be moved.
305*/
306_VECTOR_TEMPLATE_LIST
307inline
308void
309_VECTOR_CLASS_NAME::_MoveItems(Value* items, int32 offset, int32 count)
310{
311	if (count > 0 && offset != 0)
312		memmove(items + offset, items, count * sizeof(Value));
313}
314
315// Insert
316/*!	\brief Inserts a copy of the the supplied value at the given index.
317	\param value The value to be inserted.
318	\param index The index at which to insert the new element. It must
319		   hold: 0 <= \a index <= Count().
320	\return
321	- \c B_OK: Everything went fine.
322	- \c B_BAD_VALUE: \a index is out of range.
323	- \c B_NO_MEMORY: Insufficient memory for this operation.
324*/
325_VECTOR_TEMPLATE_LIST
326status_t
327_VECTOR_CLASS_NAME::Insert(const Value &value, int32 index)
328{
329	if (index < 0 || index > fItemCount)
330		return B_BAD_VALUE;
331	if (!_Resize(fItemCount + 1))
332		return B_NO_MEMORY;
333	_MoveItems(fItems + index, 1, fItemCount - index - 1);
334	new(fItems + index) Value(value);
335	return B_OK;
336}
337
338// Insert
339/*!	\brief Inserts a copy of the the supplied value at the given position.
340	\param value The value to be inserted.
341	\param iterator An iterator specifying the position at which to insert
342		   the new element.
343	\return
344	- \c B_OK: Everything went fine.
345	- \c B_BAD_VALUE: \a iterator is is invalid.
346	- \c B_NO_MEMORY: Insufficient memory for this operation.
347*/
348_VECTOR_TEMPLATE_LIST
349status_t
350_VECTOR_CLASS_NAME::Insert(const Value &value, const Iterator &iterator)
351{
352	int32 index = _IteratorIndex(iterator);
353	if (index >= 0)
354		return Insert(value, index);
355	return B_BAD_VALUE;
356}
357
358// Remove
359/*!	\brief Removes all elements of the supplied value.
360	\param value The value of the elements to be removed.
361	\return The number of removed occurrences.
362*/
363_VECTOR_TEMPLATE_LIST
364int32
365_VECTOR_CLASS_NAME::Remove(const Value &value)
366{
367	int32 count = 0;
368	for (int32 i = fItemCount - 1; i >= 0; i--) {
369		if (ElementAt(i) == value) {
370			Erase(i);
371			count++;
372		}
373	}
374	return count;
375}
376
377// Erase
378/*!	\brief Removes the element at the given index.
379	\param index The position of the element to be removed.
380	\return An iterator referring to the element now being located at index
381			\a index (End(), if it was the last element that has been
382			removed), or Null(), if \a index was out of range.
383*/
384_VECTOR_TEMPLATE_LIST
385typename _VECTOR_CLASS_NAME::Iterator
386_VECTOR_CLASS_NAME::Erase(int32 index)
387{
388	if (index >= 0 && index < fItemCount) {
389		fItems[index].~Value();
390		_MoveItems(fItems + index + 1, -1, fItemCount - index - 1);
391		_Resize(fItemCount - 1);
392		return Iterator(fItems + index);
393	}
394	return Null();
395}
396
397// Erase
398/*!	\brief Removes the element at the given position.
399	\param iterator An iterator referring to the element to be removed.
400	\return An iterator referring to the element succeeding the removed
401			one (End(), if it was the last element that has been
402			removed), or Null(), if \a iterator was an invalid iterator
403			(in this case including End()).
404*/
405_VECTOR_TEMPLATE_LIST
406typename _VECTOR_CLASS_NAME::Iterator
407_VECTOR_CLASS_NAME::Erase(const Iterator &iterator)
408{
409	int32 index = _IteratorIndex(iterator);
410	if (index >= 0 && index < fItemCount)
411		return Erase(index);
412	return Null();
413}
414
415// Count
416/*!	\brief Returns the number of elements the vector contains.
417	\return The number of elements the vector contains.
418*/
419_VECTOR_TEMPLATE_LIST
420inline
421int32
422_VECTOR_CLASS_NAME::Count() const
423{
424	return fItemCount;
425}
426
427// IsEmpty
428/*!	\brief Returns whether the vector is empty.
429	\return \c true, if the vector is empty, \c false otherwise.
430*/
431_VECTOR_TEMPLATE_LIST
432inline
433bool
434_VECTOR_CLASS_NAME::IsEmpty() const
435{
436	return (fItemCount == 0);
437}
438
439// MakeEmpty
440/*!	\brief Removes all elements from the vector.
441*/
442_VECTOR_TEMPLATE_LIST
443void
444_VECTOR_CLASS_NAME::MakeEmpty()
445{
446	for (int32 i = 0; i < fItemCount; i++)
447		fItems[i].~Value();
448	_Resize(0);
449}
450
451// Begin
452/*!	\brief Returns an iterator referring to the beginning of the vector.
453
454	If the vector is not empty, Begin() refers to its first element,
455	otherwise it is equal to End() and must not be dereferenced!
456
457	\return An iterator referring to the beginning of the vector.
458*/
459_VECTOR_TEMPLATE_LIST
460inline
461typename _VECTOR_CLASS_NAME::Iterator
462_VECTOR_CLASS_NAME::Begin()
463{
464	return Iterator(fItems);
465}
466
467// Begin
468/*!	\brief Returns an iterator referring to the beginning of the vector.
469
470	If the vector is not empty, Begin() refers to its first element,
471	otherwise it is equal to End() and must not be dereferenced!
472
473	\return An iterator referring to the beginning of the vector.
474*/
475_VECTOR_TEMPLATE_LIST
476inline
477typename _VECTOR_CLASS_NAME::ConstIterator
478_VECTOR_CLASS_NAME::Begin() const
479{
480	return ConstIterator(fItems);
481}
482
483// End
484/*!	\brief Returns an iterator referring to the end of the vector.
485
486	The position identified by End() is the one succeeding the last
487	element, i.e. it must not be dereferenced!
488
489	\return An iterator referring to the end of the vector.
490*/
491_VECTOR_TEMPLATE_LIST
492inline
493typename _VECTOR_CLASS_NAME::Iterator
494_VECTOR_CLASS_NAME::End()
495{
496	return Iterator(fItems + fItemCount);
497}
498
499// End
500/*!	\brief Returns an iterator referring to the end of the vector.
501
502	The position identified by End() is the one succeeding the last
503	element, i.e. it must not be dereferenced!
504
505	\return An iterator referring to the end of the vector.
506*/
507_VECTOR_TEMPLATE_LIST
508inline
509typename _VECTOR_CLASS_NAME::ConstIterator
510_VECTOR_CLASS_NAME::End() const
511{
512	return ConstIterator(fItems + fItemCount);
513}
514
515// Null
516/*!	\brief Returns an invalid iterator.
517
518	Null() is used as a return value, if something went wrong. It must
519	neither be incremented or decremented nor dereferenced!
520
521	\return An invalid iterator.
522*/
523_VECTOR_TEMPLATE_LIST
524inline
525typename _VECTOR_CLASS_NAME::Iterator
526_VECTOR_CLASS_NAME::Null()
527{
528	return Iterator(NULL);
529}
530
531// Null
532/*!	\brief Returns an invalid iterator.
533
534	Null() is used as a return value, if something went wrong. It must
535	neither be incremented or decremented nor dereferenced!
536
537	\return An invalid iterator.
538*/
539_VECTOR_TEMPLATE_LIST
540inline
541typename _VECTOR_CLASS_NAME::ConstIterator
542_VECTOR_CLASS_NAME::Null() const
543{
544	return ConstIterator(NULL);
545}
546
547// IteratorForIndex
548/*!	\brief Returns an iterator for a given index.
549	\return An iterator referring to the same element as \a index, or
550			End(), if \a index is out of range.
551*/
552_VECTOR_TEMPLATE_LIST
553inline
554typename _VECTOR_CLASS_NAME::Iterator
555_VECTOR_CLASS_NAME::IteratorForIndex(int32 index)
556{
557	if (index >= 0 && index <= fItemCount)
558		return Iterator(fItems + index);
559	return End();
560}
561
562// IteratorForIndex
563/*!	\brief Returns an iterator for a given index.
564	\return An iterator referring to the same element as \a index, or
565			End(), if \a index is out of range.
566*/
567_VECTOR_TEMPLATE_LIST
568inline
569typename _VECTOR_CLASS_NAME::ConstIterator
570_VECTOR_CLASS_NAME::IteratorForIndex(int32 index) const
571{
572	if (index >= 0 && index <= fItemCount)
573		return ConstIterator(fItems + index);
574	return End();
575}
576
577// ElementAt
578/*!	\brief Returns the element at a given index.
579	\param index The index identifying the element to be returned.
580	\return The element identified by the given index.
581*/
582_VECTOR_TEMPLATE_LIST
583inline
584const Value &
585_VECTOR_CLASS_NAME::ElementAt(int32 index) const
586{
587	if (index >= 0 && index < fItemCount)
588		return fItems[index];
589	// Return the 0th element by default. Unless the allocation failed, there
590	// is always a 0th element -- uninitialized perhaps.
591	return fItems[0];
592}
593
594// ElementAt
595/*!	\brief Returns the element at a given index.
596	\param index The index identifying the element to be returned.
597	\return The element identified by the given index.
598*/
599_VECTOR_TEMPLATE_LIST
600inline
601Value &
602_VECTOR_CLASS_NAME::ElementAt(int32 index)
603{
604	if (index >= 0 && index < fItemCount)
605		return fItems[index];
606	// Return the 0th element by default. Unless the allocation failed, there
607	// is always a 0th element -- uninitialized perhaps.
608	return fItems[0];
609}
610
611// IndexOf
612/*!	\brief Returns the index of the next element with the specified value.
613	\param value The value of the element to be found.
614	\param start The index at which to be started to search for the element.
615	\return The index of the found element, or \c -1, if no further element
616			with the given value could be found or \a index is out of range.
617*/
618_VECTOR_TEMPLATE_LIST
619int32
620_VECTOR_CLASS_NAME::IndexOf(const Value &value, int32 start) const
621{
622	if (start >= 0) {
623		for (int32 i = start; i < fItemCount; i++) {
624			if (fItems[i] == value)
625				return i;
626		}
627	}
628	return -1;
629}
630
631// Find
632/*!	\brief Returns an iterator referring to the next element with the
633		   specified value.
634	\param value The value of the element to be found.
635	\return An iterator referring to the found element, or End(), if no
636			further with the given value could be found.
637*/
638_VECTOR_TEMPLATE_LIST
639inline
640typename _VECTOR_CLASS_NAME::Iterator
641_VECTOR_CLASS_NAME::Find(const Value &value)
642{
643	return Find(value, Begin());
644}
645
646// Find
647/*!	\brief Returns an iterator referring to the next element with the
648		   specified value.
649	\param value The value of the element to be found.
650	\param start And iterator specifying where to start searching for the
651		   element.
652	\return An iterator referring to the found element, or End(), if no
653			further with the given value could be found or \a start was
654			invalid.
655*/
656_VECTOR_TEMPLATE_LIST
657typename _VECTOR_CLASS_NAME::Iterator
658_VECTOR_CLASS_NAME::Find(const Value &value, const Iterator &start)
659{
660	int32 index = IndexOf(value, _IteratorIndex(start));
661	if (index >= 0)
662		return Iterator(fItems + index);
663	return End();
664}
665
666// Find
667/*!	\brief Returns an iterator referring to the of the next element with the
668		   specified value.
669	\param value The value of the element to be found.
670	\return An iterator referring to the found element, or End(), if no
671			further with the given value could be found.
672*/
673_VECTOR_TEMPLATE_LIST
674inline
675typename _VECTOR_CLASS_NAME::ConstIterator
676_VECTOR_CLASS_NAME::Find(const Value &value) const
677{
678	return Find(value, Begin());
679}
680
681// Find
682/*!	\brief Returns an iterator referring to the of the next element with the
683		   specified value.
684	\param value The value of the element to be found.
685	\param start And iterator specifying where to start searching for the
686		   element.
687	\return An iterator referring to the found element, or End(), if no
688			further with the given value could be found or \a start was
689			invalid.
690*/
691_VECTOR_TEMPLATE_LIST
692typename _VECTOR_CLASS_NAME::ConstIterator
693_VECTOR_CLASS_NAME::Find(const Value &value, const ConstIterator &start) const
694{
695	int32 index = IndexOf(value, _IteratorIndex(start));
696	if (index >= 0)
697		return ConstIterator(fItems + index);
698	return End();
699}
700
701// []
702/*!	\brief Semantically equivalent to ElementAt().
703*/
704_VECTOR_TEMPLATE_LIST
705inline
706Value &
707_VECTOR_CLASS_NAME::operator[](int32 index)
708{
709	return ElementAt(index);
710}
711
712// []
713/*!	\brief Semantically equivalent to ElementAt().
714*/
715_VECTOR_TEMPLATE_LIST
716inline
717const Value &
718_VECTOR_CLASS_NAME::operator[](int32 index) const
719{
720	return ElementAt(index);
721}
722
723// _Resize
724/*!	\brief Resizes the vector.
725
726	The internal element array will be grown or shrunk to the next multiple
727	of \a fChunkSize >= \a count, but no less than \a fChunkSize.
728
729	Also adjusts \a fItemCount according to the supplied \a count, but does
730	not invoke a destructor or constructor on any element.
731
732	\param count The number of element.
733	\return \c true, if everything went fine, \c false, if the memory
734			allocation failed.
735*/
736_VECTOR_TEMPLATE_LIST
737bool
738_VECTOR_CLASS_NAME::_Resize(size_t count)
739{
740	bool result = true;
741	// calculate the new capacity
742	int32 newSize = count;
743	if (newSize <= 0)
744		newSize = 1;
745	newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize;
746	// resize if necessary
747	if ((size_t)newSize != fCapacity) {
748		Value* newItems = (Value*)realloc(fItems, newSize * sizeof(Value));
749		if (newItems) {
750			fItems = newItems;
751			fCapacity = newSize;
752		} else
753			result = false;
754	}
755	if (result)
756		fItemCount = count;
757	return result;
758}
759
760// _IteratorIndex
761/*!	\brief Returns index of the element the supplied iterator refers to.
762	\return The index of the element the supplied iterator refers to, or
763			\c -1, if the iterator is invalid (End() is considered valid
764			here, and Count() is returned).
765*/
766_VECTOR_TEMPLATE_LIST
767inline
768int32
769_VECTOR_CLASS_NAME::_IteratorIndex(const Iterator &iterator) const
770{
771	if (iterator.Element()) {
772		int32 index = iterator.Element() - fItems;
773		if (index >= 0 && index <= fItemCount)
774			return index;
775	}
776	return -1;
777}
778
779// _IteratorIndex
780/*!	\brief Returns index of the element the supplied iterator refers to.
781	\return The index of the element the supplied iterator refers to, or
782			\c -1, if the iterator is invalid (End() is considered valid
783			here, and Count() is returned).
784*/
785_VECTOR_TEMPLATE_LIST
786inline
787int32
788_VECTOR_CLASS_NAME::_IteratorIndex(const ConstIterator &iterator) const
789{
790	if (iterator.Element()) {
791		int32 index = iterator.Element() - fItems;
792		if (index >= 0 && index <= fItemCount)
793			return index;
794	}
795	return -1;
796}
797
798#endif	// _VECTOR_H
799