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

// 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
// 

#ifndef Array_h
#define Array_h

#include <LINK/basic/Container.h>

class Vertex;
class Edge;
template <class Item> class ArrayWrapper;

template <class Item>
class Array : public SimpleContainer<Item> {
public:
    //int 		ref_count;

    Array();
    Array(int sz);
    Array(const Array<Item>& ar);
    Array(const Container<Item>& ar);
    virtual ~Array();

    Array&		operator=(const Array&);

    Item&		operator[] (int ix) const;
    Item&               Subscript(int ix) {return _ia[ix];}

    int			size() const	{ return _count; }
    Bool		emptyQ() const	{ return _count ? FALSE : TRUE; }
    Bool		fullQ() const	{ return FALSE; }
    Bool		memberQ(const Item& item) const;
    Bool		sortedQ() const { return FALSE; }
    DataType		type() const	{ return ARRAY; }

    Item		first() const	{ return _ia[0]; }
    Item		last() const	{ return _ia[_count - 1]; }
    Item*		start() const	{ return _ia; }

    Item		min();
    Item		max();
    virtual int		search(const Item& item) const;

    ContainerNode*	insert(Item e);
    ContainerNode* 	append(Item e);
    void		remove(Item e);
    void		clear();
    Item		get();
    int 		order();


    ostream&		display(ostream&) const;

protected:
    int			iterate(Iterator<Item>& i, Item& e) const;
    void		newArray(const Item*, int);
    void		swap(int, int);
    void		resize(int new_size = -1);

    int			_size;
    int			_count;
    Item*		_ia;
    friend class ArrayWrapper<Item>;

};

template <class Item>
class SortedArray : public Array<Item> {
public:
    SortedArray() : Array<Item>() {}
    SortedArray(int sz);
    SortedArray(const SortedArray<Item>& ar);
    SortedArray(const Container<Item>& ar);
    SortedArray<Item>&          operator=(const SortedArray<Item>&);
    Bool	                memberQ(const Item& item) const;
    Bool	                sortedQ() const { return TRUE; }
    Item              		min();
    Item                	max();
    int                 	search(const Item& item) const;
    ContainerNode*      	insert(Item e);
    ContainerNode*      	append(Item e);
};

#ifdef DEFINE_TEMPLATE
#include <LINK/basic/Array.cc>
#endif


#endif