// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): ??, Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 
#include <iostream.h>

#define Array_CC

//
// Creates an empty array of default size
//
template <class Item>
Array<Item>::Array() : _count(0)
{
    static Item it;
    _ia = new Item[_size = ARRAYSIZE];
    for (int i = 0; i < ARRAYSIZE; i++)
	_ia[i] = it;  // empty_data; //(Item)0; 
}

//
// Creates an empty array of given size sz
//
template <class Item>
Array<Item>::Array(int sz) : _count(0)
{
    static Item it;
    _ia = new Item[_size = sz];
    for (int i = 0; i < sz; i++)
	_ia[i] = it; //empty_data; //(Item)0;
}

//
// Copy constructor of array
//
template <class Item>
Array<Item>::Array(const Array<Item>& ar) : 
			_count(ar._count),
			_size(ar._size)
{
    _ia = new Item[_size];
    for (int ix = 0; ix < _size; ix++)
        _ia[ix] = ar._ia[ix];
}

template <class Item>
Array<Item>::Array(const Container<Item>& c)
{
	_count = 0;
	_ia = new Item[_size=ARRAYSIZE];
	Iterator<Item> get_next(&c);
	Item elem;
	while (get_next(elem))
		append(elem);
}

//
// Destructor of array
//
template <class Item>
Array<Item>::~Array()
{
    delete [] _ia;
}

//
// Copy the contents of array
//
template <class Item>
Array<Item>& 
Array<Item>::operator=(const Array<Item> &iA)
{
    if (this == &iA) return *this;
    delete [] _ia;
    _size = iA._size;
    _count = iA._count;
    _ia = new Item[_size];
    for (int ix=0; ix < _size;  ix++)
	_ia[ix] = iA._ia[ix];
    return *this;
}


//
// Return item of index ix
//
template <class Item>
Item& 
Array<Item>::operator[] (int ix) const 
{
    if ((ix < 0) || (ix >= _size)) {
        warning("array index out of bounds! Returning Element 0"); 
        return _ia[0];
    }
    // allow random access
    if (ix>=_count) 
	((Array<Item>&)(*this))._count=ix+1;
    return _ia[ix];
}


//
// Return the smallest element
// 
template <class Item>
Item 
Array<Item>::min()
{
    Item min_val = _ia[0];
    for (int ix = 1; ix < _count; ++ix)
        if (ElementOps<Item>::compareItems(min_val, _ia[ix]) > 0)
            min_val = _ia[ix];
    return min_val;
}

//
// Return the larggest element
//
template <class Item>
Item 
Array<Item>::max()
{
    Item max_val = _ia[0];
    for (int ix = 1; ix < _count; ++ix)
        if (ElementOps<Item>::compareItems(max_val, _ia[ix]) < 0)
            max_val = _ia[ix];
    return max_val;
}

//
// Find item in array and return index; -1 returned if not found
//
template <class Item>
int 
Array<Item>::search(const Item& val) const
{
    for (int ix = 0; ix < _count; ++ix)
        if (ElementOps<Item>::compareItems(val, _ia[ix])==0) return ix;
    return -1;
}

//
// check if the item is in the array
//
template <class Item>
Bool 
Array<Item>::memberQ(const Item& val) const
{
    for (int ix = 0; ix < _count; ++ix)
        if (ElementOps<Item>::compareItems(val, _ia[ix])==0) return TRUE;
    return FALSE;
}

//
// remove all items from the array
//
template <class Item>
void 
Array<Item>::clear()
{
    static Item it;
    for (int i = 0; i < _count; i++) 
        _ia[i] = it; // empty_data; //(Item) 0;
    _count = 0;
}


//
// Insert the item at the beginning of the array and move
// the rest of the array down to accomodate.
//
template <class Item>
ContainerNode*
Array<Item>::insert(Item e)
{
    int iPos = 0;

    if (_count == _size) 
	resize(2*_size);
    for (int i = _count; i > iPos; i--)
        _ia[i] = _ia[i - 1];
    _ia[iPos] = e;
    _count++;
    return (ContainerNode*) 0;
}

//
// Append the item at the end of array
//
template <class Item>
ContainerNode*
Array<Item>::append(Item e)
{
    if (_count == _size)
	resize(2*_size);
    _ia[_count] = e;
    _count++;
    return (ContainerNode*) 0;
}


//
// remove the passed item from the array
//
template <class Item>
void 
Array<Item>::remove(Item e)
{
    int idx = search(e);
    if (idx == -1)  {
        return;
    }
    static Item it;
    for (int i = idx; i < _count - 1; i++)
        _ia[i] = _ia[i+1];
    _ia[_count-1] = it;  // empty_data; //0;
    _count--;
}


//
// remove the last item from the array and return
//
template <class Item>
Item 
Array<Item>::get()
{
    if (_count == 0)
    {
        static Item it;
	warning("can't get from empty array, return 0");
	return it;  // empty_data; //0;
    }
    if (_count > 0) {
	_count--;
	return _ia[_count];
    }
}

template <class Item>
int
Array<Item>::order()
{
    return _size;
}

template <class Item>
ostream& 
Array<Item>::display(ostream& os) const
{
    const lineLength = 12;

    os << "[";
    for (int ix = 0; ix < _count; ++ix)  {
        if (ix % lineLength == 0 && ix) 
	    os<< "\n\t";
	ElementOps<Item>::displayItem(os, _ia[ix]);

        if (ix % lineLength != lineLength-1 && ix != _count-1) 
	    os << " ";
    }
    os << "]" ;
    return os;
}

