2005/5/9

     
 

TreeMap.cpp

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, 2000, 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.cpp,v 1.21 2005/03/08 12:45:46 kommer Exp $
#include <acdk.h>

#include "TreeMap.h"

#include <acdk/lang/System.h>
#include <acdk/lang/IllegalArgumentException.h>
#include <acdk/lang/IllegalStateException.h>
#include "NoSuchElementException.h"
#include <acdk/lang/UnsupportedOperationException.h>

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

namespace acdk {
namespace util {

NilRedBlackNode::NilRedBlackNode()
: RedBlackNode(Nil, Nil)
{
  ACDK_SAFE_CONSTRUCTOR();
  _left = this;
  releaseRef();
  _right = this;
  releaseRef();
  _parent = this;
  releaseRef();
}

NilRedBlackNode::~NilRedBlackNode()
{
  _setObjectRefFlag(true, IsWeakRef);
}

RRedBlackNode RedBlackNode::_nilNode;// = new RedBlackNode(null, null);
//static 
RRedBlackNode 
RedBlackNode::nilNode()
{
  static bool initialiseNilNode = false;
  if (_nilNode == Nil && initialiseNilNode == false) {
    initialiseNilNode = true;
    _nilNode = new NilRedBlackNode();
    System::registerStaticReference(_nilNode);
    initialiseNilNode = false;
  }
  return _nilNode;
}

TreeMap::TreeMap(IN(RComparator) comp)
: _root(nilNode()),
  _size(0),
  _comparator(comp),
  _modCount(0)
{
}
  
TreeMap::TreeMap(IN(RMap) map)
: _root(nilNode()),
  _size(0),
  _comparator(Nil),
  _modCount(0)
{
  if (map != Nil)
    putAll(map);
}


TreeMap::TreeMap(IN(RSortedMap) sortedMap)
: _root(nilNode()),
  _size(0),
  _comparator(sortedMap->comparator()),
  _modCount(0)
{
  RMapEntryArray entries = new (allocator()) MapEntryArray(sortedMap->size());
  RIterator it = sortedMap->entrySet()->iterator();
  int i = 0;
  while (it->hasNext() == true) {
    RMapEntry tmapentry = RMapEntry(it->next());
    entries[i++] = tmapentry;
  }
  _size = i;
  putAllLinear(entries);
}

//virtual 
void 
TreeMap::clear()
{
  RRedBlackNode nn = nilNode();
  
  if (_root != nn && _root != Nil)
    _root->_clear();

  _root = nn;
  _size = 0;
  _modCount++;
}

//virtual 
acdk::lang::Object 
TreeMap::clone(sys::Allocator* alc)
{
  return new (alc) TreeMap(RSortedMap(const_cast<TreeMap*>(this)));
}

//virtual 
bool 
TreeMap::containsValue(IN(acdk::lang::Object) val)
{
  RRedBlackNode nod = treeMin(_root); 
  acdk::lang::Object curVal;
  while (nod != nilNode()) {
    curVal = nod->getValue();
    if (((val == Nil) && (curVal == Nil)) || val->equals(curVal))
      return true;
    nod = treeSuccessor(nod);
  }
  return false;
}

//virtual 
RSet 
TreeMap::entrySet()
{
  return new TreeMapSet(this, this, Entries);
}


//virtual 
acdk::lang::Object 
TreeMap::firstKey()
{
  try {
    return treeMin(_root)->getKey();
  } catch (RNullPointerException ) {
    THROW1(NoSuchElementException, "TreeMap is empty");
  }
  return Nil;
}

//virtual 
acdk::lang::Object 
TreeMap::get(IN(acdk::lang::Object) key)
{
  RRedBlackNode nod = treeSearch(_root, _comparator, key);
  return (nod != nilNode()) ? nod->getValue() : acdk::lang::Object(Nil);
}


//virtual 
RSortedMap 
TreeMap::headMap(IN(acdk::lang::Object) key)
{
  if (keyInClosedMaxRange(_comparator, key, Nil))
    return new SubTreeMap(this, Nil, key);
  THROW0(IllegalArgumentException);
  return Nil;
}


//virtual 
RSet 
TreeMap::keySet()
{
  return new TreeMapSet(this, this, Keys);
}


//virtual 
acdk::lang::Object 
TreeMap::lastKey()
{
  try {
    return treeMax(_root)->getKey();
  } catch (RNullPointerException) {
    THROW1(NoSuchElementException, "TreeMap is empty");
  }
  return Nil;
}

//virtual 
acdk::lang::Object 
TreeMap::put(IN(acdk::lang::Object) key, IN(acdk::lang::Object) val)
{
  RRedBlackNode entry = rbInsert(this, _comparator, new (allocator()) RedBlackNode(key, val));
  if (entry == nilNode())
    _size++;
  _modCount++;
  return ((entry == nilNode()) ? acdk::lang::Object(Nil) : entry->getValue());
}

//virtual 
void 
TreeMap::putAll(IN(RMap) map)
{
  RIterator it = map->entrySet()->iterator();
  RMapEntry entry;
  while (it->hasNext()) {
    entry = RMapEntry(it->next());
    put(entry->getKey(), entry->getValue());
  }
}

//virtual 
acdk::lang::Object 
TreeMap::remove(IN(acdk::lang::Object) key)
{
  RRedBlackNode result = treeSearch(_root, _comparator, key);
  if (result == nilNode()) 
    return Nil;
  result = rbDelete(this, result, allocator());
  _size--;
  _modCount++;
  return result->getValue();
}

//virtual 
RSortedMap 
TreeMap::subMap(IN(acdk::lang::Object) from, IN(acdk::lang::Object) to)
{
  if (compare(_comparator, from, to) < 0)
      return new SubTreeMap(this, from, to);
  THROW0(IllegalArgumentException);
  return Nil;
}

//virtual 
RSortedMap 
TreeMap::tailMap(IN(acdk::lang::Object) from)
{
  if (keyInMinRange(_comparator, from, Nil))
      return new SubTreeMap(this, from, Nil);
  THROW0(IllegalArgumentException);
  return Nil;
}

//virtual 
RCollection 
TreeMap::values()
{
  return new TreeMapCollection(this);
}

void 
TreeMap::putAllLinear(IN(RMapEntryArray) entries)
{
  double dHeight = Math::pow((double) entries->length(), (double) 0.5);
  int height = (int) dHeight;
  bool completed = (dHeight == ((double) height));
  _root = buildTree(entries, height, completed, 0, 0, entries->length(), allocator());
}

//static 
RRedBlackNode 
TreeMap::buildTree(IN(RMapEntryArray) entries, int height,  bool completed, int currentTier,  int start, int end,
                   acdk::lang::sys::Allocator* alloc)
{
  
  
  if (start == end) 
    return nilNode();
  int rootIndex = (end + start) / 2;
  RMapEntry tentry = entries[rootIndex];
  RRedBlackNode newTree = new (alloc) RedBlackNode(tentry->getKey(), tentry->getValue());
  newTree->_left = buildTree(entries, height, completed,  (currentTier + 1), start, rootIndex, alloc);
  newTree->_right = buildTree(entries, height, completed, (currentTier + 1),  (rootIndex + 1), end, alloc);
  if ((completed == false) &&  ((height % 2) == 1) && (currentTier >= (height - 2)))
    newTree->_color = (currentTier == (height - 1)) ? BlackNodeType : BlackNodeType; // ### ????
  else
    newTree->_color = ((currentTier % 2) == 1) ? BlackNodeType : BlackNodeType; // ### ?????
  if (newTree->_left != nilNode())
    newTree->_left->_parent = newTree;
  if (newTree->_right != nilNode())
    newTree->_right->_parent = newTree;
  return newTree;
}

//static 
RRedBlackNode 
TreeMap::treeSearch(IN(RRedBlackNode) rootNode, IN(RComparator) comp, IN(acdk::lang::Object) key)
{
  int res;
  RRedBlackNode root = rootNode;
  while (root != nilNode()) {
    res = compare(comp, key, root->getKey());
    if (res == 0)
      return root;
    if (res < 0)
      root = root->_left;
    else
      root = root->_right;
  }
  return root;
}

//static 
RRedBlackNode 
TreeMap::treeMin(IN(RRedBlackNode) rootNode)
{
  
  RRedBlackNode root = rootNode;
  while (root->_left != nilNode())
    root = root->_left;
  return root;
}

//static 
RRedBlackNode 
TreeMap::treeMinConstrained(IN(RRedBlackNode) rootNode, IN(RComparator) comp, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey)
{
  int dif;
  RRedBlackNode root = rootNode;
  RRedBlackNode curNode = nilNode();
  do {
    curNode = root;
    dif = compare(comp, minKey, curNode->getKey());
    if (dif == 0)
      return root;
    root = (dif < 0) ? curNode->_left : curNode->_right;
  } while (root != nilNode());
  if (dif > 0)
    curNode = treeSuccessor(curNode);
  return curNode;
}

//static 
RRedBlackNode 
TreeMap::treeMax(IN(RRedBlackNode) rootNode)
{
  
  RRedBlackNode root = rootNode;
  while (root->_right != nilNode())
    root = root->_right;
  return root;
}

//static 
RRedBlackNode 
TreeMap::treeMaxConstrained(IN(RRedBlackNode) rootNode, IN(RComparator) comp, IN(acdk::lang::Object) minKey, IN(acdk::lang::Object) maxKey)
{
  int dif;
  RRedBlackNode curNode = nilNode();
  RRedBlackNode root = rootNode;
  do {
    curNode = root;
    dif = compare(comp, maxKey, curNode->getKey());
    if (dif == 0)
      return root;
    root = (dif < 0) ? curNode->_left : curNode->_right;
  } while (root != nilNode());
  if (dif < 0)
    curNode = treePredecessor(curNode);
  return curNode;
}


//static 
RRedBlackNode 
TreeMap::treeSuccessor(IN(RRedBlackNode) nod)
{
  
  if (nod->_right != nilNode())
    return treeMin(nod->_right);

  RRedBlackNode node = nod;

  RRedBlackNode parent = node->_parent;
  while ((parent != nilNode()) && (node == parent->_right)) {
    node = parent;
    parent = parent->_parent;
  }
  return parent;
}

//static 
RRedBlackNode 
TreeMap::treePredecessor(IN(RRedBlackNode) node)
{
  if (node->_left != nilNode())
    return treeMax(node->_left);

  RRedBlackNode nod = node;
  RRedBlackNode parent = nod->_parent;
  while ((parent != nilNode()) && (nod == parent->_left)) {
    nod = parent;
    parent = parent->_parent;
  }
  return parent;
}

//static 
RRedBlackNode 
TreeMap::treeInsert(IN(RTreeMap) tree, IN(RComparator) comp, IN(RRedBlackNode) newNode, acdk::lang::sys::Allocator* alloc)
{
  int res;
  acdk::lang::Object newKey = newNode->getKey();
  RRedBlackNode parent = nilNode();
  RRedBlackNode root = tree->_root;
  RRedBlackNode result = nilNode();

  while (root != nilNode()) {
    parent = root;
    res = compare(comp, newKey, root->getKey());
    if (res == 0) {
      result = new (alloc) RedBlackNode(root->getKey(), root->getValue());
      root->_key = newNode->_key;
      root->_value = newNode->_value;
      return result;
    } else {
      root = (res < 0) ? root->_left : root->_right;
    }
  }
  
  newNode->_parent = parent;
  if (parent == nilNode())
    tree->_root = newNode;
  else if (compare(comp, newKey, parent->getKey()) < 0)
    parent->_left = newNode;
  else
    parent->_right = newNode;
  return root;
}


//static 
void 
TreeMap::leftRotate(IN(RTreeMap) tree, IN(RRedBlackNode) nod)
{
  RRedBlackNode child = nod->_left;
  nod->_left = child->_right;
  if (child->_right != nilNode())
    child->_right->_parent = nod;
  child->_parent = nod->_parent;
  if (nod->_parent == nilNode())
    tree->_root = child;
  else if (nod == nod->_parent->_right)
    nod->_parent->_right = child;
  else
    nod->_parent->_left = child;
  child->_right = nod;
  nod->_parent = child;
}

//static 
void 
TreeMap::rightRotate(IN(RTreeMap) tree, IN(RRedBlackNode) nod)
{
  RRedBlackNode child = nod->_left;
  nod->_left = child->_right;
  if (child->_right != nilNode())
    child->_right->_parent = nod;
  child->_parent = nod->_parent;
  if (nod->_parent == nilNode())
    tree->_root = child;
  else if (nod == nod->_parent->_right)
    nod->_parent->_right = child;
  else
    nod->_parent->_left = child;
  child->_right = nod;
  nod->_parent = child;
}

//static 
RRedBlackNode 
TreeMap::rbInsert(IN(RTreeMap) tree,  IN(RComparator) comp, IN(RRedBlackNode) node)
{
  RRedBlackNode uncle = nilNode();
  RRedBlackNode nod = node;
  RRedBlackNode result = treeInsert(tree, comp, nod, tree->allocator());
  
  if (result == nilNode()) 
  {
    nod->_color = RedNodeType;
    while ((nod != tree->_root) && (nod->_parent->_color == RedNodeType)) 
    {
      if (nod->_parent == nod->_parent->_parent->_right) {
        uncle = nod->_parent->_parent->_right;
        if (uncle->_color == RedNodeType) {
          nod->_parent->_color = BlackNodeType;
          uncle->_color = BlackNodeType;
          nod->_parent->_parent->_color = RedNodeType;
          nod = nod->_parent->_parent;
        } else {
          if (nod == nod->_parent->_right) {
            nod = nod->_parent;
            leftRotate(tree, nod);
          }
          nod->_parent->_color = BlackNodeType;
          nod->_parent->_parent->_color = RedNodeType;
          rightRotate(tree, nod->_parent->_parent);
        }
      } else {
        uncle = nod->_parent->_parent->_left;
        if (uncle->_color == RedNodeType) {
          nod->_parent->_color = BlackNodeType;
          uncle->_color = BlackNodeType;
          nod->_parent->_parent->_color = RedNodeType;
          nod = nod->_parent->_parent;
        } else {
          if (nod == nod->_parent->_left) {
            nod = nod->_parent;
            rightRotate(tree, nod);
          }
          nod->_parent->_color = BlackNodeType;
          nod->_parent->_parent->_color = RedNodeType;
          leftRotate(tree, nod->_parent->_parent);
        }
      }
    }
  }
  tree->_root->_color = BlackNodeType;
  return result;
}


//static 
RRedBlackNode 
TreeMap::rbDelete(IN(RTreeMap) tree, IN(RRedBlackNode) nod, acdk::lang::sys::Allocator* alloc)
{
  RRedBlackNode splice = nilNode();
  RRedBlackNode child = nilNode();
  RRedBlackNode sentinelParent = nilNode();
  RRedBlackNode result = nod;
  
  splice = (((nod->_left == nilNode()) || (nod->_right == nilNode())) ? nod : treeSuccessor(nod));
  child = (splice->_left != nilNode()) ? splice->_left : splice->_right;
  
  child->_parent = splice->_parent;
  
  if (splice->_parent == nilNode())
    tree->_root = child;
  else if (splice == splice->_parent->_left)
    splice->_parent->_left = child;
  else
    splice->_parent->_right = child;
  
  if (splice != nod) {
    result = new (alloc) RedBlackNode(nod->getKey(), nod->getValue());
    nod->_key = splice->_key;
    nod->_value = splice->_value;
  }
  
  if (splice->_color == BlackNodeType)
    rbDeleteFixup(tree, child);
  
  return result;
}

//static 
void 
TreeMap::rbDeleteFixup(IN(RTreeMap) tree, IN(RRedBlackNode) node)
{
  
  RRedBlackNode sibling = nilNode();
  RRedBlackNode nod = node;
  while ((nod != tree->_root) && (nod->_color == BlackNodeType)) {
    if (nod == nod->_parent->_left) {
      sibling = nod->_parent->_right;
      if (sibling->_color == RedNodeType) {
        sibling->_color = BlackNodeType;
        nod->_parent->_color = RedNodeType;
        leftRotate(tree, nod->_parent);
        sibling = nod->_parent->_right;
      }
      if ((sibling->_left->_color == BlackNodeType) && 
        (sibling->_right->_color == BlackNodeType)) {
        sibling->_color = RedNodeType;
        nod = nod->_parent;
      } else {
        if (sibling->_right->_color == BlackNodeType) {
          sibling->_left->_color = BlackNodeType;
          sibling->_color = RedNodeType;
          rightRotate(tree, sibling);
          sibling = nod->_parent->_right;
        }
        sibling->_color = nod->_parent->_color;
        nod->_parent->_color = BlackNodeType;
        sibling->_right->_color = BlackNodeType;
        leftRotate(tree, nod->_parent);
        nod = tree->_root;
      }
    } else {
      sibling = nod->_parent->_left;
      if (sibling->_color == RedNodeType) {
        sibling->_color = BlackNodeType;
        nod->_parent->_color = RedNodeType;
        rightRotate(tree, nod->_parent);
        sibling = nod->_parent->_left;
      }
      if ((sibling->_right->_color == BlackNodeType) && 
        (sibling->_left->_color == BlackNodeType)) {
        sibling->_color = RedNodeType;
        nod = nod->_parent;
      } else {
        if (sibling->_left->_color == BlackNodeType) {
          sibling->_right->_color = BlackNodeType;
          sibling->_color = RedNodeType;
          leftRotate(tree, sibling);
          sibling = nod->_parent->_left;
        }
        sibling->_color = nod->_parent->_color;
        nod->_parent->_color = BlackNodeType;
        sibling->_left->_color = BlackNodeType;
        rightRotate(tree, nod->_parent);
        nod = tree->_root;
      }
    }
  }
  nod->_color = BlackNodeType;
}


TreeMapIterator::TreeMapIterator(IN(RTreeMap) map, IN(MapEntryTyp) type)
: _map(map),
  _first(),
  _last(),
  _prev(TreeMap::nilNode()),
  _type(type),
  _knownMods(map->_modCount)
{
  if (_map->isEmpty()) {
    _first = RedBlackNode::nilNode();
  } else {
    _first = TreeMap::treeSearch(_map->_root, _map->_comparator, _map->firstKey());
    _last = TreeMap::treeSearch(_map->_root, _map->_comparator, _map->lastKey());
  }
}

//virtual 
acdk::lang::Object 
TreeMapIterator::next()
{
  _checkMod();
  RRedBlackNode result = _first;
  if (result == RedBlackNode::nilNode())
    THROW0(NoSuchElementException);
  if (result == _last)
    _first = RedBlackNode::nilNode();
  else
    _first = TreeMap::treeSuccessor(_first);
  _prev = result;
  if (_type == Keys) 
    return result->getKey();
  if (_type == Values)
    return result->getValue();
  return (acdk::lang::Object)result;
}

//virtual 
acdk::lang::Object 
TreeMapIterator::element() // ### @todo implement me
{
  THROW0(UnsupportedOperationException);
  return Nil;
}
//virtual 
void 
TreeMapIterator::remove()
{
  _checkMod();
  if (_prev == RedBlackNode::nilNode()) 
    THROW0(IllegalStateException);
  acdk::lang::Object key = _prev->getKey();
  if (_map->containsKey(key)) {
    _map->remove(key);
    _knownMods++;
  }
  _prev = RedBlackNode::nilNode();
}
  

TreeMapSetIterator::TreeMapSetIterator(IN(RSortedMap) map, IN(RTreeMap) treemap, MapEntryTyp type)
: _map(map),
  _treeMap(treemap),
  _first(),
  _last(),
  _prev(TreeMap::nilNode()),
  _type(type),
  _knownMods(treemap->_modCount)
{
  if (_map->isEmpty()) {
    _last = _first = RedBlackNode::nilNode();
  } else {
    _first = TreeMap::treeSearch(_treeMap->_root, _treeMap->_comparator, _map->firstKey());
    _last = TreeMap::treeSearch(_treeMap->_root, _treeMap->_comparator, _map->lastKey());
  }
}

//virtual 
acdk::lang::Object 
TreeMapSetIterator::next()
{
  _checkMod();
  RRedBlackNode result = _first;
  if (result == RedBlackNode::nilNode())
    THROW0(NoSuchElementException);
  if (result == _last)
    _first = RedBlackNode::nilNode();
  else
    _first = TreeMap::treeSuccessor(_first);
  _prev = result;
  if (_type == Keys) 
    return result->getKey();
  if (_type == Values)
    return result->getValue();
  return (acdk::lang::Object)result;
}

//virtual 
acdk::lang::Object 
TreeMapSetIterator::element()
{
  THROW0(UnsupportedOperationException);
  return Nil;
}
//virtual 
void 
TreeMapSetIterator::remove()
{
  _checkMod();
  if (_prev == RedBlackNode::nilNode()) 
    THROW0(IllegalStateException);
  acdk::lang::Object key = _prev->getKey();
  if (_map->containsKey(key)) {
    _map->remove(key);
    _knownMods++;
  }
  _prev = RedBlackNode::nilNode();
}
  

//virtual 
RIterator 
TreeMapCollection::iterator()
{
  if (instanceof(_map, TreeMap) == true)
    return new TreeMapIterator(RTreeMap(_map), Values);
  else if (instanceof(_map, SubTreeMap) == true) 
  {
    RSubTreeMap sbm = (RSubTreeMap)_map;
    return new TreeMapSetIterator(_map, sbm->parentTreeMap(), Values);
  } else
    return Nil;
}


//virtual 
bool 
TreeMapSet::contains(IN(acdk::lang::Object) object)
{
  if (_type == Keys) 
      return _map->containsKey(object);
  if (instanceof(object, MapEntry)) {
    RMapEntry entry = RMapEntry(object);
    acdk::lang::Object key = entry->getKey();
    if (_map->containsKey(key)) {
      acdk::lang::Object inputVal = entry->getValue();
      acdk::lang::Object mapValue = _map->get(key);
      return ((inputVal == Nil)  ? (mapValue == Nil) : (inputVal->equals(mapValue)));
    }
  }
  return false;
}

//virtual 
RIterator 
TreeMapSet::iterator()
{
  RTreeMapSetIterator tmi = new TreeMapSetIterator(_map, _treeMap, _type); 
  return (RIterator)tmi;
}


//virtual 
bool 
TreeMapSet::remove(IN(acdk::lang::Object) object)
{
  if (_type == Keys)
    return (_map->remove(object) != Nil);
  if (instanceof(object, MapEntry) == true)
    return _map->remove(RMapEntry(object)->getKey()) != Nil;
  return false;
}


//virtual 
void 
SubTreeMap::clear()
{
  RRedBlackNode minNode = TreeMap::lowerBound(_map->_root, _map->_comparator, _minKey, _maxKey);
  RRedBlackNode maxNode = TreeMap::upperBound(_map->_root, _map->_comparator, _minKey, _maxKey);
  acdk::lang::Object maxKey = maxNode->getKey();
  while ((minNode != RedBlackNode::nilNode()) &&  ((maxNode == RedBlackNode::nilNode()) ||  
          (TreeMap::compare(_map->_comparator,  minNode->getKey(), maxKey) < 0))) {
    _map->remove(minNode->getKey());
    minNode = TreeMap::treeSuccessor(minNode);
  }
}

//virtual 
bool 
SubTreeMap::containsKey(IN(acdk::lang::Object) key)
{
  return  (TreeMap::keyInRange(_map->_comparator, key, _minKey, _maxKey) && _map->containsKey(key)); 
}    
  
//virtual 
bool 
SubTreeMap::containsValue(IN(acdk::lang::Object) val)
{
  acdk::lang::Object curVal;
  RRedBlackNode minNode = TreeMap::lowerBound(_map->_root,  _map->_comparator, _minKey, _maxKey);
  RRedBlackNode maxNode = TreeMap::upperBound(_map->_root,  _map->_comparator, _minKey, _maxKey);
  acdk::lang::Object maxKey = maxNode->getKey();
  while ((minNode != RedBlackNode::nilNode()) && 
        ((maxNode == RedBlackNode::nilNode()) || 
        (TreeMap::compare(_map->_comparator, 
        minNode->getKey(), maxKey) < 0))) {
    curVal = minNode->getValue();
    if (((val == Nil) && (curVal == Nil)) || val->equals(curVal))
      return true;
    minNode = TreeMap::treeSuccessor(minNode);        
  }
  return false;
}

//virtual 
RSet 
SubTreeMap::entrySet()
{
  RSubTreeMap stm((SubTreeMap*) this);
  RSortedMap sm = (RSortedMap) stm;
  RTreeMapSet tms = new TreeMapSet(sm, _map, Entries); // RSortedMap sortedmap, RTreeMap treeMap, MapEntryTyp type)
  return (RSet) tms;
}

//virtual 
acdk::lang::Object 
SubTreeMap::get(IN(acdk::lang::Object) key)
{
  if (TreeMap::keyInRange(_map->_comparator, key, _minKey, _maxKey))
    return _map->get(key);
  return Nil;
}
  
//virtual 
acdk::lang::Object 
SubTreeMap::put(IN(acdk::lang::Object) key, IN(acdk::lang::Object) val)
{
  if (TreeMap::keyInRange(_map->_comparator, key, _minKey, _maxKey))
    return _map->put(key, val);
  THROW0(IllegalArgumentException);
  return Nil;
}
    
//virtual 
void 
SubTreeMap::putAll(IN(RMap) map)
{
  RMapEntry entry;
  RIterator it = map->entrySet()->iterator();
  while (it->hasNext()) {
    entry = RMapEntry(it->next());
    put(entry->getKey(), entry->getValue());
  }
}

//virtual 
acdk::lang::Object 
SubTreeMap::remove(IN(acdk::lang::Object) key)
{
  if (TreeMap::keyInRange(_map->_comparator, key, _minKey, _maxKey))
    return _map->remove(key);
  THROW0(IllegalArgumentException);
  return Nil;
}
  
//virtual 
int 
SubTreeMap::size()
{
  
  RRedBlackNode minNode = TreeMap::lowerBound(_map->_root, _map->_comparator, _minKey, _maxKey);
  RRedBlackNode maxNode = TreeMap::upperBound(_map->_root, _map->_comparator, _minKey, _maxKey);
  acdk::lang::Object maxKey = maxNode->getKey();
  int count = 0;
  while ((minNode != RedBlackNode::nilNode()) && 
        ((maxNode == RedBlackNode::nilNode()) || 
        (TreeMap::compare(_map->_comparator, 
        minNode->getKey(), maxKey) < 0))) {
    count++;
    minNode = TreeMap::treeSuccessor(minNode);
  }
  return count;
}

//virtual 
acdk::lang::Object 
SubTreeMap::firstKey()
{
  RRedBlackNode first = TreeMap::lowerBound(_map->_root, _map->_comparator, _minKey, _maxKey);
  return (first != RedBlackNode::nilNode()) ? first->getKey() : acdk::lang::Object(Nil);
}

//virtual 
acdk::lang::Object 
SubTreeMap::lastKey()
{
  RRedBlackNode last = RedBlackNode::nilNode();
  if (_maxKey == Nil) {
    last = TreeMap::treeMax(_map->_root);
    return (last != RedBlackNode::nilNode()) ? last->getKey() : acdk::lang::Object(Nil);
  } else {
    last = TreeMap::treeMaxConstrained(_map->_root,
      _map->_comparator,
      _minKey, _maxKey);
    return (last != RedBlackNode::nilNode()) ? TreeMap::treePredecessor(last)->getKey() : acdk::lang::Object(Nil);
  }
}


//virtual 
RSortedMap 
SubTreeMap::subMap(IN(acdk::lang::Object) from, IN(acdk::lang::Object) to)
{
  if ((TreeMap::compare(_map->_comparator, from, to) < 0) &&
      TreeMap::keyInMinRange(_map->_comparator,  from, _minKey) &&
      TreeMap::keyInClosedMaxRange(_map->_comparator, from, _maxKey) &&
      TreeMap::keyInMinRange(_map->_comparator,  to, _minKey) &&
      TreeMap::keyInClosedMaxRange(_map->_comparator, to, _maxKey))
    return new SubTreeMap(_map, from, to);
  THROW0(IllegalArgumentException);
  return Nil;
}
  
//virtual 
RSortedMap 
SubTreeMap::headMap(IN(acdk::lang::Object) to)
{
  if (TreeMap::keyInMinRange(_map->_comparator, to, _minKey) &&
      TreeMap::keyInClosedMaxRange(_map->_comparator, to, _maxKey))
    return new SubTreeMap(_map, _minKey, to);
  THROW0(IllegalArgumentException);
  return Nil;
}
  
//virtual 
RSortedMap 
SubTreeMap::tailMap(IN(acdk::lang::Object) from)
{
  if (TreeMap::keyInMinRange(_map->_comparator, from, _minKey) &&
      TreeMap::keyInClosedMaxRange(_map->_comparator, from, _maxKey))
    return new SubTreeMap(_map, from, _maxKey);

  THROW0(IllegalArgumentException);
  return Nil;
}

} // util
} // acdk