flu_tree_browser.cpp

来自「ncbi源码」· C++ 代码 · 共 2,583 行 · 第 1/5 页

/*
 * ===========================================================================
 * PRODUCTION $Log: Flu_Tree_Browser.cpp,v $
 * PRODUCTION Revision 1000.1  2004/06/01 21:06:08  gouriano
 * PRODUCTION PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.6
 * PRODUCTION
 * ===========================================================================
 */

/*
 * These files were imported into NCBI's CVS directly from FLU version 2.9.1.
 * Modifications to the source are listed below.
 *
 * ==========================================================================
 * $Log: Flu_Tree_Browser.cpp,v $
 * Revision 1000.1  2004/06/01 21:06:08  gouriano
 * PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.6
 *
 * Revision 1.6  2004/05/21 22:27:51  gorelenk
 * Added PCH ncbi_pch.hpp
 *
 * Revision 1.5  2004/03/11 14:10:10  dicuccio
 * Fixes for 64-bit compilation.  Cast away const from strchr() where needed
 *
 * Revision 1.4  2004/03/11 13:51:40  dicuccio
 * Imported FLU version 2.9.1.  Altered export specifiers to match NCBI layout.
 * Altered include paths to match NCBI toolkit layout.
 *
 * ==========================================================================
 */
// $Id: Flu_Tree_Browser.cpp,v 1000.1 2004/06/01 21:06:08 gouriano Exp $

/***************************************************************
 *                FLU - FLTK Utility Widgets 
 *  Copyright (C) 2002 Ohio Supercomputer Center, Ohio State University
 *
 * This file and its content is protected by a software license.
 * You should have received a copy of this license with this file.
 * If not, please contact the Ohio Supercomputer Center immediately:
 * Attn: Jason Bryan Re: FLU 1224 Kinnear Rd, Columbus, Ohio 43212
 * 
 ***************************************************************/



#include <ncbi_pch.hpp>
#include <FL/Fl.H>
#include <FL/fl_draw.H>
#include <FL/math.h>
#include <stdlib.h>

#include <gui/widgets/FLU/Flu_Tree_Browser.h>
#include <gui/widgets/FLU/flu_pixmaps.h>

#define MAX( x, y ) ( (x)>(y) ? (x) : (y) )
#define MIN( x, y ) ( (x)<(y) ? (x) : (y) )
#define ABS( x ) ( (x)>0 ? (x) : -(x) )
#define LERP( t, x0, x1 ) ( (x0) + (t)*( (x1) - (x0) ) )

#ifdef USE_FLU_DND
Flu_Tree_Browser :: DND_Object :: DND_Object() : Flu_DND( "DND_Object" )
{
}
#endif

Flu_Tree_Browser :: IntStack :: IntStack()
{
  _list = NULL;
  _size = _bufferSize = 0;
}

Flu_Tree_Browser :: IntStack :: IntStack( const Flu_Tree_Browser::IntStack& s )
{
  _list = NULL;
  _size = _bufferSize = 0;
  *this = s;
}

Flu_Tree_Browser :: IntStack :: ~IntStack()
{
  clear();
}

Flu_Tree_Browser::IntStack& Flu_Tree_Browser :: IntStack :: operator =( const Flu_Tree_Browser::IntStack& s )
{
  clear();
  if( s._size )
    {
      _list = (int*)malloc( s._size*sizeof(int) );
      memcpy( _list, s._list, s._size*sizeof(int) );
      _size = _bufferSize = s._size;
    }
  return *this;
}

void Flu_Tree_Browser :: IntStack :: push( int i )
{
  if( _size == _bufferSize )
    {
      // allocate a new list
      _bufferSize += 4;
      int *newList = (int*)malloc( _bufferSize*sizeof(int) );
      // copy the old list
      if( _size > 0 )
	memcpy( newList, _list, _size*sizeof(int) );
      if( _list )
	free( _list );
      _list = newList;
    }
  // add the new item
  _list[_size] = i;
  _size++;
}

int Flu_Tree_Browser :: IntStack :: pop()
{
  if( _size == 0 )
    return 0;
  int val = _list[_size];
  _size--;
  return val;
}

void Flu_Tree_Browser :: IntStack :: clear()
{
  if( _list )
    free( _list );
  _list = NULL;
  _size = _bufferSize = 0;
}

Flu_Tree_Browser :: NodeList :: NodeList()
{
  _nodes = NULL;
  _nNodes = _size = 0;
}

Flu_Tree_Browser :: NodeList :: ~NodeList()
{
  clear();
}

typedef Flu_Tree_Browser::Node* NodeP;

bool Flu_Tree_Browser :: NodeList :: search( const char *n, int &index )
{
  index = _nNodes;
  if( _nNodes == 0 )
    return false;

  // we know we have at least one node. so use it to get the RData struct to find out what
  // the insertion mode is
  int iMode = _nodes[0]->tree->insertion_mode();

  if( iMode == FLU_INSERT_SORTED || iMode == FLU_INSERT_SORTED_REVERSE )
    return( binSearch( n, index ) );
  else
    return( linSearch( n, index ) );
}

