2005/5/9

     
 

TreeMap.h

artefaktur
// -*- mode:C++; tab-width:2; c-basic-offset:2; indent-tabs-mode:nil -*- 
//
// Parts of this class are ported from the of GNU Classpath project 
//  (http://www.gnu.org/software/classpath/classpath.html)
//   with following copyright statement:
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU Library General Public License as published
// by the Free Software Foundation, version 2. (see COPYING.LIB)
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public License
// along with this program; if not, write to the Free Software Foundation
// Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307 USA
// Copyright (C) 1998, 1999, 2001, 2002, 2003, 2004
//                Free Software Foundation, Inc.
// END
// Copyright (C) 2000-2005 by Roger Rene Kommer / artefaktur, Kassel, Germany.
// 
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Library General Public License (LGPL).
// 
// 
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the 
// License ACDK-FreeLicense document enclosed in the distribution
// for more for more details.
// This file is part of the Artefaktur Component Development Kit:
//                         ACDK
// 
// Please refer to
// - http://www.acdk.de
// - http://www.artefaktur.com
// - http://acdk.sourceforge.net
// for more information.
// 
// $Header: /cvsroot/acdk/acdk/acdk_core/src/acdk/util/TreeMap.h,v 1.22 2005/04/09 19:26:57 kommer Exp $
#ifndef acdk_util_TreeMap_h
#define acdk_util_TreeMap_h

#include "Map.h"
#include "AbstractMap.h"
#include "AbstractSet.h"

#include "SortedMap.h"
#include "Comparator.h"
#include "BasicMapEntry.h"
#include "ConcurrentModificationException.h"
#include "AbstractCollection.h"

#include "ConcurrentModificationException.h"
#include <acdk/lang/UnsupportedOperationException.h>

#include <acdk/lang/Cloneable.h>
#include <acdk/io/Serializable.h>