template<class Item>
int
Array<Item>::iterate(Iterator<Item>& iterator, Item& item) const
{
    if (iterator._index == 0) {
	// start of iteration, return first, point to next
        if (_count == 0)
            return 0;
        else {
            item = _ia[0];
            iterator._index = 1;
            return 1;
        }
    } else
        if (iterator._index >= _count || _count == 0)
            return 0;
        else {
            item = _ia[iterator._index];
            iterator._index++;
            return 1;
        }
}


//
// create an empty array of size sz
//
template <class Item>
void
Array<Item>::newArray(const Item* ar, int sz)
{
    static Item it;
    _ia = new Item[_size = sz];
    for (int ix = 0; ix < _size; ++ix)
        _ia[ix] = (ar != 0) ? ar[ix] : it;  // empty_data; //(Item) 0;
}

//
// Swap two items in the array
//
template <class Item>
void 
Array<Item>::swap(int i, int j)
{
    Item tmp = _ia[i];
    _ia[i] = _ia[j];
    _ia[j] = tmp;
}

//
// expand the array's size
//
template <class Item>
void 
Array<Item>::resize(int new_size)
{
    int i, old_size = _size, copy_ulimit;
    if (new_size == -1)
        new_size = old_size + old_size/2 + 1;
    Item *oldia = _ia;
    _ia = new Item[_size=new_size];

    copy_ulimit = (old_size > new_size) ? new_size : old_size;
	
    static Item it;
    for(i = 0; i < copy_ulimit; ++i) {
	cout << i;
        _ia[i] = oldia[i];
	if (it != _ia[i]) 
		_count = i+1;
	cout << endl;
    }
    for (i=copy_ulimit; i < _size; ++i) 
        _ia[i] = it; // empty_data; //(Item)0;

    delete oldia;
}

template <class Item>
SortedArray<Item>::SortedArray(int sz)
{
    _count = 0;
    _ia = new Item[_size = sz];
    static Item it;
    for (int i = 0; i < sz; i++)
        _ia[i] = it;  // empty_data; //(Item)0;
}

template <class Item>
SortedArray<Item>::SortedArray(const SortedArray<Item>& c) 
{
	_count = 0;
	Iterator<Item> get_next(&c);
	Item elem;
	while (get_next(elem))
		append(elem);
}

template <class Item>
SortedArray<Item>::SortedArray(const Container<Item>& c) 
{
	_count = 0;
	Iterator<Item> get_next(&c);
	Item elem;
	while (get_next(elem))
		insert(elem);
}

template <class Item>
SortedArray<Item>&
SortedArray<Item>::operator=(const SortedArray<Item> &iA)
{
    if (this == &iA) return *this;
    delete [] _ia;
    _size = iA._size;
    _count = iA._count;
    _ia = new Item[_size];
    for (int ix=0; ix < _size;  ix++)
        _ia[ix] = iA._ia[ix];
    return *this;
}

template <class Item>
Bool
SortedArray<Item>::memberQ(const Item& val) const
{
    for (int ix = 0; ix < _count; ++ix)
    {
        if (ElementOps<Item>::compareItems(val,_ia[ix])==0) return TRUE;
	if (ElementOps<Item>::compareItems(val, _ia[ix])>0) return FALSE;
    }
    return FALSE;
}
    
template <class Item>
Item
SortedArray<Item>::min()
{
    return _ia[0];
}

template <class Item>
Item
SortedArray<Item>::max()
{
    if (_count == 0) {
	static Item i;
	return i;
    }
    return _ia[_count-1];
}

template <class Item>
int
SortedArray<Item>::search(const Item& val) const
{
    int low=0, high=_count-1, mid, comp;
    while (low <= high) {
	mid = low + (int) (high-low)/2;
        if ((comp=ElementOps<Item>::compareItems(_ia[mid],val))==0) 
		return mid;
	else if (comp < 0)
		low = mid+1;
	else
		high = mid-1;
    }
    return -1;
}

template <class Item>
ContainerNode*
SortedArray<Item>::insert(Item e)
{
    int i = _count-1;

    if (_count == _size)
        resize(2*_size);
    while ((i >= 0) && (ElementOps<Item>::compareItems(_ia[i], e)>0))
    {
        _ia[i+1] = _ia[i];
	i--;
    }
    _ia[i+1] = e;
    _count++;
    return (ContainerNode*) 0;
}

template <class Item>
ContainerNode*
SortedArray<Item>::append(Item e)
{
    if (_count == _size)
        resize(2*_size);
    if ((_count ==0) || (ElementOps<Item>::compareItems(_ia[_count-1], e) > 0))
    {
	return insert(e);
    }
    _ia[_count] = e;
    _count++;
    return (ContainerNode*) 0;
}

//template <class Item>
//int
//Array<Item>::operator<(const Array<Item>& col) const
//{
//   return 0;
//}
//
//template <class Item>
//int
//Array<Item>::operator>(const Array<Item>& col) const
//{
//   return 0;
//}
//
//template <class Item>
//int
//Array<Item>::operator==(const Array<Item>& col) const 
//{
//   return 0;
//}
//
//template <class Item>
//ostream&
//operator<<(ostream& os, Array<Item>& col)
//{
//   return 0;
//}