2005/5/9

--
down ACDK
down API Docs
down Namespaces
down acdk
down acdk::util
down TreeMap
  down members
  down Java (java.sun.com)
See also:
  down TreeMap.cpp
  down TreeMap.h

(c) 2005 by
Roger Rene Kommer

Kindly hosted at:
SourceForge.net Logo

     
 

class TreeMap
artefaktur
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]