/*
 * Licensed under BSD license.  See LICENCE.TXT  
 *
 * Produced by:	Jeff Lait
 *
 *      	7DRL Development
 *
 * NAME:        blocklist.h ( Pointless Library, C++ )
 *
 * COMMENTS:
 *	Implements a list of zero-collapsible blocks.
 *	The idea is to allow for use of unbounded UIDs so long
 *	as live sequence is low.  Unlike a hash, we are assuming
 *	the uids are streaky, which is pretty safe for item uids.
 *	The main goal is for separate "sessions" to reset the list.
 */

#ifndef __blocklist_h__
#define __blocklist_h__

#include <iterator>
#include "mygba.h"

#define BLOCKLIST_BLOCKSIZE (1 << BLOCKLIST_BLOCKBITS)
#define BLOCKLIST_BLOCKMASK ((1 << BLOCKLIST_BLOCKBITS) - 1)
#define BLOCKLIST_BLOCKBITS 5

template <typename PTR>
class BLOCKLIST
{
public:
    BLOCKLIST();
    ~BLOCKLIST();

    // No copy constructors as you should be passing by reference to build!
    // That is a noble sentiment, but we live in a corrupt world
    BLOCKLIST(const BLOCKLIST<PTR> &ref);
    BLOCKLIST<PTR> &operator=(const BLOCKLIST<PTR> &ref);

    int		 	 append(PTR item);
    int		 	 append();
    void		 append(const PTRLIST<PTR> &list);
    void		 append(const BLOCKLIST<PTR> &list);

    // Empties, note this does free.
    void		 clear();

    // Frees all the blocks as they are now "zero", but keeps size.
    void		 zero();

    // Sets entries to the given size.
    void		 resize(int size);

    // Resizes only if it is a grow
    void		 resizeIfNeeded(int newsize)
			 { if (newsize > entries()) resize(newsize); }

    // Allocates copacity
    // Only valid on empty list!
    // For compatibility, these don't have a capacity sense.
    void		 setCapacity(int /*size*/)
    { J_ASSERT(entries() == 0); }
    int			 capacity() const { return myBlocks.entries() * BLOCKLIST_BLOCKSIZE; }

    // This must be by value as we want to return holes.
    PTR		 	 operator()(int idx) const;

    // I've been avoiding adding this for a long time for what
    // I believed was a very good reason.  But I've given up.
    // In this case we need to track zeroing of indices, so
    // there is a good reason.
    //PTR			 &operator()(int idx);

    // Treats the array as padded with 0s after the end.
    // Note does not resize like indexAnywhere, as we'd then
    // have different side effects for const and non const
    // which will be very confusing.
    PTR			 safeIndexAnywhere(int idx) const
    { 
	if (idx < entries()) return (*this)(idx);

	PTR result;
	new (&result) PTR();
	return result;
    }

    // Will grow the array to contain the given index.
    // Invalid if negative.
    void		 setAnywhere(int idx, PTR ptr) 
    { 
	resizeIfNeeded(idx+1);
	set(idx, ptr);
    }


    int			 entries() const;

    void		 set(int idx, PTR item);

    // Returns the last element.
    // The index allows you to specify N elements from the end, where
    // 0 is the last element and 1 second last.
    PTR			 top(int idx = 0) const { return (*this)(entries()-1-idx); }

    PTR			 last() const { return top(); }

    bool		 verify() const
    {
	if (myEntries)
	{
	    int		numblock, lastidx;
	    splitIndex(myEntries-1, numblock, lastidx);
	    if (myBlocks.entries() > numblock)
	    {
		J_ASSERT(!"Invalid block count");
		return false;
	    }
	}
	for (auto && block : myBlocks)
	    if (!block->verify()) return false;
	return true;
    }

    class BLOCK
    {
    public:

	bool		 isZero() const { return myNonZero == 0; }
	int		 nonZero() const { return myNonZero; }
	void		 tryCompress()
	{
	    if (myNonZero == 0) myData.reset();
	}

