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