bool Flu_Tree_Browser :: NodeList :: search( Node *n, int &index )
{
  index = _nNodes;
  if( _nNodes == 0 )
    return false;

  // we know we have at least one node. so use it to get the RData struct to find out what
  // the insertion mode is
  int iMode = _nodes[0]->tree->insertion_mode();

  if( iMode == FLU_INSERT_SORTED || iMode == FLU_INSERT_SORTED_REVERSE )
    return( binSearch( n, index ) );
  else
    return( linSearch( n, index ) );
}

bool Flu_Tree_Browser :: NodeList :: linSearch( const char *n, int &index )
{
  index = _nNodes;
  for( int i = 0; i < _nNodes; i++ )
    {
      if( strcmp( n, _nodes[i]->label() ) == 0 )
	{
	  index = i;
	  return true;
	}
    }
  return false;
}

bool Flu_Tree_Browser :: NodeList :: linSearch( Node *n, int &index )
{
  index = _nNodes;
  for( int i = 0; i < _nNodes; i++ )
    {
      if( n == _nodes[i] )
	{
	  index = i;
	  return true;
	}
    }
  return false;
}

bool Flu_Tree_Browser :: NodeList :: binSearch( Node *n, int &index )
{
  if( binSearch( n->label(), index ) )
    {
      // the search found the first node with the label. since there are identical entries
      // allowed, it may not be the actual node we want. therefore search forward until we find it
      for( ; index < _nNodes; index++ )
	if( _nodes[index] == n )
	  return true;
      return false;
    }
  else
    return false;
}

bool Flu_Tree_Browser :: NodeList :: binSearch( const char *n, int &index )
{
  // do a binary search for a child with name == "n"
  // return true if the child is found, and store its index in "index"
  // return false if the child is not found, and store the index it would
  // be in in "index"

  // special case: no nodes
  if( _nNodes == 0 )
    {
      index = 0;
      return false;
    }

  // we know we have at least one node. so use it to get the RData struct to find out what
  // the insertion mode is
  int iMode = _nodes[0]->tree->insertion_mode();

  // special case: 1 node
  if( _nNodes == 1 )
    {
      int val = strcmp( n, _nodes[0]->label() );
      if( iMode == FLU_INSERT_SORTED_REVERSE )
	val *= -1;
      if( val == 0 )
	{
	  index = 0;
	  return true;
	}
      else if( val < 0 )
	index = 0;
      else
	index = 1;
      return false;
    }

  int first = 0, last = _nNodes - 1;
  int val1, val2, mVal;
  for(;;)
    {
      // the range is down to 2 nodes
      if( last == first + 1 )
	{
	  val1 = strcmp( n, _nodes[first]->label() );
	  if( iMode == FLU_INSERT_SORTED_REVERSE )
	    val1 = -val1;
	  if( val1 < 0 )
	    {
	      index = first;
	      return false;
	    }
	  else if( val1 == 0 )
	    {
	      index = first;
	      break;
	    }
	  val2 = strcmp( n, _nodes[last]->label() );
	  if( iMode == FLU_INSERT_SORTED_REVERSE )
	    val2 = -val2;
	  if( val2 < 0 )
	    {
	      index = last;
	      return false;
	    }
	  else if( val2 == 0 )
	    {
	      index = last;
	      break;
	    }
	  else
	    {
	      index = last+1;
	      return false;
	    }
	}

      // pick which half of the array to search next
      int midpoint = first + ((last-first)>>1);
      mVal = strcmp( n, _nodes[midpoint]->label() );
      if( iMode == FLU_INSERT_SORTED_REVERSE )
	mVal = -mVal;
      if( mVal < 0 )
	last = midpoint;
      else if( mVal > 0 )
	first = midpoint;
      else
	{
	  index = midpoint;
	  break;
	}
    }

  // we found *a* node equal to "n", now find the first node equal to "n"
  // by searching until we hit a node not equal to "n"
  for( first = index; first > 0; first-- )
    if( strcmp( n, _nodes[first-1]->label() ) != 0 )
      break;
  index = first;

  return true;
}

int Flu_Tree_Browser :: NodeList :: compareNodes( const void *arg1, const void* arg2 )
{
  Flu_Tree_Browser::Node *n1 = *((Flu_Tree_Browser::Node**)arg1), *n2 = *((Flu_Tree_Browser::Node**)arg2);
  return strcmp( n1->text.c_str(), n2->text.c_str() );
}

int Flu_Tree_Browser :: NodeList :: reverseCompareNodes( const void *arg1, const void* arg2 )
{
  Flu_Tree_Browser::Node *n1 = *((Flu_Tree_Browser::Node**)arg1), *n2 = *((Flu_Tree_Browser::Node**)arg2);
  return( -strcmp( n1->text.c_str(), n2->text.c_str() ) );
}