	void		 zero()
	{
	    myData.reset();
	    myNonZero = 0;
	}

	bool		 verify() const
	{
	    if (!myData.get())
	    {
		J_ASSERT(myNonZero == 0);
		return myNonZero == 0;
	    }
	    int		 nonzcount = 0;
	    PTR		*data = myData.get();
	    for (int j = 0; j < BLOCKLIST_BLOCKSIZE; j++)
	    {
		if (data[j] != 0)
		    nonzcount++;
	    }
	    J_ASSERT(myNonZero == nonzcount);
	    return myNonZero == nonzcount;
	}

	PTR 		 get(int lclidx) const
	{
	    if (myNonZero == 0) return 0;

	    return myData.get()[lclidx];
	}

	void		 set(int lclidx, PTR item)
	{
	    if (item == 0)
	    {
		// Trivial:
		if (isZero()) return;
		if (myData.get()[lclidx])
		{
		    // Non zero so we overwrite.
		    myData.get()[lclidx] = item;
		    myNonZero--;
		    // Reset on last!
		    if (!myNonZero) myData.reset();
		}
	    }
	    else
	    {
		if (!myData.get())
		{
		    J_ASSERT(myNonZero == 0);
		    myData.reset(new PTR[BLOCKLIST_BLOCKSIZE]);
		    memset(myData.get(), 0, sizeof(PTR) * BLOCKLIST_BLOCKSIZE);
		    myData.get()[lclidx] = item;
		    myNonZero = 1;
		}
		else
		{
		    if (!myData.get()[lclidx])
			myNonZero++;
		    myData.get()[lclidx] = item;
		}
	    }
	    J_ASSERT(verify());
	}

	void		 harden()
	{
	    if (myData.get() && myData.use_count() != 1)
	    {
		std::shared_ptr<PTR> clone;
		clone.reset(new PTR[BLOCKLIST_BLOCKSIZE]);
		memcpy(clone.get(), myData.get(), sizeof(PTR)*BLOCKLIST_BLOCKSIZE);
		myData = clone;
	    }
	}

    protected:
	std::shared_ptr<PTR> myData;
	int		 myNonZero = 0;
    };

    /// op is [](int idx) -> bool.
    ///  Will quit if true, return if true returned.
    template <typename OP>
    bool		 processNonZeroIndex(const OP &op) const
    {
	bool		done = false;

	for (int i = 0; i < myEntries; )
	{
	    int	blockidx, localindex;
	    splitIndex(i, blockidx, localindex);

	    if (myBlocks(blockidx).isZero())
		i += BLOCKLIST_BLOCKSIZE;
	    else
	    {
		int		nzero = 0;
		for (int j = 0; j < BLOCKLIST_BLOCKSIZE && i < myEntries; j++,i++)
		{
		    if (myBlocks(blockidx).get(j))
		    {
			done = op(i);
			if (done) return true;
			// Might have been zeroed, so check after.
			if (myBlocks(blockidx).get(j))
			    nzero++;
		    }
		}
		// A free data validation here:
		J_ASSERT(nzero == myBlocks(blockidx).nonZero());
	    }
	}
	return false;
    }

    /// op is [](PTR ptr) -> bool.
    ///  Will quit if true, return if true returned.
    template <typename OP>
    bool		 processNonZeroPtr(const OP &op) const
    {
	return processNonZeroIndex([&](int idx) -> bool
	{
	    return op( (*this)(idx) );
	});
    }

protected:
    static void		  splitIndex(int index, int &block, int &local)
    {
	J_ASSERT(index >= 0);
	block = index >> BLOCKLIST_BLOCKBITS;
	local = index & (BLOCKLIST_BLOCKSIZE-1);
    }

private:
    PTRLIST<BLOCK>	  myBlocks;
    int			  myEntries = 0;
};

// For crappy platforms:
#include "blocklist.cpp"

#endif

