artefaktur
software engineer &        architecture

 
 
 
 

class TreeMap

Modules   Namespace List   Class Hierarchy   Alphabetical List   Compound List   Namespace Members   Compound Members   Related Pages  

acdk::util::TreeMap Class Reference

#include <TreeMap.h>

Inheritance diagram for acdk::util::TreeMap:

acdk::util::AbstractMap acdk::util::SortedMap acdk::lang::Cloneable acdk::io::Serializable acdk::lang::Object acdk::util::Map acdk::lang::ObjectBase acdk::lang::dmi::StdDispatch List of all members.

Detailed Description

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.

ACDK: Roger Rene Kommer (mailto:kommer@artefaktur.com)

Version:
Revision
1.22
Date:
Date
2005/04/09 19:26:57


Public Member Functions

 TreeMap (IN(RComparator) comp=Nil)
 TreeMap (IN(RMap) map)
 TreeMap (IN(RSortedMap) sortedMap)
virtual void clear ()
virtual acdk::lang::Object clone ()
virtual acdk::lang::Object clone (sys::Allocator *alc)
virtual RComparator comparator ()
virtual bool containsKey (IN(acdk::lang::Object) key)
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 ()
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)
 Normally check for equality (not identity) Object::equals() is true only if both objects are the same instance.

virtual int hashCode ()
virtual bool isEmpty ()

Static Public Member Functions

acdk::lang::Object create_instance ()

Protected Member Functions

void putAllLinear (IN(RMapEntryArray) entries)

Static Private Member Functions

RRedBlackNode buildTree (IN(RMapEntryArray) entries, int height, bool completed, int currentTier, int start, int end, acdk::lang::sys::Allocator *alloc)
int compare (IN(RComparator) comp, IN(acdk::lang::Object) o1, IN(acdk::lang::Object) o2)
bool keyInMinRange (IN(RComparator) comp, IN(acdk::lang::Object) key, IN(acdk::lang::Object) minKey)
bool keyInMaxRange (IN(RComparator) comp, IN(acdk::lang::Object) key, IN(acdk::lang::Object) maxKey)
bool keyInClosedMaxRange (IN(RComparator) comp, IN(acdk::lang::Object) key, IN(acdk::lang::Object) maxKey)
bool keyInRange (IN(RComparator) comp, IN(acdk::lang::Object) key, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey)
bool keyInClosedRange (IN(RComparator) comp, IN(acdk::lang::Object) key, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey)
RRedBlackNode treeSearch (IN(RRedBlackNode) root, IN(RComparator) comp, IN(acdk::lang::Object) key)
RRedBlackNode treeMin (IN(RRedBlackNode) root)
RRedBlackNode treeMinConstrained (IN(RRedBlackNode) root, IN(RComparator) comp, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey)
RRedBlackNode treeMax (IN(RRedBlackNode) root)
RRedBlackNode treeMaxConstrained (IN(RRedBlackNode) root, IN(RComparator) comp, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey)
RRedBlackNode lowerBound (IN(RRedBlackNode) root, IN(RComparator) comp, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey)
RRedBlackNode upperBound (RRedBlackNode root, RComparator comp, acdk::lang::Object minKey, acdk::lang::Object maxKey)
RRedBlackNode treeSuccessor (IN(RRedBlackNode) nod)
RRedBlackNode treePredecessor (IN(RRedBlackNode) nod)
RRedBlackNode treeInsert (IN(RTreeMap) tree, IN(RComparator) comp, IN(RRedBlackNode) newNode, acdk::lang::sys::Allocator *alloc)
void leftRotate (IN(RTreeMap) tree, IN(RRedBlackNode) nod)
void rightRotate (IN(RTreeMap) tree, IN(RRedBlackNode) nod)
RRedBlackNode rbInsert (IN(RTreeMap) tree, IN(RComparator) comp, IN(RRedBlackNode) nod)
RRedBlackNode rbDelete (IN(RTreeMap) tree, IN(RRedBlackNode) nod, acdk::lang::sys::Allocator *alloc)
void rbDeleteFixup (IN(RTreeMap) tree, IN(RRedBlackNode) nod)
RRedBlackNode nilNode ()

Private Attributes

RRedBlackNode _root
int _size
RComparator _comparator
int _modCount

Friends

class TreeMapIterator
class SubTreeMap
class TreeMapSetIterator
class TreeSet

Constructor & Destructor Documentation

