/home/gian/Progetti/falcon/core/include/falcon/itemset.h

Go to the documentation of this file.

/*
   FALCON - The Falcon Programming Language.
   FILE: itemset.h

   (Ordered) set of falcon items.
   -------------------------------------------------------------------
   Author: Giancarlo Niccolai
   Begin: Fri, 07 Aug 2009 18:36:22 +0200

   -------------------------------------------------------------------
   (C) Copyright 2009: the FALCON developers (see list in AUTHORS file)

   See LICENSE file for licensing details.
*/

#ifndef FALCON_ITEMSET_H
#define FALCON_ITEMSET_H

#include <falcon/setup.h>
#include <falcon/basealloc.h>
#include <falcon/falcondata.h>
#include <falcon/sequence.h>
#include <falcon/item.h>
#include <falcon/iterator.h>
#include <falcon/mt.h>

namespace Falcon {

class ItemSetElement;
class ItemSet;

class FALCON_DYN_CLASS ItemSetElement: public BaseAlloc
{
   Item m_item;

   ItemSetElement *m_left;
   ItemSetElement *m_right;
   ItemSetElement *m_parent;
public:

   ItemSetElement( const Item &itm, ItemSetElement* p=0, ItemSetElement *l = 0, ItemSetElement *r = 0 ):
      m_item( itm ),
      m_left( l ),
      m_right( r ),
      m_parent( p )
   {}

  ~ItemSetElement()
  {
  }

   const Item &item() const { return m_item; }
   Item &item() { return m_item; }

   void left( ItemSetElement *n ) { m_left = n; }
   ItemSetElement *left() const { return m_left; }

   void right( ItemSetElement *p ) { m_right = p; }
   ItemSetElement *right() const { return m_right; }

   void parent( ItemSetElement *p ) { m_parent = p; }
   ItemSetElement *parent() const { return m_parent; }
};


class FALCON_DYN_CLASS ItemSet: public Sequence
{
private:
   uint32 m_size;
   ItemSetElement *m_root;
   uint32 m_mark;

   // temporary variable using during iter-erase
   Iterator* m_erasingIter;
   ItemSetElement* m_disposingElem;

   static ItemSetElement* duplicateSubTree( ItemSetElement* parent, const ItemSetElement* source );
   static void clearSubTree( ItemSetElement* source );
   static ItemSetElement* smallestInTree( ItemSetElement* e );
   static ItemSetElement* largestInTree( ItemSetElement* e );
   static bool insertInSubtree( ItemSetElement* elem, const Item& item );
   static void markSubTree( ItemSetElement* e );
   static ItemSetElement* nextElem( ItemSetElement* e );
   static ItemSetElement* prevElem( ItemSetElement* e );
   static ItemSetElement* findInTree( ItemSetElement* elem, const Item &item );

public:
   ItemSet():
      m_size(0),
      m_root(0),
      m_mark( 0xFFFFFFFF ),
      m_erasingIter(0),
      m_disposingElem(0)
   {}

   ItemSet( const ItemSet &l );

   virtual ~ItemSet()
   {
      clear();
   }

   virtual FalconData *clone() const;

   virtual const Item &front() const;

   virtual const Item &back() const;

   ItemSetElement *first() const;

   ItemSetElement *last() const;

   virtual void append( const Item& itm ) { insert( itm ); }
   virtual void prepend( const Item& itm ) { insert( itm ); }


   virtual void clear();

   void erase( ItemSetElement *elem );

   ItemSetElement* find( const Item &item );

   void getIteratorAt( Iterator &tgt, ItemSetElement* elem );


   void insert( const Item &item );


   virtual bool empty() const { return m_root == 0; }

   uint32 size() const { return m_size; }

   virtual void gcMark( uint32 mark );

   // Deletion criterion.
   virtual bool onCriterion( Iterator* elem ) const;

   //========================================================
   // Iterator implementation.
   //========================================================
protected:

   virtual void getIterator( Iterator& tgt, bool tail = false ) const;
   virtual void copyIterator( Iterator& tgt, const Iterator& source ) const;

   virtual void insert( Iterator &iter, const Item &data );
   virtual void erase( Iterator &iter );
   virtual bool hasNext( const Iterator &iter ) const;
   virtual bool hasPrev( const Iterator &iter ) const;
   virtual bool hasCurrent( const Iterator &iter ) const;
   virtual bool next( Iterator &iter ) const;
   virtual bool prev( Iterator &iter ) const;
   virtual Item& getCurrent( const Iterator &iter );
   virtual Item& getCurrentKey( const Iterator &iter );
   virtual bool equalIterator( const Iterator &first, const Iterator &second ) const;
};


}

#endif

/* end of itemset.h */

---