void Flu_Tree_Browser :: NodeList :: sort()
{
  if( _nNodes )
    {
      // we know we have at least one node. so use it to get the RData struct to find out what
      // the insertion mode is
      int iMode = _nodes[0]->tree->insertion_mode();
      if( iMode == FLU_INSERT_SORTED )
	qsort( _nodes, _nNodes, sizeof(Node*), compareNodes );
      else if( iMode == FLU_INSERT_SORTED_REVERSE )
	qsort( _nodes, _nNodes, sizeof(Node*), reverseCompareNodes );
    }
}

bool Flu_Tree_Browser :: Node :: move( Node* n1, int where, Node* n2 )
{
  if( isMoveValid( n1, where, n2 ) )
    return( NodeList::move( n1, where, n2 ) );
  else
    return false;
}

void Flu_Tree_Browser :: Node :: sort()
{
  _children.sort();
  for( int i = 0; i < _children.size(); i++ )
    _children.child(i)->sort();
}

bool Flu_Tree_Browser :: Node :: is_ancestor( Node* n )
{
  Node *p = parent();
  while( p )
    {
      if( p == n )
	return true;
      else
	p = p->parent();
    }
  return false;
}

bool Flu_Tree_Browser :: Node :: is_descendent( Node* n )
{
  return n->is_ancestor( this );
}

bool Flu_Tree_Browser :: NodeList :: move( Node* n1, int where, Node* n2 )
{
  if( !n1 || !n2 )
    return false;

  if( n1->tree )
    n1->tree->redraw();
  if( n2->tree )
    n2->tree->redraw();

  // try to move n1 to the first child position of n2
  if( where == MOVE_INSIDE )
    {
      if( !n2->is_branch() )
	return false;
      // get the parent of n1
      Node* p1 = n1->parent();
      if( p1 )
	// remove n1 from its parent's list
	p1->_children.erase( n1 );
      // insert into n2
      int iMode = n1->tree->insertion_mode();
      if( iMode == FLU_INSERT_SORTED || iMode == FLU_INSERT_SORTED_REVERSE )
	n2->_children.add( n1 );
      else
	n2->_children.add( n1, 0 );
      // update the parent of n1
      n1->_parent = n2;
      return true;
    }

  // find the position of n2 in its parent's list
  Node* p2 = n2->parent();
  if( !p2 )
    return false;
  int index = 0, removed = -1;
  if( p2->_children.search( n2, index ) )
    {
      // get the parent of n1
      Node* p1 = n1->parent();
      if( p1 )
	// remove n1 from its parent's list. remember the position it was removed from
	removed = p1->_children.erase( n1 );

      // if n1 and n2 have the same parent, and if n1 came before the spot where
      // n2 will be inserted, then our indexing is off by one because n1 has been removed
      if( p1 == p2 && removed <= index )
	index--;

      if( where == MOVE_AFTER )
       index++;

      // insert n1 at the proper position
      p2->_children.add( n1, index );

      // update the parent of n1
      n1->_parent = p2;
    }

  return true;
}

void Flu_Tree_Browser :: NodeList :: add( Node* n, int position )
{
  int i, index;
  int mode = n->tree->insertion_mode();

  // if the list is out of room, allocate a new one that's bigger
  if( _nNodes == _size )
    {
      int newSize = ( _size == 0 ) ? 1 : _size*2; // double the size of the old list (same behavior as STL vector)
      // allocate the new list
      Node** newNodes = new NodeP[ newSize ];
      // copy the old list to the new list
      memcpy( newNodes, _nodes, _nNodes*sizeof(Node*) );
      // delete the old list and replace it with the new list
      delete[] _nodes;
      //n->tree->rdata.cbNode = NULL;
      _nodes = newNodes;
      _size = newSize;
    }

  if( position >= 0 )
    {
      if( position > _nNodes )
	index = _nNodes;
      else
	index = position;
    }
  else if( mode == FLU_INSERT_SORTED || mode == FLU_INSERT_SORTED_REVERSE )
    {
      // search through the list until we find where to insert the node
      binSearch( n->label(), index );
    }
  else if( mode == FLU_INSERT_FRONT )
    {
      index = 0;
    }
  else if( mode == FLU_INSERT_BACK )
    {
      index = _nNodes;
    }
  else
    return;

  // shift all entries from the new insertion point down one spot
  // to make room for the new node
  for( i = _nNodes - 1; i >= index; i-- )
    _nodes[i+1] = _nodes[i];

  // add the new node
  _nodes[index] = n;

  _nNodes++;
}

int Flu_Tree_Browser :: NodeList :: erase( Node *n )
{
  if( n == NULL )
    return -1;

  int index;
  if( search( n, index ) )
    {
      // move all the others down one spot to remove the node
      for( int i = index; i < _nNodes-1; i++ )
	_nodes[i] = _nodes[i+1];
      _nNodes--;

      return index;
    }
  return -1;
}

int Flu_Tree_Browser :: NodeList :: erase( const char* n )
{
  if( _nNodes == 0 )