acdk::util::TreeMap::TreeMap IN(RComparator comp = Nil  ) 
 

acdk::util::TreeMap::TreeMap IN(RMap map  ) 
 

acdk::util::TreeMap::TreeMap IN(RSortedMap sortedMap  ) 
 


Member Function Documentation

RRedBlackNode acdk::util::TreeMap::buildTree IN(RMapEntryArray entries,
int  height,
bool  completed,
int  currentTier,
int  start,
int  end,
acdk::lang::sys::Allocator alloc
[static, private]
 

virtual void acdk::util::TreeMap::clear  )  [virtual]
 

Reimplemented from acdk::util::AbstractMap.

virtual acdk::lang::Object acdk::util::TreeMap::clone sys::Allocator *  alc  )  [virtual]
 

Reimplemented from acdk::lang::Cloneable.

virtual acdk::lang::Object acdk::util::TreeMap::clone  )  [inline, virtual]
 

Implements acdk::lang::Cloneable.

virtual RComparator acdk::util::TreeMap::comparator  )  [inline, virtual]
 

Implements acdk::util::SortedMap.

int acdk::util::TreeMap::compare IN(RComparator comp,
IN(acdk::lang::Object o1,
IN(acdk::lang::Object o2
[inline, static, private]
 

virtual bool acdk::util::TreeMap::containsKey IN(acdk::lang::Object key  )  [inline, virtual]
 

Reimplemented from acdk::util::AbstractMap.

virtual bool acdk::util::TreeMap::containsValue IN(acdk::lang::Object val  )  [virtual]
 

Reimplemented from acdk::util::AbstractMap.

acdk::lang::Object acdk::util::TreeMap::create_instance  )  [inline, static]
 

Reimplemented from acdk::lang::Object.

virtual RSet acdk::util::TreeMap::entrySet  )  [virtual]
 

Implements acdk::util::AbstractMap.

virtual bool acdk::util::TreeMap::equals IN(acdk::lang::Object other  )  [inline, virtual]
 

Normally check for equality (not identity) Object::equals() is true only if both objects are the same instance.

See also:
serialized_equals()

Reimplemented from acdk::util::AbstractMap.

virtual acdk::lang::Object acdk::util::TreeMap::firstKey  )  [virtual]
 

Implements acdk::util::SortedMap.

virtual acdk::lang::Object acdk::util::TreeMap::get IN(acdk::lang::Object key  )  [virtual]
 

Reimplemented from acdk::util::AbstractMap.

virtual int acdk::util::TreeMap::hashCode  )  [inline, virtual]
 

See also:
serialized_hashCode

Reimplemented from acdk::util::AbstractMap.

virtual RSortedMap acdk::util::TreeMap::headMap IN(acdk::lang::Object key  )  [virtual]
 

Implements acdk::util::SortedMap.

virtual bool acdk::util::TreeMap::isEmpty  )  [inline, virtual]
 

Reimplemented from acdk::util::AbstractMap.