namespace acdk {
namespace util {

using namespace acdk::lang;

ACDK_DECL_CLASS(RedBlackNode);

enum NodeType 
{
  RedNodeType = -1,
  BlackNodeType = 1
};

/**
  API: Java<br/>
  @author Roger Rene Kommer (mailto:kommer@artefaktur.com)
  @version $Revision: 1.22 $
  @date $Date: 2005/04/09 19:26:57 $
  
*/
class ACDK_CORE_PUBLIC RedBlackNode 
: extends BasicMapEntry 
, implements ::acdk::io::Serializable
{
  ACDK_WITH_METAINFO(RedBlackNode)
public:
 
  NodeType _color;
  RRedBlackNode _left;
  RRedBlackNode _right;
  RRedBlackNode _parent;

  RedBlackNode(IN(acdk::lang::Object) key, IN(acdk::lang::Object) value)
  : BasicMapEntry(key, value),
    _color(BlackNodeType),
    _left(nilNode()),
    _right(nilNode()),
    _parent(nilNode())
  {
  }
  static RRedBlackNode _nilNode;
  static RRedBlackNode nilNode();

  void _clear()
  {
    RRedBlackNode nn = nilNode();
    if (_left != nn && _left != Nil && _left.iptr() != this)
      _left->_clear();
    if (_right != nn && _right != Nil && _right.iptr() != this)
      _right->_clear();
    _left = Nil;
    _right = Nil;
    _parent = Nil;
  }
};

/**
  Specialized Version for the NilNode

*/
class ACDK_CORE_PUBLIC NilRedBlackNode
: extends RedBlackNode
{
public:
  NilRedBlackNode();
  ~NilRedBlackNode();
};



/**
  API: Java<br/>
  @author Roger Rene Kommer (mailto:kommer@artefaktur.com)
  @version $Revision: 1.22 $
  @date $Date: 2005/04/09 19:26:57 $
  
*/
enum MapEntryTyp 
{
  Entries = 0,
  Keys = 1,
  Values = 2
};
ACDK_DEF_LIB_ENUM(ACDK_CORE_PUBLIC, MapEntryTyp);


ACDK_DECL_CLASS(TreeMap);
/**
  Implements a standard sortable map using black/red trees

  This class is partly ported from the GNU Classpath implementation
  @author Original GNU Classpath implementation: Jon Zeppieri
          // Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
  @author ACDK: Roger Rene Kommer (mailto:kommer@artefaktur.com)
  @version $Revision: 1.22 $
  @date $Date: 2005/04/09 19:26:57 $
  
*/
class ACDK_CORE_PUBLIC TreeMap 
: extends AbstractMap,
  implements SortedMap,
  implements acdk::lang::Cloneable,
  implements acdk::io::Serializable
{
  ACDK_WITH_METAINFO(TreeMap)
private:
  RRedBlackNode _root;
  int _size;
  RComparator _comparator;
  int _modCount;
public:
  static acdk::lang::Object create_instance() { return new TreeMap(RMap(Nil)); }
  TreeMap(IN(RComparator) comp = Nil);
  TreeMap(IN(RMap) map);
  TreeMap(IN(RSortedMap) sortedMap);

  virtual void clear();
  virtual acdk::lang::Object clone() { return clone(allocator()); }
  virtual acdk::lang::Object clone(sys::Allocator* alc);
  
  virtual RComparator comparator()
  {
    return _comparator;
  }

  virtual bool containsKey(IN(acdk::lang::Object) key)
  {
    return (treeSearch(_root, _comparator, key) != nilNode());
  }

  virtual bool containsValue(IN(acdk::lang::Object) val);
  
  virtual RSet entrySet();
  virtual acdk::lang::Object firstKey();
  virtual acdk::lang::Object get(IN(acdk::lang::Object) key);
  virtual RSortedMap headMap(IN(acdk::lang::Object) key);
  virtual RSet keySet();
  virtual acdk::lang::Object lastKey();
  virtual acdk::lang::Object put(IN(acdk::lang::Object) key, IN(acdk::lang::Object) val);
  virtual void putAll(IN(RMap) map);
  virtual acdk::lang::Object remove(IN(acdk::lang::Object) key);
  virtual int size()
  {
    return _size;
  }
  virtual RSortedMap subMap(IN(acdk::lang::Object) from, IN(acdk::lang::Object) to);
  virtual RSortedMap tailMap(IN(acdk::lang::Object) from);
  virtual RCollection values();
  
  virtual bool equals(IN(acdk::lang::Object) other)
  {
    return AbstractMap::equals(other);
  }
  virtual int hashCode()
  {
    return AbstractMap::hashCode();
  }
  virtual bool isEmpty()
  {
    return AbstractMap::isEmpty();
  }
protected:
  void putAllLinear(IN(RMapEntryArray) entries);
private:
  foreign static RRedBlackNode buildTree(IN(RMapEntryArray) entries, int height,  bool completed, int currentTier,  int start, int end,
                                         acdk::lang::sys::Allocator* alloc);
  static int compare(IN(RComparator) comp, IN(acdk::lang::Object) o1, IN(acdk::lang::Object) o2)
  {
    if (comp == Nil)
      return RComparable(o1)->compareTo(o2);
    return comp->compare(o1, o2);
  }

  static bool keyInMinRange(IN(RComparator) comp, IN(acdk::lang::Object) key, IN(acdk::lang::Object) minKey)
  {
    return ((minKey == Nil) ||  (compare(comp, minKey, key) <= 0));
  }

  static bool keyInMaxRange(IN(RComparator) comp, IN(acdk::lang::Object) key, IN(acdk::lang::Object) maxKey)
  {
    return ((maxKey == Nil) ||  (compare(comp, maxKey, key) > 0));
  }
  static bool keyInClosedMaxRange(IN(RComparator) comp, IN(acdk::lang::Object) key, IN(acdk::lang::Object) maxKey)
  {
    return ((maxKey == Nil) ||  (compare(comp, maxKey, key) >= 0));
  }
  static bool keyInRange(IN(RComparator) comp, IN(acdk::lang::Object) key, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey)
  {
    return (keyInMinRange(comp, key, minKey) && keyInMaxRange(comp, key, maxKey));
  }

  static bool keyInClosedRange(IN(RComparator) comp, IN(acdk::lang::Object) key, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey)
  {
    return (keyInMinRange(comp, key, minKey) && keyInClosedMaxRange(comp, key, maxKey));
  }
  static RRedBlackNode treeSearch(IN(RRedBlackNode) root, IN(RComparator) comp, IN(acdk::lang::Object) key);
  static RRedBlackNode treeMin(IN(RRedBlackNode) root);
  static RRedBlackNode treeMinConstrained(IN(RRedBlackNode) root, IN(RComparator) comp, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey);
  static RRedBlackNode treeMax(IN(RRedBlackNode) root);
  static RRedBlackNode treeMaxConstrained(IN(RRedBlackNode) root, IN(RComparator) comp, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey);

  static RRedBlackNode lowerBound(IN(RRedBlackNode) root, IN(RComparator) comp, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey)
  {
    return ((minKey != Nil) ? treeMinConstrained(root, comp, minKey, maxKey) : treeMin(root));
  }

  static RRedBlackNode upperBound(RRedBlackNode root, RComparator comp, acdk::lang::Object minKey, acdk::lang::Object maxKey)
  {
    return ((maxKey != Nil) ? treeMaxConstrained(root, comp, minKey, maxKey) : nilNode());
  }

  static RRedBlackNode treeSuccessor(IN(RRedBlackNode) nod);
  static RRedBlackNode treePredecessor(IN(RRedBlackNode) nod);
  foreign static RRedBlackNode treeInsert(IN(RTreeMap) tree,  IN(RComparator) comp,  IN(RRedBlackNode) newNode, acdk::lang::sys::Allocator* alloc);
  static void leftRotate(IN(RTreeMap) tree, IN(RRedBlackNode) nod);
  static void rightRotate(IN(RTreeMap) tree, IN(RRedBlackNode) nod);
  
  static RRedBlackNode rbInsert(IN(RTreeMap) tree,  IN(RComparator) comp, IN(RRedBlackNode) nod);
  
  static RRedBlackNode rbDelete(IN(RTreeMap) tree, IN(RRedBlackNode) nod, acdk::lang::sys::Allocator* alloc);
  static void rbDeleteFixup(IN(RTreeMap) tree, IN(RRedBlackNode) nod);

  static RRedBlackNode nilNode()
  {
    return RedBlackNode::nilNode();
  }
  friend class TreeMapIterator;
  
  friend class SubTreeMap;
  friend class TreeMapSetIterator;
  friend class TreeSet;
};


ACDK_DECL_CLASS(TreeMapIterator);
/**
  API: Java<br/>
  @author Roger Rene Kommer (mailto:kommer@artefaktur.com)
  @version $Revision: 1.22 $
  @date $Date: 2005/04/09 19:26:57 $
  
*/
class ACDK_CORE_PUBLIC TreeMapIterator
: extends acdk::lang::Object,
  implements Iterator
{
  ACDK_WITH_METAINFO(TreeMapIterator)
private:
  RTreeMap _map;
  RRedBlackNode _first;
  RRedBlackNode _last;
  RRedBlackNode _prev;
  MapEntryTyp _type;
  int _knownMods;
public:
  TreeMapIterator(IN(RTreeMap) map, IN(MapEntryTyp) type);
  virtual bool hasNext()
  {
    _checkMod();
    return (_first != TreeMap::nilNode());
  }
  virtual acdk::lang::Object element();
  virtual acdk::lang::Object next();
  
  virtual void remove();
private:
  void _checkMod()
  {
    if (_knownMods < _map->_modCount)
      THROW0(ConcurrentModificationException);
    }

};

ACDK_DECL_CLASS(TreeMapCollection);
/**
  API: Java<br/>
  @author Roger Rene Kommer (mailto:kommer@artefaktur.com)
  @version $Revision: 1.22 $
  @date $Date: 2005/04/09 19:26:57 $
  
*/
class ACDK_CORE_PUBLIC TreeMapCollection 
: extends AbstractCollection
, implements ::acdk::io::Serializable
{
  ACDK_WITH_METAINFO(TreeMapCollection)
private:
  RSortedMap _map;
public:
  TreeMapCollection(IN(RSortedMap) map)
  : AbstractCollection(),
    _map(map)
  {
  }
  virtual bool add(IN(acdk::lang::Object) object)
  {
    THROW0(UnsupportedOperationException);
    return false;
  }
  virtual bool addAll(IN(RCollection) coll) 
  {
    THROW0(UnsupportedOperationException);
    return false;
  }
  virtual void clear()
  {
    _map->clear();
  }
  virtual bool contains(IN(acdk::lang::Object) object)
  {
    return _map->containsValue(object);
  }
  virtual bool isEmpty()
  {
    return _map->isEmpty();
  }
  virtual int size()
  {
    return _map->size();
  }
  virtual RIterator iterator();
  virtual bool equals(IN(acdk::lang::Object) obj)
  {
    return _map->equals(obj);
  }
  virtual int hashCode()
  {
    return _map->hashCode();
  }
};

  
ACDK_DECL_CLASS(TreeMapSet);
/**
  API: Java<br/>
  @author Roger Rene Kommer (mailto:kommer@artefaktur.com)
  @version $Revision: 1.22 $
  @date $Date: 2005/04/09 19:26:57 $
  
*/
class ACDK_CORE_PUBLIC TreeMapSet 
: extends AbstractSet
, implements ::acdk::io::Serializable
{
  ACDK_WITH_METAINFO(TreeMapSet)
private:
  RSortedMap _map;
  RTreeMap _treeMap;
  MapEntryTyp _type;
public:
  TreeMapSet(IN(RSortedMap) sortedmap, IN(RTreeMap) treeMap, IN(MapEntryTyp) type)
  : AbstractSet(),
    _map(sortedmap),
    _treeMap(treeMap),
    _type(type)
  {
  }
  virtual bool add(IN(acdk::lang::Object) object) 
  {
    THROW0(UnsupportedOperationException);
    return false;
  }
  virtual bool addAll(IN(RCollection) coll) 
  {
    THROW0(UnsupportedOperationException);
    return false;
  }
  virtual void clear()
  {
    _map->clear();
  }
  virtual bool contains(IN(acdk::lang::Object) object);
  virtual bool isEmpty()
  {
    return _map->isEmpty();
  }
  virtual bool remove(IN(acdk::lang::Object) object);
  virtual int size()
  {
    return _map->size();
  }
  virtual RIterator iterator();
};


ACDK_DECL_CLASS(TreeMapSetIterator);  

class ACDK_CORE_PUBLIC TreeMapSetIterator
: extends acdk::lang::Object
, implements Iterator
{
  ACDK_WITH_METAINFO(TreeMapSetIterator)
private:
  RSortedMap _map;
  RTreeMap _treeMap;
  RRedBlackNode _first;
  RRedBlackNode _last;
  RRedBlackNode _prev;
  MapEntryTyp _type;
  int _knownMods;
public:
  TreeMapSetIterator(IN(RSortedMap) map, IN(RTreeMap) treemap, MapEntryTyp type);

  virtual bool hasNext()
  {
    _checkMod();
    return (_first != TreeMap::nilNode());
  }
  virtual acdk::lang::Object element();
  virtual acdk::lang::Object next();
  
  virtual void remove();
private:
  void _checkMod()
  {
    if (_knownMods < _treeMap->_modCount)
      THROW0(ConcurrentModificationException);
    }

};



ACDK_DECL_CLASS(SubTreeMap);  
/**
  API: Java<br/>
  @author Roger Rene Kommer (mailto:kommer@artefaktur.com)
  @version $Revision: 1.22 $
  @date $Date: 2005/04/09 19:26:57 $
  
*/
class ACDK_CORE_PUBLIC SubTreeMap
: extends AbstractMap
, implements SortedMap
, implements ::acdk::io::Serializable
{
  ACDK_WITH_METAINFO(SubTreeMap)
private:
  RTreeMap _map;
  acdk::lang::Object _minKey;
  acdk::lang::Object _maxKey;
public:
  SubTreeMap(IN(RTreeMap) map, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey)
  : _map(map),
    _minKey(minKey),
    _maxKey(maxKey)
  {
  }
  virtual void clear();
  virtual bool containsKey(IN(acdk::lang::Object) key);
  virtual bool containsValue(IN(acdk::lang::Object) val);
  virtual acdk::lang::Object get(IN(acdk::lang::Object) key);
  virtual acdk::lang::Object put(IN(acdk::lang::Object) key, IN(acdk::lang::Object) val);
  virtual void putAll(IN(RMap) map);
  virtual acdk::lang::Object remove(IN(acdk::lang::Object) key);
  virtual int size();
  virtual RSet entrySet();
  virtual RSet keySet()
  {
    return new TreeMapSet(RSortedMap(this), _map, Keys);
  }
  virtual RCollection values()
  {
    // probbly doesn't work
    return new TreeMapCollection(RSortedMap(this));
  }
  virtual RComparator comparator()
  {
    return _map->_comparator;
  }
  virtual acdk::lang::Object firstKey();
  virtual acdk::lang::Object lastKey();
  virtual RSortedMap subMap(IN(acdk::lang::Object) from, IN(acdk::lang::Object) to);
  virtual RSortedMap headMap(IN(acdk::lang::Object) to);
  virtual RSortedMap tailMap(IN(acdk::lang::Object) from);
  
  virtual bool equals(IN(acdk::lang::Object) other)
  {
    return AbstractMap::equals(other);
  }
  virtual int hashCode()
  {
    return AbstractMap::hashCode();
  }
  virtual bool isEmpty()
  {
    return AbstractMap::isEmpty();
  }
  RTreeMap parentTreeMap() { return _map; }
};


} // util
} // acdk
#endif //acdk_util_TreeMap_h