groupadjacencylist.java

java B++树 一个很好的算法来实现这些问题 推荐！

package mddb.client.components;

import java.util.*;
import mddb.packets.*;

//邻接表数据结构,专门用来封装邻接表及其操作
public class GroupAdjacencyList {
    private ArrayList localGatewayId, adjacencyGatewayId, adjacencyMasterId;

    int size; //表示股邻接表的长度

    public static final int LOCAL_GATEWAY_ID = 0;
    public static final int ADJACENCY_GATEWAY_ID = 1;
    public static final int ADJACENCY_MASTER_ID = 2;

    public GroupAdjacencyList() {
        this.localGatewayId = new ArrayList();
        this.adjacencyGatewayId = new ArrayList();
        this.adjacencyMasterId = new ArrayList();
        size = 0;
    }

    //清空列表内容
    public void clear() {
        synchronized( this ) {
            this.localGatewayId.clear();
            this.adjacencyGatewayId.clear();
            this.adjacencyMasterId.clear();
            size = 0;
        }
    }

    //获得组邻接表的长度
    public final int getSize() {
        synchronized( this ) {
            return size;
        }
    }

    //返回lineNumber(从0开始)位置的值，无效位置返回null-----------------------------
    public long[] get( int position ) {
        synchronized( this ) {
            if( isValidPosition( position ) ) {
                long[] result = new long[3];
                result[0] = ( ( Long )this.localGatewayId.get( position ) ).
                            longValue();
                result[1] = ( ( Long )this.adjacencyGatewayId.get( position ) ).
                            longValue();
                result[2] = ( ( Long )this.adjacencyMasterId.get( position ) ).
                            longValue();
                return result;
            }
            return null;
        }
    }

    public long getLocalGeyId(int position){
        synchronized(this){
            if( isValidPosition(position) ){
                return ((Long)this.localGatewayId.get(position)).longValue();
            }
            return -1;
        }
    }

    public long getAdjGtyId(int position){
        synchronized(this){
            if( isValidPosition(position) ){
                return ((Long)this.adjacencyGatewayId.get(position)).longValue();
            }
            return -1;
        }
    }

    public long getAdjGtyMstrId(int position){
        if( isValidPosition(position) ){
                return ((Long)this.adjacencyMasterId.get(position)).longValue();
            }
            return -1;
    }
    //--------------------------------------------------------------------------
    //在指定位置插入值,插入成功返回true,否则返回flase--------------------------------
    public void add( int position, long lGtwyId, long adGtwyId, long adMstrId ) {
        synchronized( this ) {
            if( isValidPosition( position ) ) {
                this.localGatewayId.add( position, new Long( lGtwyId ) );
                this.adjacencyGatewayId.add( position, new Long( adGtwyId ) );
                this.adjacencyMasterId.add( position, new Long( adMstrId ) );
                size++;
            }
            else if( position == size ) {
                this.localGatewayId.add( new Long( lGtwyId ) );
                this.adjacencyGatewayId.add( new Long( adGtwyId ) );
                this.adjacencyMasterId.add( new Long( adMstrId ) );
                size++;
            }
        }
    }

    //将值插入到表尾
    public void add( long lGtwyId, long adGtwyId, long adMstrId ) {
        synchronized( this ) {
            this.localGatewayId.add( new Long( lGtwyId ) );
            this.adjacencyGatewayId.add( new Long( adGtwyId ) );
            this.adjacencyMasterId.add( new Long( adMstrId ) );
            size++;
        }
    }

    //将值插入到表尾
    public void add( Long lGtwyId, Long adGtwyId, Long adMstrId ) {
        synchronized( this ) {
            this.localGatewayId.add( lGtwyId  );
            this.adjacencyGatewayId.add( adGtwyId );
            this.adjacencyMasterId.add( adMstrId );
            size++;
        }
    }
    //--------------------------------------------------------------------------
    //删除指定位置的元素
    public void remove( int position ) {
        synchronized( this ) {
            if( isValidPosition( position ) ) {
                this.localGatewayId.remove( position );
                this.adjacencyGatewayId.remove( position );
                this.adjacencyMasterId.remove( position );
                size--;
            }
        }
    }

    //判断是否存在给定的localGatewayID--存在返回位置，不存在返回-1
    public int containsGatewayId( long gId, int type ) {
        synchronized( this ) {
            switch( type ) {
                case LOCAL_GATEWAY_ID:
                    return this.localGatewayId.indexOf( new Long( gId ) );
                case ADJACENCY_GATEWAY_ID:
                    return this.adjacencyGatewayId.indexOf( new Long( gId ) );
                case ADJACENCY_MASTER_ID:
                    return this.adjacencyMasterId.indexOf( new Long( gId ) );
                default:
                    return -1;
            }
        }
    }

    //设置指定位置的值
    public synchronized void set( int position, long gatewayId,
                                  long adjacencyGatewayId,
                                  long adjacencyMasterId ) {
        synchronized( this ) {
            if( isValidPosition( position ) ) {
                this.localGatewayId.set( position, new Long( gatewayId ) );
                this.adjacencyGatewayId.set( position,
                                             new Long( adjacencyGatewayId ) );
                this.adjacencyMasterId.set( position,
                                            new Long( adjacencyMasterId ) );
            }
        }
    }

    //判断是否是合法位置
    private boolean isValidPosition( int pos ) {
        synchronized( this ) {
            if( pos >= size || pos < 0 ) {
                return false;
            }
            return true;
        }
    }

    //利用MI包对组邻接表进行更新---------------------------------------------------
    public void updateWithMIPacket( NeighbourList miSenderNeiList, long miSenderId,
                                    long localId ) {//localId是本地Id
        synchronized( this ) {
            //先将miSender在本节点邻接表中的信息全部删除
            int position;
            while( ( position = containsGatewayId( miSenderId,
                GroupAdjacencyList.LOCAL_GATEWAY_ID ) ) >= 0 ) {
                remove( position );
            }
            for(int i = 0; i < miSenderNeiList.getSize(); i++){
                Object[] temp = miSenderNeiList.get(i);
                //过滤掉自己节点和自己节点之间的无用邻接信息
                //temp[0]=nebrId temp[1]=nebrMasterId temp[2]=nebrPosition
                if( ((Long)temp[1]).longValue() == localId ) {
                    continue;
                }
                add( new Long(miSenderId), (Long)temp[0], (Long)temp[1] );
            }
        }
    }

}