bool acdk::util::TreeMap::keyInClosedMaxRange IN(RComparator comp,
IN(acdk::lang::Object key,
IN(acdk::lang::Object maxKey
[inline, static, private]
 

bool acdk::util::TreeMap::keyInClosedRange IN(RComparator comp,
IN(acdk::lang::Object key,
IN(acdk::lang::Object minKey,
IN(acdk::lang::Object maxKey
[inline, static, private]
 

bool acdk::util::TreeMap::keyInMaxRange IN(RComparator comp,
IN(acdk::lang::Object key,
IN(acdk::lang::Object maxKey
[inline, static, private]
 

bool acdk::util::TreeMap::keyInMinRange IN(RComparator comp,
IN(acdk::lang::Object key,
IN(acdk::lang::Object minKey
[inline, static, private]
 

bool acdk::util::TreeMap::keyInRange IN(RComparator comp,
IN(acdk::lang::Object key,
IN(acdk::lang::Object minKey,
IN(acdk::lang::Object maxKey
[inline, static, private]
 

virtual RSet acdk::util::TreeMap::keySet  )  [virtual]
 

Reimplemented from acdk::util::AbstractMap.

virtual acdk::lang::Object acdk::util::TreeMap::lastKey  )  [virtual]
 

Implements acdk::util::SortedMap.

void acdk::util::TreeMap::leftRotate IN(RTreeMap tree,
IN(RRedBlackNode nod
[static, private]
 

RRedBlackNode acdk::util::TreeMap::lowerBound IN(RRedBlackNode root,
IN(RComparator comp,
IN(acdk::lang::Object minKey,
IN(acdk::lang::Object maxKey
[inline, static, private]
 

RRedBlackNode acdk::util::TreeMap::nilNode  )  [inline, static, private]
 

virtual acdk::lang::Object acdk::util::TreeMap::put IN(acdk::lang::Object key,
IN(acdk::lang::Object val
[virtual]
 

Reimplemented from acdk::util::AbstractMap.

virtual void acdk::util::TreeMap::putAll IN(RMap map  )  [virtual]
 

Reimplemented from acdk::util::AbstractMap.

void acdk::util::TreeMap::putAllLinear IN(RMapEntryArray entries  )  [protected]
 

RRedBlackNode acdk::util::TreeMap::rbDelete IN(RTreeMap tree,
IN(RRedBlackNode nod,
acdk::lang::sys::Allocator alloc
[static, private]
 

void acdk::util::TreeMap::rbDeleteFixup IN(RTreeMap tree,
IN(RRedBlackNode nod
[static, private]
 

RRedBlackNode acdk::util::TreeMap::rbInsert IN(RTreeMap tree,
IN(RComparator comp,
IN(RRedBlackNode nod
[static, private]
 

virtual acdk::lang::Object acdk::util::TreeMap::remove IN(acdk::lang::Object key  )  [virtual]
 

Reimplemented from acdk::util::AbstractMap.

void acdk::util::TreeMap::rightRotate IN(RTreeMap tree,
IN(RRedBlackNode nod
[static, private]
 

virtual int acdk::util::TreeMap::size  )  [inline, virtual]
 

Reimplemented from acdk::util::AbstractMap.

virtual RSortedMap acdk::util::TreeMap::subMap IN(acdk::lang::Object from,
IN(acdk::lang::Object to
[virtual]
 

Implements acdk::util::SortedMap.

virtual RSortedMap acdk::util::TreeMap::tailMap IN(acdk::lang::Object from  )  [virtual]
 

Implements acdk::util::SortedMap.

RRedBlackNode acdk::util::TreeMap::treeInsert IN(RTreeMap tree,
IN(RComparator comp,
IN(RRedBlackNode newNode,
acdk::lang::sys::Allocator alloc
[static, private]
 

RRedBlackNode acdk::util::TreeMap::treeMax IN(RRedBlackNode root  )  [static, private]
 

RRedBlackNode acdk::util::TreeMap::treeMaxConstrained IN(RRedBlackNode root,
IN(RComparator comp,
IN(acdk::lang::Object minKey,
IN(acdk::lang::Object maxKey
[static, private]
 

RRedBlackNode acdk::util::TreeMap::treeMin IN(RRedBlackNode root  )  [static, private]
 

RRedBlackNode acdk::util::TreeMap::treeMinConstrained IN(RRedBlackNode root,
IN(RComparator comp,
IN(acdk::lang::Object minKey,
IN(acdk::lang::Object maxKey
[static, private]
 

RRedBlackNode acdk::util::TreeMap::treePredecessor IN(RRedBlackNode nod  )  [static, private]
 

RRedBlackNode acdk::util::TreeMap::treeSearch IN(RRedBlackNode root,
IN(RComparator comp,
IN(acdk::lang::Object key
[static, private]
 

RRedBlackNode acdk::util::TreeMap::treeSuccessor IN(RRedBlackNode nod  )  [static, private]
 

RRedBlackNode acdk::util::TreeMap::upperBound RRedBlackNode  root,
RComparator  comp,
acdk::lang::Object  minKey,
acdk::lang::Object  maxKey
[inline, static, private]
 

virtual RCollection acdk::util::TreeMap::values  )  [virtual]
 

Reimplemented from acdk::util::AbstractMap.


Friends And Related Function Documentation

friend class SubTreeMap [friend]
 

friend class TreeMapIterator [friend]
 

friend class TreeMapSetIterator [friend]
 

friend class TreeSet [friend]
 


Member Data Documentation

RComparator acdk::util::TreeMap::_comparator [private]
 

int acdk::util::TreeMap::_modCount [private]
 

RRedBlackNode acdk::util::TreeMap::_root [private]
 

int acdk::util::TreeMap::_size [private]
 

 
Last modified 2005-05-08 18:33 by SYSTEM By Artefaktur, Ing. Bureau Kommer