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

#ifndef Buckets_h
#define Buckets_h

#include<iostream.h>
#include<LINK/basic/Array.h>
#include<LINK/basic/DList.h>
#include<LINK/graph/Vertex.h>

class VertexInfo {
public:
	int node_num;
	int loc;
	int lock;
	int bucket_num;
	int cost;
	ContainerNode *lp;
	Vertex* v;
	int operator<(const VertexInfo& vinfo) const
		{ return (*v < *vinfo.v); }
	int operator==(const VertexInfo& vinfo) const
		{ return (*v == *vinfo.v); }
	friend ostream& operator<<(ostream& os, const VertexInfo& vinfo)
	{
		cout << "{VertexInfo";
		cout << " node_num=" << vinfo.node_num;
		cout << " loc=" << vinfo.loc;
		cout << " lock=" << vinfo.lock;
		cout << " bucket_num=" << vinfo.bucket_num;
		cout << " cost=" << vinfo.cost;
		Container<Vertex*> *cp;
		cout << " lp=" << cp->info(vinfo.lp);
		cout << " v=" << *vinfo.v << "}";
	}
};
typedef VertexInfo * VertexInfoPtr;


class BucketArray : public Array<DList<VertexInfo*> > {
public:
	int current_max_bucket, current_min_bucket;
	int num_pos_buckets, num_buckets;

	BucketArray() : Array<DList<VertexInfo*> >(), 
			current_max_bucket(0),
	                current_min_bucket(0), 
			num_pos_buckets((ARRAYSIZE-1)/2),
			num_buckets(ARRAYSIZE) {}
	BucketArray(int sz) : Array<DList<VertexInfo*> >(sz), 
			      	current_max_bucket(0),
	                      	current_min_bucket(0),
				num_pos_buckets((sz-1)/2),
				num_buckets(sz) {}
	BucketArray(const BucketArray& a) : Array<DList<VertexInfo*> >(a), 
				current_max_bucket(a.current_max_bucket),
	                        current_min_bucket(a.current_min_bucket),
				num_pos_buckets(a.num_pos_buckets),
				num_buckets(a.num_buckets) {}
	ContainerNode * insert(int cost, VertexInfo *v);
	ContainerNode * insert(int cost, ContainerNode *cn);
	ContainerNode * remove(VertexInfo *v);
	int  		findMax();
	int  		findMin();
	ContainerNode *	extractMax();
	ContainerNode *	extractMin();
	void 		pfirst(int bnum);
	void 		print();
    	friend ostream&     operator<<(ostream& stream, BucketArray& b);
};

#endif